操作系统实验五页面置换算法
1. 实验目的
设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法；通过页面访问序列随机发生器实现对上述算法的测试及性能比较。
2. 实验基础知识及背景说明
（1） 请求分页虚拟内存管理
请求分页虚拟内存管理是建立在基本分页基础上的，为了能支持虚拟存储器功能，而增加了请求调页功能和置换功能。
（2） 工作集
多数程序都显示出高度的局部性，也就是说，在一个时间段内，一组页面被反复引用。这组被反复引用的页面随着时间的推移，其成员也会发生变化。有时这种变化是剧烈的，有时这种变化则是渐进的。我们把这组页面的集合称为工作集
（3） 缺页率
缺页中断次数/总的页面访问次数
3. 实验前提说明
（1） 页表用整数数组或结构数组来表示
（2） 页面访问序列串是一个整数序列，整数的取值范围为0到N - 1。页面访问序列串中
的每个元素p表示对页面p的一次访问
（3） 符合局部访问特性的随机生成算法
a. 确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集
移动率m（每处理m个页面访问则将起始位置p +1），以及一个范围在0和1之间的值t
b. 生成m个取值范围在p和p + e间的随机数，并记录到页面访问序列串中 c. 生成一个随机数r，0 ≤ r ≤ 1
d. 如果r < t，则为p生成一个新值，否则p = (p + 1) mod N
e. 如果想继续加大页面访问序列串的长度，请返回第2步，否则结束
4. 实验算法介绍
（1） 最佳置换算法
最佳置换算法的主要思想是，在发生页面替换时，被替换的对象应该满足，在以后的页面访问中，该对象不会再次被访问或者较晚被访问。是一种理想化算法，具有最好性能（对于固定分配页面方式，本法可保证获得最低的缺页率），但实际上却难于实现，故主要用于算法评价参照
（2） 先进先出置换算法
先进先出置换算法的主要思想是，在发生页面替换时，被替换的对象应该是最早进入内存的。
（3） 最近最久未使用置换算法
最近最久未使用置换算法的主要思想是，在发生页面替换时，被替换的页面应该满足，在之前的访问队列中，该对象截止目前未被访问的时间最长
（4） 改进型Clock置换算法
改进型Clock置换算法的主要思想是，在每次页面替换时，总是尽可能地先替换掉既未被访问又未被修改的页面。
（5） 页面缓冲算法
设立空闲页面链表和已修改页面链表采用可变分配和基于先进先出的局部置换策略，并规定被淘汰页先不做物理移动，而是依据是否修改分别挂到空闲页面链表或已修改页面链表的末尾,空闲页面链表同时用于物理块分配,当已修改页面链表达到一定长度如Z个页面时，一起将所有已修改页面写回磁盘，故可显著减少磁盘I/O操作次数
5. 相关数据结构设计
根据各个算法的特点，程序实现的过程中用到的数据结构主要有以下两种
（1） 数组：定义的时候利用指针定义，然后根据全局变量block设定的给进程分配
的物理内存的块数动态分配内存。一旦完成内存分配，不再改变数组的大小。 用到数组结构来实现的算法程序有：最佳置换算法，先进先出置换算法，最近最久未使用置换算法，改进型置换算法。
（2） 队列：为单向队列，队列长度仍然由全局变量指定。
用到队列的算法程序有：先进先出置换算法。队列结点元素的结构体如下
typedef struct node {
int num;//页号
node* next;//下一个结点页面 } Node, *pNode;
typedef struct queue {
int n;//总的结点数 pNode front;//队首指针 pNode rear; //队尾指针 } Queue, *pQueue;
（3） 链表：主要是将装入内存的页块串联起来。
用到链表的算法程序：页面缓冲算法。链表结点元素的结构体如下
struct LNode {
int data;//页号 int flag;//访问位 int modify;//修改位 LNode* next; };
struct Link {
int num;//当前链表上的结点数 LNode* next; };
6. 主要函数功能说明
（1） 全局共享函数
void initMemo();//初始化存储空间，主要是设置分配空间的大小 void generate();//生成访问序列
bool isInMemo (int n); //指定页号是否已经在内存中
（2） 最佳置换算法
void optimal (int n); //访问一个页面，执行一次最佳置换算法 void testOptimal();//算法实现函数
（3） 先进先出置换算法
void initQueue (pQueue q);//初始化队列
void push (pQueue q, int num);//队列中加入新的页面结点
void pop (pQueue q);//将页面移出内存 void destroy (pQueue q);//销毁队列
bool findInQueue (pQueue q, int num);//查找页面是否已经调入内存 void generate();//生成访问序列
void fifoTest();//每访问一个页面，执行一次算法
void fifo (pQueue q, int num);//先进先出置换算法实现函数
（4） 最近最久未使用置换算法
void LRU (int n);//每访问一个新的页面，执行一次LRU算法 void testLRU();//LRU算法实现函数
（5） 改进型clock置换算法
void updated_Clock (int n);//改进型clock算法实现函数 void test_Clock();//每访问一个新的页面，执行一次算法
（6） 页面缓冲算法
bool isInNodes (int n); //页面是否已经在链表中
void addToLink (int data, int type);//页面添加到已修改页面链表和空闲链表上 void emptyIdle();//将空闲链表上的所有页面送出内存 void emptyModi();//将已修改页面链表上所有的链表送出内存 void PBA (int n);//PBA算法实现函数
7. 程序运行
每个算法实现的代码量不同，以及不同算法使用的数据结构有差别，为了不至于程序过于臃肿庞大，所以所有的算法总共是在三个程序实现的（具体代码如8附录所示）.其中，最佳置换算法，LRU算法，改进型clock置换算法是在experiment5.cpp中实现的，先进先出置换算法是在FIFO.cpp中实现的，页面缓冲置换算法是在PBA.cpp中实现的。为了便于对比，程序中会先用genenrate（）函数产生大小为32的访问序列，然后在每种算法下运行。测试过程如下： （1） 利用generate函数产生访问序列如下
access[32]={ 2, 3, 3, 7, 2, 8, 3, 7, 9, 7, 10, 8, 12, 11, 8, 8, 61, 61, 3, 61, 62, 60, 2,60, 3,62,62, 3, 3, 4, 2, 62} （2） 各算法执行结果如下
a.最佳置换算法（局部）
可以看到，32个页面，有12个页面发生了缺页，缺页率为0.375
b.先进先出算法
可以看到，32个页面，有15个页面发生了缺页，缺页率为0.46875