(完整word版)页面置换算法的实现和比较实验报告.doc

浙江万里学院《操作系统》实验报告实验名称：页面置换算法的实现和比较实验时间：2018.11.27指导教师：詹卫华组号：26学号：2016011147姓名：林文辉班级：计算机164学号：2016011133姓名：王旭升班级：计算机164一、实验目的理解各种常见的页面置换算法的原理，并能实现这些算法，并进行比较。二、实验内容实现以下页面置换算法：先进先出最近最久未使用时钟页面置换算法（选做）OPT置换算法要求根据输入的页面引用序列和物理块数k，各算法输出对应的页面置换序列，并统计缺页率。测试样例为，k=3和k=4，页面引用序列为：【70120304230321201701】二、实验过程1.功能设计（1）重要的数据结构设计1）顺序队列queue实际代码中使用的是deque，双端队列，只是因为STL标准库容器中的queue没有迭代器不便于遍历队列才选的deque，实际上只需要让双端队列一头只能进，另一头只出即可实现顺序队列。代码的话直接通过#include<deque>头文件的构造函数deque<int>创建队列，具体构造细节不表。作用的话相当于内存的物理地址空间，页面调入内存在这里就是调入该队列，页面置换就相当于出队列成员并入队列新成员的过程。deque<int>displace;deque<int>::iteratorpos;//迭代器2）栈stack与队列的理由类似，stcak不提供遍历，没有迭代器，在实际使用中选择deque进行替代，只需要让双端队列的一端堵死（既不让它进也不让它出）即可实现栈。声明方式与（1）相同，值得一提的是，在实际使用中可能会出现如是情况deque<page>displace;deque<page>::iteratorpos;//迭代器不建立默认int类型的队列，而是建立一个page（结构体类型）的队列在LRU算法中，在页面进行替换的时候，为了方便，使用erase直接进行队列中的指定元素删除而不是用出队列，其实破坏了双端队列的规则（在两端进行删除插入），实际上…在这一点上可能连双端队列都算不上…反而更像普通的线性表了…3）动态数组在CLOCK算法中，在页面进行替换的时候，用了insert函数，这里用了deque支持随机访问的特性，实际上已经跟双端队列没啥关系了，性质源于它的原型——动态数组，实际上是若干连续空间。4)页面结构体LRU和OPTtypedefstructPAGE{intnum;//页号inttime;//时间}page;考虑到部分算法的需求，当然实际上不特地定义结构体，在程序中随便设置一些标志位或者标志数组也是可以考虑的。其中，CLOCK算法还用到了如下页面结构体typedefstructPAGE{intnum;//页号intvisit;//使用位}page;5)全局常量#definePAGE_VIEW20//访问总次数其中，OPT算法还用到了一个常量，表示接下来永远不会被访问的页面#defineInfinite65535//无穷大（2）主要函数或接口设计代码本身没有采用函数的形式，实际上很多部分是可以写成函数的形式的。包括三段程序本身也可以写成三个函数合成为一段程序，每个算法对应一个子函数。很多数据结构全局变量实际上三个函数是差不多的，可以使用同一个。以及一些反复执行的常见操作也可以进行封装。例如：利用迭代器遍历队列，然后输出队列，就可以封装成一个out有参函数包括四种情况的判断主程序部分可以改为switchcase然后情况判断封装成一个函数返回状态类型，包括每种状态执行的内容也可以封装成几个小函数。LRU算法和OPT算法开头关于时间计算的函数也可以封装成函数。实现起来并不复杂，虽然能简洁不少，不过现在的代码也挺好，每个算法独立开来，某些情况下还是对阅读代码有很大帮助的，所以就没改:)此外调用了不少STL标准库函数：[对deque而言]例如迭代器访问操作函数.begin()指向第一个元素的迭代器.end()指向最后一个元素的下一个位置的迭代器这样，利用这两个操作，就可以遍历整个队列。for(pos=displace.begin();pos!=displace.end();pos++)front()队首元素的引用back()队尾元素的引用这一组在涉及结构体的话用的比较，例如：displace.front().time这样.pop_front()队首元素出队列.push_back()入队列到队尾其实相对应的还有pop_back()和push_front()不过其实意义不大，毕竟是双端队列，倒过来看头和尾也没差。FIFO算法中只用这一组操作，所以相当于还是一个顺序队列。（没有用到双端队列的特点）LRU基本只用到了入队列，因为出队列被erase()替代了——————上述6个函数均为无参函数—————