计算机科学 专业课程设计任务书
学生姓名 题 目 课题性质 指导教师 专业班级 学号 动态分区分配方式的模拟1 其它 马宏琳 课题来源 同组姓名 自拟课题 无 1）用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。 2）假设初始状态如下，可用的内存空间为640KB，并有下列的请求序列； 作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200 KB；作业3释放100 KB；作业1释放130 KB；作业5申请140 KB；作业6申请60 KB；作业7申请50KB；作业6释放60 KB 请采用首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。 了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。 任满杰等《操作系统原理实用教程》 电子工业出版社 2006 汤子瀛 《计算机操作系统》（修订版）西安电子科技大学出版社 2001 张尧学 史美林《计算机操作系统教程》实验指导 清华大学出版社 2000 罗宇等 《操作系统课程设计》机械工业出版社 2005 主要内容 任务要求 参考文献 指导教师签字： 审查意见 教研室主任签字： 年 月 日
1 需求分析
了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。采用首次适应算法的动态分区分配过程alloc()和回收过程free()。
空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小分配给作业。
作业完成时，需要释放作业所占空间，此时要考虑到四种情况：
(1)回收区与插入点的前一个空闲分区相邻接。此时将二者合并，修改前一分区的大小。
(2)回收区与插入点的后一空闲分区相邻接，将二者合并，用回收区的首址作为新空闲区的首址。
(3)回收区同时与插入点的前后两个空闲分区相邻接，三者合并，使用前一空闲分区的表项和首址。 (4)回收区单独存在。
由于该算法的实现相对简单，仅由我一人完成。
2 概要设计
typedef struct freearea{}ElemType;
定义一个空闲区说明表结构，每申请一个作业，改作业便具有此结构体 typedef struct DuLNode{}DuLNode,*DuLinkList; 定义一个双向链表 Status Initblock(){}
开创带头结点的内存空间链表,通过双向链表把申请的作业链接起来，作业的插入和删除，和链表中节点的插入和删除类似。
1
双向链表如图1所示
Status First_fit(int ID,int request){}
传入作业名及申请量采用首次适应算法实现动态内存分区分配的模拟，初始态640KB，只是一个虚态，每申请成功一个作业，便相应的640KB做相应的减少，同过双向链表模拟主存的分配情况。
内存分配流程如图2所示
Status free(int ID)
传过来需要回收的分区号实现分区的回收，对不同情况采取不同的处理
2
void show()显示当前主存的分配情况
3 运行环境
硬件环境：Cpu:P2.4GH DRR: 0.98GB WINDOWS XP。 软件环境：在VC++6.0下编译、调试。
4 开发工具和编程语言
开发工具: Microsort visual c++6.0中文版 编程语言: c++
5 详细设计
1)空闲区数据结构
typedef struct freearea//定义一个空闲区说明表结构 {
int ID; long size; long address; int state;
}ElemType;
2）双向链表数据结构
typedef struct DuLNode //双向链表结构体 {
ElemType data;
struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针 }DuLNode,*DuLinkList; 3）创建内存空间链表
Status Initblock()//开创带头结点的内存空间链表 {
block_first=(DuLinkList)malloc(sizeof(DuLNode)); block_last=(DuLinkList)malloc(sizeof(DuLNode));
3
block_first->prior=NULL; block_first->next=block_last; block_last->prior=block_first; block_last->next=NULL; block_last->data.address=0; block_last->data.size=MAX_length; block_last->data.ID=0; block_last->data.state=Free; return OK; }
4）分配主存 Status alloc() {
int ID,request;
cout<<\请输入作业(分区号)：\cin>>ID;
cout<<\请输入需要分配的主存大小(单位:KB)：\ cin>>request;
if(request<0 ||request==0)
{ }
if(First_fit(ID,request)==OK)调用函数First_fit(ID,request)才是真正实
cout<<\分配大小不合适，请重试！\return ERROR;
现首次适应算法 }
cout<<\分配成功！\
else
cout<<\内存不足，分配失败！\
4