动态分区分配方式首次适应算法

计算机科学 专业课程设计任务书

学生姓名 题 目 课题性质 指导教师 专业班级 学号 动态分区分配方式的模拟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

Status First_fit(int ID,int request)//传入作业名及申请量，真正实现首次适应算法，从头开始查找合适的空间 {

//为申请作业开辟新空间且初始化

DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));

temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next;

while(p) {

if(p->data.state==Free && p->data.size==request) { }

if(p->data.state==Free && p->data.size>request) {

//有空闲块能满足需求且有剩余 temp->prior=p->prior; temp->next=p;

temp->data.address=p->data.address; p->prior->next=temp; //有大小恰好合适的空闲块 p->data.state=Busy; p->data.ID=ID; return OK; break;

p->prior=temp;

p->data.address=temp->data.address+temp->data.size; p->data.size-=request;

5

}

}

}

return OK; break;

p=p->next;

return ERROR;

5）主存回收 Status free(int ID) {

DuLNode *p=block_first; while(p) {

if(p->data.ID==ID) {

p->data.state=Free; p->data.ID=Free;

if(p->prior->data.state==Free)//与前面的空闲块相连 {

p->prior->data.size+=p->data.size;

p->prior->next=p->next; p->next->prior=p->prior;

}

if(p->next->data.state==Free)//与后面的空闲块相连 {

p->data.size+=p->next->data.size; if(p->next->next==NULL)p->next=null; else{

p->next->next->prior=p;

6

p->next=p->next->next;

}

}

}

} break;

p=p->next;

cout<<”分区号：”<

6）显示主存分配情况 void show() {

cout<<\cout<<\主存分配情况 ++++++\\n\

return OK;

cout<<\DuLNode *p=block_first->next; while(p) {

cout<<\分区号：\if(p->data.ID==Free)

cout<<\

else

cout<data.ID<

cout<<\起始地址：\cout<<\分区大小：\cout<<\状 态：\if(p->data.state==Free)

cout<<\空 闲\

7

}

}

else

cout<<\已分配\

p=p->next;

7）主 函 数 void main() { \

cout<<\动态分区分配方式的模拟一Initblock(); int choice; int i; for(i=0;;i++)

{ cout<<\

+++++++++++++++++\\n\

cout<<\首次适应算法

++++++++++++++++++++++++\\n\

cout<<\cout<<\分配内存 2: 回收内存 ++\\n\cout<<\查看分配 0: 退 出 ++\\n\cout<<\cout<<\请输入您的操作：\cin>>choice;

if(choice==1)// 分配内存

alloc();

else if(choice==2)// 内存回收 {

int ID;

cout<<\请输入您要释放的分区号：\

8

}

cin>>ID; }

free(ID); }

else if(choice==3)//显示主存

show();

else if(choice==0)//退出

break;

else //输入操作有误 { }

cout<<\输入有误，请重试！\continue;

6 调试分析

调试问题结果如图3所示

调试问题结果如图4所示

9

本实验要实现的功能是用首次适应算法来实现动态分区分配，通过不断调试，程序中出现了多处不足之处，首先是程序的运行结果不够清晰，不便于用户进行观察，不过这个比较容易优化，其次就是在内存回收功能上不够完善，开始的时候每次回收最后一个作业时都会出现问题，如图3所示，回收别的作业都很成功，原因就在与在回收情况的判断上少了一种情况后来，后来增加了

if(p->next->next==NULL)p->next=null;else{}满足了要求，得到了正确

结果，还有就是程序允许回收内存中不存在的作业，如图4所示这是不符合要求的，因为才程序中少了对用户输入作业号的判断不符合情况的处理。

7 测试结果

作业1 申请30KB 作业5 申请70KB 作业2 申请600KB 作业2 申请-80KB 作业2申请30KB 作业2 回收30KB 作业3 申请78KB

测试分区分配如图5所示

10

测试分区分配如图6所示

测试分区分配如图7所示

测试分区回收如图8所示

11

测试主存当前分配情况如图9所示

程序运行结果如图10所示

12

参考文献

[1]任满杰等《操作系统原理实用教程》 电子工业出版社 2006

[2]汤子瀛 《计算机操作系统》（修订版）西安电子科技大学出版社 2001 [3]张尧学 史美林《计算机操作系统教程》实验指导 清华大学出版社 2000 [4]罗宇等 《操作系统课程设计》机械工业出版社 2005 [5]曾平，曾林 《操作系统》清华大学出版社 2006

13

心得体会

由于已经学过动态分区分配，我也了解了什么是首次适应算法，以及首次适应算法的实现过程，刚开始以为会很顺利的做完此次课程设计，但往往会出现眼高手低的情况，先是因为很久都没用过C++来编写代码了，以致刚开始时，出现了很多小问题，真是把头都搞大了，如具体的格式，以及链表的具体使用等等出现问题，还得拿出原来的课本学习查看，费了点时间，不过让我再次回味了曾经的C++编程，加深了原来的记忆。经过网上搜材料以及整体平时的学习材料，后来程序的大体框架算是出来了，不过在不断调试过程中我发现了很多不完善的地方，比如在回收内存方面，少了一种情况的处理，以致每次要回收最后一个作业时都会出现错误的框子；还有就是若要删除内存中不存在的作业，程序却允许执行，这个问题难为了我好久，改完后又接着出现新的问题，成了内存中存在的作业在删除时也提示用户重新输入，原因在于判断条件加的地方不合适。通过本次课程设计我学到了很多东西，也增加了我不断摸索和学习的兴趣，由原来的书本知识演化成了真的动手实践，获益匪浅。

14

实验代码

//********动态分区分配方式的模拟一首次适应算法 ********* #include #include

#define Free 0 //空闲状态 #define Busy 1 //已用状态 #define OK 1 //完成 #define ERROR 0 //出错

#define MAX_length 640 //最大内存空间为640KB typedef int Status;

typedef struct freearea//定义一个空闲区说明表结构 { int ID; long size; long address; int state; }ElemType;

typedef struct DuLNode //double linked list { ElemType data;

struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针 }DuLNode,*DuLinkList;

DuLinkList block_first; //头结点 DuLinkList block_last; //尾结点 Status alloc();//内存分配 Status free(int); //内存回收

Status First_fit(int,int);//首次适应算法 void show();//查看分配

Status Initblock();//开创空间表

Status Initblock()//开创带头结点的内存空间链表 { block_first=(DuLinkList)malloc(sizeof(DuLNode)); block_last=(DuLinkList)malloc(sizeof(DuLNode)); 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;

15

block_last->data.ID=0;

block_last->data.state=Free; return OK; }

//----------------------- 分 配 主 存 ------------------------- Status alloc() { int ID,request; cout<<\请输入作业(分区号)：\ cin>>ID;

cout<<\请输入需要分配的主存大小(单位:KB)：\ cin>>request;

if(request<0 ||request==0) { cout<<\分配大小不合适，请重试！\ return ERROR; } if(First_fit(ID,request)==OK) cout<<\分配成功！\ else cout<<\内存不足，分配失败！\}

//------------------ 首次适应算法 ----------------------- Status First_fit(int ID,int request)//传入作业名及申请量 { //为申请作业开辟新空间且初始化 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID;

temp->data.size=request; temp->data.state=Busy;

DuLNode *p=block_first->next; while(p) { if(p->data.state==Free && p->data.size==request) { //有大小恰好合适的空闲块 p->data.state=Busy; p->data.ID=ID; return OK; break; } if(p->data.state==Free && p->data.size>request) {

16

//有空闲块能满足需求且有剩余 temp->prior=p->prior; temp->next=p; temp->data.address=p->data.address; p->prior->next=temp; p->prior=temp; p->data.address=temp->data.address+temp->data.size; p->data.size-=request; return OK; break; } p=p->next; } return ERROR; }

//----------------------- 主 存 回 收 -------------------- Status free(int ID) { DuLNode *p=block_first; while(p) { if(p->data.ID==ID) { p->data.state=Free; p->data.ID=Free; if(p->prior->data.state==Free)//与前面的空闲块相连 { p->prior->data.size+=p->data.size; p->prior->next=p->next; p->next->prior=p->prior; } if(p->next->data.state==Free)//与后面的空闲块相连 { p->data.size+=p->next->data.size;if(p->next->next==NULL)p->next=NULL;else{ p->next->next->prior=p; p->next=p->next->next;} } break; } p=p->next; } cout<<\分区：\回收成功\ return OK;

17

// }

//--------------- 显示主存分配情况 ------------------ void show() { cout<<\ cout<<\ 主 存 分 配 情 况 ++++++\\n\ cout<<\ DuLNode *p=block_first->next; while(p) { cout<<\分 区 号：\ if(p->data.ID==Free) cout<<\ else cout<data.ID<data.state==Free) cout<<\空 闲\ else cout<<\已分配\ p=p->next; } }

//----------------------- 主 函 数--------------------------- void main() { Initblock(); int choice; int i; for(i=0;;i++) { cout<<\ cout<<\动态分区分配方式的模拟一+++++++++++++++++\\n\ cout<<\首次适应算法++++++++++++++++++++++++\\n\ cout<<\ ++++++++++++++++++++++++++++++++++++++++++++\\n\ cout<<\ ++ 1: 分配内存 2: 回收内存 ++\\n\ cout<<\ ++ 3: 查看分配 0: 退 出 ++\\n\ cout<<\ ++++++++++++++++++++++++++++++++++++++++++++\\n\ cout<<\请输入您的操作 ：\ cin>>choice; if(choice==1)// 分配内存

18

}

alloc(); else if(choice==2)// 内存回收 { int ID;

cout<<\请输入您要释放的分区号：\ cin>>ID; free(ID); } else if(choice==3)//显示主存 show(); else if(choice==0)//退出 break; else //输入操作有误 { cout<<\输入有误，请重试！\ continue; } }

19

本文来源：https://www.bwwdw.com/article/ul7o.html