自适应Lru(最近最少使用)算法

在缓存管理算法中,Lru 几乎是公认的最优的算法。然而它也有一些缺陷,主要是因为:它假定对实体的访问有局部特性。当访问模式没有局部特性的时候,它就会退化为FIFO(先进先出)算法。

在我写一个文件系统的实现时,这种现象很让我头疼,因为很多时候,对一个文件的访问大多是顺序的,前面读取过的内容几乎不会被再次读取。苦思冥想之后,我终于找到了一种方案:

就是在缓存击中率降低时,移动将被换出的缓存结点,当击中率很低时,此算法就变成了LIFO(后进先出)。在顺序访问,和完全随机访问时,比Lru有很大的优越性。而在击中率比较高的时侯,它就是 Lru 算法。

以下是算法的关键代码:

 

作者:
该日志由 rockeet 于2005年11月05日发表在操作系统, 算法分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: 自适应Lru(最近最少使用)算法
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

发表评论

您必须 登录 后才能发表评论。