lru - LRU 算法中的页面错误

Question

我无法从我的编程讲座中理解某些内容。我知道页面替换算法有页面错误。

LRU算法中，什么时候会出现缺页？是在没有更多空闲帧的时候吗？是框架已经存在但也已经使用了吗？

我的演讲中有这张照片（我只剪掉了重要的部分，因为原件是另一种语言的）：

这张图中的问题是“只有4帧，如果使用LRU算法，什么时候会出现页面错误？” 正如我所看到的，前 3 行有一个 x。这就是为什么我要问当还有空闲帧时是否发生页面错误？或者当我们需要“踢出”一帧时，页面错误是否只发生在红色 X 中？

Answer 1

当页面不在其中一个框架中时，就会发生页面错误。

因此，如果还剩下一些空闲帧并且我们需要输入一个新页面 - 将发生页面错误，因为该页面尚未在其中一个帧中。这意味着页面错误将继续发生，直到我们遇到已经在其中一个帧中的相同页面（编号）。这就是为什么在图片的前 3 行中有一个“x”。第四行没有“x”，因为页面已经在其中一个框架中。

如果所有框架都已经有页面并且我们正在输入的新页面尚未在其中一个框架中，则会发生页面错误，我们需要“踢出”一个框架以便为新的框架释放一个框架页。这可以用不同的算法来完成，比如最近最少使用、先进先出等。这就是为什么在图片中，一些“X”是红色的，因为发生了页面错误并且我们踢出了一个帧。

感谢@Blorgbeard 帮助我回答。