FIFO什么时候战胜LRU置换算法？

Question

当FIFO战胜LRU时，我需要一个数字序列。假设少于 15 个数字，页数为 3。我希望 FIFO 比 LRU 获得更少的页面错误。可能吗？

Answer 1

FIFO 是简单的缓存实现，虽然实现简单，但不提供最佳页面错误。

当使用基于 CLOCK（FIFO 的变体）的数据结构时，我们可以获得更好的性能，与 LRU 相比，它提供更少的页面错误。 CLOCK 有多种变体。

实际上，LRU 是最佳缓存实现和各种 OS，数据库使用 LRU 的变体，例如 ARC、LIRS ...

有关各种缓存策略的更多信息，请参阅 wiki

https://en.wikipedia.org/wiki/Cache_replacement_policies https://en.wikipedia.org/wiki/Page_replacement_algorithm

Answer 2

对于三页缓存，序列 1, 2, 3, 1, 4, 2 就可以了。缓存的演变：

FIFO    LRU
1       1
12      12
123     123 [three misses for both as the cache fills]
123     231 [LRU moves 1 to the back]
234     314
234     142 [LRU but not FIFO misses on 2]

FIFO什么时候战胜LRU置换算法？

When does FIFO win over LRU replacement algorithm?

algorithm

replace

fifo

lru