操作系统实验报告四
【实验题目】
虚拟内存页面置换算法
【实验目的】
通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。
【实验内容】
问题描述：
设计程序模拟先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。
程序要求如下：
1）利用先进先出FIFO，最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。
2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。
3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。
4）输出：每种算法的缺页次数和缺页率。
【实验要求】
1) 上机前认真复习页面置换算法，熟悉FIFO，OPI，LRU三种页面分配和置换算法的过程；
2) 上机时独立编程、调试程序；
3) 根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图）。
【源代码】
//--------------- YeMianZhiHuan.cpp -----------------
#include "iostream.h"
const int DataMax=100;
const int BlockNum = 10;
int DataShow[BlockNum][DataMax]; // 用于存储要显示的数组
bool DataShowEnable[BlockNum][DataMax]; // 用于存储数组中的数据是否需要显示
//int Data[DataMax]={4,3,2,1,4,3,5,4,3,2,1,5,6,2,3,7,1,2,6,1}; // 测试数据
//int N = 20; // 输入页面个数
int Data[DataMax]; // 保存数据
int Block[BlockNum]; // 物理块
int count[BlockNum]; // 计数器
int N ; // 页面个数
int M;//最小物理块数
int ChangeTimes;
void DataInput(); // 输入数据的函数
void DataOutput();
void FIFO(); // FIFO 函数
void Optimal(); // Optimal函数
void LRU(); // LRU函数
///*
int main(int argc, char* argv[])
{
DataInput();// DataInput();
// FIFO();
// Optimal();
// LRU();
// return 0;
int menu;
while(true)
{
cout<<endl;
cout<<"* 菜单选择 *"<<endl;
cout<<"*******************************************************"<<endl;
cout<<"* 1-FIFO *"<<endl;
cout<<"* 2-Optimal *"<<endl;
cout<<"* 3-LRU *"<<endl;
cout<<"* 0-EXIT *"<<endl;
cout<<"*******************************************************"<<endl;
cin>>menu;
switch(menu)
{
case 1: FIFO();break;
case 2: Optimal();break;
case 3: LRU();break;
default: break;
}
if(menu!=1&&menu!=2&&menu!=3) break;
}
}
//*/
void DataInput()
{
cout<<"请输入最小物理块数：";
cin>>M;
while(M > BlockNum) // 大于数据个数
{
cout<<"物理块数超过预定值，请重新输入：";
cin>>M;
}
cout<<"请输入页面的个数：";
cin>>N;
while(N > DataMax) // 大于数据个数
{
cout<<"页面个数超过预定值，请重新输入：";
cin>>N;
}
cout<<"请输入页面访问序列："<<endl;
for(int i=0;i<N;i++)
cin>>Data[i];
}
void DataOutput()
{
int i,j;
for(i=0;i<N;i++) // 对所有数据操作
{
cout<<Data[i]<<" ";
}
cout<<endl;
for(j=0;j<M;j++)
{
cout<<" ";
for(i=0;i<N;i++) // 对所有数据操作
{
if( DataShowEnable[j][i] )
cout<<DataShow[j][i]<<" ";
else
cout<<" ";
}
cout<<endl;
}
cout<<"缺页次数: "<<ChangeTimes<<endl;
cout<<"缺页率: "<<ChangeTimes*100/N<<"%"<<endl;
}
void FIFO()
{
int i,j;
bool find;
int point;
int temp; // 临时变量
ChangeTimes = 0;
for(j=0;j<M;j++)
for(i=0;i<N;i++)
DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据
for(i=0;i<M;i++)
{
count[i] = 0; // 大于等于BlockNum，表示块中没有数据，或需被替换掉
// 所以经这样初始化（3 2 1），每次替换>=3的块，替换后计数值置1，
// 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段
}
for(i=0;i<N;i++) // 对有所数据操作
{
// 增加count
for(j=0;j<M;j++)
count[j]++;
find = false; // 表示块中有没有该数据
for(j=0;j<M;j++)
{
if( Block[j] == Data[i] )
{
find = true;
}
}
if( find ) continue; // 块中有该数据，判断下一个数据
// 块中没有该数据
ChangeTimes++; // 缺页次数++
if( (i+1) > M ) // 因为i是从0开始记，而M指的是个数，从1开始，所以i+1
{
//获得要替换的块指针
temp = 0;
for(j=0;j<M;j++)
{
if( temp < count[j] )
{
temp = count[j];
point = j; // 获得离的最远的指针
}
}
}
else point = i;
// 替换
Block[point] = Data[i];
count[point] = 0; // 更新计数值
// 保存要显示的数据
for(j=0;j<M;j++)
{
DataShow[j][i] = Block[j];
DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据
}
}
// 输出信息
cout<< endl;
cout<<"FIFO => "<< endl;
DataOutput();
}
void Optimal()
{
int i,j,k;
bool find;
int point;
int temp; // 临时变量，比较离的最远的时候用
ChangeTimes = 0;
for(j=0;j<M;j++)
for(i=0;i<N;i++)
DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据
// for(i=0;i<M;i++)
// {
// count[i] = 0 ; //
// }
for(i=0;i<N;i++) // 对有所数据操作
{
find = false; // 表示块中有没有该数据
for(j=0;j<M;j++)
{
if( Block[j] == Data[i] )
find = true;
}
if( find ) continue; // 块中有该数据，判断下一个数据
// 块中没有该数据，最优算法
ChangeTimes++; // 缺页次数++
for(j=0;j<M;j++)
{
// 找到下一个值的位置
find = false;
for( k =i;k<N;k++)
{
if( Block[j] == Data[k] )
{
find = true;
count[j] = k;
break;
}
}
if( !find ) count[j] = N;
}
if( (i+1) > M ) // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1
{
//获得要替换的块指针
temp = 0;
for(j=0;j<M;j++)
{
if( temp < count[j] )
{
temp = count[j];
point = j; // 获得离的最远的指针
}
}
}
else point = i;
// 替换
Block[point] = Data[i];
// 保存要显示的数据
for(j=0;j<M;j++)
{
DataShow[j][i] = Block[j];
DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据
}
}
// 输出信息
cout<< endl;
cout<<"Optimal => "<< endl;
DataOutput();
}
void LRU()
{
int i,j;
bool find;
int point;
int temp; // 临时变量
ChangeTimes = 0;
for(j=0;j<M;j++)
for(i=0;i<N;i++)
DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据
for(i=0;i<M;i++)
{
count[i] = 0 ;
}
for(i=0;i<N;i++) // 对有所数据操作
{
// 增加count
for(j=0;j<M;j++)
count[j]++;
find = false; // 表示块中有没有该数据
for(j=0;j<M;j++)
{
if( Block[j] == Data[i] )
{
count[j] = 0;
find = true;
}
}
if( find ) continue; // 块中有该数据，判断下一个数据
// 块中没有该数据
ChangeTimes++; // 缺页次数++
if( (i+1) > M ) // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1
{
//获得要替换的块指针
temp = 0;
for(j=0;j<M;j++)
{
if( temp < count[j] )
{
temp = count[j];
point = j; // 获得离的最远的指针
}
}
}
else point = i;
// 替换
Block[point] = Data[i];
count[point] = 0;
// 保存要显示的数据
for(j=0;j<M;j++)
{
DataShow[j][i] = Block[j];
DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据
}
}
// 输出信息
cout<< endl;
cout<<"LRU => "<< endl;
DataOutput();
}
【效果截图】
以作业为测试数据：
第二篇：计算机操作系统实验模拟比较页面置换页算法及缺页率(1)
计算机操作系统实验
模拟比较页面置换页算法及缺页率
实验名称: 模拟比较页面置换页算法及缺页率
实验目的: （1）掌握先进先出页面置换算法；
（2）掌握最近未用页面置换算法；
（3）了解最近最久未使用页面置换算法以及其他页面置换算法；
（4）熟悉C/C++编程。
实验学时： 6学时
实验内容: 编写程序，设置不同的页面数，使用不同的页面替换策略算法进行模拟页面替换。先进先出，最近未用页面置换算法等，并计算缺页率。
实验环境:
(1)．PC微机
(2)．Windows 操作系统
(3)．C/C++开发环境
实验原理及算法参考程序段:
#include <conio.h>
#include <stdio.h>
#include <dos.h>
#include <stdlib.h>
#include <math.h>
int add[256]/*地址*/,page[256]/*页面*/;
int k,j,ram,t;
float rate;/*缺页率*/
struct s1
{ int page;
int free;
int tag;
} fifo[33],opt[33],lru[33];
struct s2
{ int time;
};
void address();
float FIFO(int ram);/*先进先出*/
float LRU(int ram);/*最近最久未使用页面置换*/
void address() /*产生指令地址*/
{ int i;
add[0]=1000;
for (i=1; i<=255; i++)
{ int x=random(1024);
if ((x>=0)&&(x<512))
add[i]=add[i-1]+1;
if ((x>=512)&&(x<768))
add[i]=random(add[i-1]-1)+1;
if ((x>=768)&&(x<1024))
add[i]=add[i-1]+random(30*1024-add[i-1]-1)+1;
}
}
float FIFO(int ram)
{ int absent=0,t=0,i,z,l,yn;
for (i=0; i<ram; i++)
{ fifo[i].page=-1;
fifo[i].free=1;
fifo[i].tag=0;
}
i=0;
while (i<j)
{ yn=0;
for (z=0; z<ram; z++) /*the page is in the ram?*/
if (fifo[z].page==page[i])
{yn=1;
for (z=0; z<ram; z++)
if (fifo[z].free==0)
fifo[z].tag+=1;
}
if (yn!=1)
{ absent+=1; /*count the absent page*/
l=0;
while ((l<ram)&&(fifo[l].free==0))
l++;
if ((l<ram)&&(fifo[l].free==1)) /*any free ram?*/
{ fifo[l].page=page[i];
fifo[l].free=0;
for (l=0; l<ram; l++)
if (fifo[l].free==0 )
fifo[l].tag+=1;
}
else /*there is no free ram*/
{ t=0;
for (l=0; l<ram; l++)
if ( fifo[l].tag<fifo[t].tag)
t=l;
fifo[t].page=page[i];
fifo[t].free=0;
fifo[t].tag=1;
l=0;
}
}
i++;
}
rate=(float)absent/j*100;
return rate;
}
float LRU(int ram)
{ int absent=0,yn,t,i,l,z,now=0;
struct s2 P[250];
for (i=0;i<j;i++)
P[i].time=0;
for (i=0; i<ram; i++)
{ lru[i].page=-1;
lru[i].free=1;
}
i=0;
while(i<j)
{ for(l=0; l<ram; l++)
yn=0;
{ for(z=0; z<ram; z++)
if (lru[z].page==page[i])
{ now+=1;
P[lru[z].page].time=now;
yn=1;
}
if (yn!=1)
{ absent+=1; now+=1;
l=0;
while ((l<=ram)&&(lru[l].free==0))
l++;
if ((l<=ram)&&(lru[l].free==1)) /*any free ram?*/
{ lru[l].page=page[i];
P[lru[l].page].time=now;
lru[l].free=0;
}
else /*there is no ram*/
{ t=0;
for (l=0; l<ram; l++)
if ( P[lru[l].page].time<P[lru[t].page].time)
t=l;
lru[t].page=page[i];
P[lru[t].page].time=now;
}
}
}
i++;
}
rate=(float)absent/j*100;
return rate;
}
void main()
{ int i,p[256];/*页号*/
clrscr();
address();
for (k=1; k<=8;) /*页面大小: 1k,2k,4k,8K*/
{ printf("the size of a page is %d k\n ",k);
printf("the page num is ...\n");
for (i=0; i<256; i++)
{p[i]=add[i]/(k*1024);/*将指令地址生成相应的页号*/
printf("%d ",p[i]);
}
j=0;
for (i=0; i<256; i++)
{ while (p[i]==p[i+1])
i++;
page[j]=p[i];
j++;
}
printf("\nafter connect the same pages the page num is:\n");
for (i=0; i<j; i++)
printf("%d ",page[i]);
printf("\n");
getch();
for (ram=1; ram<=32; ram++)
{ if (ram==10) getch();
printf("\nblock=%d pages= %d,absent rate: ",ram,j);
printf("FIFO=%0.2f%%",FIFO(ram));
printf("LRU =%0.2f%%",LRU(ram));
printf("OPT =%0.2f%%",OPT(ram));
}
k=k*2;
getch();
}
}
实验小结：
通过本次实验掌握了先进先出和最近最久未使用页面置换算法，同时也对其他的页面置换算法也更加熟悉。在实验过程中熟悉了C语言的编程环境,并能够用C编程模拟比较也面置换算法，对编程也有一定的提高。
代码：
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "ctype.h"
//定义页,采用双向链表存储结构
struct page
{
unsigned int number;//页号
unsigned int baseaddress;//页开始地址
//其它信息
struct page *nextpage,*priorpage;//下一页和前一页
};
//定义页表
struct pagetable
{
unsigned int pid;//进程号
unsigned int pagenum;//页表大小
unsigned int pagetablesize;//页表最大表目
struct page *head;//页表头指针，指向头结点，头结点指向第一页
};
//FIFO页面访问程序,函数调用时要传递过来页表pt，要访问的页面号accesspage，返回是否发生缺页中断（1是0否）
int access(struct pagetable *pt, unsigned int accesspage)
{
struct page *newpage;//新页面
struct page *currentpage=pt->head->nextpage;//当前页
struct page * replacedpage;//要淘汰的页
//在当前页中寻找要访问的页号
while(currentpage&¤tpage->number!=accesspage)
{
currentpage=currentpage->nextpage;
}
//找到页号则打印√,并返回0
if(currentpage!=NULL&¤tpage->number==accesspage)
{
printf("√");
return 0;
}
//没找到则判断页表是否已经满了,没满则调入新页并打印×返回1
else if(pt->pagenum<pt->pagetablesize)
{
newpage=(struct page *)malloc(sizeof(struct page));
newpage->number=accesspage;
newpage->nextpage=newpage->priorpage=NULL;
newpage->nextpage=pt->head->nextpage;
if(pt->head->nextpage)
{
pt->head->nextpage ->priorpage=newpage;
}
pt->head->nextpage=newpage;
newpage->priorpage=pt->head;
pt->pagenum++;
printf("×");
return 1;
}
//如页表已经满,则采用fifo算法进行淘汰选择
else
{
currentpage=pt->head->nextpage;
replacedpage=NULL;
while(currentpage->nextpage)
{
currentpage=currentpage->nextpage;
}
replacedpage=currentpage;
if(replacedpage->nextpage)
{
replacedpage->nextpage->priorpage=replacedpage->priorpage;
}
replacedpage->priorpage->nextpage=replacedpage->nextpage;
free(replacedpage);
newpage=(struct page *)malloc(sizeof(struct page));
newpage->number=accesspage;
newpage->nextpage=newpage->priorpage=NULL;
newpage->nextpage=pt->head->nextpage;
if(pt->head->nextpage)
{
pt->head->nextpage->priorpage=newpage;
}
pt->head->nextpage=newpage;
newpage->priorpage=pt->head;
printf("×");
return 1;
}
}
main()
{
struct pagetable pt;
unsigned int totalabsence=0,totalpagenum=10;
unsigned int restpage[100];
unsigned int i=0;
pt.pagenum=0;
pt.pagetablesize=3;
pt.head=(struct page*)malloc(sizeof(struct page));
pt.head->nextpage=pt.head->priorpage=NULL;
//从文件获取要读入的页面流
FILE *fp;
fp=fopen("IN.dat","r");
if(fp==NULL)
{printf("can not open file IN.DAT!");return;}
while(!feof(fp))
{
fscanf(fp,"%d",&restpage[i]);
i++;
}
fclose(fp);
totalpagenum=i;
printf("this program for fifo \n\n");
//打印要访问的页
for(i=0;i<totalpagenum;i++)
{
printf("%2d",restpage[i]);
}
printf("\n");
//调用函数访问页
for(i=0;i<totalpagenum;i++)
{
totalabsence+=access(&pt,restpage[i]);
}
printf("\nabsence times:%d\ntotal access times:%d\nabsence ratio:%.2f%%\n",totalabsence,totalpagenum,totalabsence*100.0/totalpagenum);
getchar();
}