淮海工学院计算机工程学院
实验报告书
课程名：
《操作系统原理》
题
目：
虚拟存储器
班
级：
学
号：
姓
名：
评语:
成绩： 指导教师：
批阅时间:
一、 目的与要求
目的由于超大规模集成电器电路(VLSI)技术的发展，使存贮器的容量不断扩大， 价格大幅度下降。但从应用角度看，存贮器的容量和成本总会受到一定的限制。所以， 提高存贮器的使用效率始终是操作系统研究的重要课题之一，虚拟存贮器技术是用来扩 大主存容量的一种重要的方法。
本实习要求学生独立地用高级语言编写几个常用的存贮器分配算法，并能设计一个 存贮管理的模拟程序，能对各种算法进行分析比较，评测其性能优劣， 从而加深对这些
算法的了解。
要求
为了比较真实地模拟存贮器管理，可预先生成一个大致符合实际情况的指令地址
流。然后，通过模拟这样一种指令序列的执行来计算和分析比较各种算法的访问命中率。
二、 示例
1 ?题目
本示例给出采用页式分配存贮器管理方案，并通过分析、计算不同页面淘汰算法情 况下的访问命中率来比较各种算法的优劣，另外也考虑改变页面尺寸大小和实际存贮器 容量对计算结果的影响，从而可为选择好的算法、合适的页面尺寸和存贮器实际容量提 供依据。
本程序是按下述原则生成指令序列的：
50%的指令是顺序执行的。
25%的指令是均匀分布在前地址部分。
25%的指令是均匀分布在后地址部分。
示例中选用最佳淘汰算法（OPT）和最近最少使用页面淘汰算法（LRU）计算页 面命中率。公式为：
页面失败次数
命中率=]_
页地址流长度
假定虚拟存贮容量为3 2K，页面尺寸从1K到8K,实存容量从4页到32页。
2 .算法与框图
（1） 最佳淘汰算法（OPT）。这是一种理想的算法，可用来作为衡量其他算法优劣
的依据，在实际系统中是难以实现的，因为它必须先知道指令的全部地址流。 由于本示
例中已生成了全部地址流，故可计算最佳命中率。
该算法的准则是淘汰已满页表中以后不再访问或是最迟访问的页。这就要求将页表 中的页逐个与后继指令访问的所有页比较，如后继指令不再访问此页，则把此页淘汰， 不然得找出后继指令中最迟访问的页面予以淘汰。 可见最佳淘汰算法要化费较长的运算
时间。
（2） 最近最少使用页面淘汰算法（LRU）。这是一种经常使用的方法，有各种不同
的实施方案，这里是采用的是不断调整页表链的方法，即总是淘汰页表链链首的页， 而
把新访问的页插入链尾。如果当前调用页已在页表内，则把它再次调整到链尾。 这样就
能保证最近使
用的页，总是处于靠近链尾部分，而不常使用的页就移到链首，逐个被淘汰，在页表较 大时，调整页表链的代价也是不小的。
三、实验步骤与源程序
#i nclude "iostream"
#in elude "stdio.h"
#in elude "stdlib.h"
using namespace std;
#define Max 30 // 某进程调入内存中的最大页面数
#define Size 10 // 系统为某进程分配的最大物理块数
void Init(int Block[],int m)// 初始化物理块
{ int i; for(i=0;i<m;i++)
{
Block[i]=-1;
}
void creat(int Page[],int n)// 输入页面串引用号
{ int i; for(i=0;i<n;i++)
{ cin>>Page[i];
}
}
void Init1(int Block1[],int m1)
{ int i; for(i=0;i<m1;i++)
{
Block1[i]=-1;
}
}
void creat1(int Page[],int n1)
{ int i;
for(i=0;i<n1;i++)
{
Page[i];
}
}
void LRU(int Page[],int Block1[],int n1,int m1)
{
int i,j,max_stay=0,count=0;
int get=-1,flag=-1,block_num=-1;
int time[Size]; for(i=0;i<m1;i++)// 初始化 time[]
{
time[i]=0;
} for(i=0;i<n1;i++)
{ for(j=0;j<m1;j++)// 有空闲物理块时，页面直接驻入内存空闲块
{ if(Block1[j]==-1)
get=j; // 物理块 j 即将(/等待 )驻入新页面 break;
}
for(j=0;j<m1;j++) // 查找序号相同的页面
{ if(Block1[j]==Page[i])// 物理块 j 中页面与当前期望调入内存的页面相同 { time[j]=0; flag=j; break;
}
for(j=0;j<m1;j++) // 找到驻留内存时间最久的页面置换出
if(time[j]>max_stay) max_stay=time[j];
block_num=j; //block_num 标记当前序号物理块中页面驻留时间 最久
}
if(flag==-1) // 不存在相同页面
{ if(get!=-1) // 物理块即将 (/ 等待)驻入新页面
Block1[get]=Page[i]; // 存入页面
time[get]=0; // 当前物理块重新计时 for(j=0;j<=get;j++) // 已驻入页面的驻留时间加 1 {
time[j]++;
}
get=-1;
else // 页面调度置换，序号 block_num 的物理块是驻留时间最久的Block1[block_num]=Page[i];
time[block_num]=0;
for(j=0;j<Size;j++)
{
time[j]++;
}
block_num=-1;
max_stay=0;
count++;
}
else // 待调入页面与序号 flag 的物理块中页面相同
for(j=0;j<m1;j++)
{
time[j]++;
flag=-1;
for(j=0;j<m1;j++)// 输出物理块中的页面驻入情况
{
cout<<" "<<Block1[j];
}
cout<<endl;
}
if(n1>m1)
count=count+m1;
cout<<" 缺页中断次数为 :"<<count<<endl;
}
void FIFO(int Page[],int Block[],int n,int m)
{
int i,j,max_stay=0,count=0;
int get=-1,flag=-1,block_num=-1;
int time[Size];
for(i=0;i<m;i++)
{ time[i]=0;
}
for(i=0;i<n;i++)
{ for(j=0;j<m;j++)
{ if(Block[j]==-1)
get=j; break;
}
for(j=0;j<m;j++)
{ if(Block[j]==Page[i])
{
flag=j;
break;
}
}
for(j=0;j<m;j++)
{
if(time[j]>max_stay)
{
max_stay=time[j]; block_num=j;
}
}
if(flag==-1)
{ if(get!=-1)
{
Block[get]=Page[i]; time[get]=0; for(j=0;j<=get;j++) { time[j]++;
}
get=-1;
else
Block[block_num]=Page[i]; time[block_num]=0; for(j=0;j<Size;j++) {
time[j]++;
}
block_num=-1;
max_stay=0; count++;
}
else
for(j=0;j<m;j++)
{
time[j]++;
}
flag=-1;
for(j=0;j<m;j++)
{
cout<<" "<<Block[j];
}
cout<<endl;
}
if(n>m)
count=count+m;
cout<<" 缺页中断次数为 :"<<count<<endl;
}
void menu()
cout?" 1.LRU 页面置换算法 "<<e ndl;
coutvv" 2.FIFO 页面置换算法 ——"<<e ndl;
coutvv" 3. 退出——"<<e ndl;
cout?" 默认：-1表示物理块空闲 "<<endl;
cout?"请选择算法"<<endl;
}
void main()
{ int n,m,Page[Max],Block[Size],n1,m1,Block1[Size];
char t
coutvve ndlvv" 请输入系统为进程分配的物理块数 m<=10:";
cin>>m;
m1=m;
In it(Block,m);
In it1(Block1,m1);
coutvv"请输入总页面数nv=30:";
cin>>n;
n1= n;
cout<<"\n 请输入页面号引用串:";
creat(Page ,n);
creat1(Page, n1);
while(1)
{
menu();
cin> >t;
switch(t)
{
case '1':LRU(Page,Block1, n1,m1);
con ti nue;
case 2:FIFO(Page,Block, n,m);
con ti nue;
case 3:exit(0);
}
}
}
四、测试数据与实验结果
-' F :\Debu g\C p p Le "
清莽入系统为进程分配的物理块数n<=iB：3
请输入忌页面ffih<-30=±2
请输入页面号引用串注35432154321
图1输入要分配的物理块数、页面总数、页面序列号
请输入页面号宝単 1.LRII 页面
请输入页面号宝単
1.LRII 页面
*^=4 3543215422
鹹二二
4-1-1
1
您.FIFO页面
9 ■退岀——
丄.駅认—表示物理块空闲- 请选择算法
3 2 1
缺贝中断次数为血
图2 LRU算法的实现
r :■' X —①他匸 J = I
请选择聲法
2
4 -1 -1
4 3-1
4 3 5
4 3 5
4 3 5
2 3 S
2 15
2 1 S
TOC \o "1-5" \h \z 14
14
3 2 4
3 2 1 缺页中断尿数宜学" ~~ I I
图3 FIFO算法的实现
五、结果分析与实验体会
页面置换算法理解比较容易，这次根据学号要求实现的是LRU和FIFO算法的实现。
其实这两种算法的程序编写比较容易， 虽然不全是自己编写的，一部分是参考的网
上的例题，但是通过对每一语句的理解，自己弄懂了整个程序的执行原理。但是，在编
写过程中自己还是遇到了一些问题。
最大的一个问题就是两个算法的正确实现，在程序的编写时，两个程序是分开进行 编写的，分别执行起来没有什么问题，但是把两个程序融合在一起后，却出现了问题,
即在执行完成一个算法后再执行另外一个算法时， 开始的数据是紧接着上次算法结果的 数据进行实验的。这个问题困扰了我好长时间，直到现在还没有很好的解决掉， 程序只 能分别执行一次，如果再进行执行的话，就会出现问题。
自己的编程技术不好，程序编的也很繁琐， 但是基本的要求已经实现了，希望这次
的实验是自己动手的一个开始，自己应该更加努力，再接再厉。