页面置换算法实验报告.doc

页面置换算法
实验报告

一、 实验目的：
设计和实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简单Clock置换算法及改进型Clock置换算法；通过支持页面访问序列随机发生实现有关算法的测试及性能比较。
二、 实验内容：
l 虚拟内存页面总数为N，页号从0到N-1
l 物理内存由M个物理块组成
l 页面访问序列串是一个整数序列，整数的取值范围为0到N - 1。页面访问序列串中的每个元素p表示对页面p的一次访问
l 页表用整数数组或结构数组来表示

q 符合局部访问特性的随机生成算法
1. 确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m（每处理m个页面访问则将起始位置p +1），以及一个范围在0和1之间的值t；
2. 生成m个取值范围在p和p + e间的随机数，并记录到页面访问序列串中；
3. 生成一个随机数r，0 ≤ r ≤ 1；
4. 如果r < t，则为p生成一个新值，否则p = (p + 1) mod N；
5. 如果想继续加大页面访问序列串的长度，请返回第2步，否则结束。
三、 实验环境：
操作系统：Windows 7
软件： VC++6.0
四、 实验设计：
本实验包含六种算法，基本内容相差不太，在实现方面并没有用统一的数据结构实现，而是根据不同算法的特点用不同的数据结构来实现：
1、 最佳置换和随机置换所需操作不多，用整数数组模拟内存实现；
2、 先进先出置换和最近最久未使用置换具有队列的特性，故用队列模拟内存来实现；
3、 CLOCK置换和改进的CLOCK置换具有循环队列的特性，故用循环队列模拟内存实现；

4、 所有算法都是采用整数数组来模拟页面访问序列。

五、 数据结构设计：

//页面访问序列数组：
int ref[ref_size];

//内存数组：
int phy[phy_size];

//队列数据结构定义：
typedef struct QNode //定义队列数据结构
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front; //头指针
QueuePtr rear; //尾指针
}LinkQueue;

//定义链表数据结构
typedef struct LNode //定义循环链表数据结构
{
int data;
int flag; //访问位
int modify; //修改位
struct LNode *next;
}LNode,*LinkList;

六、 主要函数说明：

1、 void set_rand_num() //产生具有局部特性的随机数列；
2、 int Exchange_LNode(LinkList &L,int e,int i)//将链表L中序号为i的结点替换为内容为e的结点；
3、 bool Search_LinkList(LinkList &L,int e,int &i)//找到链表L中内容为e的结点，并用i返回其位置，i=1表示第一个非头结点，依次类推；
4、 void Search_LL_Flag(LinkList &L,int &i)//用i返回第一个flag为0的结点的位置,i=1表示第一个非头结点，以此类推；
5、 void Set_LL_Flag(LinkList &L,int i) //设置链表L中的序号为i的结点的flag标志为1；
6、 int Search_LL_ModifyClock(LinkList &L,int &modify_num)//找到改进的CLOCK算法所需要淘汰的页，用modify_num返回其位置；
此函数根据书上给的思路，第一遍扫描A=0且M=0的页面予以淘汰，若失败，则进行第二轮扫描A=0且M=1的页面，第二轮扫描时将所有访问过的页面的访问位A置0；若失败则重复上述两部；
7、void Set_LL_modify(LinkList &L,int i) //设置链表L中的序号为i的结点的modify标志为1；
8、bool SearchQueue(LinkQueue &Q,int e,int &i) //寻找队列Q中结点data域等于e的结点，并用i返回其在Q中的位置；

9、int getnum(int a,int b) //用b返回元素a在被引用数列中的下一个位置
10、void ORA() //实现最佳置换算法，包括判断页面是否在内存中、页面进内存、输出内存状态等内容；
11、void RAND() //随机置换算法
12、void FIFO() //先进先出算法
13、void LRU() //最近最久未使用算法
实现最近最久未使用算法的思想是：判断待进入内存的页面，如果与内存中的第一个页面相同，则将它移到最后一个，即标志为最近使用的页；如果与内存中的第二个页面相同，则将它删除，并在队列尾部添加相同元素，即标志为最近使用的页；
14、void CLOCK() //实现CLOCK算法
15、void Modified_Clock() //实现改进的CLOCK算法
16、int main() //主函数，调用实现各算法的6个主要函数，并输出各算法的缺页率。
七、 实验问题回答：
1、FIFO算法是否比随机置换算法优越？
答：FIFO算法比随机置换算法优越，但优势并不明显。

2、LRU算法比FIFO 算法优越多少？
答：LRU算法FIFO算法的效率要高5%-10%，有理论知识可知，页面访问序列具有局部性，而FIFO 算法并不符合实际情况。

3、LRU算法和Optimal算法有何差距？
答：LRU算法是所有算法中效率最接近Optimal算法的算法，由理论知识可知，Optimal算法是理想的算法，现实中几乎不可能实现，只能作为一种测评标准，LRU算法是效率较高的可实现置换算法，但其硬件要求较高，如果规模较小，则略显麻烦。

4、Clock算法和LRU算法有何差距？
答：Clock算法和LRU算法从结果看来差距不大，Clock算法是使用软件的方式实现LRU算法中硬件的功能，从而在执行效率上会稍逊色些。

八、 实验过程结果截图：
实验结果截图
测评一：

测评二：

测评三：

实验过程截图
（注：只截取第三次测评，蓝色字体表示产生缺页中断）

九、 实验结果分析：
1、最佳置换算法效果最佳
不论在那组数据中，最佳置换算法的效果都是最好的，且都会比其它算法的性能高出不少。但通过课堂上的学习，我们知道这只是一种理想化算法，但实际上却难于实现，故主要用于算法评价参照。
2、随机算法的性能总是最不好的
这是由于随机算法每次总是从所有页面中随机挑一个置换出去，但我们知道页面的访问存在着局部性的原理，并不是随机的，因此它的性能较差。
3、最近最久未使用算法的性能较好
相较于先进先出和两种clock算法，最近最久未使用算法的性能略好，我们测试的数据规模相对较小，相信如果采用更大规模的数据，其优势会更加明显。
当从课堂上我们知道要想在实际的应用中实现本算法，用软件的方法速度太慢，影响程序执行效率，如果采用硬件方法实现，则需要增加大量的硬件设备。
4、先进先出与clock算法的性能基本相同
这是由于两种clock算法遍历链表采用的就是FIFO的方法，而改进的clock算法相比于简单clock算法的优势主要体现在会根据是否被修改进行选择，以减少写回所花费的时间。

十、 实验总结：
这次实验总体难度不是很大，需要实现的算法数目虽然不少，但基本思路较为相似，因此实现起来也并不是十分困难。通过完成这次实验，除了加深了我对几种策略的理解，锻炼了我的编程能力，另一个巨大的收获就是了解了一些生成测试数据的方法。为了使我们的测试数据更贴近现实，我们引入了工作集的概念，并根据实际使用情况的特点设计出尽可能符合实际情况的随机数生成方案。通过阅读课件再加上自己的理解，我了解了老师的设计思路，感觉这个思路极其巧妙，设计中用到的方法和体现出的很多思想值得我们学习。

十一、 程序清单：
#include<iostream>
#include<windows.h>
#include<time.h>
#include<malloc.h>
#include<conio.h>
using namespace std;
#define ref_size 20
#define phy_size 3
int ref[ref_size];
float interrupt[6]={0.0};
//int ref[ref_size]={0};
int phy[phy_size];
//////////////////////////////////////////////////////////////////

void set_rand_num() //产生具有局部特性的随机数列
{
cout<<"页面访问序列："<<endl;
int p=12;
int e=4;
int m=4;
int i=0;
int j=0;
int n=0;
double t=0.6;
int temp;
for(i=0;i<m;i++,j++)

{
Sleep(1000*i);
srand(time(NULL));
temp=rand()%e+p;
ref[j]=temp;
cout<<ref[j]<<" ";
}
for(n=0;n<4;n++)
{
Sleep(1000*n);
srand(time(NULL));
double r=(double)(rand()%10)/10.0;
//cout<<r<<endl;
if(r<t) p=p+int(10*r);
else
p=(p+1)%20;
for(i=0;i<m;i++,j++)
{
Sleep(1000*i);
srand(time(NULL));
temp=rand()%e+p;
ref[j]=temp;
cout<<ref[j]<<" ";
}
}
cout<<endl;
}

////////////////////////////////////////////////////////////////
typedef struct QNode //定义队列数据结构
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front; //头指针
QueuePtr rear; //尾指针
}LinkQueue;
//定义链表结点
typedef struct LNode //定义循环链表数据结构
{
int data;
int flag; //访问位

int modify; //修改位
struct LNode *next;
}LNode,*LinkList;

//////////////////////////////////////////////////////////////////////////对循环链表的一些操作
int CreatList(LinkList &L)//创建循环带有头结点的链表
{
L=(LinkList)malloc(sizeof(LNode));
if(!L) exit(-1);
L->next=L;
L->flag=0;
return 1;
}

int Exchange_LNode(LinkList &L,int e,int i)//将链表L中序号为i的结点替换为内容为e的结点
{
if(L->next==L) exit(-1);
LinkList p,q;
int j=0;
p=(LinkList)malloc(sizeof(LNode));
q=(LinkList)malloc(sizeof(LNode));
q->data=e;
p=L;
for(j=0;j<i;j++)//使p为待更换结点的前一个结点，故应保证，删除第一个非头结点时i=0，以此类推
p=p->next;
q->next=p->next->next;
p->next=q;
q->flag=1; //设置新结点的访问位为1
q->modify=0; //设置新结点的修改位为0
return 1;
}

int Insert_LNode(LinkList &L,int e)//在循环链表中插入新的结点，从L头结点开始依次向后插入
{
LinkList p,q;
p=(LinkList)malloc(sizeof(LNode));
q=(LinkList)malloc(sizeof(LNode));
q->data=e;
q->flag=1; //设置新结点的访问位为1
q->modify=0; //设置新结点的修改位为0

p=L;
while(p->next!=L)
{
p=p->next;
}
p->next=q;
q->next=L;
return 1;
}

bool Search_LinkList(LinkList &L,int e,int &i)//找到链表L中内容为e的结点，并用i返回其位置，i=1表示第一个非头结点，依次类推
{
i=1;
if(L->next==L) exit(-1);
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
if(!p) exit(-1);
p=L->next; //p指向链表的第一个结点（非头结点）
while(p!=L && p->data!=e)
{
p=p->next;
i++;
}
if(p==L) //没有找到符合要求的结点
return false;
return true;
}

void Search_LL_Flag(LinkList &L,int &i)//用i返回第一个flag为0的结点的位置,i=1表示第一个非头结点，以此类推
{
i=1;
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
if(!p) exit(-1);
p=L->next;
while(p->flag!=0)
{
p->flag=0; //修改访问标志位为0
p=p->next;
if(p==L) //跳过头结点
p=p->next;
i++;

if(i==4) //跳过头结点
i=1;
}
//return 1;
}

void Set_LL_Flag(LinkList &L,int i) //设置链表L中的序号为i的结点的flag标志为1；
{
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
if(!p) exit(-1);
p=L->next;
if(i==1)
p->flag=1;
if(i==2)
{
p=p->next;
p->flag=1;
}
if(i==3)
{
p=p->next;
p=p->next;
p->flag=1;
}
}

int Search_LL_ModifyClock(LinkList &L,int &modify_num)//找到改进的CLOCK算法所需要淘汰的页，用modify_num返回其位置
{
modify_num=1;
if(L->next==L) exit(-1);
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
if(!p) exit(-1);
p=L->next; //p指向链表的第一个结点（非头结点）
while(p!=L) //第一轮扫描A=0并且M=0的结点
{
if(p->flag==0 && p->modify==0)
break; //找到
p=p->next;
modify_num++;
}

if(p==L)
{
modify_num=1;
p=L->next;
while(p!=L) //第二轮扫描A=0并且M=1的结点，同时修改访问过的结点的访问位为0
{
if(p->flag!=0)
p->flag=0;
else if(p->modify==1)
break;
p=p->next;
modify_num++;

}
}
if(p==L)
{
modify_num=1;
p=L->next;
while(p!=L) //第三轮扫描A=0并且M=0的结点
{
if(p->flag==0 && p->modify==0)
break;
p=p->next;
modify_num++;
}
if(p==L)
{
modify_num=1;
p=L->next;
while(p!=L) //第四轮扫描A=0并且M=1的结点
{
if(p->flag!=0)
p->flag=0;
else if(p->modify==1)
break;
p=p->next;
modify_num++;

}
}

}

return 1;
}

void Set_LL_modify(LinkList &L,int i) //设置链表L中的序号为i的结点的modify标志为1；
{
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
if(!p) exit(-1);
p=L->next;
if(i==0)
p->modify=1;
if(i==1)
{
p=p->next;
p->modify=1;
}
if(i==2)
{
p=p->next;
p=p->next;
p->modify=1;
}
}

int DestroyLinkList(LinkList &L) //删除链表，并释放链表空间
{
LinkList p,q;
p=(LinkList)malloc(sizeof(LNode));
if(!p) exit(-1);
q=(LinkList)malloc(sizeof(LNode));
if(!q) exit(-1);
p=L->next;
while(p!=L)
{
q=p->next;
free(p);
p=q;
}
free(q);
return 1;
}
////////////////////////////////////////////////////////////////对队列的一些操作

int InitQueue(LinkQueue &Q) //队列初始化
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(-1);
Q.front->next=NULL;
return 1;
}

int EnQueue(LinkQueue &Q,int e) //插入元素e为Q的新的队尾元素
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(-1);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return 1;
}

int DeQueue(LinkQueue &Q,int &e) //若队列不空，则删除Q的队头元素，用e返回其值
{
if(Q.front==Q.rear) return -1;
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return 1;
}

bool SearchQueue(LinkQueue &Q,int e,int &i) //寻找队列Q中结点data域等于e的结点，并用i返回其在Q中的位置
{
i=1;
if(Q.front==Q.rear) exit(-1);
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(-1);
p=Q.front->next; //p指向队列的第一个节点（非头结点）

while(p!=NULL && p->data!=e)
{
p=p->next;
i++;
}
if(!p)
return false;
return true;
}

int DelMid_Queue(LinkQueue &Q,int &e) //删除Q的中间元素，并用e返回其值
{
if(Q.front==Q.rear) return -1;
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(-1);
p=Q.front->next;
e=p->next->data;
p->next=p->next->next;
return 1;
}

int DestroyQueue(LinkQueue &Q) //删除队列并释放空间
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return 1;
}
//////////////////////////////////////////////////////////////
int max1(int a,int b, int c) //返回a,b,c中的最大值
{
if(a<b) a=b;
if(a<c) a=c;
return a;
}
int getnum(int a,int b) //用b返回元素a在被引用数列中的下一个位置
{
for(;b<ref_size;b++)

{
if(a==ref[b])
break;
}
return b;
}
void ORA() /////////////最佳置换算法
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_RED);
cout<<"\n***********************最佳置换算法*************************"<<endl;
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_INTENSITY);//设置字体颜色为白色
int i,j;
int num_0,num_1,num_2,num_max;
int interrupt_num=0;
//num_0=num_1=num_2=0;
for(i=0;i < phy_size;i++) //前三个数进内存
phy[i]=ref[i];
for(i=0;i<phy_size;i++) //输出最初的三个数
cout<<phy[i]<<"\t";
cout<<endl;
for(j=phy_size;j<ref_size;j++)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_INTENSITY);
if(!(ref[j]==phy[0] || ref[j]==phy[1] || ref[j]==phy[2])) //若产生缺页中断，选择最久不会被使用的页被替换
{
num_0=getnum(phy[0],j+1);
num_1=getnum(phy[1],j+1);
num_2=getnum(phy[2],j+1);
num_max=max1(num_0,num_1,num_2);
if(num_0==num_max)
phy[0]=ref[j];
else
if(num_1==num_max)
phy[1]=ref[j];
else
if(num_2==num_max)
phy[2]=ref[j];
interrupt_num++;

SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_BLUE);//设置字体为蓝色
}
cout<<"进入页："<<ref[j]<<endl;
for(i=0;i<phy_size;i++) //输出内存状态
cout<<phy[i]<<"\t";
cout<<endl<<endl;
}
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_GREEN);
cout<<"最佳置换算法缺页中断次数："<<interrupt_num<<endl; //以绿色字体输出中断次数
interrupt[0]=((float)interrupt_num/20.0)*100.0;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////
void RAND() /////////////随机置换算法
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_RED);
cout<<"\n***********************随机置换算法************************"<<endl;
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_INTENSITY);
int i,j,temp;
int interrupt_num=0;
//num_0=num_1=num_2=0;
Sleep(1000);
srand(time(NULL)); //设置时间种子
for(i=0;i < phy_size;i++)
phy[i]=ref[i];
for(i=0;i<phy_size;i++)
cout<<phy[i]<<"\t";
cout<<endl;
for(j=phy_size;j<ref_size;j++)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_INTENSITY);
if(!(ref[j]==phy[0] || ref[j]==phy[1] || ref[j]==phy[2])) //产生缺页中断，随机选择页被替换
{
temp=rand()%3;

//cout<<temp<<endl;
phy[temp]=ref[j];
interrupt_num++;
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_BLUE);
}
cout<<"进入页："<<ref[j]<<endl;
for(i=0;i<phy_size;i++)
cout<<phy[i]<<"\t";
cout<<endl<<endl;
}
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_GREEN);
cout<<"随机置换算法缺页中断次数："<<interrupt_num<<endl; //以绿色字体输出中断次数
interrupt[1]=((float)interrupt_num/20.0)*100.0;
}

///////////////////////////////////////////////////////////////////////////////////////////////
void FIFO()
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_RED);
cout<<"\n***********************先进先出置换算法*************************"<<endl;
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_INTENSITY);
LinkQueue L;
QueuePtr p;
int i,j,e,m;
int interrupt_num=0;
InitQueue(L);
for(i=0;i<phy_size;i++)
{
EnQueue(L,ref[i]);
}
p=(QueuePtr)malloc(sizeof(QNode));
p=L.front->next;
for(j=0;p!=NULL && j<phy_size;j++)//前三个数进内存
{
cout<<p->data<<"\t";
p=p->next;

}
cout<<endl;
for(i=phy_size;i<ref_size;i++)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_INTENSITY);
if(!SearchQueue(L,ref[i],m)) //产生缺页中断，选择最先进入的页被替换
{
DeQueue(L,e);
//cout<<e<<endl;
EnQueue(L,ref[i]);
interrupt_num++;
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_BLUE);
}
cout<<"进入页："<<ref[i]<<endl;
p=L.front->next;
for(j=0;p!=NULL && j<phy_size;j++)
{
cout<<p->data<<"\t";
p=p->next;
}
cout<<endl<<endl;
}
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_GREEN);
cout<<"先进先出置换算法缺页中断次数："<<interrupt_num<<endl; //以绿色字体输出中断次数
interrupt[2]=((float)interrupt_num/20.0)*100.0;
free(p);
DestroyQueue(L);
}
////////////////////////////////////////////////////////////////////////////////////////////////
void LRU() /////////最近最久未使用算法
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY | FOREGROUND_RED);
cout<<"\n**********************最近最久未使用置换算法**********************"<<endl;
int QNode_num=0;

S