动态分区分配方式的模拟第一部分设计思想的说明1 设计目标用 C语言或 C+ 语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端空间。预期结果：假设初始状态如下，可用的内存空间为640KB ，并有下列请求序列：作业 1 申请 130KB 作业 2 申请 60KB 作业 3 申请 100KB 作业 2 释放 60KB 作业 4 申请 200KB 作业 3 释放 100KB 作业 1 释放 130KB 作业 5 申请 140KB 作业 6 申请 60KB 作业 7 申请 50KB 作业 6 释放 60KB 分别用首次适应算法和最佳适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。2、设计理论首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余， 则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。最佳适应算法（Best-fit）： 当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。内存回收： 将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 7 页第二部分程序清单/* /* 动态分区分配方式的模拟 */*#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();/开创空间表精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 7 页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) /初始化最小空间和最佳位置精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 7 页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;/- 主 存 回 收 -精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 7 页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;精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 7 页else cout已分配 endl;cout next;/- 主函数-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;精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 7 页