代码之家  ›  专栏  ›  技术社区  ›  wkkuna

LRU缓存算法

  •  0
  • wkkuna  · 技术社区  · 4 年前

    我需要一个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的行(前提是该组已满)。

    我想我可以在有位的4路缓存中使用它 bit_4 , bit_3 , bit_1 , bit_0 对应于 line_0 , line_1 , line_2 , line_3 中间的位表示最近使用了哪一侧。我很快意识到它不够精确。即在序列之后 line_0 , 线2 , 线3 , line_1 比特将是:10101,这将指示左侧最近被引用(这是真的),但这并不一定意味着该侧最近没有被引用。

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

    0 回复  |  直到 4 年前
        1
  •  1
  •   Matt Timmermans    4 年前

    为了一致地找到最近使用最少的项,您需要跟踪最近使用4个缓存行的顺序。

    有4个!可能的订单。4!有24种可能性,额外的5位有32种可能的配置,所以你有足够的位(耶!)。不过,你没有很多额外的比特,所以你不能真的指望顺序的编码非常容易使用。

    我突然想到,我会这样做:

    • 最近最少使用的项目为2位:0-3。如果你需要的话,这是要驱逐的。
    • 最近使用次数第二少的项目为2位:0-3
    • 1位表示第三个最近最少使用的项目。只有两种可能性,因为另外两种已经被使用了。0表示数字较小的剩余缓存行。
    • 最近使用的0位(最近使用最少的第四位)。只剩下一个了,所以你不需要存储任何东西来知道它是哪一个。