《存储管理系统—动态异长存储资源分配算法》由会员分享，可在线阅读，更多相关《存储管理系统—动态异长存储资源分配算法（8页珍藏版）》请在金锄头文库上搜索。
1、word存储管理动态异长存储资源分配算法一、设计目的理解动态异长存储分区资源管理，掌握所需数据结构和管理程序，了解各种存储分配算法的优点和缺点。二、设计内容1分析UNIX最先适应First Fit,FF存储分配算法，即map数据结构、存储分配函数malloc()和存储释放函数mfree()，找出与算法有关的成分。(2) 修改上述与算法有关的成分，使其分别表现BFBest Fit,最优适应分配原如此和WF(Worst Fit，最环适应)分配原如此。三、设计准备理论、技术1.最先适应First Fit，FF算法指对于存储申请命令，选取满足申请长度要求且起始地址最小的空闲区域。在实现时，可以将系统中
2、所有的空闲区域按照起始地址由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时，系统由表的头部开始查找，取满足要求的第一个表目。如果表目所对应的区域长度恰好与申请的区域长度一样，如此将该区域全局部配给申请者，否如此将该区域分割为两局部，一局部的长度与申请长度一样，将其分配给申请者；另一局部的长度为原长度与分配长度之差，将其记录在空闲区域表中2.最优适应Best Fit，BF算法是为了克制最先适应算法缺点提出的。它在分配时取满足申请要求且长度最小的空间区域。在实现时，可以将系统中所有的空闲区域按照长度由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时，系统由表的头部开始查找，取满足
3、要求的第一个表目。3.最坏适应Worst Fit，WF算法是为了克制最优适应算法的缺点而提出的。它在分配时取满足申请要求且长度最大的空闲区域。在实现时，可以将系统中所有的空闲区域按照长度由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时，取第一个表目。按题目题目首先对存储分配表进展初始化；然后对用户输入的请求和释放，按照动态更新存储分配表，并将每次更新之后的存储分配表在屏幕上显示出来动态分区分配需要解决三个问题：A.对于请求表中的要求内存长度，从可用表或自由链寻找出适宜的空闲区域分配程序。B.分配空闲区后更新自由链或可用表。C.进程或作业释放内存资源时，合并相邻空闲区并刷新可用表。四、
4、设计过程设计思想、代码实现(1)分析最先适应算法，定义map数据结构；设置整形变量存储存储资源表信息struct mapint m_addr;int m_size;(2) 分析UNIX最先适应存储分配算法编写最优适应算法BF_malloc()；遍历链表，取满足申请要求且长度最小的空间区域for(bpp=bp;bpp-m_size;bpp+)/最优适应if(bpp-m_size=size&bpp-m_sizem_addr;s=bpp-m_size;bp=bpp;(3)根据最好适应算法编写最坏适应算法WF_malloc()，主要代码如下：for(bpp=bp;bpp-m_size;bpp+)/最坏
5、适应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()#ifdef HAVE_CONFIG_H#include/分配布局函数#endif#include#include#include#define MAPSIZE 100str
6、uct map/存储资源表结构int m_addr;int m_size;struct map mapMAPSIZE;/存储资源表/BF存储分配函数int BF_malloc(struct map *mp,int size)register int a,s;register struct map *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_sizem_addr;s=bpp-m_
7、size;bp=bpp;bp-m_addr+=size;if(bp-m_size-=size)=0)dobp+;(bp-1)-m_addr=bp-m_addr;while(bp-1)-m_size=bp-m_size)return(a);return(1);/WF存储分配函数int WF_malloc(struct map *mp,int size)register int a,s;register struct map *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;b
8、pp-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)dobp+;(bp-1)-m_addr=bp-m_addr;while(bp-1)-m_size=bp-m_size);return(a);return(-1);/存储释放函数void mfree(struct map *mp,int aa,int size)register struct map *bp;register int t;register int a;a=aa;for(bp=mp
9、;bp-m_addrm_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;elseif(a+size=bp-m_addr&bp-m_size)/与后合并bp-m_addr-=size;bp-m_size+=size;else if(size)do/无合并t=bp-m_addr;bp-m_addr=a;a=t;t=bp-
10、m_size;bp-m_size=size;bp+;while(size=t);void init()/初始化该链表的指针struct map *bp;int addr,size;int i=0;bp=map;coutplease input starting addr and total sizeaddrsize;bp-m_addr=addr;bp-m_size=size;(+bp)-m_size=0;/表尾void showMap()/显示存储资源表int i=0;struct map *bp;bp=map;coutnCurrent memory map.m_size!=0)coutm_a
11、ddrttm_sizeendl;bp+;printf(n);void main()int a,s;/地址，表长int c;/选择算法int i;/选择需求init();coutPlease input,b for BF,w for WF:c;doshowMap();coutPlease input,1 for request,2 for release,0 for exit:i;switch(i)case 1:coutPlease input sizes;if(c=b)a=BF_malloc(map,s);elsea=WF_malloc(map,s);if(a=-1)coutrequest c
12、ant be satisfiedendl;elsecoutalloc memory at address:asize:sendl;break;case 2:coutPlease input addr and sizeas;mfree(map,a,s);break;case 0:exit(0);while(1);五、设计结果并分析根据提示输入存储资源表地址和表长;测试数据：0，100；选择适应算法：最好适应算法输入b，最坏适应算法输入w；测试数据：b初始化存储资源表；显示地址和表长选择要求1.请求，2.释放，0.退出；测试数据：1；输入表长；测试数据：20；分配存储器地址，长度；测试数据：0，20；显示更新之后的存储分配表继续选择要求；测试数据：1；输入表长；测试数据：15；分配存储器地址，长度；测试数据：20，15；显示更新之后的存储分配表如下列图：继续选择要求；测试数据：2；输入地址和表长；测试数据16，10；显示更新之后的存储分配表继续选择要求；测试数据：2；输入地址和表长；测试数据27，5；显示更新之后的存储分配表如下列图：
