存储管理实验报告
北方工业大学
《计算机操作系统》实验报告
实验名称存储管理实验序号 2
实验日期2013.11.27实验人
一、实验目的和要求
1．请求页式存储管理是一种常用的虚拟存储管理技术。
本实验目的
是通过请求页式存储管理中页面置换算法的模拟设计，了解虚拟存储
技术的特点，掌握请求页式存储管理的页面置换算法。
二、相关背景知识
1．随机数产生办法
关于随机数产生办法， Linux 或 UNIX 系统提供函数 srand() 和 rand() ，分
别进行初始化和产生随机数。
三、实验内容
(1)．通过随机数产生一个指令序列，共320条指令。
指令的地址按下述原则生成：
1.50% 的指令是顺序执行的；
2.25% 的指令是均匀分布在前地址部分；
3.25% 的指令是均匀分布在后地址部
分；具体的实施方法是：
1.在[0， 319]的指令地址之间随机选取一起点 m；
2.顺序执行一条指令，即执行地址为 m+1 的指令；
3.在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；
4.顺序执行一条指令，其地址为 m’+1；
5.在后地址 [m ’+2, 319]中随机选取一条指令并执行；
6.重复上述步骤 1~5，直到执行 320 次指令。
(2)将指令序列变换成页地址流，设
1.页面大小为 1K ；
2.用户内存容量为 4 页到 32 页；
3.用户虚存容量为 32K 。
在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存
中存放的方式为：
第 0 条至第 9 条指令为第 0 页（对应虚存地址为 [0， 9]）；
第 10 条至第 19 条指令为第 1 页（对应虚存地址为 [10， 19]）；
第 310 条至第 319 条指令为第 31 页（对应虚存地址为 [310，319]）；
按以上方式，用户指令可以组成 32 页。
(3)计算并输出下述各种算法在不同内存容量下的命中率。
1.先进先出页面淘汰算法（ FIFO ）
2.最近最久未使用页面淘汰法（ LRU ）
命中率 =1 - 页面失效次数 /页地址流长度
在本实验中，页地址流长度为 320，页面失效次数为每次访问相应指令时，
该指令对应的页不在内存的次数。
四、关键数据结构与函数的说明
ty ：页地址流长度。
int d[320] ：装指令序列。
int page[320] ：装页地址流。
int p[32] ：内存页面。
que：记录缺页次数。
time[32] ：记录页面距离上次被访问的时间。
creat() ：对内存页面进行初始化
FIFO() ：先进先出页面淘汰算法。
LRU() ：最近最久未使用算法。
srand(10*getpid()): 每次运行时进程号不同，用来作为初始化随机数队列的" 种子"。
rand() ：可以生成0~RAND_MAX之间的一个随机
数。
五、编译与执行过程截图
六、实验结果与分析
运行结果： FIFO 算法与 LRU 算法的命中率相差不大，一般在0.03 以内，随着内存页面的增加，命中率上升， 4 页时一般在50%左右， 32 页一般在90% 左右。
分析： FIFO 算法是以先进内存先替换而LRU 是以最久没访问先替换，当内存中页面数量增加时，访问的内容在内存的概率会越高。
七、调试时遇到的问题及解决方法（提供BUG 截屏）
解决： linux 不支持头文件 PROCESS.H ，但是使用 srand() 需要
用该头文件，于是用支持srand() 的头文件 unistd.h 替代
PROCESS.H 。
解决后试调：
八、调试后的程序源代码
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include<string.h>
#define NULL 10000
const int ty=320;
int d[320]; //指令序列
int page[320]; // 页地址流
int p[32]; // 内存页面
int que; //缺页次数
int time[32]; //记录页面距离上次被访问的时间
//******* 初始化内存页面
void creat(int leng) //leng 为内存页面数量{
int i;
que=0;
for(i=0;i<leng;i++)
{
//让内存页面置空
p[i]=NULL;
time[i]=0;
}
}
//****** 先进先出算法
//leng 为内存页面数量
void FIFO(int leng)
{
int i,j,k;
int n; //n 为要被替换的页面号，按 0,1,2...leng,0,1,2...leng循环变化creat(leng); //初始化内存页面
n=0;
for(i=0;i<ty;i++)
{
k=0;
for(j=0;j<leng;j++)
{
if(p[j]==NULL)
break;
else if(p[j]==page[i])// 在内存中有该页
{
k=1;
break;
}
}
if(k==0)
{
北方工业大学
que++;
p[n]=page[i];
n++;
}
if(n==leng)
n=0;
}
printf("%-7.3f\t",1-(float)que/ty);
}
//******** 最近最久未使用算法
//leng 为内存页面数量void LRU(int leng)
{
int i,j,k;
//存 time 的最大值
int tmax;
int t; //t 为要被访问的页面号
creat(leng); //初始化内存页面
for(i=0;i<ty;i++)
{
k=0;
for(j=0;j<leng;j++)
{
if(p[j]==NULL)
break;
else if(p[j]==page[i])// 在内存中有该页
{
k=1;
t=j;
break;
}
}
if(k==0)
{
que++;
tmax=time[0];
t=0;
for(j=0;j<leng;j++)//查找最久没访问的页面号赋予t
{
if(tmax<time[j])
{
tmax=time[j];
t=j;
}
}
p[t]=page[i];
}
for(j=0;j<leng;j++)//将每个页面 time 自增
time[j]++;
time[t]=0; //将这次被访问的页面time 清零
}
printf(" %-7.3f\t",1-(float)que/ty);
}
void main( )
{
int m,i;
srand(10*getpid()); // 用来作为初始化随机数队列的
" 种子"
m=(int)((float)(ty-1)*(rand()/(RAND_MAX+1.0))); // 选 0-319 中一数
for (i=0; i<ty; i+=4) //产生指令队列
{
d[i]=m; // 任选一指令访问点m
d[i+1]=d[i]+1;//顺序执行一条指令m+1
d[i+2]=(int)((float)d[i]*(rand()/(RAND_MAX+1.0)));/* 执行前地址指
令 m',即选择 (0，m+1)之间的数 */ d[i+3]=d[i+2]+1;//顺序执行一条指令
m= (int)((float)((ty-1)-d[i+2])*(rand()/(RAND_MAX+1.0))) + d[i+2];
//选(m'+2,319) 之间数}
for(i=0;i<ty;i++) //将指令序列变换成页地址流
page[i]=d[i]/10;
printf("PAGE\tFIFO\t LRU\t\n");
for(i=4;i<=32;i++)//内存从 4 页到 32 页
{
printf(" %2d\t",i);
FIFO(i);
LRU(i);
printf("\n");
}
}
九、实验体会
这一次实验是对请求页式存储管理的一次模拟实验，设计和测试了 FIFO 和 LRU 这两种请求页式存储管理的页面置换算法的命中率。
通过这次实验我了解虚拟存储技术的特点，并掌握了这两种请求页式存储管理的页面置换算法，知道它们的操作是如何进行的，同时实验中查找资料时，也了解了其他的一些
替换算法，还知道了如何使用 srand（）、rand （）如何使用，如何生成随机
数。
对于存储管理的课程内容更为熟练和明白。