仮想記憶とページング

仮想記憶は、各プログラムにそれぞれ独自の大きく連続したアドレス空間を提供し、ハードウェアとオペレーティングシステムがこれを固定サイズのページに分割して物理メモリにマッピングすることで、分離、保護、そして物理的に存在する以上のメモリがあるかのような錯覚を実現する。

Definition

仮想記憶とは、プログラムが使用する仮想アドレスをページテーブルを介して物理メモリのアドレスにマッピングするメモリ管理技術であり、メモリを固定サイズのページに分割し、必要に応じてページを物理メモリまたはバッキングストアに配置できるようにするものである。

Scope

このトピックでは、ページテーブルを介したアドレス変換、変換をキャッシュするトランスレーション・ルックアサイド・バッファ（TLB）、ページフォールトとデマンドページング、ページ置換とワーキングセットの原則、および仮想記憶が提供する保護について扱う。これはアーキテクチャとオペレーティングシステムの境界に位置する。ページアウトされたデータのファイルストレージ（ファイルシステム）やオンチップデータキャッシング（キャッシュの構成とポリシー）は含まれないが、これら両方と相互作用する。

Core questions

• 仮想アドレスはページテーブルを介してどのように物理アドレスに変換されるのか？
• TLBはどのように変換を高速化し、TLBミスが発生した場合はどうなるのか？
• ページフォールトでは何が起こり、デマンドページングはどのように処理されるのか？
• ワーキングセットの概念は、ページ置換をどのように導き、スラッシングを防止するのか？

Key concepts

• 仮想アドレス空間と物理アドレス空間
• ページとページフレーム
• ページテーブル
• トランスレーション・ルックアサイド・バッファ (TLB)
• ページフォールトとデマンドページング
• ページ置換
• ワーキングセットとスラッシング
• メモリ保護

Key theories

ワーキングセットモデル

ワーキングセットとは、プロセスが最近の一定期間に参照したページの集合である。各アクティブなプロセスのワーキングセットを物理メモリに常駐させることで、過剰なページングによってパフォーマンスが著しく低下するスラッシングを回避し、置換および受け入れの決定に役立つ。

Mechanisms

プログラムの仮想アドレスはページ番号とオフセットに分割される。ページ番号はページテーブル（しばしば多段階）をインデックスとして物理フレームを見つける。TLBは最近の変換をキャッシュし、アクセスごとにテーブルを走査するのを避ける。参照されたページが常駐していない場合、ページフォールトが発生し、制御がオペレーティングシステムに移る。オペレーティングシステムはバッキングストアからページをフェッチし、局所性とワーキングセットの振る舞いに基づく置換ポリシーに従って別のページを追い出すことがある。

Clinical relevance

仮想記憶は現代のオペレーティングシステムにとって不可欠である。プロセスを相互に分離してセキュリティと安定性を確保し、多くのプログラムが物理メモリを共有できるようにし、物理RAMよりも大きなプログラムを実行可能にする。TLBとページフォールトの挙動はパフォーマンスに大きく影響し、アドレス空間のレイアウトは保護とメモリ安全性の防御の基盤となる。

History

仮想記憶は1960年代初頭にマンチェスターのAtlasコンピュータで始まり、ページングとページフォールトのメカニズムを導入した。Denningの1968年のワーキングセットモデルは、局所性とスラッシングについて原理的な説明を与えた。TLBと多段階ページテーブルによるハードウェアサポート、そして後にラージページなどの機能が加わり、仮想記憶は汎用システムで遍く利用されるようになった。

Key figures

• Peter J. Denning
• Maurice Wilkes
• John L. Hennessy
• Abraham Silberschatz

Seminal works

• denning1968
• hennessy2019
• silberschatz2018

Frequently asked questions

ページフォールトが発生するとどうなりますか？

ページフォールトは、プログラムが現在物理メモリにない仮想ページにアクセスしたときに発生する。ハードウェアはオペレーティングシステムにトラップし、オペレーティングシステムはバッキングストア上のページを見つけ、それを空いているまたは追い出されたフレームに読み込み、ページテーブルを更新し、何事もなかったかのようにプログラムを再開する。

スラッシングとは何ですか？

スラッシングとは、アクティブなプロセスのワーキングセットの合計が物理メモリを超過したときにパフォーマンスが著しく低下する現象である。システムは有用な作業を行うよりも、データのページインとページアウトにほとんどの時間を費やすことになる。ワーキングセットを常駐させるか、負荷を軽減することでこれを回避できる。