高速缓存问题解决.docVIP

问题描述 假设有n个页面驻留在内存中，且有一个能容纳k个页面的高速缓存。现有依次访问内存中m个页面的请求序列I=I1,I2,…,Ii,…,Im，其中mk。我们必须确定任何时刻哪k个页面放在高速缓存中。对某个访问请求Ii，若该页面在高速缓存中，则可很快完成访问。否则发生一次缺页，必须将其调入高速缓存。这时，若高速缓存未满，则直接将其调入，否则必须确定将高速缓存中哪个页面置换出来以便为Ii腾出空间。高速缓存调度问题是指如何调度页面使得缺页的总数尽可能少。 算法分析 LRU算法: LRU策略淘汰上次使用距离当前最远的页。LRU实现耗费较高，由于LUR淘汰的是上次使用距时刻t最远的页，故须记录这个距离。记录方法可使用计数器，给每个页帧增设一个计数器，每访问一页，就把对应的页帧的计数器清零，其余页帧加一，因此，计数器最大的页就是上次访问距今最远的页。 Opt算法: 虽然OPT策略被誉为驻留集固定策略中的最优策略，但是由于控制页面调度时需预先知道整个访问串，而在大多数情况下，访问串是不可知的，故难以付诸实用。在现实情况下并不能完全知晓整个请求序列，但假设我们事先已经知道，这样采取OPT就是最优的。 缓存调度采用OPT策略，OPT策略是驻留集大小固定策略中的最优策略。它淘汰下次访问距当前最远的那些页中序号最小的一页。称OPT为驻留集固定类策略中的最优策略理由是，OPT策略对任意一个访问串的控制均有最小的时空积（所占空间与时间的乘积）。就驻留集固定这类策略而言，由于所占空间为一常数，因此评判策略的性能时只需比较处理同一访问串各自所花费的时间量，即也故障的次数。 设计的关键点： 首先在缓存中遍历寻找是否有相应的页面，如果有责结束。否则，如果缓存内还有空间，则无条件调入内存。当缓存已满，则进行淘汰，用times记录最远的距离，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 驻留集大小：3 LRU策略： 访问串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，3 驻留集大小：3 分析输出结果 OPT策略过程： 7 0 1 2 0 3 0 4 2 7 7 7 2 2 2 2 2 2 0 0 0 0 0 0 4 4 1 1 1 3 3 3 3 Miss 空直接进入 Miss 空直接进入 Miss 空直接进入 Miss 7为无 0为1 1为11 0hit Miss 2为1 0为2 1为9 0 hit Miss 2为1 0 为3 3为 2 2 hit 淘汰7 淘汰1 淘汰0 3 0 3 2 1 2 0 1 2 2 2 2 2 2 2 2 4 0 0 0 0 0 0 0 3 3 3 3 1 1 1 1 3 hit Miss 2为2 4为无 3为1 3 Hit 2 hit Miss 2为1 0为2 3为无 2 hit 0 hit 1hit 淘汰4 淘汰3 LRU策略： 7 0 1 2 0 3 0 4 2 7 7 7 2 2 2 2 4 4 0 0 0 0 0 0 0 0 1 1 1 3 3 3 2 Miss 空直接进入 Miss 空直接进入 Miss 空直接进入 Miss 7为3 0为2 1为1 Hit Miss 2为2 0为1 1为3 Hit Miss 2为4 0为1 3为2 Miss 4为1 0为2 3为3 淘汰7 淘汰1 淘汰2 淘汰3 3 0 3 2 1 2 0 1 3 4 0 0 0 1 1 1 1 1 3 3 3 3 3 3 0 0 0 2 2 2 2 2 2 2 2 3 Miss 4为2 0为3 2为1 Miss 4为3 3为1 2为2 Hit Hit Miss 0为3 3为2 2为1 Hit Miss 1为2 3为4 2为1 Hit Miss 1为1 0为2 2为3 淘汰0 淘汰4 淘汰0 淘汰3 淘汰2 代码: lru算法： #includeiostream.h //定义全局变量 typedef struct{ int state; //块状态true满，false为空 int value; //块内的页面号 int cou