操作系统课程设计报告--页面淘汰算法实现

《操作系统课程设计报告--页面淘汰算法实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、操作系统课程设计报告一、课程设计题目：页面淘汰算法实现二、基本要求：l设计随机页面序号产生程序，并说明随机的性能和其性能可能对算法的影响l编写页面淘汰算法(FIFO、OPT、LRU)l结果数据的显示或提取l结果数据的分析几点说明：l设计并绘制算法流程，附加说明所需的数据结构l如何标记时间的先后、最久的将来、最久未被使用三、算法描述：（1）先进先出页面置换算法（FIFO）FIFO算法这是最早出现的置换算法，该算法总是淘汰最先进入内存的页面，即选择在内存中驻时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换

2、指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。（2）最佳置换算法（OPT）它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用此算法来评价其它算法。（3）最近最久未使用置换算法（L

3、RU）最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。四、总体设计l根据要求设计页面淘汰算法的活动图运行程序进入主页面，在正上方，已经通过随机生成函数生成了页面号，在其下方，显示可选项：0、退出程序1、FIFO算法2、OPT算法3、LRU算法。根据需

4、要，选择相应的法，程序自动生成页面淘汰的先后顺序，以及置换次数和缺页次数，并打印在下方，执行完以后，再次进入主页面，到输入0，退出程序。l算法流程图ØFIFO算法流程图：ØOPT算法流程图ØLRU算法流程图：五、详细设计首先根据程序要求，我们分别定义两个宏，用以存放我们的物理块数目以及页面数目，再定义一个结构体，用以物理块的存储，代码如下：#defineMemPageCount4#defineInstructionCount20structpage{intserial;//页面号inttime;//时间计数}mempage[MemPageCount];其次，建立主函数，根

5、据程序需要，定义相应的变量，建立switch语句，用以算法的选择，部分定义如下：inti,j,k,m,n;//指令页面集合,可以考虑让页面指令集合随机生成intinstruction[InstructionCount];intmem_counter;//内存页面集合计数器intswitch_counter;//置换次数最后，根据算法流程图，实现相应算法的代码编写。四、结果分析：物理块数为3、页面数目为20：物理块数为4、页面数目为20：根据结果，我们不难发现，OPT算法，是三种算法中性能最好的，它的置换次数最少，LRU次之，，不过性能最差的还是FIFO，由于缺页率=缺页次

6、数/总的页面数，所以我们不难发现，随着物理块数的增加，缺页率都相应有所增加，但是OPT算法的增加较为明显，即产生了belady现象。四、课程设计总结：通过本次课程设计，让我对页面淘汰算法有了充分的了解，我不仅对我们常用的算法进行了编写，还对一些理想的算法也进行了编写，并且通过适当的方法，得以了验证。就该程序而言，随机性使得程序出现了更多的可能性，为我们验证算法提供很大的方便，电脑自动分配，大大的节约了我们的时间，但是我们通过实验不难发现，如果所设的页面项目过大，也会影响我们算法的性能执行效率。对我们所涉及的算法，让我有很大的感触。在FIFO算法中，无论有无发生缺页或者置换

7、，都需要对每个在内存中的页面的time值进行增加操作，以保持最先进入的那个页面的time值是最大的；一个新进来的页面，其time值设置为0。当然，该算法也可以通过队列结构来实现，利用队列的先进先出（FIFO）特性完成，无需设置time字段。distance用于记录内存物理块集合中每个页面距离再次被使用的页面跨度，缺省值为9999，如果某个页面在后续指令集合中不再出现，则用最大值9999缺省取代；如果页面再次被使用，则两次使用所跨的页面数，为页面跨度。用最大页面跨度表示以后永不使用或未来最长时间内不再被访问。在LRU算法中，无论