○スケジューリングアルゴリズム
実行可能状態にあるプロセスの内、どのプロセスを実行するか
・到着順方式
先に起動したプロセスを先に実行する方法
先に到着したプロセスがCPUを長く利用するプロセスの場合、システムの応答性が低くなる
・処理時間方式
プロセスが必要とする処理時間の短い順に実行する
・ラウンドロビン方式
処理を一定時間行い、時間切れになったら実行可能状態に戻して列の最後に
・優先度順方式
プロセスに優先度をつけ、優先度の高いプロセスから順に実行する
優先度が低いプロセスがなかなか実行されない
・多重待ち行列方式
ラウンドロビン方式に優先度順方式を取り入れたもの
最初は高い優先順位と短いCPU時間を割り当て、その後は優先度を低くしてCPU時間を長くしていく
○排他制御
・デッドロック
複数のプロセスがお互いにロック解除を待ち、先に進まない状態
・セフォマ
排他制御を実行するための変数
0ならロック状態、1ならロック取得可能
・P操作
セフォマが0より大きければ1減らしてロック取得。0なら待機
・V操作
セフォマを1増やし、ロック解除
○データ構造
・リスト
・LIFO（スタック）
逆ポーランド記法で使う
・FIFO
○木
・２分木
親の持つ子要素が２つ以下で左右の子を区別する木
・２分探索木
各接点が持つデータについて、『左部分木の値＜親＜右部分木の値』が成り立つ』木
親が削除された場合、左部分木の最大値か右部分木の最小値を親にする
・ヒープ
各接点について、『親≦子』または『親≧子』の関係が成り立っている２分木
左右の子の大小は問わない
・AVL木
各接点について左部分木と右部分木の高さの差が±１までに収まる２分探索木
挿入や削除の後に最適化を行う必要あり
・Ｂ木
子の最大数がm、最少数がm/2となるタ分木
データは葉に格納
○探索
・線形探索法
前から順にデータをデータを調べていく。データ右端に番兵と呼ばれる目的のデータを入れて終了判定
O(n)
・２分探索法
ソート済みのデータに対し、真ん中の値を調べ、調べる範囲を半分にしていく
O(log n)
・ハッシュ表
データをハッシュ関数（データを配列の長さで割った余り）で求めた場所に格納する
値によって衝突が起こる。衝突時の処理として、オープンアドレス法とチェイン法がある
・オープンアドレス法
衝突が発生した時、別の関数でサイド計算し、そのアドレスに格納する
・チェイン法
衝突が発生した時、その場所にリストを作り、リストに格納する
・ハッシュ法
O(1)で追加、削除、嘆息を行えるが、衝突が多いとこの限りではない
○ソート
・選択整列法
先頭から順に最小値を探し、先頭を交換
比較回数O(n^2)
・交換法（バブルソート）
隣り合わせになっているデータの大小を正していく
比較回数O(n^2)
・挿入整列法
整列部分にデータを挿入する方法。前から順位整列していって、次のデータをその中に挿入する
比較回数O(n^2)
・シェルソート
挿入整列法を改良したもの
データをいくつかの部分列に分割し、分割したデータに対し挿入整列法を行う
・ヒープソート
ヒープ木を作成し、根の値を最大値としれ取り出す、残りを再構築し、これを繰り返す
計算量は、O(n log n)
・クイックソート
基準となる値を決め、それより大きいか小さいかで分割し、この分割を最後まで繰り返す分割統治法
計算量はO(n log n)
最も高速なソートだが、データが整列済みだとオワッテル
・マージソート
データを最後まで分割し、併合しながらソートしていく分割統治法
大量のメモリが必要
計算量は(n log n)
・安定な整列法
同じ値が含まれている場合、ソート前とソート後でその順序が保たれているものを安定という
安定：バブルソート、納入整列法、シェルソート、マージソート
不安定：ヒープソート、クイックソート
○文字列探索
・力任せ法
前から順に比較し、違ったら比較する位置を１つずらす
・ＫＭＰ法
前から順に比較し、違ったら、そこから比較しなおす
・ＢＭ法
見つけたい文字列の右から比較する。違ったら見つけたい文字列分ずらして比較
【CPU】
○ALU
CPUの演算子装置
○レジスタ
・命令レジスタ
取り出した命令を記憶
・プログラムカウンタ
次の命令のアドレスを記憶
・ベースレジスタ
プログラムの先頭アドレスを記憶
・指標レジスタ（インデックスレジスタ）
修飾アドレスのときに使う
・汎用レジスタ
なんにでも使える
○アドレス指定方式
・即値方式
・直接アドレス指定方式
・間接アドレス指定方式
アドレス先にアドレスがある
・指標（インデックス）アドレス指定方式
アドレス部＋インデックスレジスタ
・ベースアドレス指定指定
アドレス部＋ベースレジスタ
・相対アドレス指定方式
アドレス部＋プログラムカウンタ
○クロック周波数
・CPI(Cycles Per Instruction)
1命令を実行するのに必要なクロック数
・MIPS(Million Instruction Per Second)
1秒間に何百万回命令が実行されるか
・FLOPS(FLoating-point on Operations Per Second)
1秒間に実行できる浮動少数演算の回数
○CPUの設計
・CISC(Complex Instruction Set Computer)
可変長な複雑な命令を理解できるが高速化できない
・RISC(Reduced Instruction Set Computer)
固定長な命令しか理解できないが、高速化できる
○処理速度の高速化
・パイプライン方式
１つの命令の実行を、(1)命令取り出し、(2)命令解読、(3)オペランド読み出し、(4)実行などの段階に分け、ずらしながら実行する。
分岐があると効果が薄くなる
・スーパーパイプライン方式
パイプライン方式の命令ステージをより細かく分割したもの
・スーパースカラ方式
パイプラインを複数持つ
○マルチプロセッサ
・SISD(Single Instruction Single Data)
1命令で1つのデータを処理する
・SIMD(Single Instruction Multiple Data)
1命令で複数のデータを処理する
・MISD(Multiple Instruction Single Data)
複数命令で1データを処理する
・MIMD(Multiple Instruction Multiple Data)
複数命令で複数データを処理する
【メモリ】
○メモリ配置
・単一区間方式
メモリを１つの区画とし、１つだけロード
・多重区画方式
メモリを一定区画に分割、１区画以上のものはロードできない
・可変区画方式
区画の大きさを変更できるが、断片化（フラグメンテーション））が起こる
○メモリ不足の解消
・オーバーレイ
プログラムを分割し、必要な部分だけロード
・スワッピング
優先度の低いプログラムを補助記憶装置に退避
・仮想記憶
メモリの内容を補助記憶装置に退避
実メモリには仮想メモリのアドレスを入れる。
○仮想記憶
・ページング方式
固定長のページに分割
・セグメント方式
可変長のセグメントに分割
○仮想記憶のページ置き換え方式
・LRU(Least Recentlu Used)
最後に参照されてからの時間が長いものｋら追い出す
・FIFO(First In First Out)
最初に記憶したものから追い出す
・LFU(Least Frequently Used)
参照頻度が最も少ないものから追い出す
○RAM
・RAM(Random Access Memory)
電源を切ると消える、揮発性メモリ
・SRAM(Static RAM)
高速だが高価で、キャッシュメモリに使われている
・DRAM(Dynamic RAM)
低速だが安価で、メインメモリとして使われている
○ROM
・ROM(Read Only Memory)
電源を切っても消えない不揮発性メモリ
・マスクROM
読み出し専用メモリ。BIOSとか家電で
・PROM(Programmable ROM)
書き込み可能なメモリ
・EPROM(Erasable Programmable ROM)
紫外線でデータを消去できるメモリ
・EEPROM(Electrical Erasable Programmable ROM)
電気的にデータを消去できるメモリ。フラッシュメモリはこれ
○メモリの高速化
・ライトスルー方式
書き込みの際にキャッシュメモリとメインメモリの両方に書き込む。
読み込み時のみ高速化
・ライトバック方式
キャッシュメモリにだけ書き込み、キャッシュメモリを追い出す必要が生じた時点でメインメモリに書き込む。
読み書きで高速化され、ライトスルー方式より高速
・メモリインターリーブ
キャッシュメモリを複数の区画に分割し、連続したアドレスに同時にアクセスできるようになる
○キャッシュメモリの割付け方法
・ダイレクトマッピング
メインメモリのブロックをキャッシュメモリの決められてブロックに割付け
メインメモリのアドレスをキャッシュメモリのブロック数で割ったあまりの位置に割付け。アドレス変換は楽だけど、非効率的
・フルアソシアティブ
メインメモリのブロックをキャッシュメモリのどの場所にも割付けられる。効率的だがアドレス変換が複雑
・セットアソシアティブ
ダイレクトマッピングとフルアソシアティブの間
決められたセット内において、どこに割付けても良い
フツーはこれ
【割り込み】
○内部割込み
エラーなどにより、実行中のプログラムにより行われる
・プログラムによる割り込み
オーバーフロー、ゼロによる除算などの実行時エラー
・スーパーバイザコール(システムコール)割り込み
プログラムからOSに入出力処理を依頼したときに発生
・ページフォールト割り込み
メモリに存在しないページにアクセスした時に発生
○外部外部割込み
・入出力割込み
周辺機器との入出力動作が終了した時に発生
・タイマ割り込み
タイマから受ける一定間隔の割り込み。スレッドの交代とか
・機械チェック割り込み
ハードウェアの異常などによって発生
【周辺機器】
○補助記憶装置
・HDDのアクセス時間
シーク(位置決め)時間＋サーチ(回転待ち)時間＋データ転送時間
＝平均位置決め時間＋半回転するのにかかる時間＋読みたいデータ量を読む時間
・磁気テープ(DAT)によるバックアップ
データをレコードに分割し、レコードをブロック化因子に基づいてブロック化
ブロック間にはIBGというスペースを入れて書き込む
○周辺機器とのデータ転送
・DMA(ダイレクトメモリアクセス)
CPUを介さずに周辺機器とメモリで直接データをやりとりする。
周辺機器の転送速度の遅さをCPUに影響させないので処理が速くなる
・チャネル
周辺機器のデータ転送専用のプロセッサのこと。DMAの発展
○周辺機器との接続
・PCI
拡張バスインターフェース
・AGP
ビデオカード専用インターフェース
・IDE
HDDを接続する規格。光学式ドライブを含めATA/ATAPIとして標準化
・SCSI
補助記憶装置やプリンタを接続する規格
・USB
電源を入れたまま抜き差しができ、127台まで接続できる
・セントロニクス
プリンタ接続する規格
・RS-232C
モデム用
・IEEE1394
最大63台まで接続できる高速転送インターフェース
電源を入れたまま抜き差しできる（ホットプラグ）
・IrDA
赤外線通信の規格。通信距離は1m
・Bluetooth
2.5GHzの電波で通信。通信距離は10m
