设计性实验报告
实验题目： 分区式存储管理
学 号：
姓 名：
完成时间：
一、实验概述
1.1 实验目的
1.通过本次实验，加深对内存管理的认识，进一步掌握内存的分配、回收算法的思想。
2.通过本次实验，加深掌握对数据结构的理解和进一步提高自己的编程能力。
1.2 任务描述
设计程序模拟内存的动态分区法存储管理。内存空闲区使用自由链管理，采用最坏适应算法从自由链中寻找空闲区进行分配，内存回收时假定不做与相邻空闲区的合并。
假定系统的内存共0K，初始状态为操作系统本身占用K。在t1时间之后，有作业A、B、C、D分别请求8K、16K、K、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
输出参数：无
程序流程图：
2．函数名称：void freeMemo(char name)
功能描述：找到要回收的结点，将其释放，并将这个结点重新插入到空闲区域链中去
输入参数：char name
输出参数：无
程序流程图：
将w插入到空闲区域链中时前的归并算法的流程图如下：
四、测试数据及运行结果
4．1 测试数据准备
假定系统的内存共0K，初始状态为操作系统本身占用K。在t1时间之后，有作业A、B、C、D分别请求8K、16K、K、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 { int len, address; // len为分区长度；address为分区起始地址 struct freelink * next; }; //内存占用区用链表描述，其结点类型描述如下： struct busylink { char name; // 作业或进程名 name='S' 表示OS占用 int len , address; struct busylink *next; } ; //并设全程量： 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=; p->len=0-; //（OS占用了K） p->next=NULL; free_head->next=p; q=( struct busylink *)malloc(sizeof(struct busylink)); q->name='S'; /* S表示操作系统占用 */ q->len=; q->address=0; q->next=NULL; busy_head->next=q; busy_tail=q; } 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->len x=y; y=y->next; } if(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) { free(w); } else { w->address=w->address+require; w->len=w->len-require; u=free_head; v=free_head->next; while((v!=NULL) && (v->len { u=v; v=v->next; } u->next=w; w->next=v; } } 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)) //找到要回收的结点 { q=p; p=p->next; } if(p==NULL) { printf("%c is not exist\\n",name); } 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; v=v->next; flag1=0; } else if(((w->address+w->len)==v->address) &&flag2) { s2=v; u->next=s2->next; w->len+=v->len; v=v->next; flag2=0; } else { u=v; v=v->next; } } if(s1!=NULL) free(s1); if(s2!=NULL) free(s2); u=free_head; v=free_head->next; if(v!=NULL) { while((v!=NULL) && (v->len { u=v; v=v->next; } } u->next=w; w->next=v; } } void past(int time) /* 模拟系统过了时间time，用sleep(),或者用个空循环*/ { sleep(5); printf("时间%d后：\\n",time); } void printlink() /* 输出内存空闲情况（自由链的结点） */ { struct freelink *p; p=free_head->next; if(p==NULL) printf("无空闲区！\\n"); else { while(p!=NULL) { printf("首地址:%d\长度:%d\\n",p->address,p->len); p=p->next; } } printf("----------------------------------------\\n"); } void printlink1() /* 输出内存占用的情况 */ { 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; } } } // 设计主函数： int main() { start(); past(5); requireMemo('A',8); requireMemo('B',16); requireMemo('C',); requireMemo('D',124); printf("内存占用区为：\\n"); printlink1(); printf("内存空闲区为:\\n"); 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; } 下载本文
