操作系统实验报告(clock算法)

实验四页面置换算法一、 实验目的本实验主要对操作系统中请求分页式内存管理及其应用的一些关键算法进行模拟。学生通过设计与实现Clock算法，能够加强对相应理论的理解，并对了解操作系统内部的基本处理原理与过程也有很多益处。二、 实验要求基本要求：描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。1） 初始化：输入作业可占用的总页框数，初始化置空。2） 输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直至全部占用；3） Clock算法：当页框全部占用后，对于后续新的页号访问请求，执行Clock算法，淘汰1个页面后装入新的页号。4） 显示当前分配淘汰序列：显示淘汰的页号序列。描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。三、实验内容1）基本原理时钟页面置换算法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面，日日回I回 /回当发生缺页中断时，检查君针指向的页根据R位采取动作t£=伐淘汰页面R=It当发生缺页中断时，检查君针指向的页根据R位采取动作t£=伐淘汰页面R=It清除威位井向前翔动成针□国回回曰如图所示。当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。2）算法流程设计主函数流程：STEP1:输入分配的页框数，页面访问次数和要访问的页面号序列STEP2:内存页面初始化。内存中页面的数据结构为单循环链表，含有页号值yehao和访问位值a。开始时页号均为-1,访问位为0.STEP3：测试数据。具体算法是依要访问的页面号，调用find()函数查找是否已经存在于内存中。若存在，则修改其访问位为1.若不存在，触发缺页中断，调用tihuan()函数。最后，打印当前内存状态。如此循环直至测试串都访问完毕。主要函数实现Makenode(double)函数：用于初始化一个节点。Find(double)函数：依据输入的页号，查询内存中是否已存在此页面。若存在返回值1，不存在返回值0.Tihuan(double)函数：在发生缺页中断时，时钟指针查找访问位为0的页面进行替换，指针扫过的页面访问位置0，新加入的页面访问位置1。替换后指针下移。Print_state()函数：打印当前内存中存在的页面的状态以及当前时钟指针所指向的页面位置。测试数据输入：输入分配的页框数3输入页面访问次数15输入要访问的页面号序列342643743634846输出(仅最后一项)：页面可访问位TOC\o"1-5"\h\z4 1页荷号访问位6 1页面号访问位8 1clock^g针所在位置页面号为4结果分析以下是clock算法对应输入页面号序列342643743634846的分析表四、实验总结加深对clock算法的理解。通过与其他算法的比较，我也了解了他们的异同之处。Clock算法其实是一种改进的第二次机会算法，它通过设置访问位，找到最早最不常访问的页面，即标号为0的页面。之所以叫clock算法，依我理解是将内存中的排列顺序附上时间的概念，clock指针扫过的页面要将他们1置0就是基于这个思想，因为他们都是没被访问的，且在时钟上的排列按照访问时间顺序。这样就保证了每次替换的都是最早进来的且不最常访问的页面。在时钟内存结构的代码实现上，我使用了自建的单循环链表，对其进行顺序地遍历即可实现时钟指针的移动。另外通过全局变量node*r（时钟）node*start（开始页面项）node*r_prev（时钟指针的前驱）的设置，方便了有关算法的实现。此算法较为简单，还有一种改进版的clock算法，增加了一个修改位，表示页框是否被修改过。这样的设计更加符合现在操作系统的调度原则。参考文献（美）StanleyB.Lippman等著李师贤等译.C++Primer中文版（第4版）.人民邮电出版社，2006-03-01蒋爱军，李师贤，梅晓勇著.C++Primer习题解答（第4版）.人民邮电出版社，2007-02-01塔嫩鲍姆（Tanenbaum.A.S），陈向群，马洪兵著.现代操作系统（原书第