C语言实现动态分区分配与回收

首先,实验的目的是“熟悉动态划分的四种算法和循环利用的四种情况”。掌握动态重新定位的理念。

2。实验原理

第一自适应算法:空闲分区链按照地址递增的顺序链接。当执行内存分配时,将从开始顺序搜索链。

循环优先自适应算法:自由分区链按照地址递增的顺序链接。分配内存时,搜索从最后找到的空闲分区的下一个空闲分区开始。

最佳自适应算法:每次为一个作业分配内存时,满足要求的最小空闲分区总是被分配给该作业。

最差适应算法:每次为作业分配内存时,满足要求的最大空闲分区总是分配给作业。

动态重定位:当单个空闲分区不满足要求时,压缩所有空闲分区,形成一个更大的空闲分区,以满足进程所需的内存空间。

源程序:

# include

# include

# include

typedef结构FreeLink

typedef结构FreeLink

?char名称;//区号

?char名称;//区号

?int startAddr?//起始地址

?int大小;//大小,以k为单位?下一步构造自由链接;

}免费锁定链接;

?int addr//分配的进程所在的内存的第一个地址?int大小;//进程大小

# include

?int addr//分配的进程所在的内存的第一个地址?int大小;//进程大小

?char名称;//进程名

?char名称;//区号

?int标志;//分配状态

?结构过程*下一步;

}进程链接;

int Length Block(FreeBlockLink * L)

?p=L;

# include

?FreeBlockLink* p。

?char名称;//区号

?长度=0;

?同时(p-next!=空)

?{

length

p=p-next;

?}

?返回长度;

?p=L;

# include

?p=L;

# include

?ProcessLink* p。

?char名称;//区号

?长度=0;

?同时(p-next!=空)

?{

length

p=p-next;

?}

?返回长度;

?p=L;

# include

?p=L;

# include

?int大小;

?char名称;//区号

?FreeBlockLink*链接;

?FreeBlockLink* p。

?p=L;

?链接=(FreeBlockLink*)malloc(大小为(FreeBlockLink));

?同时(p-next!=空)

?scanf(“% c % d % d”,名称、大小、StartAddR);

?ff rush(stdin);

?link-name=name;

?链接大小=大小;

# include

?同时(p-next!=空)

?{

p=p-next;

p=p-next;

?}

?p=L;

?//(初始第一个地址是0)

# include

# include

?p=L;

?char名称;

?char名称;//区号

?ProcessLink*链接;

?FreeBlockLink*链接;

?FreeBlockLink* p。

?link=(ProcessLink *)malloc(size of(ProcessLink));

?同时(p-next!=空)

?scanf(“% c % d % d”,名称、大小、StartAddR);

?ff rush(stdin);

?//printf(“% c,%d”,名称,大小);

?链接大小=大小;

?链接大小=大小;

# include

?同时(p-next!=空)

?{

p=p-下一个;

?link-next=p-next;

p=p-next;

?//printf('%c,%d,%d\n ',链接名,链接大小,链接地址);

?//(初始第一个地址是0)

?p=L;

?int I;

?char名称;//区号

?freeNum=0;

?打印(请输入初始空闲分区的数量):

# include

?getchar();

?打印(“请输入每个可用分区的信息:\ n”);

?(I=0;我自由了;i )

?{

BlockTailInsert(L);

?}

?}

?int I;

?p=L;

?p=L;

?int I;

?char名称;//区号

?Printf('请输入请求内存分配的进程数:');

?打印(请输入初始空闲分区的数量):

?getchar();

?(I=0;I进程编号;i )

?{

?{

?}

?}

?p=L;

?p=L;

# include

?FreeBlockLink* p。

?char名称;//区号

?打印(请输入初始空闲分区的数量):

?同时(p-next!=空)

?scanf(“% c % d % d”,名称、大小、StartAddR);

?I=0;

?同时(下一个!=空)

?{

我;

printf('第%d个空闲分区信息:\n ',I);

printf('区号\t大小\t起始地址\ n ');

printf("% c \ t % Dk \ t % Dk \ n ",p-next-name,p-next-size,p-next-StartAddR);

p=p-next;

?}

?printf(' \ n ');

?p-size=p-next-size;

void PrintProcess(ProcessLink * L)

# pragma警告(禁用:4996)

?国际;

?ProcessLink* p .

?p=L;

?I=0;

?同时(下一个!=空)

?{

我;

printf('第%d个进程信息:\n ',I);

printf('进程名\t大小\t在内存的起始地址\ n ');

printf("% c \ t % Dk \ t % Dk \ n ",p-next-name,p-next-size,p-next-addr);

p=p-next;

?}

?printf(' \ n ');

?p-size=p-next-size;

sort.h

# include

# include

include

include '定义。h '

# pragma警告(禁用:4996)

?ProcessLink* p .

?{

?ProcessLink* p .

?int i,j,len

?char tempName

?p=L;

?len=长度过程(L);

?//printf("% d \ n ",len);

?临时名称="

";

?{

?temp addr=0;

?(1=0;我)

# pragma警告(禁用:4996)

p=L;

# pragma警告(禁用:4996)

?}

if(p-next!=NULL)

?{

?p=p-下一个;

?if(p-addr p-next-addr )

?{

?p-addr=p-next-addr;

?p-next-addr=tempAddr .

?p-name=p-next-name;

?p-next-name=TempName;

?}

?p-size=p-next-size;

?p-size=p-next-size;

?}

?p-size=p-next-size;

?tempSize=p-size .

# pragma警告(禁用:4996)

?tempSize=p-size .

?{

?ProcessLink* p .

?FreeBlockLink* p .

?char tempName

?int tempSize,tempStartAddr

?len=长度过程(L);

?//printf("% d \ n ",len);

?//printf("% d \ n ",len);

";

?{

?temp addr=0;

?(1=0;我)

# pragma警告(禁用:4996)

p=L;

# pragma警告(禁用:4996)

?}

?}

?{

?}

?p=p-下一个;

?if(p-size next-size )

?p-addr=p-next-addr;

?p-next-addr=tempAddr .

?p-name=p-next-name;

?p-next-name=TempName;

?}

?p-size=p-next-size;

?p-size=p-next-size;

?}

?p-size=p-next-size;

?tempSize=p-size .

# pragma警告(禁用:4996)

?tempSize=p-size .

?{

?ProcessLink* p .

?FreeBlockLink* p .

?char tempName

?int tempSize,tempStartAddr

?len=长度过程(L);

?//printf("% d \ n ",len);

?//printf("% d \ n ",len);

";

?{

?temp addr=0;

?(1=0;我)

# pragma警告(禁用:4996)

p=L;

# pragma警告(禁用:4996)

?}

for(j=0;j

?{

?}

?p=p-下一个;

?if(p-size next-size )

?p-addr=p-next-addr;

?p-next-addr=tempAddr .

?p-name=p-next-name;

?p-next-name=TempName;

?}

?p-size=p-next-size;

?p-size=p-next-size;

?}

?p-size=p-next-size;

# pragma警告(禁用:4996)

?tempSize=p-size .

?{

?ProcessLink* p .

?FreeBlockLink* p .

?char tempName

?int tempSize,tempStartAddr

?len=长度过程(L);

?//printf("% d \ n ",len);

?//printf("% d \ n ",len);

";

?{

?temp addr=0;

?(1=0;我)

# pragma警告(禁用:4996)

p=L;

# pragma警告(禁用:4996)

?}

p=L;

?{

?}

?p=p-下一个;

?if(p-size next-size )

?p-addr=p-next-addr;

?p-next-addr=tempAddr .

?p-name=p-next-name;

?p-next-name=TempName;

?}

?p-size=p-next-size;

?p-size=p-next-size;

?}

?p-size=p-next-size;

}

?}

无效动态(FreeBlockLink* L1,ProcessLink* L2,ProcessLink* m,int大小);

//删除链表元素算法

void dellfreeblock(FreeBlockLink * L1,FreeBlockLink* p)

{

?FreeBlockLink * m;

?m=L1;

?同时(下一个!=空)

?{

if(m-next==p)

{

m-next=p-next;

free(p);

break

}

m=m-下一个;

?}

}

void DellProcess(ProcessLink * L2,ProcessLink* q)

{

?过程链接* m;

?m=L2;

?同时(下一个!=空)

?{

if(m-next==q)

{

m-next=q-next;

free(q);

break

}

m=m-下一个;

?}

}

//进程分配算法

无效分配(FreeBlockLink* L1,FreeBlockLink* p,ProcessLink* q,int size)

{

?同时(下一个!=空)

?{

if(p-next-size=q-next-size)?//分配空闲分区

{

if(p-next-size - q-next-size)?//小于最小容量,直接将整个空闲分区分出去

{

?q-next-addr=p-next-StartAddr;

?q-下一个尺寸=p-下一个尺寸;

?q-next-flag=1;

?《自由之路(L1,下一页);

?休息;

}

else

{

?//改进程在内存的起始地址 和分配状态

?q-next-addr=p-next-StartAddr;

?q-next-flag=1;

?//改空闲分区

?p-next-StartAddR=q-next-size;

?p-next-size-=q-next-size;

?//标志=1;

?休息;

}

}

p=p-下一个;

//标志;

?}

?//返回标志;

}

//-首次适应算法-

void First Find(FreeBlockLink * L1,ProcessLink* L2,int size)

{

?国际;

?int m;//表示需要分配内存的进程个数

?//int标志;//标识 进程分配成功与否

?FreeBlockLink* p .

?ProcessLink* q .

?sortbayaddr(L1);//按地址递增的顺序排序

?m=纵向流程(L2);

?//printf("% d \ n ",m);

?//印刷过程(L2);

?p=L1;

?q=L2;

?//标志=0。

?(1=0;我

?{

if(q-next-flag==0)

{

p=L1;

分配(L1、p、q、大小);

}

if(q-next-flag==0)

{

动态(L1、L2、q-next、大小);//对内存进行动态重定位

}

if(q-next-flag==0)

printf('进程%c分配内存失败!“,问-下一个名字);

q=q-next;

//PrintFreeBlock(L1);

?}

}

//-循环首次适应算法-

void scan first find(FreeBlockLink * L1,ProcessLink* L2,int size)

{

?I,m,n;

?FreeBlockLink* p .

?ProcessLink* q .

?p=L1;

?q=L2;

?//标志=0。//内存分配成功或者失败标志

?sortbayaddr(L1);

?m=纵向流程(L2);

?//n=纵向块(L1);

?(1=0;我

?{

//标志=0。

if(q-next-flag==0)

{

分配(L1、p、q、大小);

}

if(q-next-flag==0)

{

p=L1;

分配(L1、p、q、大小);

}

if(q-next-flag==0)

动态(L1、L2、q-next、大小);

if(q-next-flag==0)

printf('进程%d分配内存失败!“,问-下一个名字);

q=q-next;

?}

}

//-最佳适应算法-

无效最佳查找(FreeBlockLink * L1,ProcessLink* L2,int size)

{

?我,m。

?FreeBlockLink* p .

?ProcessLink* q .

?p=L1;

?q=L2;

?sortbyMinSize(L1);

?m=纵向流程(L2);

?(1=0;我是;i )

?{

if(q-next-flag==0)

{

p=L1;

分配(L1、p、q、大小);

}

SortByMinSize(L1);

if(q-next-flag==0)

动态(L1、L2、q-next、大小);

if(q-next-flag==0)

printf('进程%d分配内存失败!“,问-下一个名字);

q=q-next;

?}

}

//-最坏适应算法-

void精纺查找(FreeBlockLink* L1,ProcessLink* L2,国际尺码)

{

?我,m。

?FreeBlockLink* p .

?ProcessLink* q .

?p=L1;

?q=L2;

?SortbyMaxSize(L1);

?m=纵向流程(L2);

?(1=0;我是;i )

?{

if(q-next-flag==0)

{

p=L1;

分配(L1、p、q、大小);

}

SortByMaxSize(L1);

if(q-next-flag==0)

动态(L1、L2、q-next、大小);

if(q-next-flag==0)

printf('进程%d分配内存失败!“,问-下一个名字);

q=q-next;

?}

}

//回收算法

void Reco(FreeBlockLink* L1,int addr,int size,char name,int choice)

//(地址大小==p-startAddr ) //下临空闲分区

?FreeBlockLink* p .

?FreeBlockLink* q .

?FreeBlockLink * m;

?int min//在最佳适应算法中帮助找到回收区域

?p=L1;

?q=L1;

?min=

?if(choice==1 || choice==2)

?{

while(p-next!=NULL)

//(地址大小==p-startAddr ) //下临空闲分区

p=p-下一个;

?{//两种情况:1 .找到了p .在空闲分区链的最后一个2 .没有找到p .要回收的进程的首地址要大于p-StartAddr;

?休息;

q=p;

p-StartAddR=addr;

?}

?else

?{

SortByAddr(L1);

while(p-next!=NULL)

//(地址大小==p-startAddr ) //下临空闲分区

p=p-下一个;

if(p-StartAddR addr p-StartAddR

?休息;

q=p;

p-StartAddR=addr;

?}

?如果(p==L1-下一个p-下一个!=空)//不可能有上临临界分区的可能性

?{

?如果(地址大小p-startAddr ) //上不临下不临

//(地址大小==p-startAddr ) //下临空闲分区

m=(FreeBlockLink *)malloc(大小为(FreeBlockLink));

m-name=name;

m-size=大小;

m-StartAddR=addr;

//头插空闲分区链

m-next=p;

L1-下一个=m。

p-StartAddR=addr;

else

//(地址大小==p-startAddr ) //下临空闲分区

if(p-StartAddR addr)

p-size=size;

p-StartAddR=addr;

?}

?}

?否则如果(p-next==空)?

?{//两种情况:1 .找到了p .在空闲分区链的最后一个2 .没有找到p .要回收的进程的首地址要大于p-StartAddr;

//(地址大小==p-startAddr ) //下临空闲分区

if(q-StartAddR q-size==addr addr size p-StartAddR)//上临临界区

//(地址大小==p-startAddr ) //下临空闲分区

?否则,如果((q-StartAddr q-size addr addr size p-StartAddr))?//上不临下不临

p-StartAddR=addr;

?q-next=m;

//(地址大小==p-startAddr ) //下临空闲分区

?否则,如果(q-startAddR q-size==AddR AddR size==p-StartAddR)?//上临下临

?m=(FreeBlockLink *)malloc(大小为(FreeBlockLink));

?m-name=name;

?m-尺寸=大小;

?m-StartAddR=addr;

?//中间插入一个空闲分区

?m-next=p;

p-StartAddR=addr;

?免费(p);

//(地址大小==p-startAddr ) //下临空闲分区

else //情况2、不可能下临临界分区了

?q尺寸=q尺寸p尺寸;

?q-next=p-next;

p-StartAddR=addr;

?p-尺寸=大小;

else //下临

{//q-StartAddR q-size addr addr size==p-StartAddR

?p-StartAddR=addr;

p-StartAddR=addr;

p-StartAddR=addr;

?p-尺寸=大小;

//(地址大小==p-startAddr ) //下临空闲分区

if(p-StartAddR p-size==addr)//上临临界分区

//(地址大小==p-startAddr ) //下临空闲分区

?p-StartAddR=addr;

p-StartAddR=addr;

?p-next=m;

//(地址大小==p-startAddr ) //下临空闲分区

?否则,如果(q-startAddR q-size==AddR AddR size==p-StartAddR)?//上临下临

?m=(FreeBlockLink *)malloc(大小为(FreeBlockLink));

?m-name=name;

?m-尺寸=大小;

?m-StartAddR=addr;

?//尾部插入一个空闲分区

?m-next=p-next;

p-StartAddR=addr;

p-StartAddR=addr;

?}

?else

?{

?{

//(地址大小==p-startAddr ) //下临空闲分区

else if(addr size==p-StartAddR q-StartAddR q-size addr)?//下临空闲分区

p-StartAddR=addr;

p-size=大小;

//(地址大小==p-startAddr ) //下临空闲分区

p-size=size;

if(p-StartAddR addr)

p-StartAddR=addr;

free(p);

//(地址大小==p-startAddr ) //下临空闲分区

else //上不临下不临

q-size=size q-size p-size;

q-next=p-next;

p-StartAddR=addr;

q-next=m;

//(地址大小==p-startAddr ) //下临空闲分区

m=(FreeBlockLink *)malloc(大小为(FreeBlockLink));

m-name=name;

m-size=大小;

m-StartAddR=addr;

m-next=p;

m-next=p;

p-StartAddR=addr;

?}

p-StartAddR=addr;

break

//(地址大小==p-startAddr ) //下临空闲分区

if(q-next-name==m)

?ProcessLink* q .

?int addr

?addr=-1;

?q=L2;

?{

?{

//(地址大小==p-startAddr ) //下临空闲分区

无效恢复(FreeBlockLink* L1,ProcessLink* L2,国际选择)

addr=q-next-addr;

size=q-next-size;

p-StartAddR=addr;

?}

?}

?}

?{

?{

printf(')内存中没有此进程!\ n ');

//printf('进程已回收完\ n ');

?}

?else

?{

?{

雷科(L1,地址,大小,m,选择);

?}

p-StartAddR=addr;

}

//(地址大小==p-startAddr ) //下临空闲分区

{

?int标志;

?茶名称;

?//同时(标志)

?//{

printf(')请输入要回收的进程名:\ n ');

scanf("% c ",名称);

getchar();

雷科夫(L2L1,姓名,选择);

SortByAddr(L1);

否则如果(choice==3)

SortByMinSize(L1);

//打印过程(标题2);

SortByMaxSize(L1);

//printf('回收后空闲分区情况如下:\ n ');

//PrintFreeBlock(L1);

//printf('是否要继续回收?是的,输入1、不,输入0 \ n ');

//scanf("% d ",标志);

//getchar();

?//}

default:退出(0);

//引入动态重定位算法

void Dynamic(FreeBlockLink* L1,ProcessLink* L2,ProcessLink* m,int size)

# pragma警告(禁用:4996)

?//紧凑空闲分区,将已分配的内存放在低址区,将空闲区放在高地址区域

?//如果紧凑后的空闲分区的大小大于要申请的大小,分配,并修改进程状态、各进程的起始地址

?//不满足大小,分配失败

?FreeBlockLink* p .

?FreeBlockLink * n;//指向p的前一个

?ProcessLink* q .

?ProcessLink * mm//指向q的前一个

?整数和;

?sum=0;

?p=L1;

?n=p;

?sortForDynamic(L2);//将在内存中的进程(已分配,或等待分配)按地址排序,便于后续重定位

?q=L2;

?mm=q .

?同时(下一个!=空)

?{

sum=p-next-size;

p=p-next;

?}

?p=L1;

?if(sum=m-size)?//空闲区=申请大小

?{

printf(')耶!重定位后可以分配了\ n ');

m-flag=1;

//printf("% d \ t % d \ n ",p-next-startAddr,q-next-AddR);

if(p-next-StartAddR q-next-addr)

# pragma警告(禁用:4996)

q=q-next;

while(q-next!=NULL )

# pragma警告(禁用:4996)

?mm=q .

?q-next-addr=mm-addr mm-size;

?//printf("% d \ n ",q-next-addr);

?q=q-下一个;

default:退出(0);

//删除第一个结点后面的所有结点。也就是合并为一个空闲区,并改起始地址和大小

p=p-next;

n=p;

while(p-next!=NULL)

# pragma警告(禁用:4996)

?p=p-下一个;

?n-next=p-next;

?免费(p);

?p=n;

default:退出(0);

n-StartAddR=q-Addr q-size;

printf("% d \ t % d \ n ",sum,m-size);

n-size=sum-m-size;

default:退出(0);

else//

# pragma警告(禁用:4996)

q=q-下一个.

q-addr=p-next-StartAddr;

mm=q;

while(q-next!=NULL )

# pragma警告(禁用:4996)

?mm=q .

?q-next-addr=mm-addr mm-size;

?q=q-下一个;

default:退出(0);

//删除第一个结点后面的所有结点。也就是合并为一个空闲区,并改起始地址和大小

p=p-next;

n=p;

while(p-next!=NULL)

# pragma警告(禁用:4996)

?p=p-下一个;

?n-next=p-next;

?免费(p);

?p=n;

default:退出(0);

n-StartAddR=q-Addr q-size;

printf('lala%d\t%d\n ',sum,m-size);

n-size=sum-m-size;

default:退出(0);

?}

?//printf("% d \ n ",m标志);

default:退出(0);

dynamic_partition.c

# include

# include

include

include '算法。h '

# pragma警告(禁用:4996)

void Choice(int Choice,FreeBlockLink* L1,ProcessLink* L2,int size)

?{

?开关(选择)

?{

case 1: First Find(L2L1,大小写);休息;

case 2: scanfirst find(L2L1,大小写);休息;

案例3: best find(L2L1,大小写);休息;

?}

default:退出(0);

?}

# pragma警告(禁用:4996)

int main()

?{

?int选择;//选择算法

?int大小;//空闲分区最小大小

?int标志;//选择分配还是回收

?int结束;//结束标志

?FreeBlockLink * head1

?ProcessLink * head2

?head 1=(FreeBlockLink *)malloc(大小为(FreeBlockLink));

?head 2=(ProcessLink *)malloc(大小为(ProcessLink));

?标题1-下一个=空;

?标题2-下一个=空;

?choice=0;

?大小=0。

?标志=1;//初始化为分配

?end=0;//初始化为未结束

?printf('请输入最小分区的大小:\ n ');

?scanf("% d ",大小);

?getchar();

?printf('请输入最小分区的大小:\ n ');

?scanf("% d ",选项);

?{

?同时(!结束)

# pragma警告(禁用:4996)

if(flag==1)

{

printf('请录入进程的分配请求:\ n ');

creat(head 2);

//打印过程(标题2);

选择(选择,头部1、头部2、尺寸);

printf('请录入进程的分配请求:\ n ');

default:退出(0);

//打印过程(标题2);

恢复(head1,head2,选项);

printf('此时的内存分配与回收情况:\ n ');

PrintFreeBlock(标题1);

//打印过程(标题2);

printf('要结束吗?1.结束0 .继续);

scanf("% d ",结束);

getchar();

如果(!end)

{

printf('继续分配还是回收?1.继续分配2 .回收);

scanf("% d ",标志);

getchar();

}

?}

?返回0;

}