页面淘汰算法实验报告

《页面淘汰算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、进一步掌握内存页面置换的方法。对操作系统中内存的管理有一个实践上的认识。1、用C语言编写OPT、FIFO、LRU三种置换算法。2、熟悉内存分页管理策略。3、了解页面置换的算法。4、掌握一般常用的调度算法。5、根据方案使算法得以模拟实现。6、锻炼知识的运用能力和实践能力。二、实验要求•设计随机页面序号产牛程序，并说明随机的性能和其性能可能对算法的影响•编写页面淘汰算法（FIFO、OPT、LRU）•结果数据的显示或提取•结果数据的分析几点说明：•设计并绘制算法流程，附加说明所需的数据结构•如何标记时间的先后、

3、最久的将來、最久未被使用•描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。1）初始化：输入作业可占用的总页框数，初始化置空。2）输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直至全部占用；3）Clock算法：当页框全部占用后，对于后续新的页号访问请求，执行Clock算法，淘汰1个页面后装入新的页号。4）显示当前分配淘汰序列：显示淘汰的页号序列。二、背景知识:在操作系统当中，在进程运行过程中，若其访问的页面不在内存中而需把他们调入内存，但内存已无空闲空间时，为了保证该

4、进程能够正常的运行，系统必须从内存中调出一页程序或数据送到磁盘的兑换区中，但是应该是哪个页面被调岀，需根据一定的算法来确定。通常，我们把这--类的算法称为“页面置换算法”，页面置换算法执行效率的高低，往往直接影响到操作系统的性能。内存页面置换算法：1、＜1＞先进先出调度算法（FIFO）先进先出调度算法根据页面进入内存的时间先后选择淘汰页面。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次置换掉最早进入的页面。这是最早岀现的置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最长的

5、页面换出，予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。〈2＞最近最久未使用的置换算法（LRU）最近最久未使用的置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将來的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此,LRU置换算

6、法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,,当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。＜3＞最佳置换算法（OPT）最佳置换算法是可以说的一种理想的页面置换算法，它是由Belady于1966年提岀的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，

7、哪一个页面是未來最长时间内不再被访问的，因而该算法是无法实现的，但可以利用此算法来评价其它算法。〈4＞时钟页面置换算法时钟页而置换算法是把所有的页而都保存在一个类似钟而的环形链表中，一个表针指向最老的页而，如图所示。当发生缺贝中断时.检査表针描向的页根1KR位來収动作'R=0t测汰5(HilR二I：沽除R位并向询移动表针当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找

8、到了一个R位为0的页面为止。四、总体设计•根据要求设计页面淘汰算法的活动图运行程序进入主页面，在正上方，已经通过随机生成函数生成了页面号，在其下方，显示可选项：0、退出程序1、FIFO算法2、OPT算法3、LRU算法。根据需要，选择相应的法，程序自动牛成页面淘汰的先后顺序，以及置换次数和缺页次数，并打印在下方，执行完以后，再次进入主页面，到输入0,退岀程序。•算法流程图>FIFO算法流程图：AOPT算法流程图>LRU算法流程图