LRU 方式のページフォールト回数
出典: 平成28年度 秋期 応用情報技術者試験 午前 問18 (IPA)
プログラムで使用可能な実メモリ枠が 3 ページである仮想記憶システムにおいて，大きさ 6 ページのプログラムが実行されたとき，ページフォールトは何回発生するか。ここで，プログラム実行時のページ読込み順序は，0，1，2，3，4，0，2，4，3，1，4，5 とする。ページング方式は，LRU（Least Recently Used）とし，初期状態では，実メモリにはいずれのページも読み込まれていないものとする。
- ア 9
- イ 10
- ウ 11
- エ 12
正解と解説を見る
正解: イ
- ア: 9 回では、ページフォールトにならないのが 3 回あることになります。数え直すと 2 回だけです。
- イ: 12 回のうち、2 回 (4 回目の読込みの 4 と、最後の手前の 4) はメモリにあるので、ページフォールトは 10 回です。正しい答えです。
- ウ: 11 回では、ページフォールトにならないのが 1 回しかありません。4 は 2 回ともメモリにあります。
- エ: 12 回は、全ての読込みでページフォールトが起きた場合の回数です。
ポイント
LRU は、最も長い間使われていないページ を追い出す方式です。実メモリは 3 ページ分です。
| 読込み | 0 | 1 | 2 | 3 | 4 | 0 | 2 | 4 | 3 | 1 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| フォールト | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ||
| 追い出し | 0 | 1 | 2 | 3 | 0 | 2 | 3 |
- 4 を 2 回目に読むときは {0，2，4}、4 を 3 回目に読むときは {3，1，4} にあるので、この 2 回だけページフォールトになりません。
- ページフォールトは 12 − 2 = 10 回 です。