【摘要】 高速缓存替换策略的动态选择方法属于存储系统高速缓存领域，其特征在于：通过统一的接口将高速缓存替换策略模块化，可以在任意两个高速缓存替换策略之间进行在线切换，可以部署新的高速缓存替换策略；异步进行访问记录采集和分析，CPU和内存开销较小，对应用影响较小；多轮策略选择可以尽快得到比较准确的决策结果，既保证快速将结果投入使用，也尽量减少方法的开销。。 【专利类型】发明授权 【申请人】清华大学 【申请人类型】学校 【申请人地址】100084 北京市100084-82信箱 【申请人地区】中国 【申请人城市】北京市 【申请人区县】海淀区 【申请号】CN200810057172.7 【申请日】2008-01-30 【申请年份】2008 【公开公告号】CN101236530B 【公开公告日】2010-09-01 【公开公告年份】2010 【授权公告号】CN101236530B 【授权公告日】2010-09-01 【授权公告年份】2010.0 【IPC分类号】G06F12/12; G06F12/126 【发明人】郑纬民; 舒继武; 薛巍; 汪旸 【主权项内容】高速缓存替换策略的动态选择方法，其特征在于：所述方法是在高速缓存存储器系统内的一个数字集成电路上依次按以下步骤实现的：步骤(1).初始化，设置以下模块：高速缓存替换策略模块，高速缓存服务模块，访问记录采集器模块以及访问记录分析器模块，其中：1)高速缓存替换策略模块，设立以下接口描述命中和替换时的逻辑：a.初始化接口，为用户指定的或第一次运行时确定的或切换后的当前高速缓存策略模块分配内存，初始化数据结构；b.释放用接口，释放即将被替换的高速缓存替换策略模块，包括释放数据结构和内存，供被替换的高速缓存替换策略模块卸载时使用；c.更新用接口，当高速缓存数据块被命中时，更新该块的优先级；d.插入用接口，当插入新的高速缓存数据块时，设置该块的优先级；e.替换用接口，取优先级最低的高速缓存数据块为被替换块时使用；所述高速缓存替换策略模块共有以下五种：最近被使用，双队列，多队列，自适应低负载和低最近相关度，各有一个固定的入口函数register，以便把自己的接口实现注册给所述高速缓存服务模块，在各高速缓存替换策略模块中，处于运行状态的为当前高速缓存替换策略模块，其余则为候选高速缓存替换策略模块；2)高速缓存服务模块，把包括磁盘在内的低速存储设备的数据缓存在内存中，当用户访问数据时直接进行内存访问，该高速缓存服务模块设有：高速缓存数据、高速缓存元数据以及哈希表，其中a.高速缓存数据，是缓存好的磁盘数据，被分成多个固定大小的高速缓存数据块，块的大小为4KB，b.高速缓存元数据，用于维护和管理所述高速缓存数据，其中包括：1)每个高速缓存数据块的物理地址；2)每个高速缓存数据块符号位用于标志该块是否已被写入磁盘；3)一个最近被使用队列，用于记录所述高速缓存数据块的优先级顺序；c.哈希表，以所述高速缓存数据块的地址作为关键字，对应的高速缓存元数据为数据，构成一个数据查找表，用于确定一个高速缓存数据块是否在所述高速缓存存储器中；所述高速缓存服务模块依次按以下顺序实现高速缓存服务：a.当用户访问数据时，该高速缓存服务模块首先根据其中数据给定的高速缓存数据块的地址查找哈希表；b.若所述地址已在哈希表中，则高速缓存命中，通过更新用接口，调用所述当前高速缓存替换策略模块的命中功能，直接访问高速缓存，读出数据返回给用户；c.若地址不存在于哈希表中，则为高速缓存缺失，判断高速缓存数据块是否已全部被占用：若未全部被占用，则取出一个未占用的高速缓存数据块，通过所述插入用接口，调用所述当前高速缓存替换策略模块的插入功能，把数据调入所述未占用的高速缓存数据块，若高速缓存数据块已用完，则通过替换用接口，调用所述当前高速缓存替换策略模块的替换功能，找到一个在所述高速缓存数据块中优先级最低的高速缓存数据块作被替换块，把数据读入替换出的高速缓存数据块，再返回给用户；3)访问记录采集器模块，记录从所述高速缓存服务模块输入的访问信息，其中包括：磁盘号、访问地址和大小，先存储在内存缓冲区中，当存满时，把这些访问信息写入到磁盘文件中；4)访问记录分析器模块，从所述访问记录采集器模块收到已采集到设定的n条访问记录的信息后，把各访问记录依次导入各候选高速缓存替换策略模块，记录所述各候选高速缓存替换策略模块的命中次数，取命中次数最多的候选高速缓存替换策略模块为最优策略模块，把结果通知所述高速缓存服务模块；步骤(2).依次按以下步骤执行高速缓存替换策略的动态选择方法：步骤(2.1).初始化高速缓存服务模块：分配和初始化所有高速缓存数据块；分配和初始化所有的通用高速缓存数据块描述符，所述高速缓存数据块用于记录该高速缓存数据块的地址和符号位，“通用”两字是指各高速缓存替换策略模块都需用到的；初始化哈希表和最近被使用队列；步骤(2.2).当前高速缓存替换策略模块的初始化：步骤(2.2.1).确定一个高速缓存替换策略模块为当前高速缓存替换策略模块：当由用户指定时，默认取上次运行结束时所用的高速缓存替换策略模块；当第一次运行时取最近被使用高速缓存替换策略模块；步骤(2.2.2).高速缓存服务模块调用所述register函数注册该当前高速缓存替换策略模块，再通过初始化接口初始化所述当前高速缓存替换策略模块；步骤(2.3).在用户访问数据时，高速缓存服务模块按步骤(1)所述方法插入用户访问数据为高速缓存数据块；步骤(2.4).访问记录采集器采集用户访问记录；步骤(2.5).访问记录分析当访问记录采集器采集到所述n条访问记录后，由访问记录分析器模块通过自己设定的一个虚拟的高速缓存服务模块来记录当访问记录依次访问各候选高速缓存替换策略模块时的记录命中次数，挑选命中次数最高的候选高速缓存替换策略模块为最优策略模块；步骤(2.6).切换高速缓存替换策略模块，首先高速缓存服务模块通过当前正处于运行状态的高速缓存替换策略模块的释放用接口释放策略元数据，所述策略元数据是指各高速缓存替换策略模块所特有的元数据；然后，高速缓存服务模块通过访问记录命中次数最高的那个新的高速缓存替换策略模块的初始化接口分配新的策略元数据空间；最后，高速缓存服务模块通过新的高速缓存替换策略模块的插入用接口把高速缓存中已有的高速缓存数据块依次导入新的高速缓存替换策略模块以重建新的策略元数据。 【当前权利人】清华大学 【当前专利权人地址】北京市100084-82信箱 【专利权人类型】公立 【统一社会信用代码】12100000400000624D 【家族被引证次数】62
