FIFO页面替换策略是否有可能胜过LRU? [英] Is it possible for a FIFO page-replacement strategy to outperform LRU?

问题描述

作为操作系统作业的一部分，我被要求比较给定的页面访问顺序，由先进先出和最近最少使用的页面替换策略产生的页面错误数.令人困惑的是，似乎FIFO产生的页面错误少于LRU.这可能吗，还是我弄错了?

As part of my operating systems homework, I was asked to compare the number of page faults produced by first-in-first-out and least-recently-used page-replacement strategies for a given sequence of page accesses. Perplexingly, it appears that FIFO produced fewer page faults than LRU. Is this possible, or have I made a mistake?

推荐答案

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

Yes, it's possible for FIFO to beat LRU. The smallest example I can think of,

缓存大小:2页.

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

Access pattern: A, B, A, C

此后，LRU缓存包含"A，C"，而FIFO缓存包含"B，C".到目前为止，他们每个人都错过了3次.因此，如果下一页访问为"B"，则FIFO胜过LRU.如果为"A"，则LRU会击败FIFO.如果还有其他问题，他们将保持联系.

After that, the LRU cache contains "A, C", whereas the FIFO cache contains "B, C". They have each missed 3 times so far. So if the next page access is "B", then FIFO beats LRU. If it's "A", LRU beats FIFO. If it's anything else, they remain tied.

这篇关于FIFO页面替换策略是否有可能胜过LRU?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！