ページ置換

非常駐ページへのアクセスで物理フレームも満杯なら、どの常駐ページを追い出すかを置換方針が決める。FIFO は最初に入ったページ、LRU は最も長く使っていないページ、Clock は一フレーム一参照ビットで最近の使用を近似する。

違いは記録だ。FIFO は到着時だけ、LRU は各使用時に時刻を更新し、Clock はヒットで置いたビットを回る針が消す。選択にも更新にも費用があり、悪い選択は後のフォールトを増やす。既定例では FIFO が他の二方式よりストレージ読込を二回増やす。

仕組み

ページが常駐ならヒットで、そのまま使う。なければフォールトで、本課は全ページをストレージから搬入する。空きがあればそこへ、なければ犠牲フレームを選ぶ。実システムにはストレージを使わないマイナーフォールトもあるが、ここは常駐と置換に絞る。

• FIFO は搬入アクセス番号 arrived を持ち、最小を選ぶ。ヒットで変えない。
• LRU は last_used を各アクセスで更新し、最小を選ぶ。
• Clock は R をヒットで 1 にする。針が環を調べ、1 なら第二機会を与えて 0 にし、先へ進む。既に 0 なら犠牲にする。選択中はそこに止まり、新頁の搬入後に次フレームへ進む。次のフォールトは続きから始め、F0 に戻らない。

FIFO はヒットから得た新情報を使わず、LRU は全体の最近順を維持する。全メモリ参照での厳密な更新は高価だ。ハードウェアの accessed ビットは Clock 系の低コストな近似を助け、前回消去後に使ったかを示すが、正確な順位までは示さない。

ステップ実行

既定は 3 フレーム、FIFO、0 1 2 · 0 1 3 · 0 1 4 · 0 1 2 の 12 参照。P0 と P1 を繰り返し、間へ冷たいページを挟む。

1. 第 1–3 参照の P0、P1、P2 は初回フォールトで F0、F1、F2 へ入る。arrived @1、@2、@3。空きなので犠牲選択はない。
2. 第 4、5 の P0、P1 はヒットし、ストレージ不要。FIFO タグは @1、@2 のままで、最近の利用を記録しない。
3. 第 6 の P3 は満杯で、@1、@2、@3 の最小を選ぶ。第 4 で使った P0 を追い出し、P3 を F0、@6 に置く。四つ目のフォールト。古いクリーンコピーは書き戻さず捨てられる。
4. 第 7 の P0 はまたフォールト。@6、@2、@3 から P1 を追い出し、P0 を F1、@7 に入れる。五つ目。
5. 第 8 の P1 は P2（@3）を追い出し、F2、@8 に入る。六つ目で、三回連続フォールトだ。
6. 第 9 の P4 は @6 の P3 を出し、F0 を @9 にする。七つ目。
7. 第 10、11 の P0、P1 は常駐してヒットし、タグは @7、@8。
8. 第 12 の P2 は @9、@7、@8 から再び P0 を出し、八つ目のフォールト。

最終 FIFO は 8 フォールト、4 ヒット。同じ入力と三フレームでは FIFO=8、LRU=6、Clock=6。初回置換は FIFO が P0（arrived @1）、LRU が P2（last used @3）、Clock も P2（R=0）。三つの規則から二つの異なる犠牲ページが選ばれる。

同じ入力の LRU と Clock

LRU の最初の三フォールトは同じだが、第 4、5 のヒットで P0、P1 のタグを @4、@5 へ変える。第 6 に P3 が必要なら @4、@5、@3 から P2 を選び、ホットな二ページを残す。第 7、8 はヒットし、第 9 は P3、第 12 は P4 を出し、計 6 フォールト。

引用する一フォールト約 100 万サイクルの尺度なら、二回の差は約 200 万のストレージサービスに相当する。ただしこの画面が数えるのは回数で、装置の時間は模擬しない。

Clock も同じ六参照でフォールトし、P2、P3、P4 を出す。本課は新頁 R=0 で、P0、P1 は後のヒットで 1 になる。針はその二つを救って消去し、まだ 0 の冷たい頁を選ぶ。この履歴では一ビットが LRU と同じ答えを出すが、全入力で同値ではない。

Clock's full sweep は全 R=1 にする。針が環全体を消し、出発位置へ戻ってそのフレームを選ぶ。このプリセットでは FIFO と同じ犠牲になる。一般には全一だからといって針の位置が最古搬入とは限らず、同じく参照済みのページを近似情報では区別できない。

メモリ増加でフォールトが増える場合

Bélády: 3 frames は FIFO で 0 1 2 3 · 0 1 4 · 0 1 2 3 4 を処理し、9 フォールト。Bélády: 4 frames は同列、同方針で一フレーム増やすと 10 になる。Bélády の異常だ。

LRU はスタック性を持つ。同じ空状態から同じ履歴を処理すると、k フレームの常駐集合は k+1 の集合に含まれる。容量増加であるヒットをミスへ変えることがなく、総フォールトは増えない。FIFO は集合が入れ子にならず、増設で追い出し順が変わり、小容量なら残した頁を捨て得る。

同プリセットを LRU にすると異常は消える。第二の終端図は 2、3、4、5 フレームを比較し、隣接容量で回数が増える箇所を印す。Clock と第二機会もスタック方式ではなく、証明なしで増量によるミス非増加を約束できない。

LRU の容量境界

A loop that thrashes は四ページを三周し、三フレームの LRU を使う。次に再利用する最古頁を毎回出し、12 参照すべてフォールトでヒット 0。

A loop that fits は一フレーム増やすだけで、初回 4 フォールトと 8 ヒットになる。作業集合が容量を越える際、性能は滑らかでなく崖のように変わり得る。ここでの三方式は三フレーム循環でいずれもヒットしない。他方式は一部を減らせても、四つの活動ページを同時に三枠へ入れられない。メモリ増量、集合縮小、アクセスや I/O の変更も検討する。

境界ケース

• 空きフレームへの冷フォールトには犠牲選択がない。需要ページング・先取りなしでは新しいページの初回を置換履歴で避けられない。ただし全実行が全フレームを埋めるとは限らず、実参照を数える。
• Nothing to reuse は六ページを一度ずつ読み、全方式が六フォールト。利用できる再使用がない。
• 搬入済みと現在常駐は違う。P0 は第 1 で入り第 4 でヒットしても、第 6 で出され、第 7 でフォールトする。
• 針の指す頁へのヒットは R=1 にするだけで針を動かさない。走査と新頁搬入で針が進み、消したビットも次の参照で再設定され得る。
• 一フレームなら犠牲は唯一で三方式同じ。スライダーは選択のある二フレームから始める。
• 最大 15 参照、P0–P5、最大 5 フレームは描画上限で、アルゴリズムの制約ではない。

よくある間違い

• 厳密 LRU をすべての OS の実回収と同一視する。全参照で順序を保つ費用が高く、カーネルはサンプリングや近似を使う。Linux は構成により Multi-Gen LRU などを使い、バッファープールにも LRU-K や Clock 系がある。名前だけで同実装としない。
• 異常を FIFO の珍例で終える。容量とミスの単調性を保証するのはスタック性で、他の非スタック方針も自動的には保証されない。
• TLB ミスとページフォールトを混同する。前者は表のウォーク、後者は本課では頁の搬入。仮想メモリで二経路を分ける。
• 集合が入らないのに犠牲規則だけを調整する。回数は変えられても容量と局所性の改善は別に必要だ。
• 追い出しをデータ消失と読む。ここは後備コピーのあるクリーン頁なので、メモリの複製を捨てる。再読の遅延はあっても値は失わない。
• 実追い出しを無料と考える。dirty 頁はフレーム再利用前に安全な書き戻しが必要で、新頁読込に追加書込が生じ得る。I/O はまとめたり先行・重複したりでき、時間が必ず倍になるわけではない。

モデルの範囲

一プロセス、需要ページング、六頁、最大五フレーム、dirty なしでフォールト数を数える。Clock は新頁 R=0。一部教材の R=1 なら初回の全周で全ビットを消し、FIFO 型の犠牲へ変わり得る。

LRU はフレームを線形に調べて最小 last_used を取る。アプリケーションのキャッシュはハッシュ表と双方向リストで一操作 O(1) にでき、LRU Cacheで扱う。ただし全実メモリ参照の追跡費用がなくなるわけではない。

約 100 万サイクルは仮想メモリからの尺度で、SSD、回転媒体、待ち行列、CPU 周波数で変わる。省略した OPT は未来で最も遅く使う頁を出す。オンラインでは未来を知らないが、保存した全トレースなら計算できる。固定列と容量の最小回数を与え、他方式の超過を測れる。ただし OPT 自身のフォールトにも初回だけでなく容量によるものがあり、全部を強制初回とは呼べない。