《存储管理—动态异长存储资源分配算法.doc》由会员分享，可在线阅读，更多相关《存储管理—动态异长存储资源分配算法.doc（8页珍藏版）》请在三一文库上搜索。
1、存储管理动态异长存储资源分配算法一、设计目的理解动态异长存储分区资源管理， 掌握所需数据结构和管理程序， 了解各种 存储分配算法的优点和缺点。二、设计内容(1) 分析UNIX最先适应(First Fit,FF )存储分配算法，即map数据结构、 存储分配函数 malloc() 和存储释放函数 mfree() ，找出与算法有关的成分。(2) 修改上述与算法有关的成分，使其分别体现 BF( Best Fit, 最佳适应) 分配原则和 WF(Worst Fit ，最环适应 ) 分配原则。三、设计准备(理论、技术)1. 最先适应(First Fit , FF)算法指对于存储申请命令，选取满足申请长度要
2、求且起始地址最小的空闲区域。在实现时，可以将系统中所有的空闲区域按照起始地址由小到大的次序依次记录 于空闲区域表中。 当进程申请存储空间时， 系统由表的头部开始查找， 取满足要 求的第一个表目。 如果表目所对应的区域长度恰好与申请的区域长度相同， 则将 该区域全部分配给申请者， 否则将该区域分割为两部分， 一部分的长度与申请长 度相同，将其分配给申请者； 另一部分的长度为原长度与分配长度之差， 将其记 录在空闲区域表中2. 最佳适应(Best Fit , BF)算法是为了克服最先适应算法缺点提出的。 它在分配时取满足申请要求且长度最 小的空间区域。 在实现时，可以将系统中所有的空闲区域按照长度
3、由小到大的次 序依次记录于空闲区域表中。 当进程申请存储空间时， 系统由表的头部开始查找， 取满足要求的第一个表目。3. 最坏适应(Worst Fit ，WF算法是为了克服最佳适应算法的缺点而提出的。 它在分配时取满足申请要求且长 度最大的空闲区域。 在实现时， 可以将系统中所有的空闲区域按照长度由小到大 的次序依次记录于空闲区域表中。当进程申请存储空间时，取第一个表目。4. 程序设计技术分析按题目题目首先对存储分配表进行初始化；然后对用户输入的请求和释放， 按照动态更新存储分配表，并将每次更新之后的存储分配表在屏幕上显示出来动态分区分配需要解决三个问题：A.对于请求表中的要求内存长度，从可用
4、 表或自由链寻找出合适的空闲区域分配程序。 B .分配空闲区后更新自由链或可用 表。C.进程或作业释放内存资源时，合并相邻空闲区并刷新可用表。四、设计过程(设计思想、代码实现)1. 设计思想(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&&am
5、p;bpp->m_size<s) a=bpp->m_addr;s=bpp->m_size; bp=bpp;(3) 根据最好适应算法编写最坏适应算法 WF_malloc() ，主要代码如下： for(bpp=bp;bpp->m_size;bpp+)/ 最坏适应if(bpp->m_size>s) a=bpp->m_addr; s=bpp->size; bp=bpp;(4) 存储释放函数 mfree(); 被释放的存储区域 与前合并条件 :if(bp>mp&&(bp-1)->m_addr+(bp-1)->m_si
6、ze=a) 与后合并条件 :if(a+size=bp->m_addr&&bp->m_size) 无合并条件 :if(size)(5) showMap() 方法显示存储资源表;(6) 存储分配表进行初始化方法 init()2. 代码实现#ifdef HAVE_CONFIG_H #include<config.h>/ 分配布局函数#endif#include<stdio.h> #include<stdlib.h> #include<iostream.h>#define MAPSIZE 100 struct map/ 存储资
7、源表结构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>=s
8、ize&&bpp->m_size<s) a=bpp->m_addr; s=bpp->m_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 struc
9、t 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>s) 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-
10、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;bp->m_addr<=a&&bp->m_size!0;bp+) if(bp>mp&&(bp-1)->m_addr+(bp-1)->m_size=a)/ 与前合并 (bp-1)->m
11、_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;else if(size)do/ 无合并 t=bp->m_addr; bp->m_addr=a; a=t; t=bp-
12、>m_size; bp->m_size=size; bp+; while(size=t);void init()/ 初始化该链表的指针 struct map *bp;int addr,size;int i=0; bp=map; cout<<"please input starting addr and total size"<<endl; cin>>addr>>size;bp->m_addr=addr;bp->m_size=size;(+bp)->m_size=0;/ 表尾void showMap
13、()/ 显示存储资源表int i=0;struct map *bp;bp=map;cout<<"nCurrent memory map."<<endl; while(bp->m_size!=0)cout<<"<"<<bp->m_addr<<"tt"<<bp->m_size<<">"<<endl; bp+; printf("n");void main()int a,s;/
14、地址，表长int c;/ 选择算法int i;/ 选择需求init();cout<<"Please input,b for BF,w for WF:"<<endl;cin>>c;doshowMap();cout<<"Please input,1 for request,2 for release,0 for exit:"<<endl;cin>>i;switch(i)case 1:cout<<"Please input size"<<endl
15、;cin>>s; if(c='b') a=BF_malloc(map,s);else a=WF_malloc(map,s);if(a=-1)cout<<"request can't be satisfied"<<endl; elsecout<<"alloc memory at address:"<<a<<"size:"<<s<<endl; break;case 2:cout<<"Please i
16、nput addr and size"<<endl; cin>>a>>s;mfree(map,a,s);break;case 0: exit(O);while(1);五、设计结果并分析根据提示输入存储资源表地址和表长；测试数据：0, 100;选择适应算法：最好适应算法输入 b,最坏适应算法输入w;测试数据：b 初始化存储资源表；显示地址和表长 <0100>选择要求1.请求，2.释放，0.退出；测试数据：1； 输入表长；测试数据：20； 分配存储器地址，长度；测试数据：0, 20；显示更新之后的存储分配表 继续选择要求；测试数据：1； 输
17、入表长；测试数据：15； 分配存储器地址，长度；测试数据：20, 15；显示更新之后的存储分配表 如图所示：llsgubuntu./hepPl ease input starting addr mnd total 5 tre;01160Please nputrb for SFrw for WF:bCurrent nehory nap.*keiee>please input F1 for request,z for releasefor exit:1 Please nput size:20attoc memory at a<i(Jress:e&Current ocnory n
18、ap.<2«80>Please input f1 For request,2 for release,fl for exit:1 Please input sire：15illoc memory at address:20,size:isCurrent r>enory hap.«4fi5>继续选择要求；测试数据：2；输入地址和表长；测试数据16, 10；显示更新之后的存储分配表 继续选择要求；测试数据：2；输入地址和表长；测试数据27, 5;显示更新之后的存储分配表 如图所示：Please input 11 for request for relea
19、se.,6 for extt:2 Please input «ddr and size:1G,1O匚 urrent menory ng* *<1014Please Input ,i for request,2 for release.O for ex11;Z Please Input addr and size:27j5CurrentnenoryE$p* .*<161&><275>C565>PleiS Input11forrequest,； for release for e>tt:|六、系统的结构、原理框图和模块等的详细说明1.主流程图功龍选择输入CH卜算法WI算法"J-,.1”另配乙释啟1.分配匚释放*, 1 JnK1/VVVVR卜运应释放WF适应释放结束2.适应算法流程图七、用户使用说明书和参考资料1. 使用说明书根据提示信息输入需求，系统调用函数，显示存储资源表分配情况 输入存储资源表地址和表长；选择适应算法：最好适应算法输入 b，最坏适应算法输入w; 初始化存储资源表；选择要求1.请求，2.释放，0.退出；2. 参考资料计算机操作系统教程左万历著，高等教育出版社出版。-