Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1712159
  • 博文数量: 230
  • 博客积分: 9346
  • 博客等级: 中将
  • 技术积分: 3418
  • 用 户 组: 普通用户
  • 注册时间: 2006-01-26 01:58
文章分类

全部博文(230)

文章存档

2015年(30)

2014年(7)

2013年(12)

2012年(2)

2011年(3)

2010年(42)

2009年(9)

2008年(15)

2007年(74)

2006年(36)

分类: LINUX

2011-07-11 10:16:08

Cache替换算法是影响代理缓存系统性能的一个重要因素,一个好的Cache替换算法可以产生较高的命中率。目前已经提出的算法可以划分为以下三类:


(1)传统替换算法及其直接演化,其代表算法有:①LRU(Least Recently Used)算法:将最近最少使用的内容替换出Cache;②LFU(Lease Frequently Used)算法:将访问次数最少的内容替换出Cache;③Pitkow/Recker[10]提出了一种替换算法:如果Cache中所有内容都是同一天被缓存的,则将最大的文档替换出Cache,否则按LRU算法进行替换。


(2)基于缓存内容关键特征的替换算法,其代表算法有:①Size[10]替换算法:将最大的内容替换出Cache;②LRU—MIN[11]替换算法:该算法力图使被替换的文档个数最少。设待缓存文档的大小为S,对Cache中缓存的大小至少是S的文档,根据LRU算法进行替换;如果没有大小至少为S的对象,则从大小至少为S/2的文档中按照LRU算法进行替换;③LRU—Threshold[11] 替换算法:和LRU算法一致,只是大小超过一定阈值的文档不能被缓存;④Lowest Lacency First[12]替换算法:将访问延迟最小的文档替换出Cache。


(3)基于代价的替换算法,该类算法使用一个代价函数对Cache中的对象进行评估,最后根据代价值的大小决定替换对象。其代表算法有:①Hybrid[12] 算法:算法对Cache中的每一个对象赋予一个效用函数,将效用最小的对象替换出Cache;②Lowest Relative Value[13] 算法:将效用值最低的对象替换出Cache;③Least Normalized Cost Replacement(LCNR)[14]算法:该算法使用一个关于文档访问频次、传输时间和大小的推理函数来确定替换文档;④Bolot等人 [15]提出了一种基于文档传输时间代价、大小、和上次访问时间的权重推理函数来确定文档替换;⑤Size—Adjust LRU(SLRU)[16] 算法:对缓存的对象按代价与大小的比率进行排序,并选取比率最小的对象进行替换。


总之,为了使Cache命中率最大化,围绕Cache替换算法已经开展了大量的工作,但是替换算法的性能很大程度上取决于WWW访问的特性,还没有哪一种替换算法能够对所有Web访问模式都优于其它算法。

阅读(2208) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~