算法LRU,实现这个算法需要多少比特？

Question

我对算法LRU有一点疑问.如果您有一个包含四个块的缓存,那么您需要多少位才能实现此算法？

Answer 1

假设你的意思是4路组关联缓存:
"完美"LRU本质上是按照使用顺序为每条线分配一个精确的索引.您也可以将其视为"年龄".因此,4个元素中的每一个都需要2比特的索引(因为我们需要计算4个不同的年龄),说明它在LRU顺序中的位置 - 这意味着每个缓存集合有2比特*4路.
在n路的一般情况下,每行需要log2(n)位,或每组需要n*log2(n)位.

顺便说一句,还有更便宜的方式来达到一个几乎LRU行为,请参阅如伪LRU这将只需要对整组3位你的情况(或一般:#ways - 1)

Answer 2

http://www.powershow.com/view/95163-NzkyO/4_4_Page_replacement_algorithms_powerpoint_ppt_presentation有一个很好的幻灯片，讨论了各种页面替换方案。它还很好地解释了使用 mxm 矩阵的 LRU 实现。