存储管理动态分区分配算法的模拟

一．题目：存储管理---动态分区分配算法的模拟二．任务：设计主界面以灵活选择某算法，且以下算法都要实现：首次适应算法、循环首次适应算法、最佳适应算法；。三．思想：对任务进行构思和设想。（1）首次适应算法：FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺巡查找，直到找到一个大小能够满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲区间仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。（2）循环首次适应算法该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块的请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查找指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则返回到第一个空闲分区，比较大小是否满足，找到后，应调整起始查询指针。（3）最佳适应算法是将最小的空闲分区分配给作业，避免大材小用。为了加速寻找，该算法要求将所有的空闲分区按照某容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。（4）内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。四．目的：在构思中提出要达到的目的。（1）按照首次适应算法对内存进行分配，得到（2）按照循环首次适应算法对内存（3）按照最佳适应算法对内存进行分配（4）在作业完成时，释放作业所在内存块，使其能够再次被利用五．方案：对构思的细化，提出粗略的方案。（1）首次适应算法：设立头指针，每次从头指针开始查找，进行内存分配（2）最佳适应算法：设立一个指针纪录最佳位置，然后根据内存大小，对最佳位置进行分配（3）循环首次适应算法：设立查找指针，查找指针初始为链首指针，最后位置为查找指针，返回查找指针，第二次运行时从查找指针开始查找。（4）内存回收：将释放的空间与前后空闲状态区间合并，改写空闲区间地址和大小六．框图：根据方案画出框图并审核框图。七．程序：是实施框图的主体并运行和修改。1.有大小恰好合适的空闲块if(p-data.state==Free&&p-data.size==request){p-data.state=Busy;p-data.ID=ID;returnOK;break;}2.有空闲块能满足需求且有剩余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;}3.回收内存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;}八．文档：运行环境，输入条件，输出结果，整理成文。1.运行环境：操作系统WINDOWSXP编译软件MicrosoftVisualC++电脑配置：主频3.0GHz内存512MB2.输入条件作业1申请130KB作业1申请60KB作业1申请100KB作业1释放130KB作业1申请100KB作业1释放60KB九．总结：谈心得体会，特别是开发一个软件的体会。开发一个软件需要有软件需求分析，软件流程图，根据流程进行软件的编写。在编写软件时需要很好的结构感，编写的程序需要有框架，编写的程序需要补充语句说明，让观看着更好的了解程序，使用程序。十．附件：完整程序#includeiostream.h#includestdlib.h#defineFree0//空闲状态#defineBusy1//已用状态#defineOK1//完成#defineERROR0//出错#defineMAX_length640//最大内存空间为640KBtypedefintStatus;typedefstructfreearea//定义一个空闲区说明表结构{intID;//分区号longsize;//分区大小longaddress;//分区地址intstate;//状态}ElemType;//----------线性表的双向链表存储结构------------typedefstructDuLNode//双向链表{ElemTypedata;structDuLNode*prior;//前趋指针structDuLNode*next;//后继指针}DuLNode,*DuLinkList;DuLinkListblock_first;//头结点DuLinkListblock_last;//尾结点Statusalloc(int);//内存分配Statusfree(int);//内存回收StatusFirst_fit(int,int);//首次适应算法StatusBest_fit(int,int);//最佳适应算法StatusNext_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==3)//选择循环首次适应算法{if(Next_fit(ID,request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;returnOK;}elseif(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-n