页面淘汰算法实验报告

1、操作系统实验报告课题：页面淘汰算法专 业：班 级：学 号：姓 名：一实验目的 错误！未定义书签。二实验要求 3三背景知识 3四总体设计 4五详细设计 错误！未定义书签。六运行结果分析 9七心得体会 13八参考文献14附：源代码15一、实验目的本实验主要对操作系统中请求分页式内存管理及其应用的一些关键算法进 行模拟。学生通过设计与实现Clock算法，能够加强对相应理论的理解，并对了 解操作系统内部的基本处理原理与过程也有很多益处。利用简单的数据结构，模拟实现操作系统中的页面置换机制，通过写程序模拟实现上述三种内存页面置换 算法，使学生进一步掌握内存页面置换的方法。 对操作系统中内存的管理有一个

2、实践上的认识。1、用C语言编写OPT FIFO、LRU三种置换算法。2、熟悉内存分页管理策略。3、了解页面置换的算法。4、掌握一般常用的调度算法。5、根据方案使算法得以模拟实现。6、锻炼知识的运用能力和实践能力。二、实验要求设计随机页面序号产生程序，并说明随机的性能和其性能可能对算法的 影响编写页面淘汰算法（FIFO、OPT LRU）结果数据的显示或提取结果数据的分析几点说明：设计并绘制算法流程，附加说明所需的数据结构如何标记时间的先后、最久的将来、最久未被使用描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实 现。1）初始化：输入作业可占用的总页框数，初始化置空。2）输入请

3、求序列：输入一个作业页号访问请求序列，依次占用相应页框，直至全部占用；3） Clock算法：当页框全部占用后，对于后续新的页号访问请求，执行Clock 算法，淘汰1个页面后装入新的页号。4）显示当前分配淘汰序列：显示淘汰的页号序列。三、背景知识: 在操作系统当中，在进程运行过程中，若其访问的页面不在内存中而需把他 们调入内存，但内存已无空闲空间时，为了保证该进程能够正常的运行，系 统必须从内存中调出一页程序或数据送到磁盘的兑换区中，但是应该是哪个 页面被调出，需根据一定的算法来确定。通常，我们把这一类的算法称为“页 面置换算法”，页面置换算法执行效率的高低，往往直接影响到操作系统的 性能。内存

4、页面置换算法：1、 <1>先进先出调度算法（FIFO）先进先出调度算法根据页面进入内存的时间先后选择淘汰页面。本算法实 现时需要将页面按进入内存的时间先后组成一个队列，每次置换掉最早进入的贡面。这是最早出现的置换算法，该算法总是淘汰最先进入内存的页面， 即选择在 内存中驻留时间最长的页面换出，予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一 个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法 与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如， 含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘

5、 汰。<2>最近最久未使用的置换算法（LRU最近最久未使用的置换算法，是根据页面调入内存后的使用情况进行决 策的。由于无法预测各页面将来的使用情况， 只能利用“最近的过去”作为“最 近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。 该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历 的时间t,当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未 使用的页面予以淘汰。<3>最佳置换算法（OPT最佳置换算法是可以说的一种理想的页面置换算法,它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以

6、后永不使用的或许 是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得 最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的， 因而该算法是无法实现的，但可以利用 此算法来评价其它算法。<4>时钟页面置换算法时钟页面置换算法是把所有的页面都保存在一个类似钟面的环形链表中，一个表 针指向最老的页面，如图所示口囚回“发生缺页中断时.检 杳表针指向的页面.根0回回臼据R位采取动作上R 二 (h淘汰页面R=l(洁除R位并向的移动表计当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该 页面，并把新的页

7、面插入这个位置，然后把表针前移一个位置；如果 R位是1 就清除R位并把表针前移一个位置，重复这个过程直到找到了一个 R位为0的页 面为止。四、总体设计根据要求设计页面淘汰算法的活动图运行程序进入主页面，在正上方，已经通过随机生成函数生成了页面号，在其下方，显示可选项：0、退出程序1、FIFO算法2、OPT算法3、 LRUB法。根据需要，选择相应的法，程序自动生成页面淘汰的先后顺序，以及置换次数和缺页次数，并打 印在下方，执行完以后，再次进入主页面，到输入 0,退出程序。算法流程图FIFO算法流程图：OPT算法流程图LRU#法流程图:五、详细设计（一）、设计思想1、 最佳置换算法（OPT）用数组

8、Temppages口存储当前物理块中页面信息，数组 TimeArry存 储当前在物理块中的页面的获得内存时的时间，当页面不在内存中时，根据当前已获得物理块数的页面在所有的页面当中将来不在请求内存 或者很少请求内存的情况进行置换2、 先进先出算法（FIFO）用数组Temppages口存储当前物理块中页面信息，变量temp记录内存 中物理块页面置换状态，每进行一次置换，页面置换状态变化，便于 下一次的置换。3、 最近最久未使用算法（LRU）用数组Temppages口存储当前物理块中页面信息，数组 TimeArry存 储当前在物理块中的页面的获得内存时的时间，当页面不在内存中时，选才T TimeAr

9、ry口数组中值最小并且对应物理块中的页面进行置换。（二）、设计步骤首先根据程序要求，我们分别定义两个宏，用以存放我们的物理块数 目以及页面数目，再定义一个结构体，用以物理块的存储，代码如下：#define MemPageCount 4#define InstructionCount 20struct pageint serial; / 页面号int time; /时间计数mempageMemPageCount;其次，建立主函数，根据程序需要，定义相应的变量，建立 switch语句，用以 算法的选择，部分定义如下：int i,j,k,m,n; /指令页面集合，可以考虑让页面指令集合随机生成int

10、 instructionInstructionCount;int mem_counter; / 内存页面集合计数器int switch_counter; /置换次数最后，根据算6流程图，实现相应算法的代码编写。（三）、算法流程设计主函数流程：STEP1输入分配的页框数，页面访问次数和要访问的页面号序列STEP2:内存页面初始化。内存中页面的数据结构为单循环链表，含有页号值 yehao和访问位值a。开始时页号均为-1 ,访问位为0.STEP3测试数据。具体算法是依要访问的页面号，调用 find()函数查找是 否已经存在于内存中。若存在，则修改其访问位为1.若不存在，触发缺页中 断，调用tihua

11、n()函数。最后，打印当前内存状态。如此循环直至测试用都 访问完毕。1)主要函数实现a) Makenode(double)函数：用于初始化一个节点。b) Find (double)函数：依据输入的页号，查询内存中是否已存在此页面。 若存在返回值1,不存在返回值0.c) Tihuan (double)函数：在发生缺页中断时，时钟指针查找访问位为0的页面进行替换，指针扫过的页面访问位置0,新加入的页面访问位置1 替换后指针下移。d) Print_state()函数：打印当前内存中存在的页面的状态以及当前时钟指针所指向的页面位置。2)测试数据估计输入：输入分配的页框数3输入页面访问次数15输入要访问

12、的页面号序列3 4 2 6 4 3 7 4 3 6 3 4 8 4 6输出(仅最后一项)：页面号 访问位页面号访问位61页面号访问位81C loc k指针所在位置见面号为43)结果分析以下是clock算法对应输入页面号序歹U 3 4 2 6 4 3 7 4 3 6 3 4 8 4 6分析表引用q串P426437436348433A666+64A4444-什内存 a44什什41 1+X 66666+22133+333-3+3+88是否跳/页J JJJJJ68六、运行结果分析:a）开始界面请按任意键进行初始化操作.:为为: 为别数续 数次继 面号理犍物意 A省省用任 >缺缺可按自定义页数和号

13、t,使用黑认埴产生结果请输入你的选择:2、采用随机数产生的结果请按任意键进行初始化操作.-为为=为别数续数既继面号理键至物意4省省用任K缺般K使用默认值产生结果2、自定义页数和支号请输入你的选择请选择覆：工为F1F。先进先出）2为LRIK最近最久未使用）3为OPT最佳置换算法， 4三洞法一起实现FIF。先进先出算法结果显示10为为甯frn数数217 面E1032、采用自定义页面信息产生结果 自定义页面数为：15物理块数为：4页面序列为：1 2 3 4 5 6 7 8 9 4 5 6 7 0 8自定义页面数和页号7 8 9234 5 6 7 0 S4 5 6 7H 94 567 0 8请选择昊苣

14、：工为FIFO先进先出2为LRIK最近最久未使用33为OPT最佳置换算法 4三福法一起实现N 15 /V 54 143 7 : 152数；*，:= ,i块为别为： 数；理数分数续 面匚厨面甚继 9改4理键 人入修义义物意 籥否定定用任 请请是自自可按根据结果，我们不难发现，OPT算法，是三种算法中性能最好的，它的置 换次数最少，LRU次之，不过性能最差的还是 FIFO,由于缺页率=缺页次数/ 总的页面数，所以我们不难发现，随着物理块数的增加，缺页率都相应有所增 加，但是OPT»法的增加较为明显，即产生了 belady现象。七、心得体会：这次课程设计，让我对算法的编写更加的熟练，同时更

15、加了解页面置换 的相关算法，也提高了我对算法设计的严密性，对以后的程序设计有很大帮 助。我们不仅对常用的算法进行了编写，还对一些理想的算法也进行了编写， 并且通过适当的方法，得以了验证。就该程序而言，随机性使得程序出现了更多的可能性，为我们验证算法 提供很大的方便，电脑自动分配，大大的节约了我们的时间，但是我们通 过实验不难发现，如果所设的页面项目过大，也会影响我们算法的性能执 行效率。对我们所涉及的算法，让我有很大的感触。在FIFO算法中，无论有无发生缺页或者置换，都需要对每个在内存中 的页面的time值进行增加操作，以保持最先进入的那个页面的time值是最 大的；一个新进来的页面，其tim

16、e值设置为0。当然，该算法也可以通过队列结构来实现，利用队列的先进先出（FIFO）特性完成，无需设置time字段。 distance用于记录内存物理块集合中每个页面距离再次被使用的页面跨 度，缺省值为9999,如果某个页面在后续指令集合中不再出现，则用最大值9999缺省取代；如果页面再次被使用，则两次使用所跨的页面数，为页面 跨度。用最大页面跨度表示以后永不使用或未来最长时间内不再被访问。在LRU算法中，无论是否发生缺页或者置换，除了命中（刚刚被访问过 的页面）页面time值清零之外，其它所有内存中的页面的time值都加一， 以保证最近刚刚被访问的页面的time值最小，相应time值最大的页面

17、就是 最近最久没有被访问的页面。上述两种算法，是我们在进程调度中使用最多的两种， 你可能会问？为 什么要使用进程调度，因为当我们的程序在运行时，若所访问的页面不再内 存而需把它调入内存，但内存已无空闲空间，这时，为了保证该程序能正常 运行，系统就必须从内存中调出一页程序或数据送到磁盘的兑换区中，但应将那个页面调出，我们就必须根据一定的算法来实现。 所以，一个页面置换 算法的好坏，将直接影响到我们系统的性能。相比较而言，我们最常用的是 LRIM法，因为它是根据页面调入内存后的使用情况就行决策的，比FIFOB法要好很多。通过与其他算法白比较，加深对clock算法的理解，也了解了他们的异同之 处。C

18、lock算法其实是一种改进的第二次机会算法，它通过设置访问位，找 到最早最不常访问的页面，即标号为0的页面。之所以叫clock算法，依我理 解是将内存中的排列顺序附上时间的概念，clock指针扫过的页面要将他们1 置0就是基于这个思想，因为他们都是没被访问的，且在时钟上的排列按照 访问时间顺序。这样就保证了每次替换的都是最早进来的且不最常访问的贡 面。八、参考文献【1】计算机操作系统（第三版）汤小丹、梁红兵、汤子瀛、哲凤屏等西安电子科技大学出版社2007-05【2】C+Primer中文版（第4版） （美）Stanley B. Lippman 等 著 李师贤 等 译.人民邮电出版社，2006-0

19、3-01【3】« C+ Primer习题解答（第4版）蒋爱军，李师贤，梅晓勇 著人民邮电出版社2007-02-014 «现代操作系统（原书第3版）塔嫩鲍姆（Tanenbaum.A.S）,陈向群，马洪兵著机械工业出版社2009-07-01【5】计算机操作系统教程张尧学，史美林，张高 清华大学出版社2006-10-01【6】«数据结构（STL框架）王晓东 著清华大学出版社2009-09-01附：源代码#include <stdio.h>#include <stdlib.h>#include <time.h>#define M_siz

20、e 100int pageNum = 0;/全局变量页面数int pagesM_size;/存储页号int TemppagesM_size;/ 辅助数组int TimeArryM_size;/ 记录页在内存中的 时间int method;/产生结果的方法int AlgorithmStyle; / 辅助变量，用于选择算法类型int Block;/ 记录物理块数int start;/ 辅助变量void Inition（）/初始化函数int i;int t = time（NULL）;/ 产生随机数种 子srand(t);/ 用t初始化随机数种子pageNum = rand()%10+8;/ 随机产生

21、4-14之内的整数，保证页面数在4-14之内for(i = 0 ; i < pageNum ; i+) pagesi = rand()%10+1;/ 初始化 页号，初始 值在1-10之内Block = 4;/初始化物理块数位3void printDefaltResult()/缺省参数显示int i;printf("缺省页面数为：dn",pageNum);printf("缺省页号分别为：");for(i = 0 ; i < pageNum ; i+) printf("%d ",pagesi);printf("n&q

22、uot;);printf("可用物理块数为：dn",Block);printf("按任意键继续:")；getchar();void PrintCustomInfo()/显示用户自定义参数int i;printf("自定 义页面数为： dn",pageNum);printf("自定义页号分别为：");for(i = 0 ; i < pageNum ; i+) (printf("%d ",pagesi);)printf("n");printf("可用物理块数为：d

23、n",Block);printf("按任意键继续:n");getchar();)void printUserInfo()/显示个人信息(system("color 0B");printf(" 1n");printf(" |页面淘汰算法I n");printf(" |学号：I n");printf(" |班级：I n");printf(" |姓名：I 'n");printf(" |1n");printf("按任

24、意键开始操作:");getchar();system("cls");system("color 0B");)void ChioceDealmethod()/ 选择解决问题的方法"1"选择缺省值，"2"选择自定 义值(n");printf(" |1、使用默认值产生结果2、自定义页数和页号I n");printf(" 11 n请输入你的选择:n");scanf("%d",&method);system("color 0F&

25、quot;);void PrintNotW让houtPages()显示一定不用换页的部分start = Block;int i,j,k=0,key = 0;for(i = 0 ; i < start ; i+) int flag = 0;for(j = 0 ; j <= i-1 ; j+) if(Temppagesj = pagesi) TimeArryj = i;flag = 1;start = start+1; key+;if(flag = 0)TimeArryk = i;Temppagesk = pagesi;k+;for(j = 0 ; j <= i-key ; j+

26、) printf(" %-7d",Temppagesj);printf("n");void PrintResult()/显示每次换页后的结果int i;for(i = 0 ; i < Block ; i+)printf(" %-7d",Temppagesi);printf("n");void FIFODealQuestion()先进先出算法int i,j；int WithOutPages = 0;/ 记录缺页数printf("FIFO(先进先出算法)结果显示：n");PrintNotWit

27、houtPages();int temp = 0;for(i = start ; i < pageNum ; i+)if(temp = Block)temp = 0;int key = 0 ;for(j = 0 ; j < Block ; j+)判断该页是否在物理 块中if(Temppagesj = pagesi)key = 1; break;if(key = 0)如果不在Temppagestemp = pagesi;temp+;WithOutPages+;PrintResult();printf("置换次数为： d ，页面总数为： d ，置换率为:",With

28、OutPages,pageNum);double re = (double)W让hOutPages)/(double)pageNum);printf("%.2lfn",re);printf("缺页次数为： %d ，页面总数为： %d ，缺页率为:",WithOutPages+Block,pageNum);re = (double)(W让hOutPages+Block)/(double)pageNum);printf("%.2lfn",re);void LRUDealQuestion()/ 最近最久未使用算法int i,j;int Wi

29、thOutPages = 0;/ 记录缺页数printf("LRU(最近最久未使用算法)结果显示：n");PrintNotWithoutPages();for(i = start ; i < pageNum; i+) int key = 0;for(j = 0 ; j < Block ; j+)判断该页是否在物理 块中 if(Temppagesj = pagesi) key = 1;TimeArryj = i;/ 更新时间break;if(key = 0)若该页不在内存中WithOutPages+;int min = TimeArry0;int flag = 0

30、;for(j = 1 ; j < Block ; j+)if(min > TimeArryj) min = TimeArryj;/ 找到最久的页面flag = j;TimeArryflag = i;/记录时间Temppagesflag = pagesi;PrintResult();，置换率为:，缺页率为:printf("置换次数为： %d ，页面总数为： %d",WithOutPages,pageNum);double re = (double)W让hOutPages)/(double)pageNum);printf("%.2lfn",re)

31、;printf("缺页次数为： %d ，页面总数为： %d",WithOutPages+Block,pageNum);re = (double)(W让hOutPages+Block)/(double)pageNum);printf("%.2lfn",re);void OPTDealQuestion()int i,j,l;int WithOutPages = 0;/ 记录缺页数printf("OPT(最佳置换算法)结果显示：n");PrintNotW计houtPages();for(i = start ; i<pageNum ;

32、i+)int key = 0;for(j = 0 ; j < Block ; j+ )/ 判断该页是否在内存中if(Temppagesj=pagesi)TimeArryj = i;key = 1;break;if(key = 0)/ 如果该页不在内存中WithOutPages+;/ 缺页数加 1/得到各物理块下一次访问的时间for(j = 0 ; j < Block ; j+)for(l = i+1; l < pageNum ; l+)if(Temppagesj=pagesl)break;TimeArryj = l;/得到下一次访问时间最长的一个页面，将当前页与其换掉int

33、min = TimeArry0;int flag = 0;for(j = 1 ; j < Block ; j+)if(TimeArryj > min) min = TimeArryj;flag = j；Temppagesflag = pagesi;TimeArryflag = i;PrintResult();，置换率为:，缺页率为:printf("置换次数为： %d ，页面总数为： %d ",WithOutPages,pageNum);double re = (double)W让hOutPages)/(double)pageNum);printf("%

34、.2lfn",re);printf("缺页次数为： %d ，页面总数为： %d",WithOutPages+Block,pageNum);re = (double)(W让hOutPages+Block)/(double)pageNum);printf("%.2lfn",re); void ChioceAlgorithm(int AlgorithmStyle) switch(AlgorithmStyle)case 1:FIFODealQuestion();/break;case 2:LRUDealQuestion();/break;case 3:OPTDealQuestion();/break;case 4:FIFODealQuestion();/LRUDealQuestion();/先进先出算法解决问题最近最久未使用算法解决问题最佳置换算法解决问题先进先出算法解决问题最近最久未使用算法解决问题OPTDealQuestion();/ 最佳置换算法解决问题 break; )void D