ページング方式 ページ置換アルゴリズム

ウィキペディア

ページング方式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/08/15 03:44 UTC 版)

ページ置換アルゴリズム

デマンドページング

アクセスしようとしたときに物理メモリをページに割り当てる方式をデマンドページング (Demand Paging) と呼ぶ。換言すれば、ページフォールトが発生したときに物理メモリを割り当てる。プロセスが実行を開始したとき物理メモリは割り当てられておらず、プロセスのワーキングセットの大部分が物理メモリに置かれるまでページフォールトが発生し続けることになる。これは遅延ロード技法の一例である。

デマンドページングの利点:

• アクセスされないページはロードされない。そのため、メモリ使用量が節約され、マルチプログラミング（マルチタスク）の度合いを向上させる。
• プログラム実行開始前のロードによる遅延がない。
• ページの読み込みが最小限なのでディスク負荷が少ない。
• ページは更新されるまで複数のプログラムから共有され、コピーオンライトによってさらにリソースを節約できる。
• 実装メモリ量よりも巨大なプログラムを実行できる。オーバーレイという古い技術よりも優れている。
• 本来のページング方式が必要とする以上のハードウェア機構を必要としない。

欠点:

• プログラムが任意の仮想ページに初めてアクセスする際、遅延が発生する。そこでプリページングという技法で以前に動作したときに使用していたページを覚えておき、スケジューリングによって実行される際にそれらのページを予め物理メモリにロードしておいて性能向上を図ることもある。また、特にアクセスしていたページを覚えておかなくとも、プログラムカウンタとスタックポインタの指している仮想ページだけでも予めロードしておけばある程度の性能向上は図れる。
• ページ置換アルゴリズムに関わるメモリ管理は複雑化しつつある。

LinuxのようなUNIX系システムでは、mmap() システムコールもデマンドページングによって実装されている。それは新たなプログラムを実行する際にも適用される。OSは実行ファイル（とそれが依存するライブラリ群）をマッピングするが、そのときにファイルの中身を物理メモリ上に実際にロードすることはない。マッピングがリードオンリーで共有可能であれば、物理メモリに残っている内容をそのまま使って実行することもある。これをページキャッシュと呼ぶ。

使われていない物理ページには、スワップ領域以外のファイルに対応するページキャッシュと何とも対応していない完全な未使用ページがある。一般にページング方式では、新たに必要となったページがページキャッシュにあればそれを再利用し、なければ完全に未使用のページを使用する。使い終わったページは、その内容がスワップ領域以外に対応していればページキャッシュとしてそのまま内容が保持され、スワップ領域に対応していた匿名 (Anonymous) ページは完全な未使用ページに戻される。もちろん、完全な未使用ページを使い切った上でさらにメモリを使用しなければならないときにはページキャッシュが他の用途に利用される。このようにして、現に使用中でない物理メモリを有効活用してなるべくディスクアクセスを減らすように工夫している。ちなみに、ページキャッシュとして存在する領域をmmap() でマッピングするとページキャッシュがそのまま使われるが、read() システムコールで読む場合にはユーザーバッファへのコピーが発生する。

プリページング

スワップ・プリフェッチとも呼ばれる技法で、（参照の局所性を利用して）近い将来参照されると予測したページを事前にロードしておく。プロセスが経験するページフォールト回数を減らす試みである。例えば、ある参照でページフォールトが発生したとき、連続する数ページにもすぐに参照するだろうと予測してまとめてロードしておく、といった戦略がある。また、ある大きなプログラムが終了して多くのメモリを解放したとき、ページアウトされていた他のプログラムがメモリを必要とするだろうと予測して、事前にページインしておくといった戦略もある。

フリーページのキュー

フリーページのキューは、ページフォールト時に使用可能なページフレームのリストである。一部のオペレーティングシステムはページの再利用をサポートしている。すなわち、かつて奪われたが他に再割当てされていないページに対してページフォールトが発生した場合、ページイン処理をせずにフリーとなっている当該ページフレームをそのまま再利用するものである。

ページの事前解放

一部のオペレーティングシステムは、定期的に最近使われていないページを探し、それらをフリーページのキューに追加し、当該ページが更新されていたら（ダーティな場合）、ページアウト処理を行っておく。すると、ページフォールト時に空のページフレームがないということがなく、ページアウトを行う必要がなくなる。

事前クリーニング

UNIXでは、sync を使って定期的に全ダーティページを書き戻してクリーンな状態にする。Windowsでは、"modified page writer" というスレッドが同じことを行っている。

事前クリーニングにより、プログラムの起動や新たなファイルのオープンが高速化される。