Segmented LRU替换算法

在LRU(Least Recently Used)算法中,我们将缓存行按照最近使用时间进行排序。每次替换其中最长时间没有访问过的缓存行。

在实际的cache替换场景中,有一个很重要的现象,即如果一个缓存行被短时间访问了超过两次,那么他极有可能在近期再次被访问。LRU算法并没有基于该现象进行优化,而常常由于某一个常用缓存行在短时间内恰好没有使用而被替换出去。

Segmented LRU算法就是用来解决上述问题的,他通过在缓存行上面新加一个位,将缓存分为两个段(segment),分别称作试用段(probationary segment)和保护段(protected segment)。保护段里面存放了那些近期被多次访问,极有可能再次被访问的缓存行。而试用段则存放最近被导入缓存,但是并没有被多次访问的段。

上图非常清楚的解释了两个段的关系——

  • 任何段的访问都会导致该行被移到保护段的顶端
  • 保护段中最近未被使用的行会被退回到试用段的顶端,在替换他之前,为它提供额外的机会

当然,如果我们仔细对比了LRU和SLRU的代码,可以发现区别并不像之前我们说的这么多。如果我们将保护段和试用段连到一起,你就会发现,SLRU和LRU唯一的区别就是当一个不在缓存中的行进入缓存时,LRU算法将它放在了第0号位置,即Most Recently Used的位置,而SLRU算法将它放在了不那么高的一个位置,即保护段和试用段连接处的位置。这样SLRU算法就不会担心某一些特定代码段(比如短时间塞入了大量无用缓存行)会完全破坏缓存的有效性了。

参考文献:R. Karedla et al, “Caching Strategies to Improve Disk System Performance”, Computer, vol. 27, no. 3, pp. 38-46, Mar. 1994.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据