面置换操作系统试验报告

1、实验二 页面置换算法实现一、实验目的（1）了解内存分页管理策略（ 2）掌握调页策略（ 3）掌握一般常用的调度算法 （4）学会各种存储分配算法的实现方法。（5）了解页面大小和内存实际容量对命中率的影响。二、实验内容采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响， 设计一个虚拟存储区和内 存工作区，并使用下述算法来模拟实现页面的置换：1. 先进先出的算法（ FIFO）2. 最近最久未使用算法（ LRU）3. 最佳置换算法（ OPT）实验分析 在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存， 但内存已无空闲时， 为

2、了保证该进程能够正常运行， 系统必须从内存中调出一页 程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定， 算法的好坏， 直接影响到系统的性能。 一个好的页面置换算法， 应该有较低的页 面更换频率。2.1 先进先出（ FIFO ）页面置换算法 当需要访问一个新的页面时， 首先查看物理块中是否就有这个页面， 若要查 看的页面物理块中就有， 则直接显示， 不需要替换页面； 如果要查看的页面物理 块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入； 若没有空闲物理块，则替换页面。并将物理块中所有页面 timer+ 。2.2最近久未使用（LRU）置换算法的思路最近久

3、未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进 行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问 以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进 行淘汰。2.3最佳（OPT置换算法的思路其所选择的被淘汰的页面，是以后不使用的，或者是在未来时间内不再被访 问的页面，采用最佳算法，通常可保证获得最低的缺页率。三、实验流程3.1系统功能图图3-1系统功能图3.2算法流程图1）先进先出（FIFO ）页面置换算法流程图开始R页熬度当前英面在内存中结束i 2丽七主斗討丽石丙存GY绪克图3-2先进先出页面置换算法流程图2)最近久未使用(LRU)置换

4、算法输出N国输岀当葡页囲输出缺页信息输出不訣页箍岀航页信息籀出不缺页迟打替抉图3-3最近久未使用置换算法流程图3）最佳（OPT ）置换算法图3-4最佳置换算法流程图四、源程序#i nclude<iostream.h>#i nclude <stdlib.h>#in elude <time.h>#i nclude <stdio.h>#define L 20 /页面长度最大为20int M; / 内存块struct Pro/定义一个结构体int num,time;Input(int m,Pro pL)/ 打印页面走向状态coutvv"请输入页

5、面长度(1020):"do cin>>m;if(m>20|m<10) cout<<endl;cout<<" 页面长度必须在 10 20 之间 "<<endl<<endl;cout<<" 请重新输入 L: "else break;while(1);int i,j;j=time(NULL);/ 取时钟时间srand(j);/ 以时钟时间 j 为种子，初始化随机数发生器cout<<endl;cout<<" 输出随机数 : "

6、<<endl;cout<<endl;for(i=0;i<m;i+)pi.num=rand( )%10;/ 产生 0 到 9 之间的随机数放到数组 p 中 pi.time=0;cout<<pi.num<<" "cout<<endl<<endl;return m;void print(Pro *page1)/ 打印当前的页面Pro *page=new ProM; page=page1;for(int i=0;i<M;i+)cout<<pagei.num<<" &

7、quot;cout<<endl;int Search(int e,Pro *page1 )/寻找内存块中与 e 相同的块号Pro *page=new ProM;page=page1;for(int i=0;i<M;i+)if(e=pagei.num)return i;/ 返回 i 值 return -1;int Max(Pro *page1)/ 寻找最近最长未使用的页面Pro *page=new ProM;page=page1;int e=page0.time,i=0;while(i<M) / 找出离现在时间最长的页面if(e<pagei.time) e=page

8、i.time;i+;找到离现在时间最长for( i=0;i<M;i+)if(e=pagei.time)return i;/ 的页面返回其块号return -1;int Count(Pro *page1,int i,int t,Pro pL)/ 记录当前内存块中页面离下次 使用间隔长度Pro *page=new ProM;page=page1;int count=0;for(int j=i;j<L;j+)if(paget.num=pj.num )break;/ 当前页面再次被访问时循环结束 else count+;/ 否则 count+1return count;/ 返回 count

9、 的值int main()int c;int m=0,t=0;float n=0;Pro pL;m=I nput(m,p); 调用in put函数，返回 m值coutvv"请输入分配的物理块 m(26):"cout<<endl<<endl;docin>>M;if(M>6|M<2) cout<<endl;cout«"物理块m必须在26之间"<<endl«endl; cout<<" 请重新输入 m： "else break;while(

10、1);Pro *page=new ProM;dofor(int i=0;i<M;i+)/ 初始化页面基本情况 pagei.num=0; pagei.time=m-1-i;i=0;cout<<endl;cout«"1:FIFO 页面置换2:LRU 页面置换"<<endl;cout«"3:OPT 页面置换 4:退出"<<endl;cout<<" 请选择页面置换算法： "<<endl;cin>>c;if(c=1)/FIFO 页面置换n=0;co

11、ut<<" FIFO 算法页面置换情况如下 : "<<endl; cout<<endl;while(i<m)if(Search(pi.num,page)>=0) / 当前页面在内存中cout<<pi.num<<" " / 输出当前页 pi.numcout<<" 不缺页 "<<endl;i+; /i 加 1else / 当前页不在内存中if(t=M)t=0;elsen+; / 缺页次数加 1paget.num=pi.num; /把当前页面放入

12、内存中cout<<pi.num<<" "print(page); / 打印当前页面t+; / 下一个内存块i+; / 指向下一个页面cout<<endl;cout<<" 缺页次数： "<<n<<" 缺页率： "<<n/m<<endl<<endl;if(c=2)/LRU 页面置换n=0;cout<<" LRU 算法页面置换情况如下 : "<<endl; cout<<endl;

13、while(i<m)int a;t=Search(pi.num,page);if(t>=0)/ 如果已在内存块中 paget.time=0;/ 把与它相同的内存块的时间置 0 for(a=0;a<M;a+)if(a!=t)pagea.time+;/ 其它的时间加 1 cout<<pi.num<<" "cout<<" 不缺页 "<<endl;else / 如果不在内存块中n+; / 缺页次数加 1t=Max(page); / 返回最近最久未使用的块号赋值给 t paget.num=pi.nu

14、m ; /进行替换paget.time=0; / 替换后时间置为 0 cout<<pi.num<<" "print(page);for(a=0;a<M;a+)if(a!=t) pagea.time+; /其它的时间加 1i+;cout<<endl;cout<<" 缺页次数： "<<n<<" 缺页率： "<<n/m<<endl<<endl;if(c=3)/OPT 页面置换n=0;cout<<" OPT

15、算法置换情况如下 :"<<endl;cout<<endl;while(i<m)if(Search(pi.num,page)>=0)/ 如果已在内存块中 cout<<pi.num<<" "cout<<" 不缺页 "<<endl;i+;else/ 如果不在内存块中int a=0;for(t=0;t<M;t+)if(paget.num=0)a+;/ 记录空的内存块数 if(a!=0) / 有空内存int q=M;for(t=0;t<M;t+)if(page

16、t.num=0&&q>t)q=t;/ 把空内存块中块号最小的找出来pageq.num=pi.num;n+; cout<<pi.num<<" " print(page);i+; else最久的页面int temp=0,s;for(t=0;t<M;t+)/ 寻找内存块中下次使用离现在if(temp<Count(page,i,t,p) temp=Count(page,i,t,p);s=t; / 把找到的块号赋给 spages.num=pi.num;n+;cout<<pi.num<<" &q

17、uot; print(page);i+;cout<<endl;cout<<" 缺页次数： "<<n<<" 缺页率： "<<n/m<<endl<<endl; if(c = 4) break;while(c=1|c=2|c=3);return 0;五、实验结果5.1 程序主界面运行程序后，将会提示用户输入页面长度，长度在10到20之间。当用户输 入长度（以12为例）后，系统将会显示随机数。系统提示用户输入分配的物理 块，用户输入数据（以3为例）。程序主界面运行图如图5-1所示

18、。请输入页面长度1020： 12输出随机数：请输入分配的物理块26?:图5-1程序主界面5.2先进先出（FIFO）页面置换算法运行结果选择算法1之后，进入算法1的操作。系统会显示算法的页面置换情况 先来先服务算法的运行图如图5-2所示。"FIFO页面真换 2：LRU页面置换 ©RPT页宙置拉心退出 字选择页面議算袪.F FIFO算法页面宜换情况如下：2 0 92 10不缺页2 159 159 8 &? e e6 E 06 106 13不缺页2 13晴页次数：l四缺帀率：0.833333图5-2先进先出页面置换算法运行结果图5.3最近久未使用（LRU）置换算法运行结果选择算法2之后，进入算法2的操作。系统会显示算法的页面置换情况最近久未使用的运行图如图5-3所示。1 z 卩2页面軍换 2 : LRU页面直换 22PT页面置桶 4：退岀请选择页面HW袪 刖算迭页面置换情況如下22 2 0 012 100不缺页5 5 109 5 9 08 S ? Sa a ? s6 9 6 910 6 13 3 6 1不缺页2 3 2 1朕页次数=10缺页率：0-833333图5-3最近久未