实验四 动态分区分配方式的模拟 答案

动态分区分配方式的模拟 第一部分  思想的说明 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）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。 内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。 第二部分  程序清单 //*************************************************************** //********            动态分区分配方式的模拟          ********* //*************************************************************** #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(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; cout<<"请输入作业(分区号)："; cin>>ID; cout<<"请输入需要分配的主存大小(单位:KB)："; cin>>request; if(request<0 ||request==0) { 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.size>request) {//有空闲块能满足需求且有剩余" 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.size>request || 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.size>request) {//空闲块大于分配需求 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) 继续阅读