分区存储管理模拟实验报告

分区存储管理模拟实验报告1．实验目的了解动态分区存储管理方式中的数据结构和分配算法，加深对动态分区存储管理方式及其实现技术的理解。2.实验内容用C语言或Pascal语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程Allocate()和回收过程Free()。其中，空闲分区采用空闲分区链来组织，内存分配时，优先使用空闲区低地址部分的空间。假设初始状态，可用内存空间为640KB，作业请求序列如下（也可以编程从键盘输入，R表示请求，F表示释放）：作业1请求130KB。作业2请求60KB。作业3请求100KB。作业2释放60KB。作业4请求200KB。作业3释放100KB。作业1释放130KB。作业5请求140KB。作业6请求60KB。作业7请求50KB。作业6释放60KB。要求每次分配和回收后显示出空闲区链的情况。如果不能为作业的请求进行内存分配，给出相应的提示信息。3．实验分析和思考采用首次适应算法和最佳适应算法，对内存的分配和回收速度有什么影响？如何解决碎片片问题？详细设计首次适应算法：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。最佳适应算法：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。typedefstructfreearea{}ElemType;定义一个空闲区说明表结构，每申请一个作业，改作业便具有此结构体typedefstructDuLNode{}DuLNode,*DuLinkList;定义一个双向链表StatusInitblock(){}开创带头结点的内存空间链表,通过双向链表把申请的作业链接起来，作业的插入和删除，和链表中节点的插入和删除类似。双向链表如图1所示StatusFirst_fit(intID,intrequest){}传入作业名及申请量采用首次适应算法实现动态内存分区分配的模拟，初始态640KB，只是一个虚态，每申请成功一个作业，便相应的640KB做相应的减少，同过双向链表模拟主存的分配情况。内存分配流程如图2所示Statusfree(intID)传过来需要回收的分区号实现分区的回收，对不同情况采取不同的处理voidshow()显示当前主存的分配情况源程序//----------------------------------------------------------------//---------动态分区分配方式的模拟---------//----------------------------------------------------------------#includeiostream.h#includestdlib.h#defineFree0//空闲状态#defineBusy1//已用状态#defineOK1//完成#defineERROR0//出错#defineMAX_length640//最大内存空间为640KBtypedefintStatus;typedefstructfreearea//定义一个空闲区说明表结构{intID;//分区号longsize;//分区大小longaddress;//分区地址intstate;//状态}ElemType;//----------线性表的双向链表存储结构------------typedefstructDuLNode//doublelinkedlist{ElemTypedata;structDuLNode*prior;//前趋指针structDuLNode*next;//后继指针}DuLNode,*DuLinkList;DuLinkListblock_first;//头结点DuLinkListblock_last;//尾结点Statusalloc(int);//内存分配Statusfree(int);//内存回收StatusFirst_fit(int,int);//首次适应算法StatusBest_fit(int,int);//最佳适应算法voidshow();//查看分配StatusInitblock();//开创空间表StatusInitblock()//开创带头结点的内存空间链表{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;returnOK;}//-----------------------分配主存-------------------------Statusalloc(intch){intID,request;cout请输入作业(分区号)：;cinID;cout请输入需要分配的主存大小(单位:KB)：;cinrequest;if(request0||request==0){cout分配大小不合适，请重试！endl;returnERROR;}if(ch==2)//选择最佳适应算法{if(Best_fit(ID,request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;returnOK;}else//默认首次适应算法{if(First_fit(ID,request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;returnOK;}}//------------------首次适应算法-----------------------StatusFirst_fit(intID,intrequest)//传入作业名及申请量{//为申请作业开辟新空间且初始化DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));temp-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;returnOK;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;returnOK;break;}p=p-next;}returnERROR;}//--------------------最佳适应算法------------------------StatusBest_fit(intID,intrequest){intch;//记录最小剩余空间DuLinkListtemp=(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;returnOK;break;}if(p-data.state==Free&&p-data.sizerequest){//空闲块大于分配需求if(p-data.size-requestch)//剩余空间比初值还小{ch=p-data.size-request;//更新剩余最小值q=p;//更新最佳位置指向}}p=p-next;}if(q==NULL)returnERROR;//没有找到空闲块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;returnOK;}}//-----------------------主存回收--------------------Statusfree(intID){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;}returnOK;}//---------------显示主存分配情况------------------voidshow(){cout---------------------------------------\n;cout---主存分配情况---\n;cout---------------------------------------\n;DuLNode*p=block_first-next;while(p){cout分区号：;if(p-data.ID==Free)coutFreeendl;elsecoutp-data.IDendl;cout