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

1、 计算机科学 专业课程设计任务书学生姓名专业班级学号题 目动态分区分配方式的模拟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申请5

2、0KB；作业6释放60 KB请采用首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。任务要求 了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。参考文献任满杰等操作系统原理实用教程 电子工业出版社 2006汤子瀛 计算机操作系统（修订版）西安电子科技大学出版社 2001张尧学 史美林计算机操作系统教程实验指导 清华大学出版社 2000 罗宇等 操作系统课程设计机械工业出版社 2005审查意见指导教师签字：教研室主任签字： 年 月 日 1 需求分析了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存

3、储管理方式及其实现过程的理解。采用首次适应算法的动态分区分配过程alloc()和回收过程free()。空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小分配给作业。作业完成时，需要释放作业所占空间，此时要考虑到四种情况：(1)回收区与插入点的前一个空闲分区相邻接。此时将二者合并，修改前一分区的大小。(2)回收区与插入点的后一空闲分区相邻接，将二者合并，用回收区的首址作为新空闲区的首址。(3)回收区同时与插入点的前后两个空闲分区相邻接，三者合并，使用前一空闲分区的表项和首址。

4、(4)回收区单独存在。由于该算法的实现相对简单，仅由我一人完成。2 概要设计typedef struct freeareaElemType;定义一个空闲区说明表结构，每申请一个作业，改作业便具有此结构体typedef struct DuLNodeDuLNode,*DuLinkList;定义一个双向链表Status Initblock()开创带头结点的内存空间链表,通过双向链表把申请的作业链接起来，作业的插入和删除，和链表中节点的插入和删除类似。双向链表如图1所示Status First_fit(int ID,int request)传入作业名及申请量采用首次适应算法实现动态内存分区分配的模拟，

5、初始态640KB，只是一个虚态，每申请成功一个作业，便相应的640KB做相应的减少，同过双向链表模拟主存的分配情况。内存分配流程如图2所示Status free(int ID)传过来需要回收的分区号实现分区的回收，对不同情况采取不同的处理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/定义一个空闲

6、区说明表结构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)

7、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; block_last-data.ID=0; block_last-data.state=Free; return OK;4）分配主存Status alloc()int ID,request;coutID; coutrequ

8、est; if(request0 |request=0)cout分配大小不合适，请重试！endl;return ERROR;if(First_fit(ID,request)=OK)调用函数First_fit(ID,request)才是真正实现首次适应算法cout分配成功！endl;elsecout内存不足，分配失败！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)/有大小

9、恰好合适的空闲块p-data.state=Busy;p-data.ID=ID;return OK;break;if(p-data.state=Free & p-data.sizerequest)/有空闲块能满足需求且有剩余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

10、;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

11、-next-next=NULL)p-next=null;elsep-next-next-prior=p;p-next=p-next-next;break;p=p-next;cout”分区号：”ID“回收成功”endl;return OK;6）显示主存分配情况void show()cout+n;cout+ 主存分配情况 +n;coutnext;while(p)coutdata.ID=Free)coutFreeendl;elsecoutdata.IDendl;cout起始地址：data.address;cout 分区大小：data.size KB;coutdata.state=Free)cout空

12、 闲endl;elsecout已分配next;7）主 函 数void main()Initblock();int choice;int i;for(i=0;i+) cout+n;cout+动态分区分配方式的模拟一+n;cout+首次适应算法+n;cout +n;cout + 1: 分配内存 2: 回收内存 +n;cout + 3: 查看分配 0: 退 出 +n;cout +n;coutchoice;if(choice=1)/ 分配内存alloc();else if(choice=2)/ 内存回收 int ID; coutID; free(ID);else if(choice=3)/显示主存sh

13、ow();else if(choice=0)/退出break;else /输入操作有误cout输入有误，请重试！next-next=NULL)p-next=null;else满足了要求，得到了正确结果，还有就是程序允许回收内存中不存在的作业，如图4所示这是不符合要求的，因为才程序中少了对用户输入作业号的判断不符合情况的处理。7 测试结果作业1 申请30KB作业5 申请70KB作业2 申请600KB作业2 申请-80KB作业2申请30KB作业2 回收30KB作业3 申请78KB测试分区分配如图5所示测试分区分配如图6所示测试分区分配如图7所示测试分区回收如图8所示测试主存当前分配情况如图9所示程

14、序运行结果如图10所示参考文献1任满杰等操作系统原理实用教程 电子工业出版社 20062汤子瀛 计算机操作系统（修订版）西安电子科技大学出版社 20013张尧学 史美林计算机操作系统教程实验指导 清华大学出版社 2000 4罗宇等 操作系统课程设计机械工业出版社 20055曾平，曾林 操作系统清华大学出版社 2006心得体会由于已经学过动态分区分配，我也了解了什么是首次适应算法，以及首次适应算法的实现过程，刚开始以为会很顺利的做完此次课程设计，但往往会出现眼高手低的情况，先是因为很久都没用过C+来编写代码了，以致刚开始时，出现了很多小问题，真是把头都搞大了，如具体的格式，以及链表的具体使用等等

15、出现问题，还得拿出原来的课本学习查看，费了点时间，不过让我再次回味了曾经的C+编程，加深了原来的记忆。经过网上搜材料以及整体平时的学习材料，后来程序的大体框架算是出来了，不过在不断调试过程中我发现了很多不完善的地方，比如在回收内存方面，少了一种情况的处理，以致每次要回收最后一个作业时都会出现错误的框子；还有就是若要删除内存中不存在的作业，程序却允许执行，这个问题难为了我好久，改完后又接着出现新的问题，成了内存中存在的作业在删除时也提示用户重新输入，原因在于判断条件加的地方不合适。通过本次课程设计我学到了很多东西，也增加了我不断摸索和学习的兴趣，由原来的书本知识演化成了真的动手实践，获益匪浅。实

16、验代码/*动态分区分配方式的模拟一首次适应算法 *#include#include#define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_length 640 /最大内存空间为640KBtypedef int Status;typedef struct freearea/定义一个空闲区说明表结构int ID;long size;long address;int state;ElemType;typedef struct DuLNode /double linked list E

17、lemType 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

18、_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; block_last-data.ID=0; block_last-data.state=Fr

19、ee; return OK;/- 分 配 主 存 -Status alloc()int ID,request;coutID; coutrequest; if(request0 |request=0)cout分配大小不合适，请重试！endl;return ERROR;if(First_fit(ID,request)=OK)cout分配成功！endl;elsecout内存不足，分配失败！data.ID=ID; temp-data.size=request; temp-data.state=Busy; DuLNode *p=block_first-next;while(p)if(p-data.sta

20、te=Free & p-data.size=request)/有大小恰好合适的空闲块p-data.state=Busy;p-data.ID=ID;return OK;break;if(p-data.state=Free & p-data.sizerequest)/有空闲块能满足需求且有剩余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

21、-=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.