OSの実行管理と記憶管理

要点と定義

OSは、プログラムにCPUや主記憶などを使わせ、実行の順序や資源を管理します。実行管理では、実行できる処理を選んでCPUに割り当て、入出力待ちなどで進めない処理を待たせます。記憶管理では、仮想アドレスと主記憶上の物理アドレスを対応付け、必要なデータを主記憶に用意します。

タスクの状態と優先度。 タスクは、実行を管理する単位です。実行可能状態はCPUが割り当てられれば動ける状態、実行状態はCPUを使用中の状態、待ち状態は入出力完了などを待ち、すぐには実行できない状態です。待ち状態のタスクは、優先度が高くても実行できません。優先度に基づくプリエンプティブ方式では、実行中のタスクより高優先度のタスクが実行可能になると、実行中のタスクを中断して実行可能状態に戻し、高優先度のタスクへCPUを切り替えます。中断されたタスクは待ち状態ではなく、再開できる実行可能状態です。

割込みとCPU時間。 割込みは、実行中の処理を一時中断し、割込み処理へ移る仕組みです。多重割込みが許され、優先度の高い割込みが低い割込みを中断する場合も、CPUは割込み処理に使われています。一定時間内にメイン処理へ使える時間を求めるときは、その区間内で実際に実行された割込み処理時間を合計し、区間全体から差し引きます。例えば6ミリ秒の区間に、2ミリ秒の割込み処理が1回、0.25ミリ秒の割込み処理が3回あれば、メイン処理に使える時間は6－(2＋0.25×3)＝3.25ミリ秒です。割込みの発生時刻だけでなく、処理時間と区間の端を確認します。

リエントラント。 リエントラントなプログラムは、複数のプロセスから同時に呼び出されても、互いの処理に干渉せず動作できます。呼出しごとの状態を個別に保つなど、共有するデータが競合しないようにすることが要点です。これは、同じプログラムを再利用できる性質や、プログラム自身を呼び出す再帰とは別の性質です。

仮想記憶とページフォールト。 仮想記憶は、仮想アドレス空間と主記憶の物理アドレス空間を対応付けて使う仕組みです。ページング方式では、それぞれの空間を固定長のページに分けます。ページテーブルは仮想ページごとに、主記憶上にデータがあるかを示す情報と、存在する場合の物理ページ番号を管理します。必要な仮想ページが主記憶にないときに発生するページフォールトを処理し、必要なデータを読み込みます。これにより、プログラムの全データを一度に主記憶へ置けない場合にも実行できます。

空き物理ページがない場合は、置換対象の物理ページを選びます。変更されたデータを保持する必要があれば補助記憶装置へ書き出し、対応するページテーブルの存在情報を更新して空きを作ります。その後、必要な仮想ページのデータを補助記憶装置から空き物理ページへ読み込み、対応関係を登録します。置換対象は物理ページ、読み込むデータの所在は仮想ページ、と役割を分けて考えます。

ページ置換えでは、FIFOは主記憶に読み込んだ順が最も古いページを選び、LRUは最も長く参照されていないページを選びます。参照のたびに、ページがあるか確認し、なければフォールトとして、選択規則に従って置換し、参照順に状態を更新します。同じ参照列でも方式や物理ページ数で回数は変わります。実際、ある参照列ではFIFOの割当てを3ページから4ページに増やすとフォールトが9回から10回に増え、LRUでは10回から8回に減ります。ページ数を増やせば常にフォールトが減る、とは限りません。

スラッシング。 多重度を上げた結果、主記憶に必要なページを保てず、ページイン・ページアウトが頻発して処理よりページ交換に時間を取られ、応答が著しく遅くなる現象をスラッシングといいます。タスク数を増やすことが、常に処理能力の向上につながるわけではありません。

スレッド並列実行とデータ依存。 反復処理を複数スレッドに分けても、各反復が互いに独立していなければ、逐次実行と同じ結果を保証できません。ある反復が読む値を別の反復が更新する場合、読み書きの順序がスレッドの実行タイミングで変わると結果が変化します。例えば、配列の隣の要素を読みながら現在の要素を書き換える処理では、分割境界の要素に読み書きの依存が生じ得ます。

適用条件と例

ページフォールトの処理では、まず必要なページが主記憶にあるかをページテーブルで調べます。存在ビットが1なら対応する物理ページを使えます。0なら、空き物理ページを探します。空きがなければFIFOやLRUなどの規則で追い出すページを決め、必要な退避を行ってから読み込みます。例えば、4つの物理ページがすべて使用中なら、選んだ1ページを空け、必要な仮想ページのデータをその場所へ読み込みます。追い出すページのデータを読み込むのではなく、読み込み元と退避先を区別してください。