《页面淘汰算法实验报告》由会员分享，可在线阅读，更多相关《页面淘汰算法实验报告（28页珍藏版）》请在金锄头文库上搜索。
1、操作系统实验报告专业：班级：学号：姓名：一实验目的错误！未定义书签。二实验要求3三背景知识3四总体设计4五详细设计错误！未定义书签。六运行结果分析9七心得体会13八参考文献14附：源代码15一、实验目的本实验主要对操作系统中请求分页式内存管理及其应用的一些关键算法进行模拟。学生通过设计与实现Clock算法，能够加强对相应理论的理解，并对了解操作系统内部的基本处理原理与过程也有很多益处。利用简单的数据结构，模拟实现操作系统中的页面置换机制，通过写程序模拟实现上述三种内存页面置换算法，使学生进一步掌握内存页面置换的方法。对操作系统中内存的管理有一个实践上的认识。1、用C语言编写OPTFIFO、LR
2、U三种置换算法。2、熟悉内存分页管理策略。3、了解页面置换的算法。4、掌握一般常用的调度算法。5、根据方案使算法得以模拟实现。6、锻炼知识的运用能力和实践能力。二、实验要求设计随机页面序号产生程序，并说明随机的性能和其性能可能对算法的影响编写页面淘汰算法（FIFO、OPTLRU）结果数据的显示或提取结果数据的分析几点说明：设计并绘制算法流程，附加说明所需的数据结构如何标记时间的先后、最久的将来、最久未被使用描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。1）初始化：输入作业可占用的总页框数，初始化置空。2）输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直
3、至全部占用；3）Clock算法：当页框全部占用后，对于后续新的页号访问请求，执行Clock算法，淘汰1个页面后装入新的页号。4）显示当前分配淘汰序列：显示淘汰的页号序列。三、背景知识:在操作系统当中，在进程运行过程中，若其访问的页面不在内存中而需把他们调入内存，但内存已无空闲空间时，为了保证该进程能够正常的运行，系统必须从内存中调出一页程序或数据送到磁盘的兑换区中，但是应该是哪个页面被调出，需根据一定的算法来确定。通常，我们把这一类的算法称为“页面置换算法”，页面置换算法执行效率的高低，往往直接影响到操作系统的性能。内存页面置换算法：1、 先进先出调度算法（FIFO）先进先出调度算法根据页面进
4、入内存的时间先后选择淘汰页面。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次置换掉最早进入的贡面。这是最早出现的置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最长的页面换出，予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。最近最久未使用的置换算法（LRU最近最久未使用的置换算法，是根据页面调入内存后的使用情况进行决策的。
5、由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。最佳置换算法（OPT最佳置换算法是可以说的一种理想的页面置换算法,它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，
6、哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用此算法来评价其它算法。时钟页面置换算法时钟页面置换算法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面，如图所示口囚回“发生缺页中断时.检 杳表针指向的页面.根0回回臼据R位采取动作上R 二 (h淘汰页面R=l(洁除R位并向的移动表计当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。四、总体设计根据要求设计页面淘汰算法的活动图运行程序进
7、入主页面，在正上方，已经通过随机生成函数生成了页面号，在其下方，显示可选项：0、退出程序1、FIFO算法2、OPT算法3、LRUB法。根据需要，选择相应的法，程序自动生成页面淘汰的先后顺序，以及置换次数和缺页次数，并打印在下方，执行完以后，再次进入主页面，到输入0,退出程序。算法流程图FIFO算法流程图：OPT算法流程图LRU#法流程图:五、详细设计（一）、设计思想1、 最佳置换算法（OPT）用数组Temppages口存储当前物理块中页面信息，数组TimeArry存储当前在物理块中的页面的获得内存时的时间，当页面不在内存中时，根据当前已获得物理块数的页面在所有的页面当中将来不在请求内存或者很少
8、请求内存的情况进行置换2、 先进先出算法（FIFO）用数组Temppages口存储当前物理块中页面信息，变量temp记录内存中物理块页面置换状态，每进行一次置换，页面置换状态变化，便于下一次的置换。3、 最近最久未使用算法（LRU）用数组Temppages口存储当前物理块中页面信息，数组TimeArry存储当前在物理块中的页面的获得内存时的时间，当页面不在内存中时，选才TTimeArry口数组中值最小并且对应物理块中的页面进行置换。（二）、设计步骤首先根据程序要求，我们分别定义两个宏，用以存放我们的物理块数目以及页面数目，再定义一个结构体，用以物理块的存储，代码如下：#defineMemPag
9、eCount4#defineInstructionCount20structpageintserial;/页面号inttime;/时间计数mempageMemPageCount;其次，建立主函数，根据程序需要，定义相应的变量，建立switch语句，用以算法的选择，部分定义如下：inti,j,k,m,n;/指令页面集合，可以考虑让页面指令集合随机生成intinstructionInstructionCount;intmem_counter;/内存页面集合计数器intswitch_counter;/置换次数最后，根据算6流程图，实现相应算法的代码编写。（三）、算法流程设计主函数流程：STEP1输入
10、分配的页框数，页面访问次数和要访问的页面号序列STEP2:内存页面初始化。内存中页面的数据结构为单循环链表，含有页号值yehao和访问位值a。开始时页号均为-1,访问位为0.STEP3测试数据。具体算法是依要访问的页面号，调用find()函数查找是否已经存在于内存中。若存在，则修改其访问位为1.若不存在，触发缺页中断，调用tihuan()函数。最后，打印当前内存状态。如此循环直至测试用都访问完毕。1)主要函数实现a) Makenode(double)函数：用于初始化一个节点。b) Find(double)函数：依据输入的页号，查询内存中是否已存在此页面。若存在返回值1,不存在返回值0.c) T
11、ihuan(double)函数：在发生缺页中断时，时钟指针查找访问位为0的页面进行替换，指针扫过的页面访问位置0,新加入的页面访问位置1替换后指针下移。d) Print_state()函数：打印当前内存中存在的页面的状态以及当前时钟指针所指向的页面位置。2)测试数据估计输入：输入分配的页框数3输入页面访问次数15输入要访问的页面号序列342643743634846输出(仅最后一项)：页面号访问位页面号访问位61页面号访问位81Clock指针所在位置见面号为43)结果分析以下是clock算法对应输入页面号序歹U342643743634846引用q串P426437436348433A666+64A
12、4444-什内存a44什什411+X66666+22133+333-3+3+88是否跳/页JJJJJJ分析表68六、运行结果分析:a）开始界面请按任意键进行初始化操作.:为为:为别数续数次继面号理犍物意A省省用任缺缺可按自定义页数和号t,使用黑认埴产生结果请输入你的选择:2、采用随机数产生的结果请按任意键进行初始化操作.-为为=为别数续数既继面号理键至物意4省省用任K缺般K使用默认值产生结果2、自定义页数和支号请输入你的选择请选择覆：工为F1F。先进先出）2为LRIK最近最久未使用）3为OPT最佳置换算法，4三洞法一起实现FIF。先进先出算法结果显示10为为甯frn数数217面E1032、采用
13、自定义页面信息产生结果自定义页面数为：15物理块数为：4页面序列为：123456789456708自定义页面数和页号7892345670S4567H9456708请选择昊苣：工为FIFO先进先出2为LRIK最近最久未使用33为OPT最佳置换算法4三福法一起实现N15/V541437:152数；*，:=,i块为别为：数；理数分数续面匚厨面甚继9改4理键人入修义义物意籥否定定用任请请是自自可按根据结果，我们不难发现，OPT算法，是三种算法中性能最好的，它的置换次数最少，LRU次之，不过性能最差的还是FIFO,由于缺页率=缺页次数/总的页面数，所以我们不难发现，随着物理块数的增加，缺页率都相应有所增加，但是OPT法的增加较为明显，即产生了belady现象。七、心得体会：这次课程设计，让我对算法的编写更加的熟练，同时更加了解页面置换的相关算法，也提高了我对算法设计的严密性，对以后的程序设计有很大帮助。我们不仅对常用的算法进行了编写，还对一些理想的算法也进行了编写，并且通过适当的方法，得以了验证。就该程序
