OSの基礎｜資源を分けて、競合と待ちを防ぐ

この分野で身に付けること

• 仮想記憶とページ置換の目的を、主記憶との関係で説明できる。
• 共有資源への同時アクセスで起こる問題を考えられる。
• ページ参照列を追い、置換対象を手順どおりに決められる。

1. 仮想記憶は、主記憶だけでは収まらない処理を扱う

プログラムが使うアドレスを仮想アドレス、実際の主記憶上の位置を物理アドレスとして区別します。仮想記憶では、必要な部分を主記憶へ置き、すべてを常に主記憶へ置かなくても実行できるようにします。ページは、その管理単位の一例です。

以下の例は、必要なページが主記憶にないときにページフォールトが起き、ページを読み込む要求ページングの単純化したモデルです。空き枠がなければ、どのページを追い出すかを置換方式に従って決めます。参照順と、各枠に今どのページがあるかを表で追うのが確実です。実際のOSのページフォールトには、新しいページの割当てやアクセス保護の違反などもあり、必ず補助記憶を読み込むとは限りません。

2. 同時実行では、読み書きの順序が結果を変える

二つの処理が同じ残高や在庫数を読み、別々に計算して書き戻すと、片方の更新が消えることがあります。共有する値を更新する部分をクリティカルセクションとして扱い、一度に一つの処理だけが入れるようにする考え方が排他制御です。

ロックを使えば常に安全というわけではありません。複数の資源を互いに待つとデッドロックになることがあります。問題では、どの処理がどの資源を保持し、何を待っているかを矢印で書くと、待ちの循環を発見しやすくなります。

3. OSは、資源を使う順番も管理する

CPUをどのプロセスにいつ割り当てるか、入出力待ちの間に何を実行するかは、応答時間や利用効率に影響します。スケジューリング問題では、到着時刻、実行時間、優先度、先取りの可否など、問題文で与えられたルールを先に表へ写します。

実際のOSは多くの要素を考慮しますが、試験問題では指定された単純化された方式を守ることが大切です。一般に公平そうな方式を選ぶのではなく、設問の方式でどの順序になるかを機械的に追います。

用語・考え方の比較

例：3枠の主記憶で、7回の参照をLRUで処理する

主記憶にページを置く枠が3個あり、初期状態はすべて空とします。参照列は1→2→3→1→4→2→5です。参照したページがなければ必ずページフォールトとし、先読みはしません。以下の「古い→新しい」は最後に使った順であり、固定された物理枠の番号ではありません。

1. 参照1回目の1は存在しないので空き枠へ入れます。状態は[1]、フォールト累計1回。参照2回目の2で[1, 2]・累計2回、参照3回目の3で[1, 2, 3]・累計3回になります。まだ追い出すページはありません。
2. 参照4回目の1は既にあるのでヒットです。主記憶にあるページの集合は変わりませんが、使った順を[2, 3, 1]へ更新します。フォールト累計は3回のままです。
3. 参照5回目の4は存在せず、空き枠もありません。[2, 3, 1]の先頭にある2が最も長く使われていないので、2を追い出して4を入れます。順は[3, 1, 4]、フォールト累計4回です。
4. 参照6回目の2は直前に追い出されているため、再びフォールトします。今度は3を追い出し、順は[1, 4, 2]、フォールト累計5回です。
5. 参照7回目の5では1を追い出します。最後の順は[4, 2, 5]、フォールト累計6回です。全7参照の内訳はフォールト6回・ヒット1回で、既存ページを追い出す置換は3回です。
6. FIFOとの差を確認します。LRUでは4回目に1を再利用したため、5回目の置換対象は2です。FIFOは読み込んだ順をヒット時に更新しないので、同じ5回目には最初に入った1を追い出します。

ここで確認：LRUは、読み込んだときだけでなくヒットしたときも使用順を更新します。最初の空き枠への3回の読込みもフォールトですが、ページを追い出す置換ではありません。この二つの回数を分けて数えましょう。

確認してから、演習へ進む

間違えやすいポイント

• 仮想アドレスと物理アドレスを同じ場所の名前だと考えない。
• ロックを使うことと、デッドロックを防ぐことを同じにしない。
• 問題文にないスケジューリングの規則を補って判断しない。

自分で確かめる三つの手順

1. ページ参照ごとに、各枠の内容を横に並べて書く。
2. 共有変数の更新を、読取・計算・書込の三段に分ける。
3. 資源待ちを矢印で描き、循環があるか確認する。