「作って理解するOS」読書メモ 第2章ソフトウェアの基礎

x86 系コンピュータを動かす理論と実装　作って理解する OS の読書メモ。第 2 章「ソフトウェアの基礎」をサクッと流し読みしつつ、気になりどころだけ自分向けにメモ。

本はこれ ↓

オートマトンの話が最初に書いてあったが、特筆してメモる内容はなし。 以前だいぶ昔に違う本読んだ時にいろいろメモった: Java でオートマトンを作ろう – ゴミ箱

OS の役割

プロセス

記憶装置に保存されていたプログラムがメモリ上に展開されプログラムの実行が行われる。OS はプログラムの実行を プロセス として管理する。プロセスは以下のような状態遷移を行う。

これらの状態遷移は OS が管理するため、プロセス自身はどのような状態にあるか知る由がないし、その必要もない。

プロセスは OS の起動時に生成されるルートプロセスからツリー構造で生成される。子プロセスは親プロセスの権限以下しか持ち得ない構造となっており、これによりリソース権限管理を実現しやすくしている。

プロセスのスケジューリング

OS は クォンタム というプロセスの実行時間を各プロセスに順番に スケジューリング してく。このような方法でマルチタスクを実現する方法を プリエンプティブなマルチタスク という。

スケジューリングを順番に行うことを ラウンドロビンスケジューリング という。そのほかにも、優先度付きスケジューリングという方法もある。

プロセスの実行要求から終了するまでの時間を ターンアラウンドタイム というが、OS が事前にこれを予測することはできない。タスクの特性に応じて平均ターンアラウンドタイムが事前に予測できる場合、短いタスクから実行していくと全体のターンアラウンドタイムが短くなる。

カーネル

OS はタスク実行管理を行いたいため、それを妨害するようなリソース操作をうまく権限管理して縛りたいが、ソフトウェアでの制御はなかなか難しいという経緯があった。CPU で以下の 2 つの動作モードを用意することによりこの課題を克服している。

OS が実際に行いたいことはリソースへのアクセスを適切に管理するということなので、システムコール というインターフェースを用意して、OS が特権的な操作を各プロセスから受け付ける形なっている。OS はシステムコールの呼び出しが適切であるか判定を行い、OS の動作に悪影響が発生するような動作を防ぐ。

特に OS 本体の肥大化・複雑化を抑制するための設計である マイクロカーネル においては特権モードでの動作に関するプログラムをカーネルとよび、非特権モードで動作する周辺のプログラムをモジュールに分離する形をとっている。

排他制御

プロセス間で協調した動作を行いたいとき、プロセス間通信が必要になる。マルチタスクにおいて単純にフラグを使った排他制御を行うと、不整合が発生する。

たとえば以下のようなコードではうまく排他できない。例えば is_busy が 0 であるタイミングで while ループを抜けたあと、 is_busy に 1 をセットする前に、別プロセスに制御が移った場合に、排他が正常に行えない。

int is_busy = 0;

// 各プロセスで以下を実行
while(1) {
    while(is_busy) {
    }
    /* クリティカルセクション */
    is_busy = 0;
}

排他は一般的に下記のような手法で行う

デッカーのアルゴリズム

あとで読む: デッカーのアルゴリズム - 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 に依存するが、おおむね以下のような処理となる。

各命令はアトミックに行われる。

int S = 1;

// 各プロセスで以下を実行
while(1) {
    P(S);
    /* クリティカルセクション */
    V(S);
}

これによりビジーウェイトの問題が解消される。

デッドロックの発生条件

以下の 4 つに分類できる