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

An Improved Clock Adaptive Cache Replacement Algorithm

缓存算法在存储系统、数据库、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