オペレーティングシステム：三つの基本

引用

Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (2018–2023). Operating Systems: Three Easy Pieces (version 1.10). Arpaci-Dusseau Books. Free official edition: https://pages.cs.wisc.edu/~remzi/OSTEP/

章の要約

本書は仮想化、並行性、永続性という三つの主題で構成される。各主題は教授と学生の短い対話で導入され、続く各章は多くの場合、枠で囲まれた「問題の核心」（crux）から始まる。最初に導入があり、三つの主要部の後に分散システムの部と、Peter Reiher（UCLA）によるセキュリティの章が続く。付録は仮想マシンモニタ、モニタ、C のチュートリアル、実習の案を扱う。

第1〜2章：本書についての対話、オペレーティングシステム入門

冒頭の対話は書名の由来（ファインマンの物理学講義への敬意）と三つの主題を説明する。第2章はフォン・ノイマン・モデルで動くプログラムから出発し、OS が CPU とメモリをどう仮想化し、並行性にどう対処し、データをどう永続的に保存するかを示す。章末では抽象化、性能、保護、信頼性といった設計目標と、OS の簡単な歴史を述べる。

第3〜6章：プロセスと制限付き直接実行

仮想化についての対話の後、第4章はプロセスとその状態、生成、管理用のデータ構造を定義する。第5章は最初の「幕間」で、UNIX のプロセス API である fork()、wait()、exec() と、それらが分かれている理由を扱う。第6章は制限付き直接実行を説明する。ユーザモードとカーネルモード、システムコールとトラップ、そしてタイマ割り込みによって OS が CPU を取り戻し、コンテキストスイッチを行う仕組みである。

第7〜11章：CPU スケジューリング

第7章は負荷に関する仮定と評価指標（ターンアラウンド時間と応答時間）から出発し、FIFO、最短ジョブ優先、最短残り時間優先、ラウンドロビンを順に扱い、I/O を加える。第8章はマルチレベルフィードバックキューを何度かの試行を通じて組み上げる。第9章は宝くじスケジューリング、ストライドスケジューリング、Linux の完全公平スケジューラを扱う。第10章はマルチプロセッサのスケジューリング（キャッシュ親和性、単一キューと複数キュー）を扱う発展的な章である。第11章はまとめの対話である。

第12〜17章：アドレス空間、アドレス変換、空き領域管理

第13章はアドレス空間とその目標を導入する。第14章は malloc() と free() およびよくあるメモリエラーを扱う幕間である。第15章はベース・バウンドによる変換を、第16章はそれを一般化したセグメンテーションを紹介し、第17章は可変サイズの割り当てのための空き領域管理を論じる。

第18〜24章：ページングと仮想メモリ

第18章はページングとページテーブルを、第19章は TLB を、第20章はページテーブルの縮小（大きなページ、混合方式、多段ページテーブル、逆引きページテーブル）を扱う。第21章と第22章はスワップの機構と置換ポリシー（OPT、FIFO、ランダム、LRU、クロック風の近似）、およびスラッシングを扱う。第23章は完全なシステムとして VAX/VMS と Linux を取り上げる。第24章はまとめの対話である。

第25〜34章：並行性

第26章はスレッドの動機を述べ、共有データと制御されないスケジューリングが競合状態を生むことを示す。第27章はスレッド API の幕間である。第28章はハードウェアの支援（test-and-set、compare-and-swap、load-linked/store-conditional、fetch-and-add）からロックを組み立て、さらに yield とキューを加える。第29章はロックを並行カウンタ、リスト、キュー、ハッシュテーブルに適用する。第30章と第31章は、生産者／消費者、リーダ・ライタロック、食事する哲学者を通じて条件変数とセマフォを扱う。第32章はデッドロックでないバグとデッドロックのバグを概観し、第33章は select() と非同期 I/O を用いたイベントベースの並行性を示す。第34章はまとめである。

第35〜46章：永続性

第36章は I/O デバイス、割り込み、DMA、デバイスドライバを扱い、第37章と第38章はハードディスク（ディスクスケジューリングを含む）と RAID を扱う。第39章はファイルとディレクトリの幕間である。第40章は inode とディレクトリで簡単なファイルシステムを構築する。第41章は Fast File System、第42章はクラッシュ一貫性（fsck とジャーナリング）、第43章はログ構造化ファイルシステムを扱う。第44章はフラッシュベースの SSD を説明し、第45章はチェックサムとスクラビングによるデータの完全性を扱う。

第47〜51章：分散

分散システムについての短い一連の章である。通信層と RPC（第48章）に続き、分散ファイルシステムの二つの事例、NFS（第49章）と AFS（第50章）を扱う。前者はステートレスなサーバと冪等な操作を軸とし、後者はファイル全体のキャッシュとコールバックを軸とする。最後にまとめの対話（第51章）がある。

第52〜57章：セキュリティ

Peter Reiher による章で、セキュリティの目標とポリシー（第53章）、認証（54）、ACL とケイパビリティによるアクセス制御（55）、公開鍵方式・ハッシュ・保存データの暗号化を含む暗号（56）、TLS による分散システムの保護（57）を順に扱う。

付録

短い付録が、仮想マシンモニタ（CPU とメモリの仮想化）、より高水準の同期構造としてのモニタ（Java の例を含む）、C プログラムのコンパイル・デバッグ・ビルドのチュートリアル、そしてシステムプログラミングと xv6 の実習の案を扱う。

主要概念

第1〜11章：CPU の仮想化

• プロセス：実行中のプログラム。その状態を OS が保存し復元する。
• 制限付き直接実行：プログラムを CPU 上で直接走らせつつ、特権モード、トラップ、タイマ割り込みによって OS が制御を保つ方式。
• スケジューリングの指標：ターンアラウンド時間と応答時間。ポリシーによってどちらを最適化するかが異なる。
• マルチレベルフィードバックキュー：履歴からジョブの振る舞いを推測するスケジューラ。

第12〜24章：メモリの仮想化

• アドレス空間：各プロセスに固有のメモリの見え方。
• ページングと TLB：固定サイズの変換単位と、それを高速にするハードウェアキャッシュ。
• 多段ページテーブル：使われないアドレス空間の変換情報を持たずに済ませる構造。
• ページ置換：メモリが一杯のとき何を追い出すかを決める方針。

第25〜34章：並行性

• 競合状態とクリティカルセクション：バグのパターンと、ロックが保護するコード領域。
• 条件変数とセマフォ：状態の変化を待ち、知らせるためのプリミティブ。
• デッドロック：待ちの循環であり、本書は四つの条件によって分析する。

第35〜46章：永続性

• inode：UNIX 型ファイルシステムの中心にあるファイルごとの構造。
• クラッシュ一貫性とジャーナリング：先に記録を書くことで、クラッシュ後もメタデータを保つ。
• ログ構造化ファイルシステム：すべての書き込みを順次書き込みに変える。
• チェックサム：サイレントな破損を検出する基本手段。

第47〜57章：分散とセキュリティ

• 冪等な操作とステートレスなサーバ：クラッシュからの復旧を容易にするための NFS の設計。
• アクセス制御リストとケイパビリティ：誰が何をできるかを記録する二つの方法。
• 公開鍵暗号と TLS：マシン間の通信を守る手段。

批判的分析

長所

• 短く、問題に導かれた章。 ほとんどの章が核心の問いを掲げ、段階的に解決策を組み立て（マルチレベルフィードバックキューの三回の試行や、段階的に改良されるロックの設計など）、まとめで終わる。一度に読み通せる長さである。
• 仮想化の後に並行性。 アドレス空間、プロセス、コンテキストスイッチを理解するまでスレッドを遅らせる理由を著者が説明しており、この順序によって競合状態の由来が明確になる。
• 実際のコードと実行できる宿題。 例は擬似コードでなく C で、コードは GitHub にある。多くの章末にはシミュレータを使った宿題があり、乱数のシードを変えれば新しい問題が得られる。計測やコーディングの課題もある。
• 歴史と出典。 各章は原論文を示し、アイデアを生んだ人々の名前を挙げるので、次に研究文献を読もうとする読者に向く。
• 無料で読める。 各章は PDF で無料公開されており、費用をかけずに教材にも独習にも使える。

短所

• 前提知識を仮定する。 導入は、プログラムが動くときに何が起きるかを読者が知っていることを前提とし（背景として Patt と Patel、または Bryant と O’Hallaron の本を勧めている）、コードは C で書かれている。
• 例は UNIX に偏る。 プロセス、ファイル、スレッドの API は UNIX/POSIX のものであり、完全なシステムの事例は VAX/VMS と Linux の仮想メモリである。
• 扱う範囲は選択的。 本書は一つの講義設計に従っている。ネットワークスタック、グラフィックス、モバイルや組み込みシステムなどは対象外で、分散システムとセキュリティの部も三つの主要部に比べると簡潔である。
• 対話とユーモアは好みが分かれる。 対話は任意であり、なくてもよいと考える読者もいる。

コースにおける位置づけ

完全なオペレーティングシステムの講義を通して学ぶための、簡潔な道筋である。三つの主題、短い章、それに見合うコードと宿題で構成される。『Operating System Concepts』は長く幅広い教科書で、多くの商用システムの例とプログラミング課題を含む。『Modern Operating Systems』は標準的な教科書で、Linux、Android、Windows の詳しい事例を含む。どちらも同じ内容をより広くカバーするが、本書はそれらの機構がどう、なぜ働くのかを語り口でより丁寧に説明する。

『How Linux Works』は実際の Linux システムの実用的な案内書で、概念を実機で確かめるときの副読本として役立つ。『Principles of Computer System Design』は厳密には OS の教科書でなく、OS、ネットワーク、耐障害性にまたがる設計原則の本であり、本書を読み終えて一般化したい読者に向く。

本書の使い方

C でプログラムを書け、プログラムがプロセッサ上でどう実行されるかをおおむね知っている読者向けで、通常は 2〜3 年次の OS の講義や独習で用いる。

実用的な進め方：

• 中核： 第2章、第4〜9章（CPU の仮想化）、第13〜22章（メモリ）、第26〜32章（並行性）、第36〜40章と第42章（デバイス、ファイルシステム、クラッシュ一貫性）。著者は、この内容が 15 週の学期におおむね収まると述べている。
• 選択または発展： 第10章（マルチプロセッサのスケジューリング）、第23章、第33章（イベントベースの並行性）、SSD・LFS・データ完全性の各章、分散システムとセキュリティの部。
• 対話： 全体の見通しをつかむために読むとよいが、飛ばしてもよい。

幕間のコードは自分で入力して実行し、各章の後でシミュレータの宿題を、新しいシードを使いながら安定して正解できるまで行う。さらに練習したい場合は、付録に挙がっているシステムプログラミングや xv6 の実習案に取り組む。詳しく学びたい話題は、引用されている論文に戻って読む。

版と出典

本ガイドは https://pages.cs.wisc.edu/~remzi/OSTEP/ の無料オンライン版に基づく。著者は版を 1.00（2018年8月）、1.01（2019年7月）、1.10（2023年10月）として挙げており、参照した章ファイルのヘッダは 1.10 と 1.20 であった。内容は、序文、目次、対話、各章の冒頭と核心の問い、およびセキュリティの章と付録を含むすべての章の節見出しという、無料公開されている本文に基づく。