高速缓存问题的解决

《高速缓存问题的解决》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、问题描述假设有n个页面驻留在内存中，且有一个能容纳k个页面的高速缓存。现有依次访问内存中m个页面的请求序列I=I1,I2,…,Ii,…,Im，其中m>k。我们必须确定任何时刻哪k个页面放在高速缓存中。对某个访问请求Ii，若该页面在高速缓存中，则可很快完成访问。否则发生一次缺页，必须将其调入高速缓存。这时，若高速缓存未满，则直接将其调入，否则必须确定将高速缓存中哪个页面置换出来以便为Ii腾出空间。高速缓存调度问题是指如何调度页面使得缺页的总数尽可能少。二、算法分析LRU算法:LRU策略淘汰上次使

2、用距离当前最远的页。LRU实现耗费较高，由于LUR淘汰的是上次使用距时刻t最远的页，故须记录这个距离。记录方法可使用计数器，给每个页帧增设一个计数器，每访问一页，就把对应的页帧的计数器清零，其余页帧加一，因此，计数器最大的页就是上次访问距今最远的页。Opt算法:虽然OPT策略被誉为驻留集固定策略中的最优策略，但是由于控制页面调度时需预先知道整个访问串，而在大多数情况下，访问串是不可知的，故难以付诸实用。在现实情况下并不能完全知晓整个请求序列，但假设我们事先已经知道，这样采取OPT就是最优的。缓存调

3、度采用OPT策略，OPT策略是驻留集大小固定策略中的最优策略。它淘汰下次访问距当前最远的那些页中序号最小的一页。称OPT为驻留集固定类策略中的最优策略理由是，OPT策略对任意一个访问串的控制均有最小的时空积（所占空间与时间的乘积）。就驻留集固定这类策略而言，由于所占空间为一常数，因此评判策略的性能时只需比较处理同一访问串各自所花费的时间量，即也故障的次数。设计的关键点：首先在缓存中遍历寻找是否有相应的页面，如果有责结束。否则，如果缓存内还有空间，则无条件调入内存。当缓存已满，则进行淘汰，用time

4、s记录最远的距离，Index记录最远者的下标。然后用当前页替换被淘汰页三、时空效率分析OPT时空分析：数据结构中最多只用到一维数组，故而空间复杂度为。由关键函数中复杂度最大的是嵌套的两层for循环可知，时间复杂度的数量级为O（m*k）LRU策略时空分析：空间消耗为一维数组和页的计数器，故而空间复杂度为O（n+k）；时间分析：时间最大消耗为每次匹配k个页块，匹配m次，故时间复杂度为O（m*k）一、运行结果OPT策略：访问串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1驻留集大小

5、：3LRU策略：访问串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，3驻留集大小：3一、分析输出结果OPT策略过程：701203042777222222000000441113333Miss空直接进入Miss空直接进入Miss空直接进入Miss7为无0为11为110hitMiss2为10为21为90hitMiss2为10为33为22hit淘汰7淘汰1淘汰0303212012222222240000000333311113hitMiss2为24为无3为13Hit2hitMis

6、s2为10为23为无2hit0hit1hit淘汰4淘汰3LRU策略：701203042777222244000000001113332Miss空直接进入Miss空直接进入Miss空直接进入Miss7为30为21为1HitMiss2为20为11为3HitMiss2为40为13为2Miss4为10为23为3淘汰7淘汰1淘汰2淘汰3303212013400011111333333000222222223Miss4为20为32为1Miss4为33为12为2HitHitMiss0为33为22为1HitMis

7、s1为23为42为1HitMiss1为10为22为3淘汰0淘汰4淘汰0淘汰3淘汰2代码:lru算法：#include//定义全局变量typedefstruct{intstate;//块状态true满，false为空intvalue;//块内的页面号intcount;//块计数器标志块据现在的时间}type;typecach[]={{false,-1,0},//初始化块信息{false,-1,0},{false,-1,0},{false,-1,0}};//type中有四块in

8、twalk_sort[]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,3};//页面访问序列intm=3;//type块的个数intn=18,count=0;//访问序列的长度voiddelay();//声明voidup_type(typetype[],intwalk_sort[]){inti=0;//i为访问序列数组的下标intx;intk;intkk;while(i