页面置换实习报告

《页面置换实习报告》由会员分享，可在线阅读，更多相关《页面置换实习报告（16页珍藏版）》请在装配图网上搜索。

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

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

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

4、构我的程序分为三局部：第一局部:键盘输入数据作为测试用例用for循环进行数据的连续输入第二局部:算法的实现算法的实现也分为三局部：1. 算法1-最正确置换算法(OPT)(1). 数据刚入栈，物理块数都为缺页数(2). 超过分配的物理块数，如果有与栈内的数据一致的称为命中数据，并把栈内数据打印出来：Print(Num)，并用一个m=1标记有命中数据(3) 超过分配的物理块数，如果没有与栈内的数据一致的数据，那么调用findspace函数，让栈内的数与后面的数进行比拟，如果有相同的数就用pos1j记下他们的标号i(j从0开始)，如果有一个没有命中，那么把此数换出去，而如果物理块都有命中，那么比拟p

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

6、:(1). 数据刚入栈，物理块数都为缺页数(2). 超过分配的物理块数，如果有与栈内的数据一致的称为命中数据，并把栈内数据打印出来：Print(Num)，并用一个m=1标记有命中数据(3) 超过分配的物理块数，如果没有与栈内的数据一致的数据，那么把先进栈的数换出去，让栈内的数从第二数开始往前移，然后把刚入栈的数据放入栈尾，打印出来，并且缺页次数+。(4)计算缺页率并打印出来第三局部:程序的运行(1). 输入进程物理块数(2). 输入进程页面地址数(3) 输入进程页面地址流，即测试的数据(4)把置换的结果、缺页次数和缺页率打印到屏幕上三一些全局数据的设置：先为物理块分配空间，然后在根据用户需求进

7、行输入物理块的大小：#define pNum 100/全局变量而每种算法都要对缺页次数和缺页次数进行统计，为了方便用户使用和理解，也设置一个全局变量：int qycs=0;/缺页次数float qyl;/缺页率进程块赋初值，赋予一个空间，方便我们输入空间大小和查看页面置换的命中率与缺页率char pblockpNum; 四程序流程图：开始初始化开始键盘输入物理块数键盘输入页面流长度键盘输入所需数据选择算法算法2算法1算法3计算缺页次数计算缺页率选择0退出打印结果是否继续？Y退出 N五. 运行例如及结果分析横着看栈，用-1标记数据没有入栈,此时说明有四个物理块栈六、心得与体会 在这两周的计算机操

8、作系统实习中，我学到了很多东西。不仅对LINUX的终端操作的了解加深了很多，不光是懂得指令的操作，而且明白了以前很多模糊的地方，比方对权限的访问那一局部，以前只知道用chmod g+w 文件名；chmod o-r 文件名这两条指令修改权限，却不知道-rw-rw-rw-是什么意思，通过这次实习，我明白了这是多级访问权限的意思，还有一些类似的指令也是一样。这次老师还要我们看了fork.cpp的代码，一开始，LINUX里面的代码太多了，找不到，后来用搜索的功能才把fork.cpp找到，发现它在，后来从老师给的资料才知道，fork的功能是复制进程里面的东西，对LINUX进程的创立、内容的复制有了更深层

9、次的了解，包括如何调用线程，父进程和子进程等等。但是让我感触最深的还是对页面置换算法程序编写的过程。一开始大家都只是懂得原理，不是很懂得怎么实现，后来我们几个做页面置换的同学就在一起讨论怎么实现题目要求的功能，最后我决定选择堆栈的方法进行页面置换。在进行FIFO和LRU这两种置换方法的时候，思想很类似，就是发现物理块内的数没有命中的时候，把需要置换的数据移出栈外，让后面的数往前移，并把最新入栈的数据放到栈的最后面，并以此类推。而OPT算法那么不是这样的，刚入栈的时候与前面两种算法一样，但是到后面的时候，在发现栈后第一个数据没有与栈内的数据一致即没有命中数据的时候，那么调用findspace()

10、函数，先用栈内的第一数分别与栈外面的数依次进行比拟，如果发现第一个一致的，那么用数POS1jj从0开始记下那个数的位置，并把标记数K2+，如果没有一致的，那么把pos1=0，再用相同的方法把第二个数分别与后面的数进行比拟。等栈内的数据比拟完了以后，看是否有pos1j=0的，如果有，那么把此页换出，把栈外第一个数换进来，如果有两个，那么把离栈顶最近的数换出，如果没有那么比拟所有pos1j中数，把最大的数的那一页换出，因为此时说明命中的数离栈最远，符合以后永不使用的，或者是最长未来时间内不再被访问的页面的原理。而在此之后如栈的数还是用同样地方法进行比拟，老师说这样的话空间花费大，代码需要优化，这也

11、是我要改良的地方。我发现我还有一个地方缺乏的是我不是很会用界面来做实习，这也是我将来要努力的方向。 这就是我这次实习的心得和体会。参考文献：1、汤子嬴 编：?计算机操作系统?，西安电子科技大学出版社2、陈智勇 编：?计算机系统结构?，西安电子科技大学出版社附录、源程序清单/*页面置换算法性能测试 要求： 1用户可以为程序指定内存块数 2用户可以自由设置程序的页面访问顺序 3.用户可在OPT、FIFO和LRU算法选择一个,并能观看到页面置换过程。*/#include#include#include#include#include#include#define pNum 100/系统为进程分配物理

12、空间int qycs=0;/缺页次数char pblockpNum;/进程块赋初值，方便我们看页面置换的命中率与缺页率float qyl;/缺页率void jpsr(int ymNum,char p)/由键盘输入n个整数放到p数组里面int i;for(i=0;iymNum;i+)scanf(%d,&pi);void Print(int Num)/打印进程块的内容int i;for(i=0;iNum;i+) printf( %3d ,pblocki);printf(n);int findspace(int m,char ym,int Num,int ymNum)/为最正确置换算法(Optima

13、l)寻找该置换的物理块号int i,j,k=0,k2=0,pos1100,pos2,pos=0; for(j=0;jNum;j+) /地址序列第M位后与Num块物理块中的每一块最近匹配的序列位置i存入pos1数组中 j=物理块号 /k2是个计数器 如果Num块物理块中的某一块地址序列第M位后的元素不会发生命中 pos1该物理块号的值为零 /发生命中pos1该物理块号=该数在序列里的位置for(i=m;iymNum;i+)if(ymi=pblockj) pos1j=i;k2+;break; else pos1j=0;if(k2=Num) /取pos1数组的最大值舍去 pos2=pos10;for

14、(k=1;kNum;k+)if(pos2pos1k)pos=k;else pos2=pos1k;return pos;else /当分配的物理块中有在后续中不使用的，可以直接舍去 语句pos1j=0;的作用在此for(pos=0;posNum;pos+)if(pos1pos=0) return pos;void Optimal(char ym,int Num,int ymNum)/最正确置换算法int i,j,m=0,p; for(j=0;jNum;j+)/数据刚入栈，都为缺页数 pblockj=ymj;Print(Num);qycs+; for(j=Num;jymNum;j+)/超过分配的物

15、理块数 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;Print(Num); qycs+;qyl=(float)qycs/ymNum;/计算缺页率printf(|-|n);printf( 缺页次数为%dn,qycs);printf( 缺页率为%fn,qyl);printf(|-|n);void FIFO(char ym,int Num,int ymNum)/先

16、进先出算法int i,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(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=(flo

17、at)qycs/ymNum;printf(|-|n);printf( 缺页次数为%dn,qycs);printf( 缺页率为%fn,qyl);printf(|-|n);void LRU(char ym,int Num,int ymNum)/最近最久未使用算法int c=0,i,j,m=0;qycs=0;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) c=ymj;for(i+;iNum;i+)pblocki-1=p

18、blocki;pblockNum-1=c;Print(Num);m=1;printf(n);if(m=0)for(i=0;i- 张莉芸 学号：3090717238 - (1) 最正确置换算法 - (2) 先进先出算法 - (3) 最近最久未使用算法 - (0) 退出 -|n);void run()void display2(int select,char ym,int Num,int ymNum);int select,s2,i,Num,ymNum;char ch;char ym20;for(Num=0;Num- 张莉芸 学号：3090717238 - (1) 键盘输入产生 - (0) 退 出

19、 -|n); printf(nnnn);printf(输入进程分配的物理块数：);scanf(%d,&Num);printf(输入进程页面地址数(不能超过20)：);scanf(%d,&ymNum);printf(请选择产生页面走向序列的方式(选择1或选择0退出):);scanf(%d,&select);switch(select)case 1:jpsr(ymNum,ym);doprintf(n你想选择那种算法?(请选择14,选0退出):n);display1();printf(选:);scanf(%d,&s2);display2(s2,ym,Num,ymNum);for(i=0;ipNum;

20、i+)pblocki=0;coutch;while(ch=y);break;case 0:break;void display2(int select,char ym,int Num,int ymNum)switch(select)case 1:printf( *Optimal算法*n);Optimal(ym,Num,ymNum);break; case 2:printf( *F I F O算法*n);FIFO(ym,Num,ymNum);break; case 3:printf( *L R U算法*n);LRU(ym,Num,ymNum);break; case 0:run();break;void main()system(color 3f);/改变显示屏的颜色 system(mode con: cols=140 lines=90);run();/运行结果