实验三 存储管理——动态不等长存储资源分配算法    

一、实验目的

理解动态异长存储分区资源管理，掌握所需数据结构和管理程序，了解各种存储分配算法的优点和缺点。

二、实验原理

最佳适应算法（Best Fit）：申请时取最小可满足区域；

最坏适应算法（Worst Fit）：申请时取最大可满足区域；

三、实验内容

 1、分析UNIX最先适应(FF)存储分配算法，即map数据结构、存储分配函数malloc()和存储释放函数mfree()，找出与算法有关的成分。

 2、修改上述与算法有关的成分，使其分别体现BF分配原则和WF分配原则。 

三、实验设计

1、按内容要求编写最佳适应和最坏适应存储分配算法。

2、编写测试程序，对存储分配表进行初始化。然后对用户输入的请求和释放，按算法动态更新存储分配表，并将每次更新之后的存储分配表在屏幕上显示出来。

四、实验源码 

 

#ifdef HAVE_CONFIG_H

#include<config.h>

#endif

#include<stdio.h>

#include<stdlib.h>

#define MAPSIZE 100

struct map

{

int m_addr;

int m_size;

};

struct map map[MAPSIZE];

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 < s)

{

a=bpp->m_addr;

a=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);

}

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->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);

}

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;

if(a+size == bp->m_addr)

{

(bp-1)->m_size += bp->m_size;

while(bp->m_size)

{

bp++;

(bp-1)->m_addr += bp->m_addr;

(bp-1)->m_size += bp->m_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;

printf("Please input starting addr and size:");

scanf("%d,%d",&addr,&size);

bp->m_addr=addr;

bp->m_size=size;

(++bp)->m_size=0;

getchar();// 消除回车换行

}

void show_map()

{

int i=0;

struct map *bp;

bp=map;

printf("\nCurrent memory map...\n");

printf("Address\tSize\n");

while(bp->m_size != 0)

{ //if()

printf("<%d\t\t%d>\n",bp->m_addr,bp->m_size);

bp++;

}

printf("\n");

}

main()

{

int a,s;

int c;

int i;

init();

printf("Please input ,b for BF, w for WF:");

scanf("%c",&c);

do

{

show_map();

printf("Please input ,1 for request, 2 for release, 0 for exit:");

scanf("%d",&i);

getchar(); //消除回车换行,否则影响下次输入

switch(i)

{

case 1:

printf("please input size:");

scanf("%d",&s);

if(c=='b')

a=BF_malloc(map,s);

else

a=WF_malloc(map,s);

if(a== -1)

printf("request can't be satisfied\n");

else

printf("alloc memory at address :%d,size:%d\n",a,s);

break;

case 2:

printf("Please input addr and size:");

scanf("%d,%d",&a,&s);

mfree(map,a,s);

break;

case 0:

exit(0);

}

}

while(1);

}

五、实验结果 

（1）用BF算法得到的结果截图如下

http://s13/middle/7d49c180hc2a954aef9fc&690

http://s8/middle/7d49c180hc2a954cab5b7&690

（2）用WF算法得到的结果如下 

http://s13/middle/7d49c180hc2a954b4169c&690

http://s3/middle/7d49c180hc2a954db9792&690

 

五、实验结论

验证了BF和WF算法申请存储空间时的分配原则。