操作系统实验三

广州大学学生实验报告

开课学院及实验室：计算机学院，电子信息楼416A室 2014年 11 月 20日计算机科学与学院 教育软件学院 实验课程名称 实验项目名称

年级/专业/班 计科122 120610002姓名 庞彬 学号 2 成绩 指导老师 操作系统 张艳玲 实验三 内存管理实验 一、 实验目的

通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

了解linux环境下如何实现内存的分配与回收。 二、 实验内容

（一）内存管理实验1：常用页面置换算法模拟实验

设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 1、最佳淘汰算法（OPT） 2、先进先出的算法（FIFO） 3、最近最久未使用算法（LRU） 4、最不经常使用算法（LFU） 5、最近未使用算法（NUR）

命中率＝１－页面失效次数／页地址流长度

（二）内存管理实验2：Linux下的内存分配与回收的管理

在Linux环境下利用下列系统调用malloc()， free()编写一段程序实现内存分配与回收的管理。

要求：

返回已分配给变量的内存地址； 返回释放后的内存地址；

释放已分配的内存空间后，返回释放内存后未使用内存的大小。

三、 实验设备

安装带Linux操作系统的电脑一台。

四、 实验程序实现及结果分析

（一） 内存管理实验1：常用页面置换算法模拟实验 实验程序如下：

#define TRUE 1 #define FALSE 0 #define INVALID -1 #define NULL 0

#define total_instruction 320 /*指令流长*/ #define total_vp 32 /*虚页长*/ #define clear_period 50 /*清0周期*/

typedef struct /*页面结构*/ { int pn,pfn,counter,time; }pl_type;

pl_type pl[total_vp]; /*页面结构数组*/

struct pfc_struct{ /*页面控制结构*/ int pn,pfn; struct pfc_struct *next; };

typedef struct pfc_struct pfc_type;

pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;

int diseffect, a[total_instruction];

int page[total_instruction], offset[total_instruction];

int initialize(int); int FIFO(int); int LRU(int); int LFU(int); int NUR(int); int OPT(int);

int main( ) {

int s,i,j;

srand(10*getpid()); /*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/

s=(float)319*rand( )/32767/32767/2+1; //

for(i=0;iif(s<0||s>319) {

printf(\"When i==%d,Error,s==%d\\n\ exit(0); }

a[i]=s; /*任选一指令访问点m*/ a[i+1]=a[i]+1; /*顺序执行一条指令*/ a[i+2]=(float)a[i]*rand( )/32767/32767/2; /*执行前地址指令m' */ a[i+3]=a[i+2]+1; /*顺序执行一条指令*/

s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2; if((a[i+2]>318)||(s>319))

printf(\"a[%d+2],a number which is :%d and s==%d\\n\ }

for (i=0;ipage[i]=a[i]/10; offset[i]=a[i]%10; }

for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/ {

printf(\"---%2d page frames---\\n\ FIFO(i); LRU(i); LFU(i); NUR(i); OPT(i);

}

return 0; }

int initialize(total_pf) /*初始化相关数据结构*/

int total_pf; /*用户进程的内存页面数*/ {int i;

diseffect=0;

for(i=0;ipl[i].pn=i;

pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/ pl[i].counter=0;

pl[i].time=-1; /*页面控制结构中的访问次数为0，时间为-1*/ }

for(i=0;ipfc[i].next=&pfc[i+1]; pfc[i].pfn=i;

} /*建立pfc[i-1]和pfc[i]之间的链接*/ pfc[total_pf-1].next=NULL; pfc[total_pf-1].pfn=total_pf-1;

freepf_head=&pfc[0]; /*空页面队列的头指针为pfc[0]*/

return 0; }

int FIFO(total_pf) /*先进先出算法*/

int total_pf; /*用户进程的内存页面数*/ {

int i,j;

pfc_type *p;

initialize(total_pf); /*初始化相关页面控制用数据结构*/ busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/ for(i=0;iif(pl[page[i]].pfn==INVALID) /*页面失效*/ {

diseffect+=1; /*失效次数*/ if(freepf_head==NULL) /*无空闲页面*/ {

p=busypf_head->next;

pl[busypf_head->pn].pfn=INVALID;

freepf_head=busypf_head; /*释放忙页面队列的第一个页面*/ freepf_head->next=NULL; busypf_head=p; }

p=freepf_head->next; /*按FIFO方式调新页面入内存页面*/ freepf_head->next=NULL; freepf_head->pn=page[i];

pl[page[i]].pfn=freepf_head->pfn; if(busypf_tail==NULL)

busypf_head=busypf_tail=freepf_head; else {

busypf_tail->next=freepf_head; /*free页面减少一个*/ busypf_tail=freepf_head; }

freepf_head=p; } }

printf(\"FIFO:%6.4f\\n\

return 0; }

int LRU (total_pf) /*最近最久未使用算法*/ int total_pf; {

int min,minj,i,j,present_time; initialize(total_pf); present_time=0;

for(i=0;iif(pl[page[i]].pfn==INVALID) /*页面失效*/ {

diseffect++;

if(freepf_head==NULL) /*无空闲页面*/ {

min=32767;

for(j=0;jpl[j].time&&pl[j].pfn!=INVALID) { min=pl[j].time;

minj=j; }

freepf_head=&pfc[pl[minj].pfn]; //腾出一个单元 pl[minj].pfn=INVALID; pl[minj].time=-1;

freepf_head->next=NULL; }

pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效 pl[page[i]].time=present_time; freepf_head=freepf_head->next; //减少一个free 页面 } else

pl[page[i]].time=present_time; //命中则增加该单元的访问次数

present_time++; }

printf(\"LRU:%6.4f\\n\return 0; }

int NUR(total_pf) /*最近未使用算法*/ int total_pf;

{ int i,j,dp,cont_flag,old_dp; pfc_type *t;

initialize(total_pf); dp=0;

for(i=0;i{ if (pl[page[i]].pfn==INVALID) /*页面失效*/ {diseffect++;

if(freepf_head==NULL) /*无空闲页面*/ { cont_flag=TRUE; old_dp=dp;

while(cont_flag)

if(pl[dp].counter==0&&pl[dp].pfn!=INVALID) cont_flag=FALSE; else { dp++;

if(dp==total_vp) dp=0;

if(dp==old_dp)

for(j=0;jfreepf_head=&pfc[pl[dp].pfn]; pl[dp].pfn=INVALID; freepf_head->next=NULL; }

pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } else

pl[page[i]].counter=1; if(i%clear_period==0) for(j=0;jprintf(\"NUR:%6.4f\\n\

return 0; }

int OPT(total_pf) /*最佳置换算法*/ int total_pf;

{int i,j, max,maxpage,d,dist[total_vp]; pfc_type *t;

initialize(total_pf);

for(i=0;idiseffect++;

if(freepf_head==NULL) /*无空闲页面*/ {for(j=0;jif(pl[j].pfn!=INVALID) dist[j]=32767; /* 最大\"距离\" */ else dist[j]=0; d=1;

for(j=i+1;jfor(j=0;j1,i=%d\\n\

max=dist[j]; maxpage=j; }

freepf_head=&pfc[pl[maxpage].pfn]; freepf_head->next=NULL; pl[maxpage].pfn=INVALID; }

pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } }

printf(\"OPT:%6.4f\\n\

return 0; }

int LFU(total_pf) /*最不经常使用置换法*/ int total_pf; {

int i,j,min,minpage; pfc_type *t;

initialize(total_pf);

for(i=0;i{ if(pl[page[i]].pfn==INVALID) /*页面失效*/ { diseffect++;

if(freepf_head==NULL) /*无空闲页面*/ { min=32767;

for(j=0;j{if(min>pl[j].counter&&pl[j].pfn!=INVALID) { min=pl[j].counter; minpage=j; }

pl[j].counter=0; }

freepf_head=&pfc[pl[minpage].pfn]; pl[minpage].pfn=INVALID; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn; //有空闲页面,改为有效 pl[page[i]].counter++; freepf_head=freepf_head->next; //减少一个free 页面 } else

pl[page[i]].counter++;

}

printf(\"LFU:%6.4f\\n\

return 0; }

实验结果如图1-图3所示。

图1

图2

图3

从实验结果看，随着设置的空闲页面数的增加，各个算法的命中率都相对提高，其中，OPT算法命中率最高，其次为NUR，而FIFO与LRU相差无几，最低的是LFU，但每个页面执行结果有所不同。

OPT算法在执行过程中可能会发生错误。 思考题：

为什么OPT在执行时会有错误产生？

OPT算法：在将来不出现的或最晚出现的先淘汰，可以看出，它是一种对未来的假设判断，假设知道了将来要使用的页面，从而根据该情况来作出选择，但是进程是动态执行的，未来是无法预知的，所以，当碰到这种未来假设与实际不符时就会出现错误。

（一） 内存管理实验2：Linux下的内存分配与回收的管理 实验程序如下：

/* MALLOC.C: This program allocates memory with * malloc, then frees the memory with free. */

#include /* For _MAX_PATH definition */ #include #include #include void main() {

int *string;

/* Allocate space for a path name */ string =(int*) malloc(10 ); if( string == NULL )

printf( \"Insufficient memory available\\n\" ); else {

printf( \"Memory space allocated for path name\\n\" ); /*printf (\"string=%d\\n\ cout<<\"string=\"<printf( \"Memory freed\\n\" ); } int *stringy;

/* Allocate space for a path name */ stringy =(int*) malloc(12 ); if( stringy == NULL )

printf( \"Insufficient memory available\\n\" ); else {

printf( \"Memory space allocated for path name\\n\" );

/*printf (\"string=%d\\n\ cout<<\"stringy=\"<printf( \"Memory freed\\n\" ); } }

实验结果如下图所示。

图4

第一次调用malloc，申请10个字节大小的连续内存空间，返回该内存空间的首地址string，释放后，第二次调用malloc，申请12个字节大小的内存空间，返回stringy，与string值相同。在第一次调用并释放后，增加一句：string=NULL;发现，此时第二次调用malloc，结果是：Insufficient memory available，说明，调用malloc后返回为空。在第二次调用malloc时，实际上并没有重新申请空间。

五、 实验总结

① 通过实验，了解到了linux操作系统常见的对内存进行管理的算法，认识了动态分配内存的概念。

② 通过对比以上几种内存管理算法，我们了解到OPT算法的命中率最高的，其次为NUR，

而FIFO与LRU相差无几，最低的是LFU。

③ 对OPT算法进行分析，OPT的命中率是常见的内存管理算法中最高的。它的原理是最将

晚出现的先淘汰，但是这样子常常会出现错误，因为程序是动态的，这样子无法对程序的将来的情况进行准确的判断，就不具有很好的健壮性。

④ 以上的内存管理算法也只是真正的系统管理的一部分，实际的情况会更加的复杂，但是

常见的算法是我们深入学习的基础，所以必须熟练掌握。

⑤ 第二部分我们了解到了内存空间的释放以及调用方式。