Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (17): 153-157.

• 数据库、信号与信息处理 • Previous Articles     Next Articles

Improved LRFU algorithm with adaptive replacement

LI Zhan-sheng1,BI Hui-juan1,LI Yan-ping2,ZHANG Li-song1   

  1. 1.Department of Software Platform,North China Institute of Computing Technology,Beijing 100083,China
    2.Department of Computer Science and Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China
  • Received:2007-09-14 Revised:2007-11-28 Online:2008-06-11 Published:2008-06-11
  • Contact: LI Zhan-sheng

一种对LRFU置换策略的自适应改进

李占胜1,毕会娟1,李艳平2,张立松1   

  1. 1.华北计算技术研究所 软件平台研究室,北京 100083
    2.北京邮电大学 计算机科学与技术学院,北京 100876
  • 通讯作者: 李占胜

Abstract: The database buffer page replacement algorithm has an important impact in the performance of the database system.Caching is one of the most fundamental metaphor in modern computing,Cache replacement policies play a crucial part in different aspects of today’s high performance computing environments.It studies some of the page replacement algorithms,including the recency based algorithms,the frequency based algorithms and the adaptive algorithms.The LRFU algorithms isn’t a self-tuning algorithm,although it combines the recency and frequency.This paper proposes an improved LRFU algorithm,that can adaptively and dynamically modify the λ value of LRFU.Conducting simulations with a variety of file access patterns and a wide range of buffer size,it shows that the improved LRFU algorithm outperforms a LRFU algorithm in many cases.

摘要: 数据库缓冲区页面置换算法对磁盘数据库的性能有着重要的影响,页面置换算法主要有基于访问时间的置换策略、基于访问次数的置换策略、两者结合的置换策略等。LRFU算法是一系列结合LRU和LFU置换策略的置换算法,很好地实现了两种置换策略的结合,但却没有给出一种在不同的应用场景中进行动态调整的机制。提出了一种对LRFU算法进行动态调整的方法,模拟测试发现改进的LRFU算法都不同程度地提高了缓冲区命中率。