操作系统请求分页式管理(共18页)

1、精选优质文档-倾情为你奉上目录专心-专注-专业课程设计题目：请求页式管理模拟实现一、需求分析请求页式管理是一种常用的虚拟存储管理技术。本设计通过请求页式存储管理中页面置换算法模拟设计，了解虚拟 存储技术的特点，掌握请求页式管理的页面置换算法。 1.设计目的1、通过模拟实现请求分页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点。2、通过页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。3、掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 2.设计要求通过随机数产生一个指令序列，共320条指令。指令的地址按下述原

2、则生成： 50% 的指令是顺序执行的； 25% 的指令是均匀分布在前地址部分； 25% 的指令是均匀分布在后地址部分。具体的实施方法是：在 0,319 的指令地址之间随机选取一起点 m；顺序执行一条指令；在前地址0,m+1中随机选取一条指令并执行，该指令的地址为 m； 顺序执行一条指令，其地址为 m+1；在后地址 m+2,319 中随机选取一条指令并执行 ；重复上述步骤 ， 直到执行 320 次指令。将指令序列变换成为页地址流设：页面大小为 1K；用户内存容量为 4 页到 32 页 ；用户虚存容量为 32K 。在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的

3、存放方式为：第 0 条 第 9 条指令为第 0 页 ( 对应虚存地址为 0,9)；第 10 条 第 19 条指令为第 1 页 ( 对应虚存地址为 10,19 ) ；第 310 条 第 319 条指令为第 31 页 ( 对应虚存地址为 310,319) 。按以上方式，用户指令可组成 32 页。计算并输出下述各种算法在不同内存容量下的命中率。先进先出的算法 (FIFO)；最近最少使用算法 (LRR)；最少访问页面算法 (LFR)；最近最不经常使用算法 (NUR)。 3.解决方案（一）FIFO页面置换算法先用bool IsExit()函数判断请求页面是否在内存中，在内存中就直接运行，不在的话，就通过

4、Simulatexy%M算出先进来的页面，比如假如第6个数内存中没有，那置换时第6行第1列数一定是第一个进来的，我y的值这时候是6，然后y除以m取余，就是6除以5取余也就是1，然后将第一个置换出来，下面的就是重复上面的过程了。每次要置换时LackNum的值就会加1,最后输出页面的置换的过程，算出缺页率。（二）LRU页面置换算法先用int IsExitLRU()函数判断请求页面是否在内存中，在内存中就直接运行，不在的话，int Compare()算出需要置换的页面，这个功能的实现需要数组PageCount来实现。PageCount这个数组记录着内存里5个物理块使用情况，找出需要置换的页面的列数，

5、然后赋值给k，再通过Simulatexk=PageOrderx语句置换，每次要置换时LackNum的值就会加1,最后输出页面的置换的过程，算出缺页率。（三）OPT页面置换算法先用int IsExitOPT()函数判断请求页面是否在内存中，在内存中就直接运行，不在的话，int Compare()2算出需要置换的页面，我将请求数后面产生的的随机数一个一个和内存中的物理块的数比较，当相等的时候，记下相等的物理块号，再做第二个循环，第二个循环比较是除了第一个记录下来的数之外的4个数，相等的时候，再记下相等的物理块号，然后再做第三个循环.第四个做完后返回10减去刚刚找到的物理块号之和。这个就是要置换的数

6、的列号，然后置换，每次要置换时LackNum的值就会加1,最后输出页面的置换的过程，算出缺页率。 4实验提示提示：A.命中率=1-页面失效次数/页地址流长度B.本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。C.关于随机数产生方法，采用TC系统提供函数RAND()和RANDOMIZE()来产生。二、概要设计 1、结构说明（一）FIFO页面置换算法在分配内存页面数小于进程页面数时，当然是最先运行的页面放入内存。这时有需要处理新的页面，则将原来内存中的页面最先进入的调出(是以称为FIFO)，然后将新页面放入。以后如果再有新页面需要调入，则都按的规则

7、进行。（二）LRU页面置换算法当分配内存页面数小于进程页面数时，当然是把最先执行的页面放入内存。当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那个页面调出，以空出内存来放置新调入的页面(称为LRU)。以后如果再有新页面需要调入，则都按的规则进行。（三）OPT页面置换算法当分配内存页面数小于进程页面数时，当然是把最先执行的页面放入内存。当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最近时间不会用到的那个页面调出，以空出内存来放置新调入的页面(称为OPT)。以后如果再有新页面需要调入，则都按的规则进行 2、数据结构及模块说明定义的变量:co

8、nst int MaxNum=320;/指令数const int M=5;/内存容量int PageOrderMaxNum;/页面请求int SimulateMaxNumM;/页面访问过程int PageCountM,LackNum;/PageCount用来记录LRU算法中最久未使用时间,LackNum记录缺页数float PageRate;/命中率函数说明：bool IsExit(int i) /FIFO算法中判断新的页面请求是否在内存中int IsExitLRU(int i) /LRU算法中判断新的页面请求是否在内存中int Compare() /LRU算法找出内存中需要置换出来的页面in

9、t IsExitOPT(int i) /OPT算法中判断新的页面请求是否在内存中int Compare2(int i) /OPT算法找出内存中需要置换出来的页面void Init() /初始化页框void designBy() /给自己加的一个标题void OutPut() /输出void FIFO() /FIFO算法void LRU() /LRU算法void OPT() /OPT算法void YourChoice(int choice) /实现你选择哪个算法的功能 3、流程图NYNY开 始随机产生320个数 初始化页框 输入算法1=choice=4FIFO算法LRU算法OPT算法 退 出请求

10、页面是否在内存中页面置换继续运行输出运行结果，显示缺页率三、详细设计主要函数设计及说明：#include#includeusing namespace std;const int MaxNum=320;/指令数const int M=5;/内存容量int PageOrderMaxNum;/页面请求int SimulateMaxNumM;/页面访问过程int PageCountM,LackNum;/PageCount用来记录LRU算法中最久未使用时间,LackNum记录缺页数float PageRate;/命中率bool IsExit(int i)/FIFO算法中判断新的页面请求是否在内存中 b

11、ool f=false; for(int j=0;jM;j+) if(Simulatei-1j=PageOrderi)/在前一次页面请求过程中寻找是否存在新的页面请求 f=true; return f;int IsExitLRU(int i)/LRU算法中判断新的页面请求是否在内存中int f=-1; for(int j=0;jM;j+) if(Simulatei-1j=PageOrderi) f=j; return f;int Compare()/LRU算法找出内存中需要置换出来的页面int p,q;p=PageCount0;q=0; for(int i=1;iM;i+)if(pPageCo

12、unti)p=PageCounti;q=i;return q;int IsExitOPT(int i)/OPT算法中判断新的页面请求是否在内存中int h=-1; for(int j=0;jM;j+) if(Simulatei-1j=PageOrderi) h=j; return h;int Compare2(int i)/OPT算法找出内存中需要置换出来的页面int q,n,l,m,y,j;q=-1,n=-1,m=-1,l=-1,y=-1; for(int d=i;d320;d+)for(j=0;jM;j+)if(Simulatei-1j=PageOrderd)q=j;break;for(d

13、=i;d320;d+)for( j=0;jM;j+)if(j!=q)if(Simulatei-1j=PageOrderd)n=j;break; for(d=i;d320;d+)for( j=0;jM;j+)if(j!=q&j!=n)if(Simulatei-1j=PageOrderd)m=j;break;for(d=i;d320;d+)for( j=0;jM;j+)if(j!=q&j!=n&j!=m)if(Simulatei-1j=PageOrderd)l=j;break;return (10-q-n-m-l); 说明：将请求数后面产生的的随机数一个一个和内存中的物理块的数比较，当相等的时候，

14、记下相等的物理块号，再做第二个循环，第二个循环比较是除了第一个记录下来的数之外的4个数，相等的时候，再记下相等的物理块号，然后再做第三个循环.第四个做完后返回10减去刚刚找到的物理块号之和，这个就是要置换的数的列号。void Init() /初始化页框for(int k=0;kMaxNum;k+)int n=rand()%320;/随机数产生320次指令PageOrderk=n/10;/根据指令产生320次页面请求 for(int i=0;iMaxNum;i+)/初始化页面访问过程 for(int j=0;jM;j+) Simulateij=-1; for(int q=0;qM;q+)/初始化

15、最久未使用数组 PageCountq=0;void designBy()printf(n);printf( 课题四：页面置换算法 n);printf( 班 级：11计本2班 n);printf( 学 号： n);printf( 姓 名：周玉亭 n);printf(n);void OutPut()/输出int i,j;cout页面访问序列:endl;for(j=0;jMaxNum;j+)coutPageOrderj ;coutendl;cout页面访问过程:endl;for(i=0;i10;i+)for(j=0;jM;j+)if(Simulateij=-1)cout ;elsecoutSimul

16、ateij ;coutendl;coutendl;cout缺页数= LackNumendl;cout命中率= PageRateendl;cout-endl;说明：将FIFO算法、LRU算法、OPT算法的页面访问过程显示出来，并输出缺页数和命中率。void FIFO()/FIFO算法int j,x=0,y=0;LackNum=0,Init(); for(j=0;jM;j+)/将前五个页面请求直接放入内存中for(int k=0;k=j;k+)if(j=k)Simulatejk=PageOrderj;else Simulatejk=Simulatej-1k; LackNum+;for(x=M;xM

17、axNum;x+)for(int t=0;tM;t+)/先将前一次页面访问过程赋值给新的页面访问过程Simulatext=Simulatex-1t;if(!IsExit(x)/根据新访问页面是否存在内存中来更新页面访问过程LackNum+;Simulatexy%M=PageOrderx;y+;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率OutPut();说明：用Simulatexy%M算出需要置换页面，比如假如第6个数内存中没有，那置换时第6行第1列数一定是第一个进来的，我y的值这时候是6，然后y除以m取余，就是6除以5取余也就是1，然后将第一

18、个置换出来。void LRU()/LRU算法int j,x=0,y=0;LackNum=0,Init(); for(j=0;jM;j+)/将前五个页面请求直接放入内存中for(int k=0;k=j;k+)PageCountk+;if(j=k)Simulatejk=PageOrderj;else Simulatejk=Simulatej-1k; LackNum+; for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/先将前一次页面访问过程赋值给新的页面访问过程Simulatext=Simulatex-1t;int p=IsExitLRU(x);if(p=-1)/根据反回

19、的p值来更新页面访问过程int k;k=Compare();for(int w=0;wM;w+)if(w!=k)PageCountw+;elsePageCountk=1;Simulatexk=PageOrderx;LackNum+;elsefor(int w=0;wM;w+)if(w!=p)PageCountw+;elsePageCountp=1;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率OutPut();说明:先用一开始的五个页面放入内存中，然后判断下面要运行的页面是否在内存中，在内存中就直接运行，不在的话，int Compare()算出需

20、要置换的页面。PageCount这个数组记录着内存里5个物理块使用情况，找出需要置换的页面的列数，然后赋值给k，再通过Simulatexk=PageOrderx语句置换，每次要置换时LackNum的值就会加1。void OPT()/OPT算法int j,x=0,y=0;LackNum=0,Init(); for(j=0;jM;j+)/将前五个页面请求直接放入内存中for(int k=0;k=j;k+)/PageCountk+;if(j=k)Simulatejk=PageOrderj;else Simulatejk=Simulatej-1k; LackNum+; for(x=M;xMaxNum;

21、x+)for(int t=0;tM;t+)/先将前一次页面访问过程赋值给新的页面访问过程Simulatext=Simulatex-1t;int p=IsExitOPT(x);if(p=-1)/根据反回的p值来更新页面访问过程int k;k=Compare2(x);Simulatexk=PageOrderx;LackNum+;PageRate=1-(float)LackNum/(float)MaxNum);/算出命中率OutPut();说明：先用一开始的五个页面放入内存中，然后判断下面要运行的页面是否在内存中，在内存中就直接运行，不在的话，就将int Compare2()算出需要置换的页面的列数

22、，带入置换，每次要置换时LackNum的值就会加1,最后输出页面的置换的过程，算出缺页率。void YourChoice(int choice)switch(choice)case 1:cout-endl;coutFIFO算法结果如下：endl;FIFO();break;case 2:cout-endl;coutLRU算法结果如下：endl;LRU();break;case 3:cout-endl;coutOPT算法结果如下：endl; OPT();break;case 4:break;default:cout重新选择算法：1-FIFO 2-LRU 3-OPT 4-退出 choice;YourChoice(choice);void main()system(color 0E);designBy();int choice,i=1;while(i)cout请选择算法：1-FIFO 2-LRU 3-OPT 4-退出 choice;if