动态分区分配算法

动态分区分配算法一实验内容与要求内容：动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了三种分配算法，分别是1.首次适应算法，2.循环首次适应算法，3.最佳适应算法。要求：动态分区算法也称为可变分区分配算法，常见的空闲区查找算法有首次适应算法，循环首次适应算法，最佳适应算法。特别注意分区回收时，相邻空闲分区需要合并。(1)参考操作系统教材理解这3种分配算法以及回收算法。(2)实现3种分配算法以及回收算法。(3)已知作业申请内存和释放内存的序列，给出内存的使用情况。(4)作业申请内存和释放内存的序列可以存放在文本文件中。(5)设计简单的交互界面，演示所设计的功能。(可以使用MFC进行界面的设计)(6)可根据自己能力，在完成以上基本要求后，对程序功能进行适当扩充。二、需求分析本次实验通过用C语言进行编程并调试、运行，形象地表现出动态分区的分配方式，直观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之间的区别。加深了我们对两种算法优缺点的理解，帮助我们了解一些数据结构和分配算法，进一步加深我们对动态分区存储器管理方式及其实现过程的理解。主要的问题在于，如何解决两种算法对内存的释放和回收空间的表示。动态分区分配：又称为可变分区分配，这种分配方式并不事先先将主存划分成一块块的分区，而是在作业进入主存时，根据作业的大小动态地建立分区。并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数目也是可变的。分区分配算法：1.首次适应法：为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。特点：优先利用内存中底地址部分的空闲分区(将所有空闲区,按其地址递增的顺序链接)2.循环首次适应算法该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N==0时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。3.最佳适应算法：接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配;为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。三、概要设计动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示：typedefstructfreearea//定义一个空闲区说明表结构{intID;//分区号longsize;//分区大小longaddress;//分区地址intstate;//状态}ElemType;typedefstructDuLNode//doublelinkedlist{ElemTypedata;structDuLNode*prior;//前趋指针structDuLNode*next;//后继指针}DuLNode,*DuLinkList;前向指针和后向指针分别用于与当前分区的前后分区相链接，address用于说明当前分区的起始地址，状态字为0时表示当前分区空闲，为1时表示已分配，id为分配的作业号，size表示分配的内存大小。流程图：开始读入文件选择算法首次循环最佳选择操作根据选择算法做出相应操作显示结果到达文件尾部显示结果选择根据要求，请求释放内存空进显示结果结束四、详细设计#includeiostream#includestdio.h#includefstream#includestdlib.husingnamespacestd;#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_mid;DuLinkListblock_last;//尾结点Statusalloc(int);//内存分配Statusalloc2(int);//内存分配2Statusfree(int);//内存回收StatusFirst_fit(int,int);//首次适应算法StatusCycleFirst_fit(int,int);//循环首次适应算法StatusBest_fit(int,int);//最佳适应算法voidshow();//查看分配StatusInitblock();//开创空间表intID,request;longadds=0;StatusInitblock()//开创带头结点的内存空间链表{block_first=(DuLinkList)malloc(sizeof(DuLNode));block_last=(DuLinkList)malloc(sizeof(DuLNode));block_mid=(DuLinkList)malloc(sizeof(DuLNode));block_first-prior=NULL;block_first-next=block_mid;block_mid-next=block_last;block_mid-prior=block_first;block_last-prior=block_mid;block_last-next=NULL;block_mid-data.address=0;block_mid-data.size=MAX_length;block_mid-data.ID=0;block_mid-data.state=Free;returnOK;}//-----------------------分配主存-------------------------Statusalloc(intch){if(request0||request==0){cout分配大小不合适，请重试！endl;returnERROR;}switch(ch){case1:if(First_fit(ID,request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;ID=0;request=0;returnOK;break;case2:if(CycleFirst_fit(ID,request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;ID=0;request=0;returnOK;break;case3:if(Best_fit(ID,request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;ID=0;request=0;returnOK;break;default:cout********ERROR!********;}}Statusalloc2(intch){intID,request;cout请输入作业(分区号)：;cinID;cout请输入需要分配的主存大小(单位:KB)：;cinrequest;if(request0||request==0){cout分配大小不合适，请重试！endl;returnERROR;}switch(ch){case1:if(First_fit(ID,request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;returnOK;break;case2:if(CycleFirst_fit(ID,request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;returnOK;break;case3:if(Best_fit(ID,request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;returnOK;break;default:cout********ERROR!********;}}//------------------首次适应算法-----------------------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;}//------------------循环首次适应算法-----------------------StatusCycleFirst_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&&p-data.address==adds){//有空闲块能满足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp;p-prior=temp;p-data