页面错误和LRU算法

Question

一个主内存最多可以保留4页。如果在随后的页面上按顺序使用LRU算法，那么哪个页面会第一个出现页面故障？

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

这是一个我认为没有答案的测试题。主存可以保留4个页面，因为有页面1、2、3、4，所以应该不会发生页面故障。

答案是第4页，但我不明白为什么。

Answer 1

唯一有意义的方法似乎是，该序列中的编号是内存中的页号，而不是从磁盘检索的页。

换句话说，它们是为加载页面而选择的页码。这是(至少是默许的)由短语“如果LRU算法被使用在下面的页面上是有序的”。

LRU算法用于选择丢弃和重用哪个页面，因此，如果选择的是页面1，则这将导致页面被换出以进行替换。

所以在这个意义上的第四页是：

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

而且，因为第一个内存中的页面已经在使用中，所以会发生页面错误，从而将新页面引入到它中。

我想不出任何其他的场景，甚至可以接近这个答案。

Answer 2

第一个“1”将是第一个页面错误，因为框架在开始时是空的，当“1”第一次被调用时，它将显示页面错误，因为框架是空的。页面错误总数将为4。

Answer 3

(即使是post，我只是添加一些其他答案中没有描述的见解) LRU是由Unix通过维护所有页面的链表来实现的。这个列表将在前面有最近使用的页面，而在后面(尾部)最近最少使用的页面，因为列表在每个内存引用上都会重新组织，所以最后4个页面的顺序是我们感兴趣的4,1,2,3。

在给定的页面序列中，4是最近最少使用的页面，而3是最近使用的页面。因此，第4页将在列表的背面。任何导致清除其中一个页面的事件都会将第4帧换出，因为它位于列表的背面