インシ - LOG>>KYO2009

◎論理回路

① ムーア型順序回路

・「現在状態」と「入力信号」を変数に置き、「次状態」のカルノー図を描くのがセオリー。
・「入力」は、取りうる値の欄だけ埋めればよい。空いたらdon't care。

② 双対定理

・双対関数・・・もとの関数の各変数の否定をとり、さらに全体を否定したもの。
・双対形・・・関数の0,1,+,*をそれぞれ1,0,*,+に置き換えたもの。
・双対関数＝双対形の証明は、演算記号の個数の帰納法で行う。



◎計算機アーキテクチャ＆ＯＳ

①　パイプライン制御

処理を複数ステージに分け、１サイクルごとに新命令をフェッチしていく。
メモリアクセスの競合がキモ。（ＩＦとＭＡ）

データハザード・・・前の出力が次に間に合わないこと
通常、レジスタの計算結果を利用する場合、
レジスタの値を決める命令のWB→レジスタを使う命令のIDの時間関係は崩せない。（3CLK遅延）
ところが、連続した命令ではEX→EXの直接接続が可能（フォワーディング）
ただしLOAD系命令とその次の命令ではEX→EXフォワーディングはできない。 MA→EXとなる。（1CLK遅延）

分岐遅延
分岐前→分岐後　は　MA→IFが崩せない（3CLK遅延）
分岐遅延の対策
①分岐しないものと予測して、その後の命令を実行しておく。予測が外れたら、分岐後の内容を破棄して正しいアドレスでやり直し
②コンパイラで命令の順番を書き換える。書き換えとは、分岐命令とそれに影響を及ぼす命令を上にズラすというもの。

② キャッシュ・メモリ

現在の「命令・データ」の近辺の「命令・データ」を主記憶からコピーしておくことで、
主記憶にアクセスすることなくキャッシュへのアクセスで済ませ、高速化させる。

アクセス速度に関して：
小容量下では・・・ブロックサイズが小さすぎても（近傍のデータが少ない）大きすぎても（ブロック数が減り、置き換えが増える）ミス率は上がる。
大容量下では・・・ブロックサイズを大きくしてもそれほどミス率は上がらない（一定のブロック数が確保できる）。

主記憶からキャッシュへのマッピングには３方式ある。
１．完全連想方式・・・ブロックを任意のキャッシュブロック枠にマッピングできる。主記憶アドレスは、ブロック番号-ブロック内アドレス
２．直接マップ方式・・・キャッシュのブロック数と同数の「群」に分けてマッピング。主記憶アドレスは、群内ブロック番号-群番号-ブロック内アドレス
３．群連想方式・・・キャッシュをm列n行に構成して、m個の群に分けてマッピング。主記憶アドレスは、群内ブロック番号-群番号-ブロック内アドレス

＃　ディレクトリのエントリ数は、キャッシュ内のブロック数と同じ。[ブロックサイズ]bit×[行数]エントリ×[列数]個の連想記憶

ページ置き換えアルゴリズム
１．FIFO・・・先入れ先出し
２．OPT・・・この先最も遠い未来で参照されるものを追い出す
３．LRU・・・一番過去に参照されたものを追い出す

③ 資源割付けグラフ

　　　　<要求>
　プロセス→リソース
　プロセス←リソース
　　　　<割付>

・グラフ簡約の流れ
プロセス終了→リソース解放→別プロセスにそのリソース割付→割り当てられてた別のリソース解放→別プロセスにリソース割付→解放→割付→解放→割付→・・・
・上記の簡約が不可な部分のプロセスはデッドロック状態にある。

④ セマフォ

・排他制御を行うための機構。２値セマフォ（０と１）とゼネラルセマフォ（３値以上とる）がある。

▼プロセスの入口では、セマフォ値が０の間は足踏みしておき、セマフォ値が１になったらすぐ０に戻し（ここをTest-and-Set、不可分処理とすると割り込みを防げる）、プロセスに突入。
▼プロセスから出たら、セマフォ値を１に変換。

・足踏みの間、ＣＰＵ時間を浪費する繁忙待機という問題が生じるので、これを防ぐためプロセスを待ち状態にするセマフォもある。

OSいろいろ♪

・スプーリング・・・時間のかかる入出力処理の際に、一時的に全てのデータをハードディスク等に書き込んで少しずつ処理させ、プロセッサを有効に利用すること。
・コンピュータファミリー・・・同一のＯＳを使用し、アーキテクチャに互換性があるが、性能や容量は異なる一連のコンピュータのシリーズ。
・デッドロック・・・複数のプロセスが互いに相手の持つ資源の解放を待ち、いつまでたっても処理が進まない状態。これの起こる条件は①排他制御を要求②資源の追加要求③資源横取り不可④循環が存在
・断片化・・・内部断片化は、ジョブの実行されている各区画内で未使用領域が存在する状態、外部断片化は区画が未使用であるにもかかわらずサイズの合致するジョブが存在せず使用不可能である状態。
ブロック、ページ等の固定長のシステムを使っていれば内部断片化はたいてい起きる。可変区画システムでは起きないが、代わりに必ず外部断片化が起きる。
スラッシング・・・ページフォルトの頻度が高くなり、システムが対応処理に忙殺され、プロセスの実行がほとんど行えなくなった状態。
・スレッド・・・ マルチスレッドＯＳにおけるプログラム実行の単位。ユーザレベルのスレッドは、ユーザが自由にスケジューリングできるが、本当にプロセッサが獲得できるか どうか不明。カーネルレベルのスレッドは、確実にプロセッサを獲得できるが、ユーザは自由にスケジューリングできない。
・pipeシステムコール（pipe(p)）・・・書き出し用・読み出し用のファイルディスクリプタをバッファで連結する。p[0]：read用、p[1]：write用。pid=folk()で生成したコピー（子プロセス）とプロセス間通信路を作れる。双方向通信の場合はパイプが２つ必要。
・ＨＤＤ内のファイルの処理は、回転待ち→シーク待ち→転送→処理。


◎情報論

①　符号理論

生成行列の行数：情報記号数（次元）・列数：符号長
検査行列の行数：符号長－情報記号数・列数：符号長
※符号化率：k/n（情報記号数/符号長）

・生成行列→符号語のつくりかた
情報ビット（t1,t2,t3,t4）×（生成行列）で求めた式のt1 t2 t3 t4を0000～1111まで動かすだけ。

・検査行列→符号語のつくりかた
（検査行列）×（符号語(v1 v2 v3・・・)）＝（0 0 0・・・）式を立てて、情報記号を000…～111…で動かす。

・符号語→生成行列のつくりかた
情報記号数３なら、符号語の最初が(100～) (010～) (001～)のものを並べるだけ。

・生成行列→検査行列のつくりかた
生成行列の冗長部（右側）を転置して、その右にマイナス単位行列をつなげる。

・検査行列を用いた復号法
シンドローム＝（受信後）×（検査行列（転置））を求める。
シンドローム＝０なら、誤りナシ。
シンドロームと一致した検査行列の列の番号が、誤りビット。
生起確率は、誤りナシ＞１ビット誤り＞複数ビット誤り。生起確率が大きいものを採用する。

・偶部分符号（重みが偶数の符号だけ取り出した集合）は、情報記号数が１減る。

・限界距離tの復号法とは？？？
限界距離t⇒最小距離2t+1
Ｃの符号数×各符号に対してハミング距離がt以下である符号数≦全符号数
↑ハミングの上界式。
ここで等号が成立するとＣは完全符号、復号に失敗することはない。
⇒各符号を中心とした半径１の円は重なっていない＆円の中に全ての符号が入っている。

・三角不等式の証明は、３点各々のn番目の符号に注目して、2*2*2パターン全て考える。

・２元ハミング符号の「使える性質」
最小距離は、符号長にかかわらず３である。



◎計算論

① オートマトン

正規表現→オートマトン
１．非決定の遷移図を描いてみる
２．ε遷移があったら消し、決定性にする
３．新たな記号で書き換えて決定性完成
４．簡単化
５．遷移図を描く

オートマトン→正規表現
１．遷移表から方程式を立てる。（p=0q+1rとか。受理状態には+εを付加）
２．解いたら、初期状態＝（コレが答え）
＃　X=AX+B ⇒ X=A*Bは必須

② 正規言語

xyz定理の使い方・・・ある言語Ｌが「正規言語でない」ことを証明するのに使う。

Ｌが正規言語であると仮定すると、xyz定理のpが存在する。
w=xyz=(与えられた言語（pを含める）)とおくと、|w|>pなので、xy(^i)zはＬに含まれるはずである。
そして、yの取り方を全パターン試して、各々１つでもＬに含まれない場合が出れば・・・矛盾→not正規言語。という流れ。

③ 形式文法

句構造文法PSG ：文法全体
⊃ 文脈依存文法CSG ：（短）→（長or同長）か、Ｓ→ε(Ｓが右辺に無いときのみ)
⊃ 文脈自由文法CFG ：A→β（A∈N, β∈N∪T）か、Ｓ→ε(Ｓが右辺に無いときのみ)
⊃ 正規文法FSG ：A→aB, A→a（A,B∈N, a∈T）か、Ｓ→ε(Ｓが右辺に無いときのみ)
＃　正規文法は決定性有限オートマトン、文脈自由文法は非決定性プッシュダウンオートマトンで表せる言語を生成する