存储管理—动态异长存储资源分配算法
一、设计目的
理解动态异长存储分区资源管理，掌握所需数据结构和管理程序，了解各种 存储分配算法的优点和缺点。
二、设计内容
（1）分析UNIX最先适应（First Fit,FF）存储分配算法，即map数据结构、存储分配函数malloc()和存储释放函数mfree()，找出与算法有关的成分。 (2) 修改上述与算法有关的成分，使其分别体现BF（Best Fit,最佳适应） 分配原则和WF(Worst Fit，最环适应)分配原则。
三、设计准备（理论、技术）
1.最先适应（First Fit，FF）算法
指对于存储申请命令，选取满足申请长度要求且起始地址最小的空闲区域。在实现时，可以将系统中所有的空闲区域按照起始地址由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时，系统由表的头部开始查找，取满足要求的第一个表目。如果表目所对应的区域长度恰好与申请的区域长度相同，则将该区域全部分配给申请者，否则将该区域分割为两部分，一部分的长度与申请长度相同，将其分配给申请者；另一部分的长度为原长度与分配长度之差，将其记录在空闲区域表中
2.最佳适应（Best Fit，BF）算法
是为了克服最先适应算法缺点提出的。它在分配时取满足申请要求且长度最小的空间区域。在实现时，可以将系统中所有的空闲区域按照长度由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时，系统由表的头部开始查找，取满足要求的第一个表目。
3.最坏适应（Worst Fit，WF）算法
是为了克服最佳适应算法的缺点而提出的。它在分配时取满足申请要求且长度最大的空闲区域。在实现时，可以将系统中所有的空闲区域按照长度由小到大的次序依次记录于空闲区域表中。当进程申请存储空间时，取第一个表目。 4.程序设计技术分析
按题目题目首先对存储分配表进行初始化；然后对用户输入的请求和释放，按照动态更新存储分配表，并将每次更新之后的存储分配表在屏幕上显示出来
动态分区分配需要解决三个问题：A.对于请求表中的要求内存长度，从可用表或自由链寻找出合适的空闲区域分配程序。B.分配空闲区后更新自由链或可用表。C.进程或作业释放内存资源时，合并相邻空闲区并刷新可用表。
四、设计过程（设计思想、代码实现）
1.设计思想
(1)分析最先适应算法，定义map数据结构；设置整形变量存储存储资源表信息 struct map{ int m_addr; int m_size;};
(2) 分析UNIX最先适应存储分配算法编写最佳适应算法BF_malloc()；遍历链表，取满足申请要求且长度最小的空间区域 for(bpp=bp;bpp->m_size;bpp++){//最佳适应 if(bpp->m_size>=size&&bpp->m_size
(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_size==a) 与后合并条件:if(a+size==bp->m_addr&&bp->m_size) 无合并条件:if(size)
(5)showMap()方法显示存储资源表； (6)存储分配表进行初始化方法init() 2.代码实现
#ifdef HAVE_CONFIG_H
#include
#include
struct map//存储资源表结构 {
int m_addr; int m_size; };
struct map map[MAPSIZE];//存储资源表 //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_size
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存储分配函数
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;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) do{
bp++;
(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;bp->m_addr<=a&&bp->m_size!0;bp++)
if(bp>mp&&(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; }
else if(size) do{//无合并
t=bp->m_addr; bp->m_addr=a; a=t;
t=bp->m_size; bp->m_size=size; bp++; }
while(size=t); } }
void init(){//初始化该链表的指针 struct map *bp; int addr,size; int i=0; bp=map;
cout<<\ cin>>addr>>size; bp->m_addr=addr;
bp->m_size=size;
(++bp)->m_size=0;//表尾 }
void showMap(){//显示存储资源表 int i=0;
struct map *bp; bp=map;
cout<<\ while(bp->m_size!=0){
cout<<\ bp++; }
printf(\}
void main(){
int a,s;//地址，表长 int c;//选择算法 int i;//选择需求 init();
cout<<\ cin>>c; do{
showMap();
cout<<\exit:\ cin>>i; switch(i){ case 1:
cout<<\ cin>>s; if(c=='b')
a=BF_malloc(map,s); else
a=WF_malloc(map,s); if(a==-1)
cout<<\ else
cout<<\ break; case 2:
cout<<\ cin>>a>>s;
mfree(map,a,s); break;