分区式存储管理

实验题目：学 号：姓 名：完成时间：

分区式存储管理

一、实验概述

1.1 实验目的

1.通过本次实验，加深对内存管理的认识，进一步掌握内存的分配、回收算法的思想。

2.通过本次实验，加深掌握对数据结构的理解和进一步提高自己的编程能力。

1.2 任务描述

设计程序模拟内存的动态分区法存储管理。内存空闲区使用自由链管理，采用最坏适应算法从自由链中寻找空闲区进行分配，内存回收时假定不做与相邻空闲区的合并。

假定系统的内存共640K，初始状态为操作系统本身占用64K。在t1时间之后，有作业A、B、C、D分别请求8K、16K、64K、124K的内存空间；在t2时间之后，作业C完成；在t3时间之后，作业E请求50K的内存空间；在t4时间之后，作业D完成。要求编程序分别输出t1、t2、t3、t4时刻内存的空闲区的状态。

二、主要数据结构设计

1. 程序中自由链队列的结点类型可描述如下：

struct freelink{

int len, address; /* len为分区长度；address为分区起始地址 struct freelink /* next; }

2. 内存占用区用链表描述，其结点类型描述如下：

struct busylink{

char name; /* 作业或进程名 name=’S’ 表示OS占用

int len , address;

struct busylink *next; }

3.设全程量：

struct freelink *free_head=NULL; // 自由链队列（带头结点）队首指针

struct busylink *busy_head=NULL, // 占用区队列队（带头结点）首指针 struct busylink *busy_tail=NULL； // 占用区队列队尾指针

三、主要函数设计

1．函数名称: requireMemo(char name, int require)

功能描述：在空闲区域链中找到第一个满足条件的结点，将其分配掉，如果结点的长度大于require，则剩下的又将作为一个空闲结点插入到空闲区域链中 输入参数：char name, int require 输出参数：无 程序流程图：

begin (y!=NULL)&&(y>lennext;noy!=NULLyes p=(structbusylink*)malloc(sizeof(busylink));p->name=name;p->address=y->address;p->len=require; p->next=NULL; busy_tail->next=p; busy_tail=p;w=x->next;x->next=w->next;w->len==requireyesFree(w)No w->address=w->address+require; w->len=w->len-require;u=free_head;v=free_head->next;no (v!=NULL) && (v->lenlen)yes u=v; v=v->next;No u->next=w; w->next=v;printf(\"can't allocate!\\n\");End

2．函数名称：void freeMemo(char name)

功能描述：找到要回收的结点，将其释放，并将这个结点重新插入到空闲区域链中去

输入参数：char name 输出参数：无

程序流程图：

Beginq=busy_headp= busy_head->next(p!=NULL)&&(p->name!=name)q=p;p=p->next; p==NULLif (p==busy_tail) busy_tail=q;q->next=p->next;len=p->len;address=p->address;free(p)printf(“%c is not exist”,name)endw=( struct freelink*) malloc(…);w->len=len;w->address=address;u=free_headv=free_head->next(v!=NULL)&&(v->len> len)u->next=w;w->next=vu=v;v=v->nextend

将w插入到空闲区域链中时前的归并算法的流程图如下：

begin u=free_head; v=free_head->next; flag1=1;flag2=1(v!=NULL) && (flag1==1 || flag2==1)(w->address==(v->address+v->len)) &&flag1 s1=v;u->next=s1->next;w->address=v->address;w->len+=v->len;flag1=0;((w->address+w->len)==v->address) &&flag2 s2=v;u->next=s2->next;w->len+=v->len;flag2=0;u=vv=v->next;end

四、测试数据及运行结果

4．1 测试数据准备

假定系统的内存共640K，初始状态为操作系统本身占用64K。在t1时间之后，有作业A、B、C、D分别请求8K、16K、64K、124K的内存空间；在t2时间之后，作业C完成；在t3时间之后，作业E请求50K的内存空间；在t4时间之后，作业D完成。要求编程序分别输出t1、t2、t3、t4时刻内存的空闲区的状态。

4．2 运行结果及说明

1.测试目标:运用按最佳适应算法[1]（空闲区未归并时的） 运行结果:

2.测试目标:运用按最佳适应算法（空闲区归并时的） 运行结果:

五、实验总结

首先，对链表又有进一步的理解，还有就是加深理解内存的分配与回收，分

配与回收的策略，并掌握动态分区这种内存管理的具体实施方法。

再者，就是在编程中遇到的困难，在编写归并程序首先是自己考虑问题不全面，写的程序就只顾及到一个结点，而没有实现有两个结点的情况，于是后来再加了一条else语句，就没有出现问题。还有一个问题就是将多余的结点free时也出现问题，加了一条if(s==NULL）,成立就释放掉。一开始把free语句写在while循环内，一旦把找到的结点释放掉，则找不到下一个结点，也会出错，所以应该把free放到while循环外。

六、参考文献

[1] 左万历，周长林，彭涛.计算机操作系统教程.第3版.北京：高等教育出版社,2010

附：程序源代码

按最先适应算法

#include #include #include struct freelink { };

//内存占用区用链表描述，其结点类型描述如下： struct busylink { } ;

//并设全程量：

struct freelink *free_head=NULL; // 自由链队列带头结点）队首指针?

struct busylink *busy_head=NULL, *busy_tail=NULL; // 占用区队列队（带头结点）首指针 // 占用区队列队尾指针 // 设计子函数：

void start(void) /* 设置系统初始状态*/ {

struct freelink * p; struct busylink *q;

free_head=(struct freelink*)malloc(sizeof(struct freelink)); free_head->next=NULL; // 创建自由链头结点

busy_head=busy_tail=(struct busylink*)malloc(sizeof(struct busylink)); busy_head->next=NULL; // 创建占用链头结点

p=( struct freelink *)malloc(sizeof(struct freelink));

p->address=64;

p->len=640-64; //（OS占用了64K） p->next=NULL; free_head->next=p;

q=( struct busylink *)malloc(sizeof(struct busylink)); q->name='S'; /* S表示操作系统占用 */ q->len=64; q->address=0; q->next=NULL; busy_head->next=q; busy_tail=q;

char name; // 作业或进程名 name='S' 表示OS占用 int len , address; struct busylink *next;

int len, address; // len为分区长度；address为分区起始地址 struct freelink * next;

}

void requireMemo(char name, int require) /*模拟内存分配*/ {

}

struct freelink *w,*u,*v,*x,*y; struct busylink *p; x=free_head; y=free_head->next;

while((y!=NULL) &&(y->lenif(y!=NULL) {

p=(struct busylink*)malloc(sizeof(busylink)); p->name=name;

p->address=y->address; p->len=require; p->next=NULL;

busy_tail->next=p; //把p插入到busy_head的尾部 busy_tail=p; w=x->next; x->next=w->next; if(w->len==require) { } else { }

w->address=w->address+require; w->len=w->len-require; u=free_head; v=free_head->next;

while((v!=NULL) && (v->lenlen))//如果此结点还有多余，就此又重新插入到空{ }

u->next=w; w->next=v;

u=v; v=v->next; free(w); x=y; y=y->next;

闲区域链中（按照长度由小到大的次序排列）

}

else

printf(\"can't allocate!\\n\");

void freeMemo(char name) /* 模拟内存回收*/ {

struct busylink *p,*q;

struct freelink *w,*u,*v,*s1=NULL,*s2=NULL; int len,address; int flag1=1,flag2=1; p=busy_head->next;

while((p!=NULL)&&(p->name!=name)) //找到要回收的结点 { }

if(p==NULL) { } else {

if (p==busy_tail)

busy_tail=q; q->next=p->next; len=p->len; address=p->address; free(p);

w=(struct freelink*) malloc(sizeof(freelink)); w->len=len; w->address=address; u=free_head; v=free_head->next;

while((v!=NULL) && (flag1==1 || flag2==1)) //归并算法 {

if((w->address==(v->address+v->len)) &&flag1) { }

s1=v;

u->next=s1->next; w->address=v->address; w->len+=v->len; flag1=0;

printf(\"%c is not exist\\n\",name); q=p; p=p->next;

v=v->next;

}

else if(((w->address+w->len)==v->address) &&flag2) }

if(s1!=NULL)

free(s1); free(s2); if(s2!=NULL) u=free_head; v=free_head->next; if(v!=NULL) { }

u->next=w; w->next=v;

while((v!=NULL) && (v->lenlen)) { }

u=v; v=v->next; { } else { }

u=v; v=v->next; s2=v;

u->next=s2->next; w->len+=v->len; v=v->next; flag2=0;

}

void past(int time) /* 模拟系统过了时间time，用sleep(),或者用个空循环*/ { }

sleep(5);

printf(\"时间%d后：\\n\",time);

void printlink() /* 输出内存空闲情况（自由链的结点） */ { }

void printlink1() /* 输出内存占用的情况 */ { }

// 设计主函数： int main() {

start(); past(5);

requireMemo('A',8); requireMemo('B',16); requireMemo('C',64); requireMemo('D',124); printf(\"内存占用区为：\\n\"); printlink1();

printf(\"内存空闲区为:\\n\"); struct busylink *p; p=busy_head->next; if(p==NULL)

printf(\"无内存占有区！\\n\"); else {

while(p!=NULL) { }

printf(\"名字:%c\首地址:%d\长度:%d\\n\",p->name,p->address,p->len); p=p->next;

struct freelink *p; p=free_head->next; if(p==NULL)

printf(\"无空闲区！\\n\"); else {

while(p!=NULL) { }

printf(\"----------------------------------------\\n\");

printf(\"首地址:%d\长度:%d\\n\",p->address,p->len); p=p->next;

}

}

}

printlink(); past(10); freeMemo('C');

printf(\"内存占用区为：\\n\"); printlink1();

printf(\"内存空闲区为:\\n\"); printlink(); past(15);

requireMemo('E',50); printf(\"内存占用区为：\\n\"); printlink1();

printf(\"内存空闲区为:\\n\"); printlink(); past(20); freeMemo('D' );

printf(\"内存占用区为：\\n\"); printlink1();

printf(\"内存空闲区为:\\n\"); printlink(); return 0;