华南师范大学操作系统实验

院 系：计 算 机 学 院实验课程：操作系统实验项目： 摸拟操作系统的页面置换指导老师：陈红英 开课时间：2013 2014年度第 2学期专 业：嵌入式班 级：2012级学 生：李聪学 号：模拟操作系统的页面置换一、 实验目的1. 掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理2. 掌握用随机数生成满足一定条件的指令地址流的方法3. 掌握页面置换的模拟方法二、 实验内容1、采用一种熟悉的语言，如C、PASCAL或C+等，编制程序，最好关键代码采用C/C+，界面设计可采用其它自己喜欢的语言。2、模拟操作系统采用OPT、FIFO和LRU算法进行页面置换的过程。3设程序中地址范围为0到32767，采用随机数生成256个指令地址，满足50%的地址是顺序执行，25%向前跳，25%向后跳。为满足上述条件，可采取下列方法：设d0=10000，第n个指令地址为dn，第n+1个指令地址为dn+1，n的取值范围为0到255。每次生成一个1到1024范围内的随机数a，如果a落在1到512范围内，则dn+1=dn+1。如果a落在513到768范围内，则设置dn+1为1到dn范围内一个随机数。如果a落在769到1024范围内，则设置dn+1为dn到32767范围内一个随机数。例如：srand();初始化一个随机函数。a010*rand()/32767*255+1;a1=10*rand()/32767*a0语句可用来产生a0与a1中的随机数。或采用以下方式：（1） 通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：A：50%的指令是顺序执行的B：25%的指令是均匀分布在前地址部分C：25%的指令是均匀分布在后地址部分具体的实施方法是：A：在0，319的指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1的指令C：在前地址0,m+1中随机选取一条指令并执行，该指令的地址为mD：顺序执行一条指令，其地址为m+1E：在后地址m+2，319中随机选取一条指令并执行F：重复步骤A-E，直到320次指令（2） 将指令序列变换为页地址流设：页面大小为1K；用户内存容量4页到32页；用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条-第9条指令为第0页（对应虚存地址为0，9）第10条-第19条指令为第1页（对应虚存地址为10，19）第310条-第319条指令为第31页（对应虚存地址为310，319）按以上方式，用户指令可组成32页。4、页面大小的取值范围为1K，2K，4K，8K，16K。按照页面大小将指令地址转化为页号。对于相邻相同的页号，合并为一个三、 程序的主要流程图1. 利用随机数生成320条指令（数据）2. 将指令序列转变为页地址流3. 合并页地址流4. 使用FIFO算法算法开始检查页面是否已经存在于数组上中先进先出原则置换数组的内容否id=(id+1)%p输出数组parray的内容，输出缺页次数计算缺页率并输出算法结束是5. 使用OPT算法算法开始检查页面的内容是否已存于数组中找出数组c值最大的序号否利用displaytime数组，看出现时间来进行置换数组displaytime更新输出缺页次数计算缺页率并输出算法结束新建一个数组displaytime记录，表示多久没被调用是6. 使用LRU算法算法开始检查页面的内容是否已存于数组中找出parray数组最大的序号 否置换更新数组parray输出缺页次数计算缺页率并输出算法结束是7. 退出四、 主要程序清单#include#include#includeusing namespace std;#define MAX 320void randarray(int a) /生成指令序列int i;srand(unsigned)time(NULL);i=0;while(iMAX)ai=rand()%(MAX-1); /在0-319中取一个值i+;ai=ai-1+1; /取下一个i+;ai=rand()%ai-1; /取值介于0aii+;ai=ai-1+1; /取下一个i+;ai=rand()%(319-ai-1)+ai-1+1;/取ai-1+1-319里一个值，公式：rand()%a+b取值范围为(b,b+a-1)i+;void changad(int p,int a) /把指序列变为页面地址流for(int i=0;iMAX;i+)ai=ai/(p*10);void merge(int a)/合并int j,i=0;while(iMAX-1)if(ai=ai+1&ai!=-1)for(j=i;jMAX-1;j+) /合并 aj=aj+1; aMAX-1=-1; /合并之后剩出的空间补入1else i=i+1;void output(int a)for(int i=0;iMAX;i+)cout.setf(ios:left);cout.width(3);coutai ;coutendl;void output(int a,int x)/构造一个复合函数for(int i=0;ix;i+)cout.setf(ios:left);cout.width(3);coutai ;coutendl;bool search(int parray,int p,int x) /jude whether x is one of the number of parrayfor(int i=0;i=p;i+)if(parrayi=x)return true;return false;int maxarray(int p,int a)int max=0;int id=0;for(int i=0;imax)max=ai;id=i;return id;/返回的是最大值的下标int locate(int x,int p,int a)for(int i=0;ip;i+)if(x=ai)return i; return 0;double FIFO(int p,int a)int i,j,id=0;double lost=0,sum=0;double lostpecent;int *parray=new int p-1;/生成一个新数组保存页面大小for(i=0;ip;i+)parrayi=-1;for(i=0,j=0;i=MAX&ai!=-1;i+)+sum;if(ip) /装载进页面数组中if(!search(parray,p,ai) /判断是否缺页parrayj=ai;j+;+lost;elseif(!search(parray,p,ai) /判断是否缺页+lost;parrayid=ai;j+;id=(id+1)%p; /不能超过p-1output(parray,p);lostpecent=lost/sum;return lostpecent;double OPT(int p,int a)int i,j,id; /id用一个数组找出double lost=0,sum=0;double lostpecent;int *parray=new int p-1; /生成一个新数组保存页面大小for(i=0;ip;i+)parrayi=-1;int *displaytime=new int p-1; /统计内存中的数,下次出现是什么候for(i=0;ip;i+)displaytimei=0; /初始化for(i=0,j=0;i=MAX&ai!=-1;i+)+sum;if(ip) /当,用的内存小于用于存放数组的大小时if(!search(parray,p,ai)parrayj=ai;j+;+lost;else /当,用的内存大于用于存放数组的大小时if(!search(parray,p,ai) /判断是否缺页+lost;parrayid=ai;j+;for(int m=0;mp;m+) /找出下次出现的时间for(int n=i;n=MAX&an!=-1;n+)/parraym=MAX; /若以后再也找不到,则其为无限大if(parraym=an)displaytimem=n;break;id=maxarray(p,displaytime); /找出后面出现最久的一个,令其为IDoutput(parray,p);lostpecent=lost/sum;return lostpecent;double LRU(int p,int a)int i,j,loc,id,t=0; /id用一个数组找出double lost=0,sum=0;double lostpecent;int *parray=new int p-1; /生成一个新数组保存页面大小for(i=0;ip;i+)parrayi=-1;id=p-1; /令id为最后一个元素的下标for(i=0,j=0;i=MAX&ai!=-1;i+)+sum;if(ip+t) /当,用的内存小于用于存放数组的大小时if(!search(parray,p,ai)parrayp-j-1=ai;j+;+lost;else /没有缺页,但要更新parray里的数据,远近表loc=locate(ai,p,parray); /找出其位置for(int n=0;nloc;n+)parrayloc-n=parrayloc-n-1;parrayp+t-i=ai; /把其放在,上一个 /bugt+;else /当,用的内存大于用于存放数组的大小时if(!search(parray,p,ai) /判断是否缺页+lost; /有缺页,数组直接向后移一个单位for(int n=0;np;n+) /bugparrayp-n=parrayp-n-1;parray0=ai; /把其放到最近的位置else /没有缺页,但要更新parray里的数据,远近表loc=locate(ai,p,parray); /找出其位置for(int n=0;nloc;n+)parrayloc-n=parrayloc-n-1;parray0=ai; /把其放到最近的位置output(parray,p);lostpecent=lost/sum;return lostpecent;int main()int i;int p; /页面大小double lostpecent=0.0;int instructMAX; int merarraynum; /计录合并后数组个数randarray(instruct); /生成指令序列int choice;bool jugde=false;while(!jugde)coutn*menu*n;cout1.生成320条指令n;cout2.将指令序列转变为页地址流n;cout3.合并页地址流n;cout4.使用FIFO算法n;cout5.使用OPT算法n;cout6.使用LRU算法n;coutchoice;switch(choice)case 0:jugde=true;break;case 1:cout生成指令序列为：endl; output(instruct);break;case 2:cout请输入页面大小（k=1,2,4,8,16）:p; /input p p=16 changad(p,instruct); /指序列变为页面地址流cout其相对页号如下：endl;output(instruct);break;case 3:cout相邻页号合并后endl;merge(instruct); /合并地址流for(i=0;i=MAX&instructi!=-1;i+); /计算合并后的merarraynum=i;cout共merarraynum页endl;output(instruct,merarraynum); /输出合并后的地址流break;case 4:lostpecent=FIFO(p,instruct);cout使用FIFO算法缺页率为:lostpecentendl;break;case 5:lostpecent=OPT(p,instruct);cout使用OPT算法缺页率为:lostpecentendl;break;case 6:lostpecent=LRU(p,instruct);cout使用LRU算法缺页率为:lostpecentendl;break;default:coutthe input is error!nplease try again!endl;system(pause);return 0;五、 程序运行结果开始菜单生成对应的序列号序列号合并到一组上使用FIFO算法（因为生万的序列太长，所以在这也截太多图了） 使用OPT算法 使用LRU算法 如图：使用FIFO算法的缺页率为：0.5625使用OPT算法的缺