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访问模式都优于其它算法。
分享到:
相关推荐
计算机组成原理之Cache替换算法
本文档介绍了几种cache替换算法,包括常用的LRU算法,Clock和2Q,也包括几种改进的cache替换算法,如Clock-Pro等,可以为研究Cache替换算法的同学提供一定的帮助
一种基于频率的多核共享Cache替换算法
cache替换算法代码一种可以机器学习的替换算法
。。。
Cache存储器系统地址映象及替换算法的简单动态演示程序VC源码
2.1 Cache替换算法 6 2.2 Cache在搜索引擎中的应用 8 第三章 一种通用Cache的设计和实现 9 3.1 通用Cache的设计目标 9 3.3.1 通用性目标 9 3.3.2 高效性要求 10 3.3.3 自评测目标 10 3.2 通用Cache的设计 10 3.2.1总...
缓存是指可以进行高速数据交换的存储器,它先于内存与CPU交换数据,因此速度很快。缓存就是把一些数据暂时存放于某些地方,可能是内存,也有...下面给大家介绍Python实现以时间换空间的缓存替换算法,需要的朋友参考下
rust-clockpro-cache Rust 的 CLOCK-Pro 缓存替换算法
在下列 cache 替换算法中,平均命中率最高的是(3)。 (1) A.全部由软件实现 B.全部由硬件实现 C.由硬件和软件相结合实现 D.有的计算机由硬件实现,有的计算机由软件实现 (2) A. 00 0100 0100 1101 (二进制) B. 01...
第5周 Cache替换算法和写策略第1讲 Cache替换算法第2讲 Cache写策略(一致性问题)第3讲 Cache实现的几个因素第4讲 Cache实现举例第5
本代码是cache代码,采用最近最少使用算法。代码量大约1000-2000行,程序包括cache替换算法的实现。映像规则的选择,以及全部的仿真程序。
Cache替换算法与写方法:各种不同替换算法的原理,写直达与写回 考点6. Cache与虚存的效率问题:使用Cache和虚存对存取效率提高的比率计算 考点7. 常见的寻址方式:各种寻址方式的寻址过程,使用到的硬件设备 考点8...
有深究打算的可以看操作系统书的第五章(cache替换算法里也采用了这其中的两种)OPT置换算法(最佳置换算法):选择以后长时间内不再使用的页面作为淘汰页面置换出
通过BWDSP模拟器对目前常用的几种替换算法和大小不同的指令Cache块进行仿真实验得出不同缺失率。实验结果表明,所提出的PLRU替换算法性能高于LRU、LFU、FIFO替换算法,并使BWDSP整体性能提高到为其他三种替换算法的...
1) 运行SimpleScalar模拟器; 2) 在基本配置情况下运行程序(请指明所选的测试程序),统计Cache总失效次数、三种不同种类的失效次数; 3) 改变Cache容量(*2,*4,*8,*64)...分析不同的替换算法对Cache性能的影响。
自适应替换缓存 自适应替换缓存算法优于LRU
D.OPT是最优替换算法,是实际应用最广泛的一种替换算法。 26、在页面替换中,如果选择近期最少访问的页面作为被替换的页面,这种替换算法叫座( )。 A、FIFO算法 B、LFU算法 C、LRU算法 D、OPT算法 27、在下述各题...
研究了BPEL4WS执行引擎WebJetFlow对Web服务的异步调用机制,在...同时引入了cache机制并设计了相应的cache替换算法,保证了引擎对异步调用结果消息的匹配效率以及数据安全性, 通过实验验证引擎的性能有了明显的提高。
缓存模拟器这使用LRU(最近最少使用)替换算法模拟L1级缓存。 c-sim [-h] [缓存大小] [关联性] [块大小] [写入策略] [跟踪文件] 在哪里: 是缓存的总大小。 这应该是2的幂。而且,<cachesize> =集数××<块大小>...