一种量化的页面淘汰算法  

A Quantization Algorithm for Page Replacement

作　　者：沈仕敏 陈闳中[1] 方钰[1] 

机构地区：[1]国家高性能计算机工程技术中心同济分中心,上海201804

出　　处：《计算机工程与科学》2008年第12期90-93,共4页Computer Engineering & Science

基　　金：国家863计划资助项目(2007AA01Z136)

摘　　要：当前,操作系统和数据库系统中使用较为广泛的页面淘汰算法是LRU-k。但是,随着大量有着不同读写速度的外存设备共存于系统中,LRU-k仅仅根据页面最近访问频率去预测近阶段"热点"页面的缺点显现。本文提出了一种量化算法ELRUK,该算法不仅考虑到了页面最近访问的频率,同时还考虑了缓冲页面等其他属性,并根据这些信息得到页面淘汰代价量化值,选取值最小的页面进行淘汰。ELRUK模型是一个针对不同外存储设备的通用模型,这使得原有的LRU-k成为ELRUK的一种退化形式。算法采用了多堆哈希表的组合数据结构,提高了执行效率。实验表明,与LRU-2相比,ELRU2在时间上节省15%～30%。LRU-k is one of the most widely applied page-replacement algorithms in the modem operating systems and database systems. However, with the increment of the number of secondary storage devices having different read-write speeds in the system, the drawback of LRU- k that only the frequency of recent page references is taken into account to predict the hot pages in the near future is coming up. In this paper, a quantization algorithm named ELRUK is proposed for page replacement. The algorithm combines another page attribute with the frequency of recent page references to evaluate the quantization value for eliminating cost and picks up the minimum one for elimination. The fact that ELRUK quantization model is commonly used for a system with different kinds of secondary storage devices demonstrates that LRU- k is just a particular form of ELRUK. Multi-heap and Hash table are used in the algorithm to improve the efficiency. The experimen- tal results show that ELRU2 reduces the read-write time by 15-30M, compared with LRU-2.

关 键 词：ELRUK 量化 LRU-k 缓冲 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]