- 1 -
一 目的与要求
（1）请求页式虚存管理是常用的虚拟存储管理方案之一。
（2）通过请求页式虚存管理中对页面置换算法的模拟，加深理解虚拟存储技术的特点。
（3）加深对请求页式虚存管理的页面调度算法的理解。
二 实验内容或题目
(1) 本实验要求使用 C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、
并在缺页中断发生时分别使用 FIFO 和 LRU算法进行页面置换的情形。
(2) 虚页的个数可以事先给定（例如 10 个），对这些虚页访问的页地址流（其长度可以事先给
定，例如 20 次虚页访问）可以由程序随机产生，也可以事先保存在文件中。
(3) 要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。
(4) 程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。
三 实验步骤与源程序
（1）实验步骤
1、理解好相关实验说明。
2、根据实验说明，画出相应的程序流程图。
3、按照程序流程图，用 C语言编程并实现。
（2）流程图如下：
① 虚页和实页结构
pnpn
pfnpfn
nexttime
虚页结构 实页结构
在虚页结构中， pn 代表虚页号，因为共 10 个虚页，所以 pn 的取值范围是 0—9。pfn 代表实
页号，当一虚页未装入实页时，此项值为 -1；当该虚页已装入某一实页时，此项值为所装入的实页
的实页号 pfn 。time 项在 FIFO 算法中不使用，在 LRU中用来存放对该虚页的最近访问时间。
在实页结构中中， pn 代表虚页号， 表示 pn 所代表的虚页目前正放在此实页中。
pfn 代表实页号，
取值范围（ 0—n-1 ）由动态指派的实页数 n 所决定。
next 是一个指向实页结构体的指针，用于多个
- 2 -
实页以链表形式组织起来，关于实页链表的组织详见下面第 4 点。
② 程序流程图如下：
create a produce
run FIFO or LRU
look menu
end
（3）源程序如下 :
#include<iostream.h>
#define M 40
int N;
struct Pro
{
int num,time;
};
int Input(int m,Pro p[M])
{
cout<<" 请输入实际页数 :";
do
{
cin>>m;
if(m>M)cout<<" 数目太多，请重试 "<<endl;
else break;
}while(1);
//cout<<" 请输入各页面号 :";
for(int i=0;i<m;i++)
{
cout<<" 第"<<i<<" 个页面号为 :";
cin>>p[i].num;
p[i].time=0;
}
return m;
- 3 -
}
void print(Pro *page1)// 打印当前的页面
{
Pro *page=new Pro[N];
page=page1;
for(int i=0;i<N;i++)cout<<page[i].num<<" ";
cout<<endl;
}
int Search(int e,Pro *page1 )
{
Pro *page=new Pro[N];
page=page1;
for(int i=0;i<N;i++)if(e==page[i].num)return i;
return -1;
}
int Max(Pro *page1)
{
Pro *page=new Pro[N];
page=page1;
int e=page[0].time,i=0;
while(i<N)// 找出离现在时间最长的页面
{
if(e<page[i].time)e=page[i].time;
i++;
}
for( i=0;i<N;i++)if(e==page[i].time)return i;
return -1;
}
int Compfu(Pro *page1,int i,int t,Pro p[M])
{
Pro *page=new Pro[N];
page=page1;
int count=0;
for(int j=i;j<M;j++)
{
if(page[t].num==p[j].num )break;
else count++;
}
return count;
}
int main()
{
cout<<" 可用内存页面数 :";
cin>>N;
- 4 -
Pro p[M];
Pro *page=new Pro[N];
char c;
int m=0,t=0;
float n=0;
m=Input(m,p);
do{
for(int i=0;i<N;i++)// 初试化页面基本情况
{
page[i].num=0;
page[i].time=2-i;
}
i=0;
cout<<"************************"<<endl;
cout<<"*****f:FIFO 页面置换 *****"<<endl;
cout<<"*****l:LRU 页面置换 ******"<<endl;
cout<<"*****o:OPT 页面置换 ******"<<endl;
cout<<"***** 按其它键结束 *******"<<endl;
cout<<"************************"<<endl;
cout<<" 请选择操作类型 (f,l,o):";
cin>>c;
if(c=='f')//FIFO 页面置换
{
n=0;
cout<<" 页面置换情况 : "<<endl;
while(i<m)
{
if(Search(p[i].num,page)>=0)i++;// 找到相同的页面
else
{
if(t==N)t=0;
else
{
n++;//
page[t].num=p[i].num;
print(page);
t++;
}
}
}
cout<<" 缺页次数： "<<n<<" 缺页率 :"<<n/m<<endl;
}
if(c=='l')//LRU 页面置换
{ n=0;
cout<<" 页面置换情况 : "<<endl;
while(i<m)
- 5 -
{
int k;
k=t=Search(p[i].num,page);
if(t>=0)
page[t].time=0;
else
{
n++;
t=Max(page);
page[t].num=p[i].num;
page[t].time=0;
}
if(t==0){page[t+1].time++;page[t+2].time++;}
if(t==1){page[2].time++;page[0].time++;}
if(t==2){page[1].time++;page[0].time++;}
if(k==-1) print(page);
i++;
}
cout<<" 缺页次数： "<<n<<" 缺页率： "<<n/m<<endl;
}
if(c=='o')//OPT 页面置换
{
n=0;
while(i<m)
{
if(Search(p[i].num,page)>=0)i++;
else
{
int temp=0,cn;
for(t=0;t<N;t++)
{
if(temp<Compfu(page,i,t,p))
{
temp=Compfu(page,i,t,p);
cn=t;
}
}
page[cn]=p[i];
n++;
print(page);
i++;
}
- 6 -
}
cout<<" 缺页次数： "<<n<<" 缺页率： "<<n/m<<endl;
}
}while(c=='f'||c=='l'||c=='o');
return 0;
});
四 测试数据与实验结果
五 结果分析与实验体会