操作系统实验4报告

桂林理工大学实验报告班级计算机11-1班学号3110717121姓名覃毅同组实验者实验名称存储管理日期2013年11月22日一、实验目的：通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。二、实验内容：1．通过随机数产生一个指令序列，共320条指令。其地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在(跳转到)前地址部分；③25%的指令是均匀分布在(跳转到)后地址部分；#具体的实施方法是：A.在[0，319]的指令地址之间随机选取一起点M;B.顺序执行一条指令，即执行地址为M+1的指令；C.在前地址[0，M+1]中随机选取一条指令(跳转到)并执行，该指令的地址为M’;D.顺序执行一条指令，其地址为M’+1；E.在后地址[M’+2，319]中随机选取一条指令(跳转到)并执行；F.重复A—E，直到执行320次指令。2．指令序列变换成页地址流设：（1）页面大小为1K；（2）用户内存容量为4页到32页；（3）用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条—第9条指令为第0页（对应虚存地址为[0，9]）；第10条—第19条指令为第1页（对应虚存地址为[10，19]）；。。。。。。。。。。。。。。。。。。。。。第310条—第319条指令为第31页（对应虚存地址为[310，319]）；按以上方式，用户指令可组成32页。3.计算并输出下述各种算法在不同内存容量下的命中率。A.FIFO先进先出的算法B.LRR最近最少使用算法C.OPT最佳淘汰算法（先淘汰最不常用的页地址）三、程序清单：#includestdio.h#includeiostream#includestdlib.h#includetime.husingnamespacestd;structaa{//代表一个物理页的节点intpage;//虚存页号intcount;//命中数,用于最佳淘汰算法aa*next;//指向下一物理页};intmain(){time_tt;srand(unsigned(time(&t)));//随机数发生器初始化inti,n,j,ii,m,answer,ffalse,count,fangfa,temp1,min,nn,mm;doublesum;aa*head,*tail,*temp,*table,*first,*ti;cinm;//从键盘输入物理页数coutfangfa:1-FIFO;2-LRU;3-OPTendl;coutMothed:;cinfangfa;//从键盘输入算法的代号ffalse=0;answer=0;/*建立物理内存链表*/table=new(aa);//新建一个代表页面的节点temp=table;table-page=-1;table-count=0;head=table;for(ii=2;ii=m;ii++)//构建m个节点的链表，表示m个物理页{table=new(aa);table-page=-1;table-count=0;temp-next=table;temp=table;if(ii==m)table-next=NULL;}tail=table;temp=head;first=head;/*生成地址流的每一个地址，计算逻辑页，根据各种算法淘汰页*/count=0;//用于生成地址流，0，1，2，3表示4种不同情况。i=0;while(i320)//构造320个地址的地址流{if(count==0){n=(rand()%320+1)%320;j=n/10;}//count=0表示，在[0，319]的指令地址之间随机选取一起点M，顺序执行一条指令(+1)，即获得M+1的指令地址；j为地址所在页号。if(count==1){n=rand()%(n+1);j=n/10;}//count=1表示，在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M';if(count==2){j=((n+1)%320)/10;}//顺序执行一条指令，其地址为M'+1；if(count==3){j=((rand()%(320-n-2))+n+2)/10;}//在后地址[M'+2，319]中随机选取一条指令并执行；table=head;temp=head;answer=0;min=400;if(fangfa==3){while(table!=NULL){if(table-page==j){answer=1;++(table-count);}//命中，命中数+1table=table-next;}if(answer!=1){table=head;while(table!=NULL){if(table-countmin)temp=table;min=table-count;table=table-next;}if(temp-page!=-1){++ffalse;temp-page=j;table=head;while(table){table-count=1;table=table-next;}}else{temp-page=j;++(temp-count);}}}//最近最少使用算法if(fangfa==2){while((table!=NULL)&&(fangfa==2)){if(table-page==j){answer=1;temp=table;}table=table-next;}if((fangfa==2)&&(answer==1)){temp1=temp-page;//temp1临时保存物理页中命中的逻辑页号while(temp-next!=NULL){temp-page=temp-next-page;//比命中页位置低的逻辑页号上移一个位置temp=temp-next;}tail-page=temp1;//命中的逻辑页放入最下面的物理页}if((answer!=1)&&(fangfa==2)){if(first-page!=-1)ffalse=ffalse+1;//未命中次数+1first-page=j;//淘汰最上面的物理页中的逻辑页号temp=head;while(temp-next!=NULL)//比命中页位置低的逻辑页号上移一个位置{temp-page=temp-next-page;temp=temp-next;}tail-page=j;//命中的逻辑页放入最下面的物理页}}table=head;while((table!=NULL)&&(fangfa==1)){if(table-page==j){answer=1;}table=table-next;}if((answer!=1)&&(fangfa==1)){if(first-page!=-1)ffalse=ffalse+1;first-page=j;if(first-next!=NULL)first=first-next;elsefirst=head;}++i;++count;if(count==4)count=0;}sum=1.0-ffalse/320.0;if(fangfa==1)coutFIFO:sumendl;if(fangfa==2)coutLRU:sumendl;if(fangfa==3)coutOPT:sumendl;for(ti=head;ti!=NULL;ti=ti-next)coutti-page;coutendl;return0;}四、运行结果：五、心得体会：进一步加深了对请求分页存储管理的理解，明白了同时也真正掌握了页面置换算法的具体实现原理！