置换算法、缺页率

存储管理置换算法实验内容（1）通过计算不同算法的命中率比较算法的优劣。同时也考虑了用户内存容量对命中率的影响。页面失效次数为每次访问相应指令时，该指令所对应的页不在内存中的次数。在本实验中，假定页面大小为1k，用户虚存容量为32k，用户内存容量为4页到32页。（2）produce_addstream通过随机数产生一个指令序列，共320条指令。A、指令的地址按下述原则生成：1）50%的指令是顺序执行的2）25%的指令是均匀分布在前地址部分3）25%的指令是均匀分布在后地址部分B、具体的实施方法是：1）在[0，319]的指令地址之间随机选取一起点m；2）顺序执行一条指令，即执行地址为m+1的指令；3）在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；4）顺序执行一条指令，地址为m’+1的指令5）在后地址[m’+2，319]中随机选取一条指令并执行；6）重复上述步骤1）~5），直到执行320次指令C、将指令序列变换称为页地址流在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条~第9条指令为第0页（对应虚存地址为[0，9]）；第10条~第19条指令为第1页（对应虚存地址为[10，19]）；。。。。。。页地址流长度页面失效次数命中率1第310条~第319条指令为第31页（对应虚存地址为[310，319]）；按以上方式，用户指令可组成32页。（3）计算并输出下属算法在不同内存容量下的命中率。1）先进先出的算法（FIFO）；2）最近最少使用算法（LRU）；3）最佳淘汰算法（OPT）；4）最少访问页面算法（LFR）；其中3）和4）为选择内容运行结果首先打印出产生的指令信息，第一列为指令序列号，第二列为指令地址，第三列为指令所在的虚页号选择FIFO调度算法，并且内存从3也开始逐渐增加到32页，打印出缺页次数缺页率，命中率选择LRU调度算法，并且内存从3也开始逐渐增加到32页，打印出缺页次数缺页率，命中率选择OPT调度算法，并且内存从3也开始逐渐增加到32页，打印出缺页次数缺页率，命中率实验程序产生指令流文件produce_addstream.h#ifndefPRODUCE_ADDSTREAM_H#definePRODUCE_ADDSTREAM_H#includestdio.h#includestdlib.h#includetime.h#includeiomanip.h#includevectorusingnamespacestd;#definerandom(x)(rand()%x)#defineMAX_LENGTH320structproduce{intnum;//指令序号intzhiling;//指令地址intvirtualpage;//指令虚页号produce*next;};structproduce*creatlist();voidinsert(structproduce*first,structproduce*s);//插入一个节点（尾插法）voidprint(structproduce*first);//打印函数intmax(vectorvectorint,int);structproduce*creatlist(){srand((int)time(0));structproduce*first=newproduce;first-next=NULL;intm=0,m1=0;/*intyanzheng[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};for(inti=0;i(MAX_LENGTH/4);i++){structproduce*s0;s0=newproduce;s0-num=i*4+0;s0-zhiling=yanzheng[i*4+0];s0-virtualpage=s0-zhiling;insert(first,s0);structproduce*s1;s1=newproduce;s1-num=i*4+1;s1-zhiling=yanzheng[i*4+1];s1-virtualpage=s1-zhiling;insert(first,s1);structproduce*s2;s2=newproduce;s2-num=i*4+2;s2-zhiling=yanzheng[i*4+2];s2-virtualpage=s2-zhiling;insert(first,s2);structproduce*s3;s3=newproduce;s3-num=i*4+3;s3-zhiling=yanzheng[i*4+3];s3-virtualpage=s3-zhiling;insert(first,s3);}//*///*for(inti=0;i(MAX_LENGTH/4);i++){structproduce*s0;s0=newproduce;m=random(MAX_LENGTH);s0-num=i*4+0;s0-zhiling=m+1;s0-virtualpage=s0-zhiling/10;insert(first,s0);m1=random(m+1);structproduce*s1;s1=newproduce;s1-num=i*4+1;s1-zhiling=m1;s1-virtualpage=s1-zhiling/10;insert(first,s1);structproduce*s2;s2=newproduce;s2-num=i*4+2;s2-zhiling=m1+1;s2-virtualpage=s2-zhiling/10;insert(first,s2);structproduce*s3;s3=newproduce;s3-num=i*4+3;s3-zhiling=random(MAX_LENGTH-m1-2)+m1+2;s3-virtualpage=s3-zhiling/10;insert(first,s3);}//*/returnfirst;}voidinsert(structproduce*first,structproduce*s){structproduce*r=first;structproduce*p;while(r){p=r;r=r-next;}p-next=s;p=s;p-next=NULL;}voidprint(structproduce*first)//打印函数{structproduce*p;p=first-next;cout随机产生的指令的信息如下endl;cout指令序号指令地址指令虚页号endl;while(p){coutp-num'\t'p-zhilingsetw(14)p-virtualpageendl;p=p-next;}}intmax(vectorvectorintpage,intMaxpage){inta=0,position=0;for(inti=0;iMaxpage;i++){if(page[i][1]a){a=page[i][1];position=i;}}returnposition;}#endif先来先出调度算法：fifo.h#ifndefFIFO_H#defineFIFO_Hvoidfifo(structproduce*first,intMaxpage){vectorintpage(Maxpage);//for(inti=0;iMaxpage;i++)page[i]=-1;intrear=0;//定义一个变量，指向要被替换的位置intpages;//定义变量保存当前指令的所在的地址intcount1=0;//intcount2=0;//缺页次数intfind=1;structproduce*p=first-next;while(p){pages=p-virtualpage;for(inti=0;iMaxpage;i++){if(page[i]==-1||count1Maxpage){page[i]=pages;count1++;count2++;find=1;break;}elseif(page[i]==pages){find=1;break;}find=0;}if(find==0){page[rear]=pages;rear++;rear=rear%Maxpage;count2++;}p=p-next;}coutFIFO调度算法缺页次数缺页率命中率endl;coutcount2setw(25)double(count2)/MAX_LENGTHsetw(10)1-double(count2)/MAX_LENGTHendl;}#endifFIFO_HLRU调度算法lru.h#ifndefLRU_H#defineLRU_H#includevectorusingnamespacestd;//intmax(vectorvectorint,int);voidlru(structproduce*first,intMaxpage){structproduce*p=first-next;vectorvectorintpage2(Maxpage,vectorint(2));intcount1=0;//定义内存已经被占用的页数intcount2=0;//定义记录缺页次数intequal=0;//定义判断如果当前页数与比较的页数，如果相等则为1，否则为0intplace=0;//定义要替换的位置for(inti=0;iMaxpage;i++){page2[i][0]=-1;page2[i][1]=0;}while(p){if(count1Maxpage){for(inti=0;iMaxpage;i++){page2[i][1]=page2[i][1]+1;if(page2[i][0]==-1){page2[i][0]=p-virtualpage;count2++;break;}elseif(page2[i][0]==p-virtualpage){page2[i][1]=1;}}count1++;}else{for(inti=0;iMaxpage;i++){page2[i][1]+=1;if(page2[i][0]==p-virtualpage){equal=1;place=i;break;}}if(equal==1){page2[place][1]=1;equal=0;}else{place=max(page2,Maxpage);page2[place][1]=1;page2[place][0]=p-virtualpage;count2++;}}p=p-next;}coutLRU调度算法缺页次数缺页率命中率endl;coutcount2setw(24)double(count2)/MAX_LENGTHsetw(10)1-double(count2)/MAX_LENGTHendl;}#endifLRU_HOPT调度算法opt.h#ifndefOPT_H#defineOPT_H#includevectorusingnamespacestd;intsearch(structproduce*place,intposition);voidopt(structproduce*first,intMaxpage){structproduce*p=first-next;vectorvectorintpage3(Maxpage,vectorint(2));intcount1=0;//定义内存已被使用的页数intcount2=0;//定义缺页次数intcurrent=0;//定义当