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