LRUのページング方式

問題

プログラムで使用可能な実メモリ枠が3ページである仮想記憶システムにおいて，大きさ6ページのプログラムが実行されたとき，ページフォールトは何回発生するか。ここで，プログラム実行時のページ読込み順序は，0，1，2，3，4，0，2，4，3，1，4，5とする。ページング方式は，LRU(Least Recently Used)とし，初期状態では，実メモリにはいずれのページも読み込まれていないものとする。

• 9
• 10
• 11
• 12

答え

10

解説

ページフォールト

ページフォールト (page fault) とは、プログラムが物理メモリがマップされていない仮想アドレス空間上のページにアクセスしたときにハードウェアが発生する割り込み（または例外）である。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Least Recently Used

Least Recently Used (LRU) はキャッシュメモリや仮想メモリが扱うデータのリソースへの割り当てを決定するアルゴリズムである。対義語はMost Recently Used (MRU)。
和訳すると「最近最も使われなかったもの」つまり「使われてから最も長い時間が経ったもの」「参照される頻度が最も低いもの」である。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

問題は、LRUの対象になるものを太字として、下記のように考えることができ、ページフォルトは合計10回発生します。