x86系コンピュータを動かす理論と実装 作って理解するOS の読書メモ。第2章「ソフトウェアの基礎」をサクッと流し読みしつつ、気になりどころだけ自分向けにメモ。
本はこれ↓
オートマトンの話が最初に書いてあったが、特筆してメモる内容はなし。
以前だいぶ昔に違う本読んだ時にいろいろメモった: Javaでオートマトンを作ろう – ゴミ箱
OS の役割
- 接続されたデバイス（リソース）の管理
- CPU の実行時間もリソースとして OS が管理し、各プロセスに割り当てる
- プロセスの管理
- ハードウェア/ソフトウェアインターフェースの提供
- ユーザーインターフェイス、および周辺機器を操作するためのソフトウェア/ハードウェアインターフェースを提供する
- 異なるハードウェアを抽象化する
プロセス
記憶装置に保存されていたプログラムがメモリ上に展開されプログラムの実行が行われる。OS はプログラムの実行を プロセス として管理する。プロセスは以下のような状態遷移を行う。
- CREATED
- READY
- RUNNING
- READY
- BLOCKED -> READY
- TERMINATED
これらの状態遷移は OS が管理するため、プロセス自身はどのような状態にあるか知る由がないし、その必要もない。
プロセスは OS の起動時に生成されるルートプロセスからツリー構造で生成される。子プロセスは親プロセスの権限以下しか持ち得ない構造となっており、これによりリソース権限管理を実現しやすくしている。
プロセスのスケジューリング
OS は クォンタム というプロセスの実行時間を各プロセスに順番に スケジューリング してく。このような方法でマルチタスクを実現する方法を プリエンプティブなマルチタスク という。
スケジューリングを順番に行うことを ラウンドロビンスケジューリング という。そのほかにも、優先度付きスケジューリングという方法もある。
プロセスの実行要求から終了するまでの時間を ターンアラウンドタイム というが、OS が事前にこれを予測することはできない。タスクの特性に応じて平均ターンアラウンドタイムが事前に予測できる場合、短いタスクから実行していくと全体のターンアラウンドタイムが短くなる。
- A(8) B(4) C(4) D(2) という順番で実行: (8 + 12 + 16 + 18) / 4 = 13.5
- A(2) B(4) C(4) D(8) という順番で実行: (2 + 6 + 10 + 18) / 4 = 9
カーネル
OS はタスク実行管理を行いたいため、それを妨害するようなリソース操作をうまく権限管理して縛りたいが、ソフトウェアでの制御はなかなか難しいという経緯があった。CPU で以下の 2 つの動作モードを用意することによりこの課題を克服している。
- 特権モード: すべての CPU 命令を利用可能
- 非特権モード: 一部の CPU 命令が利用不可
OS が実際に行いたいことはリソースへのアクセスを適切に管理するということなので、システムコール というインターフェースを用意して、OS が特権的な操作を各プロセスから受け付ける形なっている。OS はシステムコールの呼び出しが適切であるか判定を行い、OS の動作に悪影響が発生するような動作を防ぐ。
特に OS 本体の肥大化・複雑化を抑制するための設計である マイクロカーネル においては特権モードでの動作に関するプログラムをカーネルとよび、非特権モードで動作する周辺のプログラムをモジュールに分離する形をとっている。
排他制御
プロセス間で協調した動作を行いたいとき、プロセス間通信が必要になる。マルチタスクにおいて単純にフラグを使った排他制御を行うと、不整合が発生する。
たとえば以下のようなコードではうまく排他できない。例えば is_busy が 0 であるタイミングで while ループを抜けたあと、 is_busy に 1 をセットする前に、別プロセスに制御が移った場合に、排他が正常に行えない。
int is_busy = 0;
// 各プロセスで以下を実行
while(1) {
while(is_busy) {
}
/* クリティカルセクション */
is_busy = 0;
}
排他は一般的に下記のような手法で行う
- デッカーのアルゴリズム: ソフトウェア的手法
- テストアンドセット: ハードウェア
- セマフォ: ハードウェア + OS
デッカーのアルゴリズム
あとで読む: デッカーのアルゴリズム – Wikipedia
テストアンドセット
値の確認と設定をアトミックに行えるような CPU 命令を用意。
ハードウェアのサポートにより、排他制御をシンプルに実現できる。
int global = 0;
// 各プロセスで以下を実行
int local;
while(1) {
do {
TEST_AND_SET(local, global)
} while(local)
/* クリティカルセクション */
global = 0;
}
しかし while(local) として、変数の値の変化を検査するだけに CPU 時間を利用している ビジーウェイト という問題がある。理想的には該当の変数が変化するまでコンテキストスイッチが起きない状態であるのが望ましい。
セマフォ
セマフォ とは P 命令と V 命令によってのみ値が変更される変数 S を用いた同期処理を指す。具体的な実装は OS に依存するが、おおむね以下のような処理となる。
- P 命令: S がデクリメントされ
0 <= Sなら処理継続、違えば BLOCKED に遷移 - V 命令: S がインクリメントされ、処理を継続。さらに
S <= 0ならブロック状態のプロセスのうち一つを READY に遷移させる
各命令はアトミックに行われる。
int S = 1;
// 各プロセスで以下を実行
while(1) {
P(S);
/* クリティカルセクション */
V(S);
}
これによりビジーウェイトの問題が解消される。
デッドロックの発生条件
以下の 4 つに分類できる
- 排他制御状態
- 保有待機状態
- 優先取得権のない状態
- 循環待機状態