页面置换实习报告

1、实习报告-页面置换算法、设计目的：加深对请求页式存储管理实现原理的理解，掌握页面置换算法。、设计内容设计一个进程，可以实现用户可以为程序指定内存块数，自由设置程序的页面访 问顺序，还可以在 OPT FIFO和LRU算法自由选择一个，并能观看到页面置换过程。三、开发环境windows 环境，VC6.0 平台。四、分析设计内存空间的分配和回收均以页调入内存变可运行； 还支持请求一实验原理为提高内存利用率，提供了内外存进程对换机制; 为单位进行：一个进程只需将其中一部分（段或页） 调页的存储管理方式。发现其所在的页面不在内存，就当进程在进行中需要访问某部分程序和数据时，立即提出请求（向 CPU发出中

2、断），由系统将其所需页面调入内存。这种页面调入 方式叫做请求调页。当CPU接收到缺页中断信号，中断处理程序先保存现场， 分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时 内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则需按照某种置换算法从内存中选出一页准备换出，是否重新写盘由 页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要 访问数据的物理地址，再去访问内存数据。整个页面的调入程序对用户是透明的。下面把我所用到的页面置换算法：最佳置换算法（OPT）、先进先出页面置换算法（FIFO）、最近

3、最少使用页面置换算法（LRU）,并对这些原理进行描述：最佳置换算法（OPT）原理：选择淘汰的页面，将是以后永不使用的，或者是最长（未来）时间内不再被访问 的页面。采用最佳置换算法，通常课保证最低缺页率。先进先出页面置换算法（FIFO）原理:该算法总是先淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予 以淘汰。最近最少使用页面置换算法(LRU)原理：由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将 来”的近似。选择最近最久未使用的页面予以淘汰，该算法赋予每个页面一个访问 字段，用来记录一个页面自上次呗访问以来所经历的时间t，当必须淘汰一个页面时，选择现有页面中其

4、t最大的，即最近最少使用页面予以淘汰。二程序结构我的程序分为三部分：第一部分：键盘输入数据作为测试用例用for循环进行数据的连续输入第二部分：算法的实现算法的实现也分为三部分：1. 算法1-最佳置换算法(OPT)(1) .数据刚入栈，物理块数都为缺页数(2) .超过分配的物理块数，如果有与栈内的数据一致的称为命中数据，并把栈内数据打印出来：Print(Num)，并用一个m=1标记有命中数据(3) 超过分配的物理块数，如果没有与栈内的数据一致的数据，则调用fin ds pace ()函数，让栈内的数与后面的数进行比较，如果有相同的数就用Pos1j记下他们的标号i(j从0开始)，如果有一个没有命中

5、，则把此数换出去，而如果物理块都有命中，则比较Pos1j中那个数最大，+。把最大的数换出去，因为此时这个数是最长(未来)时间内不再被访问 的页面，并且缺页次数(4) 计算缺页率并打印出来2. 算法2-先进先出页面置换算法(FIFO):(1) .数据刚入栈，物理块数都为缺页数(2) .超过分配的物理块数，如果有与栈内的数据一致的称为命中数据，并把栈内数据打印出来：Print(Num)，并用一个m=1标记有命中数据(3) 超过分配的物理块数，如果没有与栈内的数据一致的数据，则把先进栈的+。数换出去，让栈内的数从第二数开始往前移，然后把刚入栈的数据放入 栈尾，打印出来，并且缺页次数(4) 计算缺页率

6、并打印出来-1 -3. 算法 3-(1).(2).最近最少使用页面置换算法 (LRU) : 数据刚入栈，物理块数都为缺页数 超过分配的物理块数，如果有与栈内的数据一致的称为命中数据，并把栈内数据打印出来：Print(Num)，并用一个m=1标记有命中数据(3) 超过分配的物理块数， 如果没有与栈内的数据一致的数据， 则把先进栈的数换出去，让栈内的数从第二数开始往前移，然后把刚入栈的数据放入 栈尾，打印出来，并且缺页次数(4) 计算缺页率并打印出来+。第三部分 : 程序的运行(1) . 输入进程物理块数(2) . 输入进程页面地址数(3) 输入进程页面地址流，即测试的数据(4) 把置换的结果、缺

7、页次数和缺页率打印到屏幕上V三一些全局数据的设置：先为物理块分配空间，然后在根据用户需求进行输入物理块的大小:#define pNum 100/ 全局变量而每种算法都要对缺页次数和缺页次数进行统计，为了方便用户使用和理解，也设 置一个全局变量：intqycs=0;/ 缺页次数float qyl;/ 缺页率 进程块赋初值，赋予一个空间，方便我们输入空间大小和查看页面置换的命中率与 缺页率char pblockpNum;四程序流程图:- 3 -五.运行示例及结果分析-9 -横着看栈，用-1标记数据没有入栈，此时表明有四个物理块(栈)t | -作者：去胡艺亨;5： 30*0717231悽S辅Ar比-

8、(B运出晴送择尸旦页配疋可序痛翳或选澤逾岀Hi楸貯:择那科算注韓请诜审f 说1F!岀:一 l-t作者.狂却主(1(afl、 (H3ee71?E38久I垂弔早往2222113 3 3吐n那:起为？675000： ! ： ：上好备点y兰-退岀揃入讲sa配他物理决数：4WWftLfeTJLSfeso： 7#选逢产生贝直走问呼貝的方貳(违円惑渤网退出、询 要迪坯吗TXjMnJnTruii 41 也 hty tu C4ittiiiu(二色也彎翦输萍屮窗“ i 1fi斗Pl乩.妲选搔那种异辛却 =- - -Hl作苦I張薊芒;iH-JB.B. Q银隹1旅g法-接進久未覆用畀怯-la 31选：2F I F 0

9、真法2&右利盟世娥喝 a/t -嗟咋显屜EE iR曲4務I 叢向 物址走 旳地面r 配10贡M 號主E 蘑-7 1 人入吟 输洞苗10 y gcii隆丄我选薛迪出汕呼送S选擇恥种舁法Y请世萍IP.选0逼出=(1-作者“的壬:CiI 1 C3 :袪算用，星未 1r岀久 5W晟 隹进歯 罠鷲也订HL n U?r 祛W-iz说匹欢數加 缺;瓦率为O显75 ft湘互醴無1|亍Jhn1 !fl学号：3070717230入严缶 720l 8选扌羊1或选佯0退出你想选择那种葬袪? ；!1!1i柞寺，张莉芸 退出学号，209 0717238 iiiiiL.= ! ! I i ! I 作若t张莉芸 学号I 30

10、9 0717238!搜盘輛入产生一_=_=_=_=退_出! 3瓦面走冋序碉的方式血择1或选F剌極出M就A聲分配的抑理块数： t入进程M面地1数烝溜过缈匸 错選堡产生匸二二二m 二Eess any key to continue六、心得与体会在这两周的计算机操作系统实习中，我学到了很多东西。不仅对LINUX的终端操作的了解加深了很多，不光是懂得指令的操作，而且明白了以前很多模糊的地方，比如对权限的访问那一部分，以前只知道用chmodg+w文件名；chmod o-r文件名这两条指令修改权限，却不知道-rw-rw-rw-是什么意思，通过这次实习，我明白了这是多级访问权限的意思，还有一些类似的指令也是

11、一样。这次老师还要我们看了fork.cp p 的代码，一开始，LINUX里面的代码太多了，找不到，后来用搜索的功能才把fork.cpP找到，发现它在，后来从老师给的资料才知道，fork的功能是复制进程里面的东西，对LINUX进程的创建、内容的复制有了更深层次的了解，包括如何调用线程，父进程和子进程等等。但是让我感触最深的还是对页面置换算法程序编写的过程。 一开始大家都只是懂 得原理，不是很懂得怎么实现，后来我们几个做页面置换的同学就在一起讨论怎么 实现题目要求的功能，最后我决定选择堆栈的方法进行页面置换。在进行 FIFO 和 LRU这两种置换方法的时候，思想很类似，就是发现物理块内的数没有命中

12、的时候， 把需要置换的数据移出栈外，让后面的数往前移，并把最新入栈的数据放到栈的最 后面，并以此类推。而OPT算法则不是这样的，刚入栈的时候与前面两种算法一样， 但是到后面的时候，在发现栈后第一个数据没有与栈内的数据一致即没有命中数据 的时候，则调用 findspace（） 函数，先用栈内的第一数分别与栈外面的数依次进行 比较，如果发现第一个一致的，则用数 POS1j （j 从 0 开始）记下那个数的位置， 并把标记数K2+,如果没有一致的，则把Pos1=0，再用相同的方法把第二个数分 别与后面的数进行比较。等栈内的数据比较完了以后，看是否有pos1j=0 的，如果有，则把此页换出，把栈外第一

13、个数换进来，如果有两个，则把离栈顶最近的数 换出，如果没有则比较所有 Pos1j 中数，把最大的数的那一页换出，因为此时 表明命中的数离栈最远，符合以后永不使用的，或者是最长（未来）时间内不再被 访问的页面的原理。而在此之后如栈的数还是用同样地方法进行比较，老师说这样 的话空间花费大，代码需要优化，这也是我要改进的地方。我发现我还有一个地方 不足的是我不是很会用界面来做实习，这也是我将来要努力的方向。这就是我这次实习的心得和体会。参考文献：1、汤子嬴 编：计算机操作系统，西安电子科技大学出版社2、陈智勇 编：计算机系统结构，西安电子科技大学出版社附录、源程序清单/*页面置换算法性能测试要求：1

14、用户可以为程序指定内存块数 2用户可以自由设置程序的页面访问顺序 3.用户可在 OPT、FIFO 和 LRU 算法选择一个 ,并能观看到页面置换过程。*/#include#include#include#include#include#include#define pNum 100/ 系统为进程分配物理空间intqycs=0;/ 缺页次数char pblockpNum;/ 进程块赋初值，方便我们看页面置换的命中率与缺页率float qyl;/ 缺页率void jpsr(intymNum,char p)/ 由键盘输入 n 个整数放到 p 数组里面int i;for(i=0;iymNum;i+)s

15、canf(%d,&pi);void Print(intNum)/ 打印进程块的内容int i;for(i=0;iNum;i+)printf(%3d ,pblocki);printf(n);intfindsPace(intm,charym,intNum,intymNum)/ 为最佳置换算法 (OPtimal) 寻找该置换的物理块号inti,j,k=0,k2=0,pos1100,pos2,pos=0;for(j=0;jNum;j+)/地址序列第 M 位后与 Num 块物理块中的每一块最近匹配的序列位置i存入pos1数组中j=物理块号/k2 是个计数器如果 Num 块物理块中的某一块地址序列第 M位

16、后的元素不会发生命中Pos1该物理块号的值为零发生命中Pos1该物理块号=该数在序列里的位置for(i=m;iymNum;i+)if(ymi=pblockj)pos1j=i;k2+;break;else pos1j=0;- 11 -if(k2=Num)/取 pos1 数组的最大值舍去pos2=pos10;for(k=1;kNum;k+)if(pos2pos1k)pos=k;else pos2=pos1k;return pos;else /当分配的物理块中有在后续中不使用的， 可以直接舍去语句 pos1j=0; 的作用在for(pos=0;posNum;pos+)if(pos1pos=0) re

17、turn pos;void Optimal(char ym,intNum,intymNum)/ 最佳置换算法inti,j,m=0,p;for(j=0;jNum;j+)/ 数据刚入栈，都为缺页数pblockj=ymj;Print(Num);qycs+;for(j=Num;jymNum;j+)/ 超过分配的物理块数m=0;for(i=0;iNum;i+)if(ymj=pblocki)/ 如果有与栈内的数据一致的称为命中数据m=1;Print(Num);break;if(m=0)/ 没有与栈内的数据一致，缺页次数加 1p=findspace(j,ym,Num,ymNum);pblockp=ymj;P

18、rint(Num);qycs+;qyl=(float)qycs/ymNum;/ 计算缺页率|n);printf(|- 12 - 14 -printf(缺页率为 %fn,qyl);|n);printf(| void FIFO(char ym,intNum,intymNum)/ 先进先出算法inti,j,m=0;qycs=0;/ 防止多次选择时 qycs 会累加for(j=0;jNum;j+)/ 数据刚入栈，都为缺页数pblockj=ymj;Print(Num);qycs+;for(j=Num;jymNum;j+)/ 如果有与栈内的数据一致的称为命中数据m=0;for(i=0;iNum;i+)if

19、(ymj=pblocki)m=1;Print(Num);break;if(m=0)/ 没有与栈内的数据一致，缺页次数加 1for(i=0;iNum-1;i+) pblocki=pblocki+1;pblockNum-1=ymj;Print(Num);qycs+;qyl=(float)qycs/ymNum;|n);printf(|printf(缺页次数为 %dn,qycs);printf(缺页率为 %fn,qyl);|n);printf(| void LRU(char ym,intNum,intymNum)/ 最近最久未使用算法int c=0,i,j,m=0;qycs=0;for(j=0;jNu

20、m;j+)/ 数据刚入栈，都为缺页数pblockj=ymj; Print(Num);qycs+;for(j=Num;jymNum;j+)m=0;for(i=0;iNum;i+) if(ymj=pblocki)c=ymj;for(i+;iNum;i+)pblocki-1=pblocki;pblockNum-1=c;Print(Num);m=1;printf(n);if(m=0)for(i=0;iNum-1;i+)pblocki=pblocki+1;pblockNum-1=ymj;Print(Num);qycs+;qyl=(float)qycs/ymNum;printf(|printf(print

21、f(printf(|void display1()printf(|n);缺页次数为 %dn,qycs);缺页率为 %fn,qyl);|n);|n);作者：张莉芸学号： 3090717238 (1)最佳置换算法printf(| (2)先进先出算法printf(| (3)最近最久未使用算法printf(| (0)退出- 13 -printf(|n);|n);|n);|n);|n);|n);printf( void run() void display2(intselect,charym,intNum,intymNum);int select,s2,i,Num,ymNum;char ch;char ym20;for(Num=0;NumpNum;Num+)pblockNum=-1;/ 进程块赋初值，方便我们看页面置换的命中率与缺页率printf(nnnn);printf(- 14 -printf(作者：张莉芸学号： 3090717238|n);printf(1) 键盘输