LRU缓存算法

Question

我需要一个LRU算法的4路关联缓存有额外的5位每组，以指示哪一行应该被逐出。

       -------------------------------------
Set x: | line_0 | line_1 | line_2 | line_3 |
       -------------------------------------

      -----------------------------------------
      | bit_4 | bit_3 | bit_2 | bit_1 | bit_0 |
      -----------------------------------------

起初，我试图把我的问题分成更小的问题。只有两行时，我会触发与当前使用的行相对应的位，同时将另一行设置为0。

受害者将是位设置为0的行(前提是该设置已满)。

我想我可以在一个具有位bit_4、bit_3、bit_1、bit_0 (对应于line_0、line_1、line_2、line_3 )和中间位的4路缓存中使用它，以指示最近使用的是哪一方。很快，我意识到它不够精确。也就是说，在序列line_0、line_2、line_3、line_1之后，位数为: 10101，这表明左边最近被引用(这是真的)，但这并不一定意味着最近没有引用。

如有任何提示，我将不胜感激。

Answer 1

为了始终如一地找到最近使用最少的项，您需要跟踪最近使用的4行缓存行的顺序。

有四个！可能的订单。4！是24种可能性，你的额外5位有32种可能的配置，所以你有足够的比特(耶！)但是，您没有太多额外的比特，因此您不能真正期望顺序的编码非常容易处理。

从头顶上，我想我会这样做：

用于最近使用最少的项的

• 2位: 0-3。如果你需要的话，这是要驱逐的。
• 2位用于第二个最近使用最少的物品: 0-3
• 1位，第3位是最近使用最少的物品。只有两种可能性，因为另外两种可能性已经被使用过了。
• 0位是指最近使用的(最近使用的第4位)。只剩下一个，所以你不需要存储任何东西就知道它是哪一个。