一种基于时钟自适应的改进缓存替换算法  

An Improved Clock Adaptive Cache Replacement Algorithm

作　　者：魏文国[1] 赵慧民[1] 庄林凯[1] 许鸿俊[1] 

机构地区：[1]广东技术师范学院电子与信息学院,广东广州510665

出　　处：《中山大学学报（自然科学版）》2012年第6期54-57,62,共5页Acta Scientiarum Naturalium Universitatis Sunyatseni

基　　金：国家自然科学基金资助项目(61272381);广东省自然科学基金资助项目(10151063301000000)

摘　　要：缓存算法在存储系统、数据库、Web服务器等计算机领域有很广泛的应用,缓存命中率是衡量缓存算法优劣的指标之一,对经典的缓存页面替代算法LRU、CLOCK、ARC和CAR进行了比较和分析,提出了一种基于时钟自适应的改进缓存替换算法———ICAR,它能更精确地对读请求的"频率"特性进行管理。实验结果表明,在几种典型的概率分布(例如随机分布、泊松分布和正态分布)的读请求进入缓存的情况下,ICAR在大部分情况下都比CAR和LRU算法有更高的缓存命中率。但是当缓存命中率相当高(高于80%)或者比较低(低于30%)的情况下,ICAR算法并不能总是表现出更好的性能,值得进一步研究。The caching algorithm has a very wide range of applications in the field of storage systems, database system and Web server, the cache hit ratio is one of cache measure indicators. Based on analy- sis of classic cache page replacement algorithms--LRU, CLOCK, ARC and CAR, the improved clock a- daptive cache replacement algorithm--ICAR is proposed, which can more accurately manage read requests ＂frequency＂ characteristics. The experimental results show that if read requests fulfill several typical probability distribution （for example, random distribution, the Poisson distribution and normal distribution） , ICAR can get higher cache hit rate than CAR and LRU algorithm in the majority of cases. But when the cache hit rate is very high （ above 80% ） or low （ less than 30% ） case, ICAR algorithm can not get better performance than CAR, worthy of further research

关 键 词：缓存 替换算法 命中率 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]