存储管理—动态异长存储资源分配算法

存储管理—动态异长存储资源分配算法一、设计目的理解动态异长存储分区资源管理，掌握所需数据结构和管理程序，了解各种存储分配算法的优点和缺点。二、设计内容（1）分析UNIX最先适应（FirstFit,FF）存储分配算法，即map数据结构、存储分配函数malloc()和存储释放函数mfree()，找出与算法有关的成分。(2)修改上述与算法有关的成分，使其分别体现BF（BestFit,最佳适应）分配原则和WF(WorstFit，最环适应)分配原则。三、设计准备（理论、技术）1.最先适应（FirstFit，FF）算法指对于存储申请命令，选取满足申请长度要求且起始地址最小的空闲区域。在实现时，可以将系统中所有的空闲区域按照起始地址由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时，系统由表的头部开始查找，取满足要求的第一个表目。如果表目所对应的区域长度恰好与申请的区域长度相同，则将该区域全部分配给申请者，否则将该区域分割为两部分，一部分的长度与申请长度相同，将其分配给申请者；另一部分的长度为原长度与分配长度之差，将其记录在空闲区域表中2.最佳适应（BestFit，BF）算法是为了克服最先适应算法缺点提出的。它在分配时取满足申请要求且长度最小的空间区域。在实现时，可以将系统中所有的空闲区域按照长度由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时，系统由表的头部开始查找，取满足要求的第一个表目。3.最坏适应（WorstFit，WF）算法是为了克服最佳适应算法的缺点而提出的。它在分配时取满足申请要求且长度最大的空闲区域。在实现时，可以将系统中所有的空闲区域按照长度由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时，取第一个表目。4.程序设计技术分析按题目题目首先对存储分配表进行初始化；然后对用户输入的请求和释放，按照动态更新存储分配表，并将每次更新之后的存储分配表在屏幕上显示出来动态分区分配需要解决三个问题：A.对于请求表中的要求内存长度，从可用表或自由链寻找出合适的空闲区域分配程序。B.分配空闲区后更新自由链或可用表。C.进程或作业释放内存资源时，合并相邻空闲区并刷新可用表。四、设计过程（设计思想、代码实现）1.设计思想(1)分析最先适应算法，定义map数据结构；设置整形变量存储存储资源表信息structmap{intm_addr;intm_size;};(2)分析UNIX最先适应存储分配算法编写最佳适应算法BF_malloc()；遍历链表，取满足申请要求且长度最小的空间区域for(bpp=bp;bpp-m_size;bpp++){//最佳适应if(bpp-m_size=size&&bpp-m_sizes){a=bpp-m_addr;s=bpp-m_size;bp=bpp;}}(3)根据最好适应算法编写最坏适应算法WF_malloc()，主要代码如下：for(bpp=bp;bpp-m_size;bpp++){//最坏适应if(bpp-m_sizes){a=bpp-m_addr;s=bpp-size;bp=bpp;}}(4)存储释放函数mfree();被释放的存储区域与前合并条件:if(bpmp&&(bp-1)-m_addr+(bp-1)-m_size==a)与后合并条件:if(a+size==bp-m_addr&&bp-m_size)无合并条件:if(size)(5)showMap()方法显示存储资源表；(6)存储分配表进行初始化方法init()2.代码实现#ifdefHAVE_CONFIG_H#includeconfig.h//分配布局函数#endif#includestdio.h#includestdlib.h#includeiostream.h#defineMAPSIZE100structmap//存储资源表结构{intm_addr;intm_size;};structmapmap[MAPSIZE];//存储资源表//BF存储分配函数intBF_malloc(structmap*mp,intsize){registerinta,s;registerstructmap*bp,*bpp;for(bp=mp;bp-m_size;bp++){if(bp-m_size=size){a=bp-m_addr;s=bp-m_size;for(bpp=bp;bpp-m_size;bpp++){//最佳适应if(bpp-m_size=size&&bpp-m_sizes){a=bpp-m_addr;s=bpp-m_size;bp=bpp;}}bp-m_addr+=size;if((bp-m_size-==size)==0)do{bp++;(bp-1)-m_addr=bp-m_addr;}while((bp-1)-m_size=bp-m_size)return(a);}}return(1);}//WF存储分配函数intWF_malloc(structmap*mp,intsize){registerinta,s;registerstructmap*bp,*bpp;for(bp=mp;bp-m_size;bp++){if(bp-m_size=size){a=bp-m_addr;s=bp-m_size;for(bpp=bp;bpp-m_size;bpp++){//最坏适应if(bpp-m_sizes){a=bpp-m_addr;s=bpp-size;bp=bpp;}}bp-m_addr+=size;if((bp-size-==size)==0)do{bp++;(bp-1)-m_addr=bp-m_addr;}while((bp-1)-m_size=bp-m_size);return(a);}}return(-1);}//存储释放函数voidmfree(structmap*mp,intaa,intsize){registerstructmap*bp;registerintt;registerinta;a=aa;for(bp=mp;bp-m_addr=a&&bp-m_size!0;bp++)if(bpmp&&(bp-1)-m_addr+(bp-1)-m_size==a){//与前合并(bp-1)-m_size+=size;(bp-1)-m_size+=bp-m_size;while(bp-m-size){bp++;(bp-1)-m_addr=bp-m_addr;(bp-1)-m_size=bp-size;}}else{if(a+size==bp-m_addr&&bp-m_size){//与后合并bp-m_addr-=size;bp-m_size+=size;}elseif(size)do{//无合并t=bp-m_addr;bp-m_addr=a;a=t;t=bp-m_size;bp-m_size=size;bp++;}while(size=t);}}voidinit(){//初始化该链表的指针structmap*bp;intaddr,size;inti=0;bp=map;coutpleaseinputstartingaddrandtotalsizeendl;cinaddrsize;bp-m_addr=addr;bp-m_size=size;(++bp)-m_size=0;//表尾}voidshowMap(){//显示存储资源表inti=0;structmap*bp;bp=map;cout\nCurrentmemorymap...endl;while(bp-m_size!=0){coutbp-m_addr\t\tbp-m_sizeendl;bp++;}printf(\n);}voidmain(){inta,s;//地址，表长intc;//选择算法inti;//选择需求init();coutPleaseinput,bforBF,wforWF:endl;cinc;do{showMap();coutPleaseinput,1forrequest,2forrelease,0forexit:endl;cini;switch(i){case1:coutPleaseinputsizeendl;cins;if(c=='b')a=BF_malloc(map,s);elsea=WF_malloc(map,s);if(a==-1)coutrequestcan'tbesatisfiedendl;elsecoutallocmemoryataddress:asize:sendl;break;case2:coutPleaseinputaddrandsizeendl;cinas;mfree(map,a,s);break;case0:exit(0);}}while(1);}五、设计结果并分析根据提示输入存储资源表地址和表长;测试数据：0，100；选择适应算法：最好适应算法输入b，最坏适应算法输入w；测试数据：b初始化存储资源表；显示地址和表长0100选择要求1.请求，2.释放，0.退出；测试数据：1；输入表长；测试数据：20；分配存储器地址，长度；测试数据：0，20；显示更新之后的存储分配表继续选择要求；测试数据：1；输入表长；测试数据：15；分配存储器地址，长度；测试数据：20，15；显示更新之后的存储分配表如图所示：继续选择要求；测试数据：2；输入地址和表长；测试数据16，10；显示更新之后的存储分配表继续选择要求；测试数据：2；输入地址和表长；测试数据27，5；显示更新之后的存储分配表如图所示：六、系统的结构、原理框图和模块等的详细说明1.主流程图2.适应算法流程图七、用户使用说明书和参考资料1.使用说明书根据提示信息输入需求，系统调用函数，显示存储资源表分配情况。输入存储资源表地址和表长;选择适应算法：最好适应算法输入b，最坏适应算法输入w;初始化存储资源表;选择要求1.请求，2.释放，0.退出;2.参考资料《计算机操作系统教程》左万历著，高等教育出版社出版。