内存管理实验报告

一、问题概述

动态分区的分配与回收主要解决3个问题：

（1）对于请求表中的要求内存长度，从可用表或自由链寻找出合适的空闲区分配程序 （2）分配空闲区之后，更新可用表或自由链

（3）进程或作业释放内存资源时，合并相邻空闲区并刷新可用表

动态分区时的分配方法有最先适应法（FF）、最佳适应法（BF）及最坏适应法（WF）三种：FF适应法要求可用表按起始地址递增次序排列，一旦找到大于或等于要求内存长度的可用块时立即分配；BF适应算法要求从小到大的次序组成可用表，每次分配可用表中长度与要求分配的内存块最接近的内存块；WF适应法要求可用表按长度大小递减排列，每次分配可用表中长度最大的内存块。

二、 设计流程图

主要流程：

图1 主流程图

FF

图2 FIFO适应法流程图

BF

图3 BF适应法流程图

WF适应法流程图：

图4 WF适应法流程图 三、数据定义

struct allocated{ };

struct all_block{ };

struct all_block *all;//内存块头指针 struct free *f; struct allocated *al; int number;//进程个数 int pid;

int size;//整个内存块长度 int select;//分配方式 struct free *f; struct allocated *a; int id;//分配的进程号 int size;//地址长度 int start;//起始地址 struct allocated *next;

四、源程序

1、首次适应算法

int FF(int size) /*首次适应算法*/ {

struct free *free_f1,*free_f2;int mem_size=size; free_f1=all->f; free_f2=free_f1->next;

for(free_f1=all->f;free_f1!=NULL;free_f1=free_f1->next) {

for(free_f2=free_f1->next;free_f2!=NULL;free_f2=free_f2->next)

if(free_f2->startstart) { free_f1->start=free_f2->start; ree_f1->size=free_f2->size;} }/*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size>0) set_pro_mem(mem_size);return 1; }

2、最佳适应算法

int BF(int size) /*最佳适应算法*/ {

struct free *free_f1,*free_f2; int mem_size=size; free_f1=all->f; free_f2=free_f1->next;

for(free_f1=all->f;free_f1!=NULL;free_f1=free_f1->next)

{ for(free_f2=free_f1->next;free_f2!=NULL;free_f2=free_f2->next)

if(free_f2->sizesize) { free_f1->start=free_f2->start; free_f1->size=free_f2->size;} }/*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size>0)set_pro_mem(mem_size); return 1; }

3、最坏适应算法

int WF(int size) /*最坏分配算法*/

{ struct free *free_f1,*free_f2; int mem_size=size; free_f1=all->f; free_f2=free_f1->next;

for(free_f1=all->f;free_f1!=NULL;free_f1=free_f1->next)

{ for(free_f2=free_f1->next;free_f2!=NULL;free_f2=free_f2->next)

if(free_f2->sizesize) {free_f1->start=free_f2->start; free_f1->size=free_f2->size;} }/*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size>0) set_pro_mem(mem_size); return 1; }

五、运行结果

初始化内存块空间如下：

15

30 45 55 80 90 100

则该内存块的可用内存块有4块，其地址分别为0~15K，25~45K，55~80K，92~100K，长度分别为15K、20K、25K、8K

运行截图如下：

图5 初始化内存块截图

1、用FF适应法为J4分配内存，大小为16K，按照FF适应算法，应该从第二块空闲块中分出16K给J4，然后更新已用表与可用表，结果如下：

15

25 41 45 55 80 92 100 截图如下:

图6 FF适应法运行截图

2、继续用BF适应法为J5分配内存，大小为6K，按照BF适应算法，应该从第四块空闲块中分出6K给J5，然后更新已用表与可用表，结果如下：

15

25 41 45 55 80 92 98 100 截图如下：

图7 BF适应法运行截图

3、继续用WF适应法为J6分配内存，大小为15K，按照WF适应算法，应该从第块空闲块中分出6K给J5，然后更新已用表与可用表，结果如下:

15

25

41 45 55 70 80 92 98 100 截图如下：

图8 WF适应法运行截图

4、销毁进程J1、J3，刷新已用表与可用表，结果如下： 0 25 41 45 55 70 92 98 100

运行截图如下：

图9 FF适应法运行截图

分析以上各图，可知结果正确。 附:

#include #include #include #include #include

struct free{ };

struct allocated{ };

struct all_block{ };

int size;//整个内存块长度 int select;//分配方式 struct free *f; struct allocated *a; int id;//分配的进程号 int size;//地址长度 int start;//起始地址 struct allocated *next; int size;//地址长度 int start;//起始地址 struct free *next;

struct all_block *all;//内存块头指针 struct free *f; struct allocated *al; int number;//进程个数 int pid;

void chushi_all(int s) {

all=(struct all_block *)malloc(sizeof(struct all_block)); all->f=(struct free *)malloc(sizeof(struct free));

all->a=(struct allocated *)malloc(sizeof(struct allocated)); all->size=s; all->f->size=s;

all->f->start=0; all->f->next=NULL; }

void chushi_allocated() {

struct allocated* ab; struct free *f1; f1=all->f; ab=all->a; int size; int start;

while(ab->next!=NULL){ab=ab->next;}

ab->next=(struct allocated *)malloc(sizeof(struct allocated)); ab->next->id=pid; printf("\n进程%d:",pid); printf("\n分配的地址长度:"); scanf("%d",&size); ab->next->size=size; printf("分配的起始地址:"); scanf("%d",&start); ab->next->start=start; ab->next->next=NULL; while(f1->next!=NULL) {

if((start>f1->start)&&((start+size)size+f1->start))) {struct free* f2;

f2=(struct free *)malloc(sizeof(struct free)); f2->next=f1->next; f2->size=(f1->size-size); f1->size=(f1->size-size); all->a->next=NULL;

} } f2->start=(size+start); f1->next=f2; break; } f1=f1->next;

int set_pro_mem(int mem_size)

{

struct free *f1,*f2;

struct allocated *a1;

f1=all->f;

f2=f1;

a1=all->a;

while(f1!=NULL && f1->size

{

if(f1==f2) f1=f1->next;

else

{ f1=f1->next;f2=f2->next;}

}

if(f1==NULL)

{printf("没有足够分配的空间!\n"); return 0;}

if(f1->size==mem_size )

{

while(a1->next!=NULL){ a1=a1->next;}

a1->next=(struct allocated *)malloc(sizeof(struct allocated)); a1->next->id=pid;

a1->next->size=f1->size;

a1->next->start=f1->start;

//sprintf(a1->next->process_name,"PROCESS-%02d",pid); a1->next->next=NULL;

if(f1==f2)

{all->f=f1->next; free(f1);}

else

{ f2->next=f1->next; free(f1);}

}

else if(f1->size>mem_size)

{

while(a1->next!=NULL){a1=a1->next;}

a1->next=(struct allocated*)malloc(sizeof(struct allocated)); a1->next->id=pid;

a1->next->size=mem_size;

a1->next->start=f1->start;

//sprintf(a1->next->process_name,"PROCESS-%02d",pid);

a1->next->next=NULL;

f1->size=(f1->size)-mem_size;

f1->start=(f1->start)+mem_size;

}

return 1;

}

int FF(int size) /*首次适应算法*/

{

struct free *free_f1,*free_f2;

int mem_size;

mem_size=size;

free_f1=all->f;

free_f2=free_f1->next;

for(free_f1=all->f;free_f1!=NULL;free_f1=free_f1->next)

{

for(free_f2=free_f1->next;free_f2!=NULL;free_f2=free_f2->next) {

if(free_f2->startstart)

{

free_f1->start=free_f2->start;

free_f1->size=free_f2->size;

}

}

}/*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size>0) set_pro_mem(mem_size);

return 1;

}

int BF(int size) /*最佳适应算法*/

{

struct free *free_f1,*free_f2;

int mem_size;

mem_size=size;

free_f1=all->f;

free_f2=free_f1->next;

for(free_f1=all->f;free_f1!=NULL;free_f1=free_f1->next)

{

for(free_f2=free_f1->next;free_f2!=NULL;free_f2=free_f2->next) {

if(free_f2->sizesize)

{

free_f1->start=free_f2->start;

free_f1->size=free_f2->size;

}

}

}/*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size>0)set_pro_mem(mem_size);

return 1;

}

int WF(int size) /*最坏分配算法*/

{

struct free *free_f1,*free_f2;

int mem_size;

mem_size=size;

free_f1=all->f;

free_f2=free_f1->next;

for(free_f1=all->f;free_f1!=NULL;free_f1=free_f1->next)

{

for(free_f2=free_f1->next;free_f2!=NULL;free_f2=free_f2->next) {

if(free_f2->sizesize)

{

free_f1->start=free_f2->start;

free_f1->size=free_f2->size;

}

}

}/*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size>0) set_pro_mem(mem_size);

return 1;

}

void menu1()

{

} int select; int size; printf("请输入所需内存大小:"); scanf("%d",&size); printf("选择内存分配方式:"); printf("1 FF 2 BF 3 WF"); scanf("%d",&select); switch(select) { case 1:FF(size);break; case 2:BF(size);break; default:break; } case 3:WF(size);break;

struct allocated* find(int id)/*进程查找函数*/

{

struct allocated *allo;

allo=all->a->next;

while(allo!=NULL&&allo->id!=id)

{allo=allo->next;}

return allo;

}

int free_block(struct allocated *ab)//释放空间，修改可用表

{

struct free *ftb,*work,*work_f,*temp;

ftb=(struct free*)malloc(sizeof(struct free));

ftb->start=ab->start;

ftb->size=ab->size;

ftb->next=all->f;

all->f=ftb;

ftb=all->f;

work_f=all->f;

work=work_f->next;

while(work!=NULL)

{

if(ftb->start+ftb->size==work->start)

{

ftb->size=ftb->size+work->size;

temp=work;

work_f->next=work->next;

work_f=all->f;

work=work_f->next;

free(temp);

}

else if(work->start+work->size==ftb->start)

{

ftb->start=work->start;

ftb->size=ftb->size+work->size;

temp=work;

work_f->next=work->next;

work_f=all->f;

work=work_f->next;

free(temp);

}

else

{

work=work->next;

work_f=work_f->next;

}

}

return 1;

}

int menu2()

{

int id; struct allocated *ab,*allo; ab=all->a; printf("输入要销毁的进程号: "); scanf("%d",&id); allo=find(id); if(allo==NULL) if(ab==ab) {all->a=all->a->next;return 1;} { printf("没有该进程!\n"); return 0;}

while(ab->next!=allo)

{ab=ab->next;}

ab->next=allo->next;

free_block(ab);

return 1;

}

int display_mem_usage()/*内存使用情况显示函数*/

{

struct free *fbt;

struct allocated *ab;

ab=all->a->next;

fbt=all->f;

printf("------------------------------\n");

printf("可用表:\n");

printf("%20s %20s\n"," 起始地址"," 地址长度"); while(fbt!=NULL)

{

printf("%20d %20d\n",fbt->start,fbt->size);

fbt=fbt->next;

}

printf("\n已用表:\n");

printf("%15s %15s %15s \n","进程号","起始地址","地址长度"); while(ab!=NULL)

{

printf("%15d %15d %15d \n",ab->id,ab->start,ab->size);

ab=ab->next;

}

printf("------------------------------\n");

return 1;

}

int main()

{

int select;

int all_size;

char c='y';

pid=0;

printf("\n请输入内存块大小：");

scanf("%d",&all_size);

chushi_all(all_size);//初始化内存块

printf("\n请初始化已分配表：");

while(c=='Y'||c=='y')

{ pid++;

chushi_allocated();printf("是否继续初始化？Y/N }

display_mem_usage();

while(1)

{

printf("\n1 创建新进程并分配空间"); printf("\n2 销毁进程释放空间");

printf("\n");

scanf("%d",&select);

switch(select)

{

case 1:menu1();break;

case 2:menu2();break;

default:break;

}

display_mem_usage();

}

getchar();

return 1;

}

");scanf("%s",&c);