模拟请求页式管理

1、目 录一、设计目的1二、设计内容1三、设计原理2四、算法实现4五、流程图5六、源程序6七、运行示例及结果分析14八、心得体会16九、参考资料16模拟请求页式管理一、设计目的1.通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点。2.通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和是实验过程的理解。3.掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、设计内容通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 50% 的指令是顺序执行的； 25% 的指令是均匀分布在前地址部分； 25

2、% 的指令是均匀分布在后地址部分。具体的实施方法是：在 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)；第

3、 10 条 第 19 条指令为第 1 页 ( 对应虚存地址为 10,19 ) ；第 310 条 第 319 条指令为第 31 页 ( 对应虚存地址为 310,319) 。按以上方式，用户指令可组成 32 页。计算并输出下述各种算法在不同内存容量下的命中率。先进先出的算法 (FIFO)；最近最久未使用算法 (LRU)；最佳访问算法（OPT）；三、设计原理 FIFO页面置换算法原理简述在分配内存页面数(AP)小于进程页面数(PP)时，当然是最先运行的AP个页面放入内存。这时有需要处理新的页面，则将原来内存中的AP个页面最先进入的调出(是以称为FIFO)，然后将新页面放入。以后如果再有新页面需要调入

4、，则都按的规则进行。算法特点：所使用的内存页面构成一个队列。 LRU页面置换算法原理算述当分配内存页面数(AP)小于进程页面数(PP)时，当然是把最先执行的AP个页面放入内存。当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那个页面调出，以空出内存来放置新调入的页面(称为LRU)。算法特点：每个页面都有属性来表示有多长时间未被CPU使用的信息。LRU算法的硬件支持把LRU算法作为页面置换算法是比较好的，它对于各种类型的程序都能适用，但实现起来有相当大的难度，因为它要求系统具有较多的支持硬件。所要解决的问题有：1.一个进程在内存中的各个页面各有多久时间未被进程

5、访问；2.如何快速地知道哪一页最近最久未使用的页面。为此，须利用以下两类支持硬件：（1）寄存器用于记录某进程在内存中各页的使用情况。实页/RR7R6R5R4R3R2R1R0101010010210101100300O001004011010115110101106001 01011700000111801101101（2）栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。四、算法实现A.命中率=1-页面失效次数/页地址流长度 B.本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数

6、。 C.关于随机数产生方法，采用TC系统提供函数RAND()和RANDOMIZE()来产生。const int MaxNum=320;/指令数const int M=5;/内存容量int PageOrderMaxNum;/页面请求int SimulateMaxNumM;/页面访问过程int PageCountM,LackNum;/PageCount用来记录LRU算法中最久未使用时间，LackNum记录缺页数float PageRate;/命中率; PageRate=1-(float)LackNum/(float)MaxNum);/计算命中率int n=rand()%320;/随机数产生320次

7、页面请求PageOrderk=n/10;/根据指令产生320次页面请求五、流程图开 始生成地址流输入算法号S1S4形成地址页号用户内存空间msize=2Msize32 FIFO()LRU()OPT()Msize加1S=? 是否用其他算法继续结 束NY123YN提示出错，重新输入六、源程序# include<iostream># include<time.h>using namespace std;const int MaxNum=320;/指令数const int M=5;/内存容量int PageOrderMaxNum;/页面请求int SimulateMaxNumM

8、;/页面访问过程int PageCountM,LackNum;/PageCount用来记录LRU算法中最久未使用时间，LackNum记录缺页数int PageCountOPTM;/PageCountOPT用来记录OPT算法中最久未使用时间float PageRate;/命中率int PageCount132;bool IsExit(int i)/FIFO算法中判断新的页面请求是否在内存中bool f=false;for(int j=0;j<M;j+)if(Simulatei-1j=PageOrderi)/在前一次页面请求过程中寻找是否存在新的页面请求f=true;return f;int

9、 IsExitLRU(int i)/LRU算法中判断新的页面请求是否在内存中int f=-1;for(int j=0;j<M;j+)if(Simulatei-1j=PageOrderi)f=j;return f;int Compare()/LRU算法找出内存中需要置换出来的页面int p,q;p=PageCount0;q=0;for(int i=1;i<M;i+)if (p<PageCounti)p=PageCounti;q=i;return q;int CompareOPT(int i)/OPT算法找出内存中需要置换出来的页面int temp5;for(int a=0;a&

10、lt;5;a+)tempa=0;for(int j=0;j<M;j+)for(int ii=i+1;ii<MaxNum;ii+)if(Simulatei-1j!=PageOrderii)tempj+;elsebreak;int max=temp0;int maxIndex=0;for(int i1=1;i1<M;i1+)if(max<tempi1)max=tempi1;maxIndex=i1;return maxIndex;void Init()/初始化页框for(int k=0;k<MaxNum;k+)int n=rand()%320;/随机数产生320次页面请

11、求PageOrderk=n/10;/根据指令产生320次页面请求for(int i=0;i<MaxNum;i+)/初始化页面访问过程for(int j=0;j<M;j+)Simulateij=-1;for (int q=0;q<M;q+)/初始化最久未使用数组PageCountq=0;PageCountOPTq=0;void AllNum()int j;cout<<"页面访问序列："<<endl;for(j=0;j<MaxNum;j+)cout<<PageOrderj<<" "voi

12、d OutPut()/输出int i,j;cout<<endl;cout<<"页面访问过程（只显示前十个）："<<endl;for(i=0;i<10;i+)for(j=0;j<M;j+)if(Simulateij=-1)cout<<" "elsecout<<Simulateij<<" "cout<<endl;cout<<"缺页率= "<<LackNum<<endl;cout<&l

13、t;"命中率= "<<PageRate<<endl;cout<<"-"<<endl;void FIFO()/FIFO算法int j,x=0,y=0;LackNum=0;Init();/初始化for(j=0;j<M;j+)/将前五个页面请求直接放入内存中for(int k=0;k<=j;k+)if(j=k)Simulatejk=PageOrderj;elseSimulatejk=Simulatej-1k;LackNum+;for(x=M;x<MaxNum;x+)for(int t=1;t&l

14、t;M;t+)Simulatext=Simulatex-1t;if(!IsExit(x)/根据新访问页面是否存在内存中来更新页面访问过程LackNum+;Simulatexy%M=PageOrderx;y+;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率AllNum();OutPut();void LRU()/LRU算法int j,x=0,y=0;LackNum=0;Init();for(j=0;j<M;j+)/将前五个页面请求直接放入内存中for(int k=0;k<=j;k+)PageCountk+;if(j=k)Simulate

15、jk=PageOrderj;elseSimulatejk=Simulatej-1k;LackNum+;for(x=M;x<MaxNum;x+)for(int t=0;t<M;t+)/先将前一次页面访问过程赋值给新的页面访问过程Simulatext=Simulatex-1t;int p=IsExitLRU(x);if(p=-1)/根据返回的p值来更新页面访问过程int k;k=Compare();for(int w=0;w<M;w+)if(w!=k)PageCountw+;elsePageCountk=1;Simulatexk=PageOrderx;LackNum+;elsef

16、or(int w=0;w<M;w+)if(w!=p)PageCountw+;elsePageCountp=1;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率AllNum();OutPut();void OPT()/最佳访问算法Optimalint j,x=0,y=0;LackNum=0;Init();for(j=0;j<M;j+)/将前五个页面请求直接放入内存中for(int k=0;k<=j;k+)PageCountOPTk+; if(j=k)Simulatejk=PageOrderj;elseSimulatejk=Simul

17、atej-1k;LackNum+;AllNum();for(x=M;x<MaxNum;x+)for(int t=0;t<M;t+)/先将前一次页面访问过程赋值给新的页面访问过程Simulatext=Simulatex-1t;int p=IsExitLRU(x);/OPT算法中判断新的页面请求是否在内存中if(p=-1)/根据返回的p值来更新页面访问过程int k;k=CompareOPT(x);/OPT算法找出内存中需要置换出来的页面for(int w=0;w<M;w+)if(w!=k)PageCountOPTw+;elsePageCountOPTk=1;Simulatexk

18、=PageOrderx;LackNum+;elsefor(int w=0;w<M;w+)if(w!=p)PageCountOPTw+;elsePageCountOPTp=1;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率OutPut();void YourChoice(int choice)switch(choice)case 1:cout<<"-"<<endl;cout<<"FIFO算法结果如下："<<endl;FIFO();break;case 2:

19、cout<<"-"<<endl;cout<<"LRU算法结果如下："<<endl;LRU();break;case 3:cout<<"-"<<endl;cout<<"OPT算法结果如下："<<endl;OPT();break;case 4:break;default:cout<<"重新选择算法：1-FIFO 2-LRU 3-OPT 4-退出"<<endl;cin>>choice;YourChoice(choice);void main()int choice,i=1;while(i)cout<<"请选择算法：1-FIFO 2-LRU 3-OPT 4-退出"<<endl;cin>>choice;if(choice=1|choice=2|choice=3|choice=4)YourCh