オペレーティングシステムの可視化
OS は複数のプログラムに計算機の資源を共有させます。このコース群では、次に実行するプロセスの選択、仮想アドレスと物理メモリの対応付け、パスからファイルデータを探す処理、共有変数へのスレッドのアクセスを扱います。コードとアニメーションを一段ずつ進めると、短い仕事の先行、CPU を使い続けるプロセスの降格、ページフォルトによるディスク読み込み、名前を消しても残るデータを確認できます。
プロセスが使う CPU、アドレス空間、ファイル名の背後には共有資源があります。OS は、その抽象と実際の状態の対応を保ちます。
CPU の共有
実行可能なプロセス数がプロセッサー数を超えると、スケジューラーが次の実行者を選びます。スループット、応答性、公平性は異なる選択を求めることがあります。
各方針が決めるのは二点です。
- 誰を選ぶか。 到着順、仕事の長さ、巡回順、または動作を観察して変える優先度で選びます。
- 途中で奪えるか。 非プリエンプティブ方式は、ブロックか終了まで実行を続けます。プリエンプティブ方式は途中で CPU を取り上げられます。応答性を高める一方、コンテキスト切り替えの費用が増えます。
選択とプリエンプションの規則が、待ち時間、飢餓、対話時の応答を左右します。
| 方針 | 選択基準 | プリエンプション | 取引条件 |
|---|---|---|---|
| FCFS | 到着順 | なし | 単純だが、長い仕事が後続を待たせるコンボイ効果がある |
| SJF | 最短の CPU バースト | なし | 仕事が準備済みで長さが既知などの条件で平均待ち時間を減らす。長い仕事は飢餓の恐れ |
| ラウンドロビン | 固定時間片で巡回 | あり | 順番に実行機会を与える。時間片の長さで遅延と切り替え費用が変わる |
| MLFQ | 動的優先度。CPU を使い続ける仕事を降格 | あり | 実行時間を予知せず、フィードバックで短い仕事の優先を近似 |
FCFS の到着順は長い仕事による待ちを防ぎません。SJF は長さの情報を必要とし、長い仕事を待たせ続ける場合があります。ラウンドロビンは長さを区別せず応答性を重視します。MLFQ は動作を観察して優先度を変え、これらの考え方を組み合わせます。
メモリの共有
プログラムは仮想アドレスを使います。ハードウェアはアドレスをページ番号とオフセットに分け、対応する物理フレームを調べ、元のオフセットを組み合わせます。
レッスンでは桁の違いを示すモデルを使います。TLB ヒットは約 1 サイクル、RAM 上のページテーブル参照は約 100、ページがメモリになくディスクを読む場合は約 100 万です。全ハードウェアに共通する固定値ではありません。このページフォルト経路はカーネルに入りディスクを読みますが、実際にはディスクを必要としないページフォルトもあります。待つ間は別のプロセスを実行でき、メモリ管理と CPU スケジューリングがつながります。
RAM が埋まると、ページ置換で追い出すページも選びます。FIFO は読み込んだ時刻、LRU は最後のアクセス時刻、Clock は参照ビットを記録します。Clock の針はビットを消しながら候補を探します。同じ三フレームと十二アクセスでも、方針の違いでディスクアクセスが二回変わります。参照ビットは最近の使用を低コストで近似する手掛かりです。
| 方針 | 各フレームの記録 | 追い出す対象 | 限界 |
|---|---|---|---|
| FIFO | 読み込んだアクセス番号 | 最古の到着 | ヒットを無視するので使用中のページも追い出す。フレームを増やすとフォルトが増える Bélády の異常もある |
| LRU | 最後のアクセス番号 | 最も長く使われていないページ | フレーム数より一つ多いページを循環すると毎回フォルトになり得る |
| Clock | 参照ビット一つ | 走査中にビットが 0 のページ | 全ビットが 1 なら一周して消す。このレッスンの対応状態では FIFO のような順序になる |
ディスク上の名前とデータ
ファイルシステムは名前とファイルの記録を分けます。このモデルの inode は種類、サイズ、リンク数、ブロック番号を持ちます。親ディレクトリの項目が名前を inode 番号へ対応付けます。
この分離からパス解決の費用を計算できます。キャッシュのないモデルでは、各ディレクトリで inode とデータを読みます。/home/user/notes.txt を開くには、ファイル本体の最初のバイトより前に七回の読み込みが必要です。この七回にファイルサイズは影響しません。
rm は親ディレクトリを編集し、リンク数を減らします。このモデルでは他の有効な参照がないため、リンク数が 0 になるとブロックを解放します。ハードリンクが残ればデータにアクセスできます。解放も元のバイトの上書きを意味しません。実際の OS では開いているファイルハンドルなどの参照も考慮します。
変数の共有
同じプロセスのスレッドはメモリを共有します。このレッスンは counter = counter + 1 を load、add、store の三段階に分けます。途中で切り替わると、二つのスレッドが同じ古い値を読み、後の書き込みが先の増分を上書きします。どちらも計算し保存したのに、二回分の増加が残りません。
ミューテックスは、同じロック規則を守るスレッド間でクリティカルセクションを排他的にします。OS のプリエンプションを禁止するものではありません。他のスレッドをロック待ちにして、保護対象の操作へ同時に入れなくします。二つの更新を失うスケジュールでも、ロックを使えば全更新を残せます。
ただし、二つのロックを逆順に取るとデッドロックが起こります。各スレッドが一つずつ保持し、相手のロックを待ち続けるためです。
学習の順序
まずプロセススケジューリングを学びます。同じ仕事を FCFS、SJF、ラウンドロビンで実行し、長い仕事による待ち、飢餓の恐れ、巡回による応答を比較します。変えるのは方針だけです。
次に MLFQ。仕事を高優先度から始め、CPU の割り当てを使い切ると降格します。実行時間を知らなくても、動作から短い仕事の優先を近似できます。
続いて仮想メモリ。アドレス分割、TLB、ページテーブル、ページフォルト、ディスクを追います。最後のコストバーでは三回のディスク読み込みが幅の大半を占め、アドレス変換は細い部分になります。無効アドレスのシナリオは、ページテーブルに対応がない場合のセグメンテーション違反を示します。
その後はページ置換。仮想メモリのレッスンでは RAM が満杯にならず、こちらは満杯の状態から始めます。同じ参照列を FIFO、LRU、Clock で実行し、フォルト数を比べます。FIFO で四フレームに増やすと悪化する例と、LRU で三フレームに四ページを循環させ、十二回すべてがフォルトになる例も試してください。
次はファイルシステム。ビットマップ、inode 表、ブロックへの参照を調べます。名前を使う探索と、削除時のリンク数の役割を確認します。
スレッドと同期はプロセススケジューリングの後なら学べます。既定の実行は 6 を期待しながら 4 で終わり、CPU の帯に失われた二つの更新を示します。ロックありと比較し、逆順のロックでデッドロックも起こしてください。
OS の全レッスン
下のレッスンを開き、仕事やアクセス列を変え、時間軸と同期するコードを一段ずつ確認してください。