什么时候FIFO会胜过LRU替换算法？

Question

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

Answer 1

对于三页缓存，序列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]

Answer 2

FIFO是一种简单的缓存实现方式，虽然实现起来很简单，但并不能提供最佳的页面错误。

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

在实践中，LRU是最优的缓存实现，各种操作系统、数据库都使用LRU的变体，如ARC、LIRS...

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

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