模拟请求页式管理

..目录TOC\o"1-1"\h\z一、设计目的1二、设计内容1三、设计原理2四、算法实现4五、流程图5六、源程序6七、运行示例及结果分析14八、心得体会16九、参考资料16..模拟请求页式管理一、设计目的1.通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点。2.通过对页面、页表、地址转换和页面置换过程的模拟,加深对请求调页系统的原理和是实验过程的理解。3.掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。二、设计内容通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分。具体的实施方法是：①在[0,319]的指令地址之间随机选取一起点m；②顺序执行一条指令；③在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m′；④顺序执行一条指令,其地址为m′+1；⑤在后地址[m′+2,319]中随机选取一条指令并执行；⑥重复上述步骤②~⑤,直到执行320次指令。将指令序列变换成为页地址流设：①页面大小为1K；②用户内存容量为4页到32页；③用户虚存容量为32K。在用户虚存中,按每K存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为：第0条~第9条指令为第0页<对应虚存地址为[0,9]>；第10条~第19条指令为第1页<对应虚存地址为[10,19]>；┇┇第310条~第319条指令为第31页<对应虚存地址为[310,319]>。按以上方式,用户指令可组成32页。计算并输出下述各种算法在不同内存容量下的命中率。先进先出的算法<FIFO>；最近最久未使用算法<LRU>；最佳访问算法〔OPT；三、设计原理㈠FIFO页面置换算法⑴原理简述①在分配内存页面数<AP>小于进程页面数<PP>时,当然是最先运行的AP个页面放入内存。②这时有需要处理新的页面,则将原来内存中的AP个页面最先进入的调出<是以称为FIFO>,然后将新页面放入。③以后如果再有新页面需要调入,则都按⑵的规则进行。算法特点：所使用的内存页面构成一个队列。㈡LRU页面置换算法⑴原理算述①当分配内存页面数<AP>小于进程页面数<PP>时,当然是把最先执行的AP个页面放入内存。②当需要调页面进入内存,而当前分配的内存页面全部不空闲时,选择将其中最长时间没有用到的那个页面调出,以空出内存来放置新调入的页面<称为LRU>。算法特点：每个页面都有属性来表示有多长时间未被CPU使用的信息。LRU算法的硬件支持把LRU算法作为页面置换算法是比较好的,它对于各种类型的程序都能适用,但实现起来有相当大的难度,因为它要求系统具有较多的支持硬件。所要解决的问题有： 1.一个进程在内存中的各个页面各有多久时间未被进程访问； 2.如何快速地知道哪一页最近最久未使用的页面。为此,须利用以下两类支持硬件：〔1寄存器用于记录某进程在内存中各页的使用情况。实页/RR7R6R5R4R3R2R1R0101010010210101100300O00100401101011511010110600101011700000111801101101〔2栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时,便将该页面的页面号从栈中移出,将它压入栈顶。四、算法实现A.命中率=1-页面失效次数/页地址流长度B.本实验中,页地址流长度为320,页面失效次数为每次访问相应指令时,该指令所对应的页不在内存的次数。C.关于随机数产生方法,采用TC系统提供函数RAND<>和RANDOMIZE<>来产生。constintMaxNum=320;//指令数constintM=5;//内存容量intPageOrder[MaxNum];//页面请求intSimulate[MaxNum][M];//页面访问过程intPageCount[M],LackNum;//PageCount用来记录LRU算法中最久未使用时间,LackNum记录缺页数floatPageRate;//命中率;PageRate=1-<<float>LackNum/<float>MaxNum>;//计算命中率intn=rand<>%320;//随机数产生320次页面请求 PageOrder[k]=n/10;//根据指令产生320次页面请求五、流程图开始开始生成地址流输入算法号S1≤S≤4形成地址页号用户内存空间msize=2Msize≤32FIFO<>LRU<>OPT<>Msize加1S=?是否用其他算法继续结束NY123YN提示出错,重新输入六、源程序#include<iostream>#include<time.h>usingnamespacestd;constintMaxNum=320;//指令数constintM=5;//内存容量intPageOrder[MaxNum];//页面请求intSimulate[MaxNum][M];//页面访问过程intPageCount[M],LackNum;//PageCount用来记录LRU算法中最久未使用时间,LackNum记录缺页数intPageCountOPT[M];//PageCountOPT用来记录OPT算法中最久未使用时间floatPageRate;//命中率intPageCount1[32];boolIsExit<inti>//FIFO算法中判断新的页面请求是否在内存中{ boolf=false; for<intj=0;j<M;j++> { if<Simulate[i-1][j]==PageOrder[i]>//在前一次页面请求过程中寻找是否存在新的页面请求 { f=true; } } returnf;}intIsExitLRU<inti>//LRU算法中判断新的页面请求是否在内存中{ intf=-1; for<intj=0;j<M;j++> { if<Simulate[i-1][j]==PageOrder[i]> { f=j; } } returnf;}intCompare<>//LRU算法找出内存中需要置换出来的页面{ intp,q; p=PageCount[0]; q=0; for<inti=1;i<M;i++> { if<p<PageCount[i]> { p=PageCount[i]; q=i; } } returnq;}intCompareOPT<inti>//OPT算法找出内存中需要置换出来的页面{ inttemp[5]; for<inta=0;a<5;a++> { temp[a]=0; } for<intj=0;j<M;j++> { for<intii=i+1;ii<MaxNum;ii++> { if<Simulate[i-1][j]!=PageOrder[ii]> { temp[j]++; } else{ break; } } } intmax=temp[0]; intmaxIndex=0; for<inti1=1;i1<M;i1++> { if<max<temp[i1]> { max=temp[i1]; maxIndex=i1; } } returnmaxIndex;}voidInit<>//初始化页框{ for<intk=0;k<MaxNum;k++> { intn=rand<>%320;//随机数产生320次页面请求 PageOrder[k]=n/10;//根据指令产生320次页面请求 } for<inti=0;i<MaxNum;i++>//初始化页面访问过程 { for<intj=0;j<M;j++> { Simulate[i][j]=-1; } } for<intq=0;q<M;q++>//初始化最久未使用数组 { PageCount[q]=0; PageCountOPT[q]=0; }}voidAllNum<>{ intj; cout<<"页面访问序列："<<endl; for<j=0;j<MaxNum;j++> { cout<<PageOrder[j]<<""; }}voidOutPut<>//输出{ inti,j; cout<<endl; cout<<"页面访问过程〔只显示前十个："<<endl; for<i=0;i<10;i++> { for<j=0;j<M;j++> { if<Simulate[i][j]==-1> cout<<""; else cout<<Simulate[i][j]<<""; } cout<<endl; } cout<<"缺页率="<<LackNum<<endl; cout<<"命中率="<<PageRate<<endl; cout<<""<<endl;}voidFIFO<>//FIFO算法{ intj,x=0,y=0; LackNum=0; Init<>; //初始化 for<j=0;j<M;j++>//将前五个页面请求直接放入内存中 { for<intk=0;k<=j;k++> { if<j==k> Simulate[j][k]=PageOrder[j]; else Simulate[j][k]=Simulate[j-1][k]; } LackNum++; } for<x=M;x<MaxNum;x++>{ for<intt=1;t<M;t++> { Simulate[x][t]=Simulate[x-1][t];} if<!IsExit<x>>//根据新访问页面是否存在内存中来更新页面访问过程{ LackNum++; Simulate[x][y%M]=PageOrder[x]; y++;} } PageRate=1-<<float>LackNum/<float>MaxNum>;//算出命中率 AllNum<>; OutPut<>;}voidLRU<>//LRU算法{ intj,x=0,y=0; LackNum=0; Init<>; for<j=0;j<M;j++>//将前五个页面请求直接放入内存中 { for<intk=0;k<=j;k++>{ PageCount[k]++; if<j==k> Simulate[j][k]=PageOrder[j]; else Simulate[j][k]=Simulate[j-1][k]; } LackNum++; } for<x=M;x<MaxNum;x++> { for<intt=0;t<M;t++>//先将前一次页面访问过程赋值给新的页面访问过程{ Simulate[x][t]=Simulate[x-1][t]; } intp=IsExitLRU<x>; if<p==-1>//根据返回的p值来更新页面访问过程 { intk; k=Compare<>; for<intw=0;w<M;w++>{ if<w!=k> PageCount[w]++; else PageCount[k]=1; } Simulate[x][k]=PageOrder[x]; LackNum++; } else { for<intw=0;w<M;w++> { if<w!=p> PageCount[w]++; else PageCount[p]=1; } } } PageRate=1-<<float>LackNum/<float>MaxNum>;//算出命中率 AllNum<>; OutPut<>;}voidOPT<>//最佳访问算法Optimal{ intj,x=0,y=0; LackNum=0; Init<>; for<j=0;j<M;j++>//将前五个页面请求直接放入内存中 { for<intk=0;k<=j;k++> { PageCountOPT[k]++; if<j==k> Simulate[j][k]=PageOrder[j]; else Simulate[j][k]=Simulate[j-1][k]; } LackNum++; } AllNum<>; for<x=M;x<MaxNum;x++> { for<intt=0;t<M;t++>//先将前一次页面访问过程赋值给新的页面访问过程{ Simulate[x][t]=Simulate[x-1][t]; } intp=IsExitLRU<x>;//OPT算法中判断新的页面请求是否在内存中 if<p==-1>//根据返回的p值来更新页面访问过程 { intk; k=CompareOPT<x>;//OPT算法找出内存中需要置换出来的页面 for<intw=0;w<M;w++>{ if<w!=k> PageCountOPT[w]++; else PageCountOPT[k]=1; } Simulate[x][k]=PageOrder[x]; LackNum++; } else { for<intw=0;w<M;w++> { if<w!=p> PageCountOPT[w]++; else PageCountOPT[p]=1; } } } PageRate=1-<<float>LackNum/<float>MaxNum>;//算出命中率 OutPut<>; }voidYourChoice<intchoice>{ switch<choice> { case1: cout<<""<<endl; cout<<"FIFO算法结果如下："<<endl; FIFO<>; break; case2: cout<<""<<endl; cout<<"LRU算法结果如下："<<endl; LRU<>; break; case3: cout<<""<<endl; cout<<"OPT算法结果如下："<<endl; OPT<>; break; case4: break; default: cout<<"重新选择算法：1--FIFO2--LRU3--OPT4--退出"<<endl; cin>>choice; YourChoice<choice>; }}voidmain<>{ intchoice,i=1; while<i> { cout<<"请选择算法：1--FIFO2--LRU3--OPT4--退出"<<en