操作系统请求分页式管理

1、目录一、需求分析 11. 设计目的 12. 设计要求 13. 解决方案 24实验提示 2二、概要设计 21、结构说明 22、数据结构及模块说明 33、流程图 4三、详细设计 4四调试分析 14五、总结 171、遇到的问题 172、不足 173、心得体会 17六、参考文献 18课程设计题目：请求页式管理模拟实现一、需求分析请求页式管理是一种常用的虚拟存储管理技术。 本设计通过请求页式存储管 理中页面置换算法模拟设计，了解虚拟 存储技术的特点，掌握请求页式管理的 页面置换算法。1. 设计目的1、通过模拟实现请求分页式存储管理的几种基本页面置换算法，了解虚拟 存储技术的特点。2、通过页面、页表、地址

2、转换和页面置换过程的模拟，加深对请求调页系 统的原理和实现过程的理解。3、掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和 实现过程，并比较它们的效率。2. 设计要求通过随机数产生一个指令序列， 共 320 条指令。指令的地址按下述原则生成： 50% 的指令是顺序执行的； 25% 的指令是均匀分布在前地址部分； 25% 的指令是均匀分布在后地址部分。 具体的实施方法是： 在 0,319 的指令地址之间随机选取一起点 m； 顺序执行一条指令； 在前地址0,m+1中随机选取一条指令并执行，该指令的地址为 m； 顺序执行一条指令，其地址为 m +1; 在后地址 m +2,319 中随机

3、选取一条指令并执行 ； 重复上述步骤 ， 直到执行 320 次指令。 将指令序列变换成为页地址流设：页面大小为1K; 用户内存容量为 4 页到 32 页 ； 用户虚存容量为 32K 。在用户虚存中， 按每 K 存放 10 条指令排列虚存地址， 即 320 条指令在虚 存中的存放方式为：第 0 条 第 9 条指令为第 0 页 （ 对应虚存地址为 0,9）；第 10 条 第 19 条指令为第 1 页 （ 对应虚存地址为 10,19 ）；第 310 条 第 319 条指令为第 31 页 （ 对应虚存地址为 310,319） 按以上方式，用户指令可组成 32 页。计算并输出下述各种算法在不同内存容量下

4、的命中率。先进先出的算法 （FIFO） ；最近最少使用算法 （LRR） ；操作系统-课程设计最少访问页面算法（LFR）;最近最不经常使用算法（NUR）。3. 解决方案（一）FIFO页面置换算法先用bool lsExit（）函数判断请求页面是否在内存中，在内存中就直接运行， 不在的话，就通过Simulatexy%M算出先进来的页面，比如假如第6个数内存中没有，那置换时第6行第1列数一定是第一个进来的，我y的值这时候是6, 然后y除以m取余，就是6除以5取余也就是1，然后将第一个置换出来，下面 的就是重复上面的过程了。每次要置换时LackNum的值就会加1,最后输出页面的置换的过程，算出缺页率。（

5、二）LRU页面置换算法先用int IsExitLRU（）函数判断请求页面是否在内存中，在内存中就直接运 行，不在的话，int Compare。算出需要置换的页面，这个功能的实现需要数组 PageCount来实现。PageCount这个数组记录着内存里5个物理块使用情况， 找出需要置换的页面的列数，然后赋值给 k，再通过 Simulatexk=PageOrderx语句置换，每次要置换时LackNum的值就会加1,最后输出页面的置换的过程，算出缺页率。（三）OP顶面置换算法先用int IsExitOPT（）函数判断请求页面是否在内存中，在内存中就直接运 行，不在的话，int Compare（）2

6、算出需要置换的页面，我将请求数后面产生的 的随机数一个一个和内存中的物理块的数比较，当相等的时候，记下相等的物理块号，再做第二个循环，第二个循环比较是除了第一个记录下来的数之外的4个数，相等的时候，再记下相等的物理块号，然后再做第三个循环 第四个做完后返回10减去刚刚找到的物理块号之和。这个就是要置换的数的列号，然后 置换，每次要置换时LackNum的值就会加1,最后输出页面的置换的过程，算出 缺页率。4 实验提示提示：A.命中率=1-页面失效次数/页地址流长度B. 本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时， 该指令所对应的页不在内存的次数。C. 关于随机数产生方法，采

7、用 TC系统提供函数RAND（和 RANDOMIZE来产 生。、概要设计1、结构说明（一）FIFO页面置换算法 在分配内存页面数小于进程页面数时，当然是最先运行的页面放入内存。 这时有需要处理新的页面，则将原来内存中的页面最先进入的调出（是以称为FIFO），然后将新页面放入。 以后如果再有新页面需要调入，则都按的规则进行。（二）LRU页面置换算法 当分配内存页面数小于进程页面数时，当然是把最先执行的页面放入内 存。操作系统-课程设计 当需要调页面进入内存，而当前分配的内存页面全部不空闲时， 选择将其中最长时间没有用到的那个页面调出，以空出内存来放置新调入的页面（称为LRU）。 以后如果再有新页

8、面需要调入，则都按的规则进行。（三）0P顶面置换算法 当分配内存页面数小于进程页面数时，当然是把最先执行的页面放入内 存。 当需要调页面进入内存，而当前分配的内存页面全部不空闲时， 选择将其中最近时间不会用到的那个页面调出，以空出内存来放置新调入的页面（称为OPT） 以后如果再有新页面需要调入，则都按的规则进行2、数据结构及模块说明定义的变量：const int MaxNum=320; 指令数const int M=5;内存容量int PageOrderMaxNum; 页面请求int SimulateMaxNumM;页面访问过程int PageCountM,LackNum;/PageCount

9、用来记录 LRU算法中最久未使用时间丄ackNu m记录缺页数float PageRate;/ 命中率函数说明：bool IsExit(i nt i)/FIFO在内存中int IsExitLRU(int i)/LRU在内存中int Compare。/LRUint lsExitOPT(i nt i)/OPT在内存中int Compare2(i nt i)/OPT贝面void Init()/void desig nBy()/void OutPut()/void FIFO()/FIFOvoid LRU()/LRUvoid OPT()/OPTvoid YourChoice(i nt choice) /

10、算法中判断新的页面请求是否算法中判断新的页面请求是否算法找出内存中需要置换出来的页面 算法中判断新的页面请求是否算法找出内存中需要置换出来的初始化页框给自己加的一个标题输出算法算法算法实现你选择哪个算法的功能操作系统-课程设计3、流程图三、详细设计主要函数设计及说明： #in clude #in clude using n amespace std;const int MaxNum=320;/ 指令数const int M=5;/ 内存容量int PageOrderMaxNum;/ 页面请求int SimulateMaxNumM;/ 页面访问过程int PageCountM,LackNum;/

11、PageCount 用来记录 LRU算法中最久未使用 时间丄ackNu m记录缺页数float PageRate;/ 命中率bool IsExit(int i)/FIFO 算法中判断新的页面请求是否在内存中bool 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

12、;return f;int Compare()/LRU 算法找出内存中需要置换出来的页面int p,q;p=PageCount0;q=0;for(int i=1;iM;i+)if(pPageCounti)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

13、,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=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

14、!=m)if(Simulatei-1j=PageOrderd)l=j;break;return (10-q-n-m-l);说明：将请求数后面产生的的随机数一个一个和内存中的物理块的数比较， 当相等的时候， 记下相等的物理块号， 再做第二个循环， 第二个循环比较是除了 第一个记录下来的数之外的 4 个数，相等的时候， 再记下相等的物理块号， 然后 再做第三个循环 . 第四个做完后返回 10 减去刚刚找到的物理块号之和， 这个就 是要置换的数的列号。void Init() / 初始化页框for(int k=0;kMaxNum;k+)int n=rand()%320;/ 随机数产生 320 次指令P

15、ageOrderk=n/10;/ 根据指令产生 320 次页面请求 for(int i=0;iMaxNum;i+)/ 初始化页面访问过程for(int j=0;jM;j+)Simulateij=-1;for(int q=0;qM;q+)/ 初始化最久未使用数组PageCountq=0;void designBy()printf( iin);prin tf(|课题四：页面置换算法n);prin tf(|班级：11计本 2 班n);printf( |学号： 20110303214n);printf( |姓名：周玉亭n);printf(n);void OutPut()/ 输出int i,j;cout

16、 页面访问序列 :endl; for(j=0;jMaxNum;j+)coutPageOrderj ;coutendl;cout 页面访问过程 :endl; for(i=0;i10;i+)for(j=0;jM;j+) if(Simulateij=-1) cout ;else coutSimulateij ;coutendl;coutendl;cout 缺页数= LackNumendl;cout 命中率= PageRateendl;coutendl;说明：将FIFO算法、LRU算法、OPT算法的页面访问过程显示出来，并输出 缺页数和命中率。void FIFO()/FIFO 算法int j,x=0,

17、y=0;LackNum=0,Init();for(j=0;jM;j+)/ 将前五个页面请求直接放入内存中for(int k=0;k=j;k+) if(j=k)Simulatejk=PageOrderj;elseSimulatejk=Simulatej-1k;LackNum+;for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/ 先将前一次页面访问过程赋值给新的页面 访问过程 Simulatext=Simulatex-1t;if(!IsExit(x)/ 根据新访问页面是否存在内存中来更新页面访问 过程LackNum+;Simulatexy%M=PageOrderx;y+;

18、PageRate=1-(float)LackNum/(float)MaxNum);/ 算出命中率 OutPut();说明：用 Simulatexy%M 算出需要置换页面，比如假如第 6 个数内存中 没有，那置换时第6行第1列数一定是第一个进来的，我y的值这时候是6,然 后y除以m取余，就是6除以5取余也就是1，然后将第一个置换出来。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=PageO

19、rderj;elseSimulatejk=Simulatej-1k;LackNum+;for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/ 先将前一次页面访问过程赋值给新的页面 访问过程Simulatext=Simulatex-1t;int p=IsExitLRU(x);if(p=-1)/ 根据反回的 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

20、;w+)if(w!=p)PageCountw+;elsePageCountp=1;PageRate=1-(float)LackNum/(float)MaxNum);/ 算出命中率 OutPut();说明: 先用一开始的五个页面放入内存中，然后判断下面要运行的页面是否 在内存中，在内存中就直接运行，不在的话， int Compare() 算出需要置换的页 面。 PageCount 这个数组记录着内存里 5个物理块使用情况，找出需要置换的 页面的列数，然后赋值给 k，再通过Simulatexk=PageOrderx 语句置换， 每次要置换时LackNum的值就会加1。void OPT()/OPT

21、算法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;elseSimulatejk=Simulatej-1k;LackNum+;for(x=M;xMaxNum;x+)for(int t=0;tM;t+)/ 先将前一次页面访问过程赋值给新的页面 访问过程Simulatext=Simulatex-1t;int p=IsExitOPT(x);if(p=-1)/ 根据反回的 p 值来更新页面访问过程int k

22、; k=Compare2(x); Simulatexk=PageOrderx; LackNum+;PageRate=1-(float)LackNum/(float)MaxNum);/ 算出命中率 OutPut(); 说明：先用一开始的五个页面放入内存中， 然后判断下面要运行的页面是否 在内存中，在内存中就直接运行，不在的话，就将 int Compare2() 算出需要置 换的页面的列数，带入置换，每次要置换时LackNum的值就会加1,最后输出页面的置换的过程，算出缺页率。void YourChoice(int choice) switch(choice) case 1:coutendl;co

23、utFIFO 算法结果如下： endl; FIFO();break;3-OPT 4- 退 出退出 endl;case 2:coutendl;coutLRU 算法结果如下： endl; LRU();break;case 3:coutendl;coutOPT 算法结果如下： endl; OPT();break;case 4: break;default:cout 重 新选择算 法： 1-FIFO 2-LRU choice; YourChoice(choice);void main()system(color 0E); designBy(); int choice,i=1;while(i)coutc

24、hoice;if(choice=4)i=0;else YourChoice(choice);四. 调试分析调试过程和调试结果 一开始运行出来的界面:页面置换算法 过计本2班 2011303214周玉亭请选择算法：1FIFO 2LRU 3OPT百-退岀F:3-Debug3.exe题选择FIFO算法运行的界面:操作系统-课程设计如下:情选择算法】1FIFO 2LRU 3OPT 4-退岀274 0,14375请选择算法：1FIFO 2LRU 3OPT 4-退岀1節中*F：-3Debug3-ex15 11 24 26 2 6 IB G24 24 12 21 Q S31 28G 7 21B14e it1

25、901i17 G3i3 12 9 9 11 1G 2022 3 7 15 21 30 121 631 3U22264 191962121291717 20 7 27 12 29 2119 21 15 19 30 2820 23G 118139 122314222B20152 2 30 30 23 9 4 2627 20 5 13 27 105 18 87 ZU83 S11号141121415142S 25 5 7 17 9 1S 2620 14 2B 17 Q B20 1823 2192322 2551712121919*2 14 12 8 28 26 6 31B 21 26 12 30 1922 824 1 :211Q27 724 16 311627 31 :!9 1J 27 1? 2? 21 2711 29 16 2? 31 287 2721 1624128 312?Ifi1 30