頁面置換算法的模擬實現(xiàn)及命中率對比實驗報告一、問題描述課程設(shè)計目的（1）、通過請求頁式管理方式中頁面置換算法的模擬設(shè)計，了解虛擬存儲術(shù)的特點，掌握請求頁式存儲管理中的頁面置換算法。（2）、課程設(shè)計內(nèi)容模擬實現(xiàn)OPT（最佳置換）、FIFO和LRU算法，并計算命中率。、課程設(shè)計要求：首先用隨機數(shù)生成函數(shù)產(chǎn)生“指令”序列，然后將指令序列變換成相應的頁地址流，再計算不同算法下的命中率。通過隨機數(shù)產(chǎn)生一個指令序列，共產(chǎn)生400條。其中50%的指令是順序執(zhí)行的（靈位50%就是非順序），且25%的指令分布在前半部分地址空間，25%的指令分布在后半部分地址空間。將指令地址流變換成頁地址流循環(huán)運行，使用戶內(nèi)存容量從4到40,。計算每個內(nèi)存容量下不同頁面置換算法的命中率。二、概要設(shè)計1.程序的數(shù)據(jù)結(jié)構(gòu)：#definetotal_instruction100/*指令流長*/#defineM100/*實際頁數(shù)*/#defineN5//可用頁面數(shù)structPro{intnum,time;};inta[total_instruction];intpage[N];2.程序的主函數(shù)：intmain(){Prop[total_instruction];Pro*page=newPro[N];charc;intt=0,i;floatn=0;Input(p);do{for(i=0;i<N;i++)//初試化頁面基本情況{page[i].num=-1;page[i].time=2-i;}printf("系統(tǒng)產(chǎn)生的隨機數(shù)為：");for(inte=0;e<M;e++)cout<<p[e].num<<"";cout<<endl;i=0;cout<<"f:FIFO頁面置換"<<endl;cout<<"l:LRU頁面置換"<<endl;cout<<"o:OPT頁面置換"<<endl;cout<<"按其它鍵結(jié)束"<<endl;cin>>c;if(c=='f')//FIFO頁面置換{n=0;cout<<"頁面置換情況:"<<endl;while(i<total_instruction){if(Search(p[i].num,page)>=0)i++;//找到相同的頁面else{if(t==N)t=0;else{n++;//page[t].num=p[i].num;print(page);t++;}}}cout<<"缺頁次數(shù)："<<n<<"命中率："<<1-n/total_instruction<<endl;}if(c=='l')//LRU頁面置換{n=0;cout<<"頁面置換情況:"<<endl;while(i<total_instruction){intk;k=t=Search(p[i].num,page);if(t>=0)page[t].time=0;else{n++;t=Max(page);page[t].num=p[i].num;page[t].time=0;}for(intj=0;j<N;j++){if(j!=t)page[j].time++;}/*if(t==0){page[t+1].time++;page[t+2].time++;}if(t==1){page[2].time++;page[0].time++;}if(t==2){page[1].time++;page[0].time++;}*/if(k==-1)print(page);i++;}cout<<"缺頁次數(shù)："<<n<<"命中率："<<1-n/total_instruction<<endl;}if(c=='o')//OPT頁面置換{n=0;while(i<total_instruction){if(Search(p[i].num,page)>=0)i++;else{if(page[N-1].num==-1){for(intg=0;g<N;g++)if(page[g].num==-1){page[g].num=p[i].num;i++;n++;print(page);break;}}else{inttemp=-1,cn;for(t=0;t<N;t++){if(temp<Compfu(page,i,t,p)){temp=Compfu(page,i,t,p);cn=t;}}page[cn]=p[i];n++;print(page);i++;}}}cout<<"缺頁次數(shù)："<<n<<"命中率："<<1-n/total_instruction<<endl;}}while(c=='f'||c=='l'||c=='o');return0;}三、詳細設(shè)計程序代碼如下：#include<stdlib.h>#include<iostream>#include<time.h>#include<stdio.h>usingnamespacestd;#definetotal_instruction100/*指令流長*/#defineM100/*實際頁數(shù)*/#defineN5//可用頁面數(shù)structPro{intnum,time;};inta[total_instruction];intpage[N];voidInput(Prop[total_instruction]){intm,i,m1,m2;srand((unsignedint)time(NULL));m=rand()%400;//for(i=0;i<total_instruction;)/*產(chǎn)生指令隊列*/{if(m<0||m>399){printf("Wheni==%d,Error,m==%d\n",i,m);exit(0);}a[i]=m;/*任選一指令訪問點m*/a[i+1]=a[i]+1;a[i+2]=a[i]+2;/*順序執(zhí)行兩條指令*/intm1=rand()%m;/*執(zhí)行前地址指令m1*/a[i+3]=m1;a[i+4]=m1+1;a[i+5]=m1+2;/*順序執(zhí)行兩條指令*///s=(158-a[i+5])*rand()/32767/32767/2+a[i+5]+2;m2=rand()%(157-m1)+m1+3;a[i+6]=m2;if((m2+2)>159){a[i+7]=m2+1;i+=8;}else{a[i+7]=m2+1;a[i+8]=m2+2;i=i+9;}m=rand()%m2;}for(i=0;i<total_instruction;i++)/*將指令序列變換成頁地址流*/{p[i].num=a[i]/10;p[i].time=0;}}voidprint(Pro*page1)//打印當前的頁面{Pro*page=newPro[N];page=page1;for(inti=0;i<N;i++)printf("%-4d",page[i].num);//cout<<page[i].num<<"";cout<<endl;//free(page);}intSearch(inte,Pro*page1){Pro*page=newPro[N];page=page1;for(inti=0;i<N;i++)if(e==page[i].num)returni;return-1;}intMax(Pro*page1){Pro*page=newPro[N];page=page1;inte=page[0].time,i=0;while(i<N)//找出離現(xiàn)在時間最長的頁面{if(e<page[i].time)e=page[i].time;i++;}for(i=0;i<N;i++)if(e==page[i].time)returni;return-1;}intCompfu(Pro*page1,inti,intt,Prop[M]){Pro*page=newPro[N];page=page1;intcount=0;for(intj=i;j<M;j++){if(page[t].num==p[j].num)break;elsecount++;}returncount;}intmain(){Prop[total_instruction];Pro*page=newPro[N];charc;intt=0,i;floatn=0;Input(p);do{for(i=0;i<N;i++)//初試化頁面基本情況{page[i].num=-1;page[i].time=2-i;}printf("系統(tǒng)產(chǎn)生的隨機數(shù)為：");for(inte=0;e<M;e++)cout<<p[e].num<<"";cout<<endl;i=0;cout<<"f:FIFO頁面置換"<<endl;cout<<"l:LRU頁面置換"<<endl;cout<<"o:OPT頁面置換"<<endl;cout<<"按其它鍵結(jié)束"<<endl;cin>>c;if(c=='f')//FIFO頁面置換{n=0;cout<<"頁面置換情況:"<<endl;while(i<total_instruction){if(Search(p[i].num,page)>=0)i++;//找到相同的頁面else{if(t==N)t=0;else{n++;//page[t].num=p[i].num;print(page);t++;}}}cout<<"缺頁次數(shù)："<<n<<"命中率："<<1-n/total_instruction<<endl”}if(c=='l')//LRU頁面置換{n=0;cout<<"頁面置換情況:"<<endl;while(i<total_instruction){intk;k=t=Search(p[i].num,page);if(t>=0)page[t].time=0;else{n++;t=Max(page);page[t].num=p[i].num;page[t].time=0;}for(intj=0;j<N;j++){if(j!=t)page[j].time++;}/*if(t==0){page[t+1].time++;page[t+2].time++;}if(t==1){page[2].time++;page[0].time++;}if(t==2){page[1].time++;page[0].time++;}*/if(k==-1)print(page);i++;}cout<<"缺頁次數(shù)："<<n<<"命中率："<<1-n/total_instruction<<endl;}if(c=='o')//OPT頁面置換{n=0;while(i<total_instruction){if(Search(p[i].num,page)>=0)i++;else{if(page[N-1].num==-1){for(intg=0;g<N;g++)if(page[g].num==-1){page[g].num=p[i].num;i++;n++;print(page);break;}}else{inttemp=-1,cn;for(t=0;t<N;t++){if(temp<Compfu(page,i,t,p)){temp=Compfu(page,i,t,p);cn=t;}}page[cn]=p[i];n++;prin