ページ置換アルゴリズム
デマンドページングを採用しているシステムもあり、実際に要求を受けてからページの内容をRAMにロードする。
一方、RAM上にないどのページが間もなく必要とされるかを推論し、そのようなページを要求される前にRAMへロードするシステムもある。これに事前クリーニングを組合わせることが多く、RAM上にあるページのうちすぐには必要とされないページを推測し、それを事前に二次記憶装置に書き戻しておく。
ページフォールトが発生したとき、「先行ページング」システムでは参照されたページを持ってくるだけでなく、参照のあったページに続く数ページも同時にロードしておく。CPUが命令プリフェッチで数個の命令を事前にフェッチしておくのと同様である。
間もなく必要になると思われるページ群を不連続であっても事前にロードする方式を「スワッププリフェッチ」と呼ぶ。
LRU(最近使われていない)ページ置換アルゴリズムは NRUと名前は似ているが、LRUでは短期間のページ使用履歴を保持している点が異なる。NRUではクロック割り込み間隔の使用/不使用で判断していた。LRU は、最近よく使われているページはその後の短時間でもよく使われるだろうという判断に基づいている。LRU は理論上は OPT に近い性能を発揮するはずだが、実際に実装するとコストがやや高い。このコストを抑える試みをした実装手法がいくつか存在している。
最もコストの高い手法はメモリ上の全ページを含むリンクリストを使う方法である。このリストの最後尾はLRUページであり、先頭は逆に最近使われているページである。この実装のコストはメモリ参照の度にリスト上のアイテムを移動させなければならない点であり、これには非常に時間がかかる。
別の方法はハードウェアのサポートを必要とする。ハードウェアで 64ビットのカウンタを命令実行毎にカウントアップする。ページにアクセスがあったときは、その時点のカウンタの値をページに与える。ページを置換するとき、オペレーティングシステムは単純に最も小さなカウンタ値を持つページを選択する。ただし、現在のハードウェアにはそのような機構はないので、OSが全ページについてカウンタを調べる必要があり、現実的ではない。
ランダム置換アルゴリズムはランダムにページを選んで置換する。おかしな話と思われるかもしれないが、このアルゴリズムはある状況では役に立つ。一般に FIFO よりも性能がよく、ループしたメモリ参照でも LRU より性能がよい。OS/390は グローバルなLRU予測をしているが、LRUの性能が悪くなったことを検出するとランダム置換に切り替えるようになっている。Intel i860 プロセッサもランダム置換方式を採用していた。