algorithm - ページ フォールトと LRU アルゴリズム

Question

メインメモリは最大 4 ページまで保持できます。次の順序であるページで LRU アルゴリズムが使用された場合、最初にページ フォールトが発生するページはどれですか?

1,2,3,1,2,4,1,2,3

これは答えがないと思っていた試験問題です。メイン メモリには 4 ページを保持できますが、ページ 1、2、3、4 があるため、ページ フォールトが発生することはありません。

答えは4ページ目ですが、理由がわかりません。

Answer 1

意味があると思われる唯一の方法は、そのシーケンスの番号が、ディスクから取得されたページではなく、メモリ内のページ番号である場合です。

つまり、ページをロードするために選択されたページ番号です。これは、「LRUアルゴリズムが次のページで使用されている場合」というフレーズによって（少なくとも暗黙のうちに）サポートされています。

破棄して再利用するページを選択するために LRU アルゴリズムが使用されるため、ページ 1 が選択されている場合、そのページは置換のためにスワップアウトされます。

したがって、この意味での 4 ページ目は次のとおりです。

1,2,3,1
      ^
      |
      +-- this one.

また、メモリ内の最初のページは既に使用されているため、ページ フォールトが発生して新しいページがそこに取り込まれます。

その答えにほぼ一致する他のシナリオは考えられません。

Answer 2

最初にフレームが空であるため、最初の '1' が最初のページ フォールトになります。最初に '1' が呼び出されると、フレームが空であるためページ フォールトが表示されます。また、合計ページ フォールトは 4 になります。