存储管理动态分区分配及回收算法

《存储管理动态分区分配及回收算法》由会员分享，可在线阅读，更多相关《存储管理动态分区分配及回收算法（19页珍藏版）》请在装配图网上搜索。

1、存储管理动态分区分配及回收算法（First Fit AlgorithmBest Fit Algor）一、目的和要求分区管理是应用较广泛的一种存储管理技术。本实验要求用一种结构化高级语 言构造分区描述器，编制动态分区分配算法和回收算法模拟程序，并讨论不同 分配算法的特点。二、实验内容1、编写：First Fit Algorithm首次适应算法（First Fit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分 配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址 部分空闲区，在低址空间造成许多小

2、的空闲区，在高地址空间保留大的空闲区。2、编写：Best Fit Algorithm 最佳适应算法（Best Fit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种 方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区 要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。 该算法保留大的空闲区，但造成许多小的空闲区。#include#include#include#define MAX_SIZE 32767typedef struct node /定义分区描述器的结构int id;/编号int adr;/分区首地址int size;/分区大小

3、struct n ode *n ext;/指向下一个分区的指针Node;Node *head 1 ,*head2,*back1 ,*back2,*assign;/*head-空闲区队列首指针back-指向释放区Node结构的指针assig n-指向申请的内存分区Node结构的指针*/- 1 -int request; /用户申请存储区的大小(由用户输入)int check(i nt add, int siz,char c)用于检查指定的释放块(由用户键入 )的合法性Node *p,*head;int check=1;if(add0|siznext;while(p!=NULL)&check)/*

4、地址不能和空闲区表中结点出现重叠*/ if(addadr)&(add+sizp-adr)|(add=p-adr)&(addadr+p-size)check=0;elsep=p-next;if(check=0)printf(t输入释放区地址或大小有错误！ n); return check; /*返回检查结果*/void in it()/初始化，生成两个带头节点的空闲队列指针， /head1指向first-fit的空闲队列头，head2指向best-fit的空闲队列头 Node *p,*q;head1=(Node*)malloc(sizeof(Node);head2=(Node*)malloc(s

5、izeof(Node); p=(Node*)malloc(sizeof(Node);q=(Node*)malloc(sizeof(Node);head1-next=p;head2-next=q;p-size=q-size=MAX_SIZE;p-adr=q-adr=0;p-next=q-next=NULL; p-id=q-id=0;Node* assig nmen t1( int num,i nt req)/实现首次适应算法的分配Node *before,*after,*ass; ass=(Node*)malloc(sizeof(Node);before=head1; after=head1-n

6、ext;ass-id=num; ass-size=req;while(after-sizenext; after=after-next;if(after=NULL)ass-adr=-1; 分配失败elseif(after-size=req)/空闲分区恰好等于所申请的内存大小before-next=after-next; ass-adr=after-adr;else/空闲分区大于所申请的内存大小after-size-=req;ass-adr=after-adr;after-adr+=req;return ass;void acceptme nt1(i nt addressnt siz,i nt

7、rd)/ 实现首次适应算法的回收Node *before,*after;int insert=0;back1=(Node*)malloc(sizeof(Node);before=head1;after=head1-next;back1-adr=address;back1-size=siz;back1-id=rd;back1-next=NULL;while(!insert&after)/将要被回收的分区插入空闲区(按首址大小从小到大插入)if(after=NULL)|(back1-adradr)&(back1-adr=before- adr)before-next=back1;back1-nex

8、t=after;insert=1;elsebefore=before-next;after=after-next;if(insert)if(back1-adr=before-adr+before-size)/和前边分区合并before-size+=back1-size;before-next=back1-next;free(back1);else if(after&back1-adr+back1-size=after-adr) /和后边分区合并back1-size+=after-size;back1-next=after-next;back1-id=after-id;free(after);a

9、fter=back1;printf(t首先分配算法回收内存成功！ ！ ！ n);elseprintf(t首先分配算法回收内存失败！ ！ n);Node* assig nmen t2(i nt num,i nt req)/实现最佳适应算法的分配Node *before,*after,*ass,*q;ass=(Node*)malloc(sizeof(Node);q=(Node*)malloc(sizeof(Node);before=head2;after=head2-next;ass-id=num;ass-size=req;while(after-sizenext;after=after-next

10、;/printf(nzphzph1n);if(after=NULL)ass-adr=-1; 分配失败/printf(nzphzph2n);elseif(after-size=req)/空闲分区恰好等于所申请的内存大小 before-next=after-next;ass-adr=after-adr;/printf(nzphzph3n);else/空闲分区大于所申请的内存大小q=after;before-next=after-next;ass-adr=q-adr;q-size-=req;q-adr+=req;/printf(nzphzph4n);before=head2;after=head2-

11、next;/printf(nzphzph4n); if(after=NULL)/printf(nzphzph5n); before-next=q; q-next=NULL;after=q;else/printf(nzphzph6n);while(after&(after-size)size) printf(nzphzph7n);before=before-next; after=after-next;/printf(nzphzph8n);before-next=q;q-next=after;after=q;return (ass);void acceptme nt2(i nt addressn

12、t siz,i nt rd)/ 实现最佳适应算法的回收 Node *before,*after;int in sert=O;是否被回收的标志 back2=(Node*)malloc(sizeof(Node);before=head2; after=head2-next;back2-adr=address; back2-size=siz;back2-id=rd; back2-next=NULL;if(head2-next=NULL)/空闲队列为空head2-next=back2;/head2-size=back2-size;else/空闲队列不为空while(after)if(back2-adr

13、=after-adr+after-size) /和前边空闲分区合并 before-next=after-next; after-size+=back2-size; back2=after;after=before-next;elsebefore=before-next;after=after-next;before=head2;after=head2-next;while(after)if(after-adr=back2-adr+back2-size) /和后边空闲区合并 before-next=after-next; back2-size+=after-size; after=before-

14、next;else before=before-next; after=after-next;before=head2;after=head2-next;while(!insert) /将被回收的块插入到恰当的位置(按分区大小从小到大)if(after=NULL|(after-sizeback2-size)&(before-sizesize)before-next=back2;back2-next=after; insert=1;break;elsebefore=before-next; after=after-next;if(insert)printf(t最佳适应算法回收内存成功！! n);

15、elseprintf(t最佳适应算法回收内存失败！ ！ n);void prin t(char choice)/输出空闲区队列信息- 9 -Node *p;if(choice=f|choice=F)p=head1-next;elsep=head2-next;if(p)printf(n空闲区队列的情况为：n);prin tf(t编号t首址t终址t大小n);while(p)printf(t%dt%dt%dt%dn,p-id,p-adr,p-adr+p-size-1,p- size);p=p-next;void me nu()菜单及主要过程char chose;int ch,num,r,add,rd

16、;while(1)system(cls);prin tf(tt存储管理动态分区分配及回收算法模拟nn);prin tf(tF.最先适应算法(First-Fit)nn);prin tf(tB .最佳适应算法(Best-Fit)nn ”)；prin tf(tE .退出程序nn);printf(t你选择(f/b) :);scanf(%c,&chose);if(chose=e|chose=E)exit(0);elsesystem(cls);while(1)if(chose=f|chose=F)prin tf(tt 最先适应算法(First-Fit)模拟nn);if(chose=b|chose=B)pr

17、in tf(tt 最佳适应算法(Best-Fit)模拟nn);prin tf(t1.分配内存tt2.回收内存nn ”)；prin tf(t3 .查看内存tt4 .返回nn ”)；printf(t你选择(1/2/3/4):);scanf(%d,&ch);fflush(stdin);switch(ch)case 1:printf(输入分区号：”);seanf(%d,&num);prin tf(输入申请的分区大小：);sca nf(%d,&r);if(ehose=f|ehose=F)assign=assignment1(num,r);elseassign=assignment2(num,r);if(

18、assign-adr=-1)printf(分配内存失败！ n);elseprintf(分配成功！分配的内存的首址为:dn,assig n-adr);- 11 -break;case 2:prin tf(输入释放的内存的首址：);sca nf(%d, &add); printf(输入释放的内存的大小：);sca nf(%d,&r); printf(输入释放的内存的编号：);sca nf(%d,&rd); if(check(add,r,chose)if(chose=f|chose=F)acceptment1(add,r,rd);elseacceptment2(add,r,rd);break;case 3:print(chose);break;case 4:menu();break;void mai n() 主函数init();menu();蹌娱| 嫙匕嗬Cz潴宐8觢書?鍉？D澪肣愂權QW,;H邪1僞弲葈vP1拫?俻櫤瞓3年艥龖刦1掴軾諟弫i?T嗂b靔m蒷忭樅j忀炭鰄h;C?粀彵zv?;芶鳗?？摻?x隚x ?鎒？H?驴珺w V粢长#EfD慓挌?W查 vP