高速缓存问题的解决.doc

一、 问题描述假设有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驻留集大小：3LRU策略：访问串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，3驻留集大小：3五、 分析输出结果OPT策略过程： 7012030427772222220 00000441113333Miss 空直接进入Miss空直接进入Miss空直接进入Miss7为无0为11为110hitMiss2为10为21为9 0 hit Miss2为10 为33为 22 hit淘汰7淘汰1淘汰0303212012222222240000000333311113 hit Miss2为24为无3为13 Hit2 hit Miss 2为10为23为无2 hit0 hit1hit淘汰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为1HitMiss1为23为42为1HitMiss1为10为22为3淘汰0淘汰4淘汰0淘汰3淘汰2代码:lru算法：#include/定义全局变量typedef struct int state; /块状态true满，false为空 int value; /块内的页面号 int count; /块计数器标志块据现在的时间 type;type cach=false,-1,0, /初始化块信息 false,-1,0, false,-1,0, false,-1,0; /type中有四块 int walk_sort=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,3; /页面访问序列int m=3; /type 块的个数int n=18,count=0; /访问序列的长度void delay(); /声明void up_type(type type,int walk_sort) int i=0; /i为访问序列数组的下标 int x; int k; int kk; while(in) int j=0; /j为type块的下标 /满? while(jm) /当块没有装满情况 if(typej.state=false)&(walk_sorti!=typej.value) /装入一块 typej.value=walk_sorti+; typej.state=true; typej.count=0;count+; int kk=0; for (x=0;xm;x+)if(typex.value!=-1)couttypex.value ;coutmissendl; /更新其它 while(kkm) if(kk!=j&typekk.value!=(-1) typekk.count+; kk+; delay(); break; if(typej.value=walk_sorti) /命中 for (x=0;xm;x+)if(typex.value!=-1)couttypex.value ; couthitendl; int kk=0; i+; typej.count=0; while(kkm) if(kk!=j&typekk.value!=(-1) typekk.count+; kk+; j+; /块下标加一 if(j=m) /考虑type块已经满的情况 int k=0; /块下标 while(km) /遍历块看其中是否有和访问序列相同的页号，有相同的则命中 if(typek.value=walk_sorti) coutendl; for (x=0;xm;x+) couttypex.value ; couthitendl; i+; typek.count=0; int kk=0; /更新其它type块没使用时间 while(kkm) if(kk!=k) typekk.count+; kk+; break; k+; if(k=m)/type满且没有命中的情况，考虑置换那一块. int ii=0;count+; int t=0;/要替换的type块号. int max=typeii.count; ii+; while(iimax) max=typeii.count; t=ii; ii+; /置换 typet.value=walk_sorti+; typet.count=0; for (x=0;xm;x+)couttypex.value ;coutmissendl; int kk=0; /更新其它type块没使用时间 while(kkm) if(kk!=t) typekk.count+; kk+; delay(); void delay() int i; for(i=0;i100;i+) ;void main(int argc, char* argv) coutLRU策略动态变化过程endl; up_type(cach,walk_sort); int i;coutmiss的次数counti;Opt算法：/高速缓存调度问题-OPT算法/#include using namespace std;#define MAX 256int n,k,m;/n个页面驻留集，k个页面的高速缓存，m长度的请求队列int IMAX;int cur_resident;/当前驻留集的个数int cacheMAX,cur_cache;/当前在高速缓存中的页面信息int page_miss;/缺页中断的次数void attemper()cache0 = I0;cur_cache = 1;page_miss = 1;cout缓存内的页面的动态变化过程为：nI0endl;for(int i=1; im; i+)int j;for( j=0; jcur_cache; j+)if(Ii = cachej)break;if(j = cur_cache)page_miss+;if(cur_cache k)cachecur_cache+ = Ii;else/cur_cache=k/淘汰最远的页面int times = 0;int index = 0;for(int q=0; qk; q+)/cache的下标int p;for( p=i+1; pm; p+)if(Ip = cacheq)if(times p-i)times = p-i;index = q;break;if(p = m)index = q;break;cacheindex = Ii;/attemperelsefor(int m=0;mcur_cache;m+)coutcachem ;coutendl;int main()page_miss = 0;c