IPA 仮想記憶・主記憶管理 — 頻出論点と過去問

頻出論点

1. この分野は何か

OSが限られた主記憶（物理メモリ）を複数のプログラムにどう割り当て、補助記憶装置と組み合わせて物理容量を超える論理的なアドレス空間をどう見せるかを考える分野です。固定長と可変長の分割方式による断片化の違いや、ページ置換えのアルゴリズムとそれに伴うオーバーヘッドの計算が主な論点になります。

2. 実際の出題のされ方

仮想記憶が何のための仕組みかを、空欄に語句を入れて答える問題がITパスポートで出ています。

応用情報技術者の午前と高度試験の午前Iでは、ページング方式の動作と主記憶の断片化を中心に問われます。具体的には、与えられたページ参照列に対してFIFO方式やLRU方式でページ置換えを順次追跡し、最終的な実記憶のページ状態や特定のページが格納される番地を求める問題が出題されています。また、ページ置換えが多発してシステムの処理能力が急激に低下するスラッシングの用語、ページフォールト・ページイン・ページアウトの発生回数の大小関係、セグメンテーション方式と比較したページング方式の長所を選ばせる問題も出ています。計算問題では、ページアウトを伴う場合と伴わない場合の処理時間からページインのみの割合を求める問題や、1命令当たりの許容遅延時間から許容できるページフォールト発生率の最大値を求める問題が出題されています。さらに、プログラムの大きさがページサイズの半分以下のシステムでページサイズを半分にしたときの効果や、ベストフィット方式の特徴、フラグメンテーションの影響も問われています。

アドレス変換テーブルの構造や主記憶管理の用語・計算は、エンベデッドシステムスペシャリストの午前IIでさらに踏み込んで問われます。仮想アドレス空間・ページサイズ・1エントリの大きさを2のべき乗で与え、ページテーブル全体の大きさを表す式を選ぶ問題や、セグメンテーションページング方式のセグメントテーブルに何が入るかを選ぶ問題が出ています。また、主記憶アクセス時間とページフォールトのオーバーヘッドから1秒当たりの最大ページフォールト発生回数を求める計算問題、可変区画方式における最適適合アルゴリズムの定義、ガーベジコレクションをはじめとする主記憶管理の用語を選ばせる問題も出題されています。

3. 学習のポイント

仮想記憶における分割方式は、固定長で管理するか可変長で管理するかによって性質が異なります。

• ページング方式: 仮想記憶と主記憶を固定長の「ページ」に分割して管理します。同じ大きさの単位で割り当てるため、主記憶上に細かな空き領域が散在する外部断片化（外部分断化）が発生しません。一方、ページの内部に未使用の余りが生じる内部フラグメンテーションは起こり得ます。ページより小さいプログラムでもページ1枚分の主記憶を使うので、ページを小さくすると使われない余りが減ります。その代わり、ページの数が増えてページテーブルが大きくなり、管理の手間は増えます。
• セグメンテーション方式: プログラムやデータなどの論理的な意味を持つ可変長の単位（セグメント）で管理します。論理的な単位でのアクセス保護やプログラム間での共用、実行時の動的なサイズ変更がしやすい反面、可変長であるため外部断片化が発生します。両者を組み合わせたセグメンテーションページング方式では、まずセグメントテーブルを参照して対象セグメントのページテーブルの実アドレスを取得し、次にページテーブルを参照してページの実アドレスを求めます。

次に、ページフォールト発生時の動作とページ置換えアルゴリズムを押さえます。試験で扱う、必要になったページを補助記憶から読み込むモデルでは、アクセス対象のページが主記憶に無いとページフォールト（割込み）が起き、ページインが行われます。空き枠が無いときは置換え対象のページを選び、読み込み後に更新されていれば補助記憶へ書き戻します（ページアウト）。更新されていなければ書き戻さずに枠を使います。このモデルでは、ページフォールトとページインの回数は等しく、ページアウトの回数はそれ以下になります。どのページを追い出すかを決める代表的な方式が次の2つです。

• FIFO（First In First Out）方式: 主記憶に最も古くから存在する（最も早くロードされた）ページを置換対象とします。すでに主記憶にあるページが再参照されても、追い出す順序は変わりません。
• LRU（Least Recently Used）方式: 最後に参照されてからの経過時間が最も長いページを置換対象とします。すでに主記憶にあるページが参照（ページヒット）された場合、そのページの参照履歴が最も新しいものに更新される点がFIFO方式との違いです。

計算問題では、単位の換算（ミリ秒は$10^{-3}$秒、マイクロ秒は$10^{-6}$秒、ナノ秒は$10^{-9}$秒）と、1回の事象当たりにかかる時間の内訳を正確に式にします。たとえば、1命令当たり主記憶に平均$k$回アクセスし、1アクセス当たりのページフォールト発生率が$p$、1回のページフォールトのオーバーヘッドが$T_{\text{pf}}$であれば、1命令当たりの平均遅延時間は$k \times p \times T_{\text{pf}}$で表せます。また、ページテーブルの大きさは、仮想アドレス空間のページ数（仮想アドレス空間の大きさ $\div$ ページサイズ）に1エントリの大きさを掛けて求めます。

主記憶の空き領域管理の用語も対比して覚えます。

• 可変区画方式の割当てアルゴリズム: 要求サイズ以上の空き領域のうち、最小のものを割り当てるのがベストフィット（最適適合）方式、最初に見つかったものを割り当てるのがファーストフィット（最初適合）方式です。ベストフィットは要求にいちばん近い大きさの領域を選ぶため、割り当てた残りがごく小さくなり、その小さな残りが使い道のないまま散らばっていきます。
• メモリプール管理と領域の整理: 獲得と返却を繰り返すと空き領域が細切れになり、空きの総量が足りていても、まとまった大きさの領域を取れなくなります。これに対し、固定長ブロックのメモリプール管理方式は同一サイズのブロックで管理するため、獲得と返却が速く外部フラグメンテーションが発生しません。使用中の領域を片側に詰め直して、散らばった空き領域を1か所にまとめる処理をコンパクションと呼び、どこからも参照されなくなったヒープ上の領域を見つけて、使える領域に戻すのがガーベジコレクションです。

4. 間違えやすいところ

用語の定義を入れ替えた誤答肢が複数の問題で見られます。

• FIFOとLRUの取り違え: LRUを、最も早くロードされたページを追い出す方式とする誤答肢があります。ロードされた時刻が最も古いものを選ぶのはFIFOであり、LRUは最後に参照されてからの経過時間が最長のものを選びます。トレース問題でも、ページヒット時にLRUでは参照履歴を更新するのに対し、FIFOでは更新しない点を混同しないよう注意が必要です。
• ページテーブルのエントリ数と格納アドレスの混同: ページテーブルを主記憶にあるページの分だけ用意すればよいとする誤答肢がありますが、ページテーブルのエントリは主記憶の枠数ではなく仮想アドレス空間の全ページ分（$\text{仮想アドレス空間の大きさ} \div \text{ページサイズ}$）必要です。また、セグメンテーションページング方式のセグメントテーブルに格納される情報を「当該セグメントに含まれるページの実アドレス」や「当該セグメントに含まれるページを管理するページテーブルの仮想アドレス」とする誤答肢もあります。ハードウェアがそのまま参照できる実アドレスである点に注意します。
• スラッシング対策の向き: 「スラッシングを防ぐためには，システムの多重度を上げることが有効である」という誤答肢があります。多重度を上げると1プログラム当たりに割り当てられる主記憶がさらに減ってページフォールトが激増するため、多重度は下げる必要があります。
• ガーベジコレクションと他の記憶管理処理の混同: 「ページフォールトが発生した場合は，ガーベジコレクションが必要である」としたり、メモリ領域が返却されるたびにガーベジコレクションを行うとしたりする誤答肢があります。ページフォールト時に必要なのはページインであり、またガーベジコレクションは負荷が高いため返却のたびに毎回行うものではありません。
• アクセス回数の掛け忘れ: 許容できるページフォールト発生率を求める計算では、1命令当たりの主記憶のアクセス回数が1回とは限りません。アクセス回数を掛け忘れると、許容できる発生率をその回数倍だけ大きく見積もってしまいます。