FIFO页面替换策略可能超越LRU吗？

作为我操作系统作业的一部分，我被要求比较先进先出和最近最少使用的页面替换策略对给定页面访问顺序产生的页面错误数量。令人困惑的是，似乎FIFO产生的页面故障比LRU少。这是可能的，还是我犯了一个错误？FIFO页面替换策略可能超越LRU吗？

来源

2012-03-05 Evan Kroske

当然这是可能的。没有一种算法在页面替换中是最好的。 LRU在现实世界的使用情况下优于FIFO，但确实有可能建立一个相反的情况。 – 2012-03-05 16:03:03

为您自己的教诲推荐的扩展：给定_any_两个页面替换策略X和Y，证明存在一个访问序列，使得X具有的页面故障少于Y. – Nemo 2012-03-05 16:11:23

是的，FIFO有可能击败LRU。我能想到的最小例子，

缓存大小：2页。

访问模式：A，B，A，C

在此之后，LRU缓存包含 “A，C”，而FIFO缓存包含 “B，C”。到目前为止，他们每个都错过了3次。所以如果下一页访问是“B”，那么FIFO会击败LRU。如果它是“A”，LRU会跳过FIFO。如果是其他任何东西，他们仍然束缚。

来源

2012-03-05 16:37:46

这必须是最小的可能的例子：当cachesize = 1时，当然没有cachesize = 1的例子是可能的，因为LRU = FIFO。并且没有cachesize = 2，totalnumaccesses = 4的例子是可能的，因为这样一个例子必须在第三次访问中包含驱逐，但是LRU和FIFO总是在第三次访问中驱逐相同的项目（如果有的话），所以在这里不会发生区分。 – 2016-04-06 02:30:38

不给你答案就很难给你一个提示。你为什么不尝试为自己设置问题？把自己放在你的老师的脑海里，一个扭曲的黑暗的地方，试着以这样一种方式来设置问题，使你的（同胞）学生深入思考这个问题。

来源

2012-03-05 16:03:13

理论上显然将取决于给定的序列。对于“扭曲的黑暗地点”+1，有一个非常好的建议可以想到它：D – 2012-03-05 16:11:59

FIFO页面替换策略可能超越LRU吗？

回答

相关问题