2012级操作系统实验报告

实验三 内存管理

【实验目的与要求】

⒈了解虚拟存储技术的特点。

⒉掌握请求页式存储管理的页面置换算法。

3.了解页面大小和内存实际容量对命中率的影响。 【实验原理】

分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，成为页面或页。

在进程运行过程中，若其所要访问的页面不在内存而需要把他们调入内存，但内存已无空闲时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page Replacement Algorithm)。

一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。

⒈ 最佳置换算法OPT(Optimal) ⒉ 先进先出页面置换算法FIFO ⒊ 最近最久未使用置换算法LRU ⒋ 最少访问页面置换算法LFU ⒌ 最近最不经常使用算法NUR 【实验主要仪器与材料】

⒈ 带Linux操作系统的PC机。 ⒉ GCC编译器。 【实验内容】

1、通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：

? 50%的指令是顺序执行的

? 25%的指令是均匀分布在前地址部分 ? 25%的指令是均匀分布在后地址部分 具体的实施方法是：

? 在【0,319】的指令地址之间随机选取一起点m； ? 顺序执行一条指令，即执行地址为m+1的指令；

? 在前地址【0，m+1】中随机选取一条指令并执行，该指令的地址为

m’；

? 顺序执行一条指令，其地址为m’+1；

? 在后地址[m’+2,319]中随机选取一条指令并执行； ? 重复上述步骤，直到执行320次指令。 2、将指令序列变换成为页地址流 设：

? 页面大小为1K；

? 用户内存容量为4页到32页； ? 用户虚拟容量为32K。

在用户虚存中，按每K存放10条指令排列虚拟地址，即320条指令在虚存

1

中的存放方式为：

第0条~第9条指令为第0页（对应虚存地址为【0,9】）； 第10条~第19条指令为第1页（对应虚存地址为【10,19】）； ?

第310条~第319条指令为第31页（对应虚存地址为【310,319】）。 按以上方式，用户指令可组成32页。

3、计算并输出下列各种算法在不同内存容量下的命中率。

? 先进先出的算法（FIFO）； ? 最近最少使用算法（LRU）； ? 最佳淘汰算法（OPT）：先淘汰最不常用的页地址； 其中OPT为选作内容。

命中率 = 1 – 页面时效次数/页地址流长度

在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。 【实验步骤及实验结果分析】

首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。

//****利用先进先出算法(FIFO)和最近最久未使用算法(LRU)****// #include #include

#include #include

#define NULL_1 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

//******先进先出算法

void FIFO(int leng) //leng为内存页面数量 { int i,j,k; int n; //n为要被替换的页面号，按0,1,2...leng,0,1,2...leng循环变化

2

}

//******最近最久未使用算法

void LRU(int leng) //leng为内存页面数量 {

int i,j,k;

int tmax; //存time的最大值

int t; //t为要被访问的页面号 creat(leng); //初始化内存页面 for(i=0;i

3

creat(leng); //初始化内存页面

n=0;

for(i=0;i

printf(\

break; } } if(k==0) { que++; tmax=time[0]; t=0; for(j=0;j

printf(\ }

void main( ) {

int m,i;

srand(10*getpid()); //用来作为初始化随机数队列的\种子\ m=(int)((float)(ty-1)*(rand()/(RAND_MAX+1.0))); //选0-319中一数 for (i=0; i

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

printf(\

for(i=4;i<=32;i++) //内存从4页到32页

4