动态分区分配方式的模拟实验报告模板.doc

.华北电力大学实 验 报 告 实验名称 动态分区分配方式的模拟 课程名称 计算机操作系统 专业班级： 学生姓名： 学 号： 成 绩：指导教师： 实验日期： ;.一实验目的：了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。二实验内容：（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。请分别用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。四设计思路和方法： 首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。五主要数据结构和算法：主要数据结构：定义一个空闲区说明表结构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 程序代码如下/*/* 动态分区分配方式的模拟 */* #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 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;coutID;coutrequest;if(request0 |request=0) cout分配大小不合适，请重试！endl;return ERROR; if(ch=2) /选择最佳适应算法if(Best_fit(ID,request)=OK) cout分配成功！endl;else cout内存不足，分配失败！endl;return OK;else /默认首次适应算法if(First_fit(ID,request)=OK) cout分配成功！endl;else cout内存不足，分配失败！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.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 | 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-requestdata.size-request;/更新剩余最小值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()cout+n;cout+ 主 存 分 配 情 况 +n;coutnext;while(p)coutdata.ID=Free) coutFreeendl;else coutdata.IDendl;cout起始地址：data.addressendl;cout分区大小：data.size KBendl;coutdata.state=Free) cout空 闲endl;else cout已分配endl;coutnext; /- 主 函 数-void main()int ch;/算法选择标记cout 动态分区分配方式的模拟 n;cout*n;cout* 1)首次适应算法 2)最佳适应算法 *n;cout*n;coutch;Initblock(); /开创空间表int choice; /操作选择标记while(1) cout*n; cout* 1: 分配内存 2: 回收内存 *n; cout* 3: 查看分配 0: 退 出 *n; cout*n; coutchoice;if(choice=1) alloc(ch); / 分配内存else if(choice=2) / 内存回收int ID;coutID;free(ID);else if(choice=3) show();/显示主存else if(choice=0) break; /退出else /输入操作有误cout输入有误，请重试！endl;continue;2输入和输出结果（1）首次适应算法 动态分区分配方式的模拟* 1)首次适应算法 2)最佳适应算法 *请选择分配算法：1* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：1请输入需要分配的主存大小(单位:KB)：130分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：Free起始地址：130分区大小：510 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：2请输入需要分配的主存大小(单位:KB)：60分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：2起始地址：130分区大小：60 KB状 态：已分配分 区 号：Free起始地址：190分区大小：450 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：3请输入需要分配的主存大小(单位:KB)：100分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：2起始地址：130分区大小：60 KB状 态：已分配分 区 号：3起始地址：190分区大小：100 KB状 态：已分配分 区 号：Free起始地址：290分区大小：350 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：2请输入您要释放的分区号：2* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：Free起始地址：130分区大小：60 KB状 态：空 闲分 区 号：3起始地址：190分区大小：100 KB状 态：已分配分 区 号：Free起始地址：290分区大小：350 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：4请输入需要分配的主存大小(单位:KB)：200分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：Free起始地址：130分区大小：60 KB状 态：空 闲分 区 号：3起始地址：190分区大小：100 KB状 态：已分配分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：2请输入您要释放的分区号：3* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：Free起始地址：130分区大小：160 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：2请输入您要释放的分区号：1* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：Free起始地址：0分区大小：290 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：5请输入需要分配的主存大小(单位:KB)：140分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：5起始地址：0分区大小：140 KB状 态：已分配分 区 号：Free起始地址：140分区大小：150 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 * 请输入您的操作 ：1请输入作业(分区号)：6请输入需要分配的主存大小(单位:KB)：60分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：5起始地址：0分区大小：140 KB状 态：已分配分 区 号：6起始地址：140分区大小：60 KB状 态：已分配分 区 号：Free起始地址：200分区大小：90 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：7请输入需要分配的主存大小(单位:KB)：50分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：5起始地址：0分区大小：140 KB状 态：已分配分 区 号：6起始地址：140分区大小：60 KB状 态：已分配分 区 号：7起始地址：200分区大小：50 KB状 态：已分配分 区 号：Free起始地址：250分区大小：40 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：2请输入您要释放的分区号：6* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：5起始地址：0分区大小：140 KB状 态：已分配分 区 号：Free起始地址：140分区大小：60 KB状 态：空 闲分 区 号：7起始地址：200分区大小：50 KB状 态：已分配分 区 号：Free起始地址：250分区大小：40 KB状 态：空 闲分 区 号：4起始地址：290分区大小：200 KB状 态：已分配分 区 号：Free起始地址：490分区大小：150 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：0Press any key to continue（2）最佳适应算法 动态分区分配方式的模拟* 1)首次适应算法 2)最佳适应算法 *请选择分配算法：2* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：1请输入需要分配的主存大小(单位:KB)：130分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配 情 况 +分 区 号：1起始地址：0分区大小：130 KB状 态：已分配分 区 号：Free起始地址：130分区大小：510 KB状 态：空 闲* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：1请输入作业(分区号)：2请输入需要分配的主存大小(单位:KB)：60分配成功！* 1: 分配内存 2: 回收内存 * 3: 查看分配 0: 退 出 *请输入您的操作 ：3+ 主 存 分 配