华北电力大学实验报告实验名称 动态分区分配方式的模拟课程名称计算机操作系统专业班级： 学生姓名 学 号： 成 绩 指导教师： 实验日期一、实验目的：了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储 管理方式及其实现过程的理解。二、实验内容：(1) 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和 回收过程free()。其中，空闲分区通过分区链来管理；在进行内存分配时，系统优先使用 空闲区低端的空间。(2) 假设初始状态下，可用内存空间为640K，并有下列请求序列： 作业1申请130KB。作业2申请60KB。 作业3申请100KB。作业2释放60KB。 作业4申请200KB。作业3释放100KB。作业1释放130KB。 作业5申请140KB。作业6申请60KB。 作业7申请50KB。作业6释放60KB。请分别用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后 显示出空闲内存分区链的情况。四、设计思路和方法：首次适应算法(Firstfit):当要分配内存空间时，就查表，在各空闲区中查找满足大小要求 的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与 所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修 改分区大小和分区始址。最佳适应算法(Bestfit)：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得 剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下 的空闲分区，并修改分区大小的起始地址。内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空 闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改 分区大小及起始地址。五、主要数据结构和算法：主要数据结构：定义一个空闲区说明表结构struct freearea int ID;分区号long size;分区大小long address; 分区地址 int state; 状态 ElemType;线性表的双向链表存储结构struct DuLNode /double linked listElemType data;struct DuLNode *prior; 前趋指针 struct DuLNode *next; 后继指针 DuLNode,*DuLinkList;算法：首次适应算法：是在分配内存时，从链首开始顺序查找，直到找到一个大小能够满足 要求的分区，即进行分配。最佳适应算法：是在分配内存时，从链首开始顺序查找，查找到链尾，并记录一个大 小不小于要求的分区的最小分区，在查找完毕后进行分配。六、程序代码和输出1程序代码如下/ / /*动态分区分配方式的模拟*/ / /#includeviostream.h#includevstdlib.h#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 listElemType data;struct DuLNode *prior; / 前趋指针 struct DuLNode *next; 后继指针 DuLNode,*DuLinkList;DuLinkList block_first; 头结点DuLinkList block_last; 尾结点Status alloc(int);/ 内存分配Status free(int); 内存回收Status First_fit(int,int); 首次适应算法Status Best_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; block_last-data.ID=0;block_last-data.state=Free;return OK;/ 分配主存 Status alloc(int ch)int ID,request;coutvv请输入作业(分区号)：;cinID;coutvv请输入需要分配的主存大小(单位:KB)：;cinrequest;if(requestdata.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.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;return ERROR;/ 最佳适应算法 Status Best_fit(int ID,int request)int ch; 记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.ID=ID;temp-data.size=request; temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; 记录最佳插入位置 while(p) /初始化最小空间和最佳位置 if(p-data.state=Free &(p-data.sizerequest II p-data.size=request)q=p;ch=p-data.size-request; break;p=p-next;while(p) if(p-data.state=Free & p-data.size=request) /空闲块大小恰好合适p-data.ID=ID; p-data.state=Busy; return OK; break;if(p-data.state=Free & p-data.sizerequest) /空闲块大于分配需求 if(p-data.size-requestvch) 剩余空间比初值还小 ch=p-data.size-request; 更新乘 0余最小值 q=p;/更新最佳位置指向 p=p-next; if(q=NULL) return ERROR;/ 没有找到空闲块 else/找到了最佳位置并实现分配temp-prior=q-prior; temp-next=q; temp-data.address=q-data.address; q-prior-next=temp;q-prior=temp; q-data.address+=request; q-data.size=ch;return OK;/ 主存回收 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; p-next-next-prior=p;p-next=p-next-next; break; p=p-next;return OK;/显示主存分配情况void show() coutvv+