
ページフォールト・FIFO・LRU
必要なページが主記憶にないときは、読み込みが必要です。空きがなければ、どのページを追い出すかも決めます。
正確な意味とざっくりした理解
ページフォールトは、アクセス対象のページが現在の主記憶上にない場合などに発生し、OSの対応が必要になる事象です。ページリプレースメントは、主記憶内のページをほかのページへ置き換える処理です。ざっくり言えば、必要なページを用意し、満席なら入れ替えます。
FIFOは主記憶へ最も早く入ったページを置換え対象とします。LRUは最後に参照されてから最も長い時間が経ったページを選びます。「入った順」と「使った順」は異なります。
参照列を追う用途
フレーム3個、初期状態は空、参照列1→2→3→1→4とします。最初の1・2・3はフォールト、次の1はヒットです。4を入れるとき、FIFOなら最初に入った1、LRUなら最後の参照が最も古い2を追い出します。この時点ではどちらもフォールト回数は4ですが、残る内容が異なります。
スラッシングは、ページの入替えが頻繁になり、本来の処理が進みにくくなる状態です。同時実行を増やしすぎて各処理が必要なページを保持できない場合などに起こります。ワーキングセットは一定期間によく参照されるページのまとまりを捉える考え方です。
問題での見方
参照ごとに、フレーム内容・フォールトの有無・置換え順を表にします。FIFOではヒットしても到着順を変えず、LRUではヒット時も参照順を更新します。TLBミスは変換情報のキャッシュミスであり、ページフォールトとは同義ではありません。
確認問題【オリジナル】
フレーム2個、初期状態は空です。LRUで1→2→1→3と参照すると、3を入れるとき追い出すページはどれでしょうか。
ア:必ず1
イ:1と2の両方
ウ:2
エ:どちらも追い出さない
正解と理由
正解はウです。1は直前に参照され、2の最後の参照の方が古いためです。アはFIFOの順と混同しています。イは一つの空きを作る条件に合わず、エは満杯なのに3の格納場所を用意していません。
参考資料と問題について
学習範囲の確認:IPA「基本情報技術者試験 シラバス Ver.9.2」(ソフトウェア)。説明と確認問題は独自に作成しています。過去問の転載・改変ではなく、出題頻度は未集計です。