《存储管理动态分区分配及回收算法》由会员分享，可在线阅读，更多相关《存储管理动态分区分配及回收算法（16页珍藏版）》请在金锄头文库上搜索。
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
3、 adr; /分区首地址int size; /分区大小struct node *next;/指向下一个分区的指针Node;Node *head1,*head2,*back1,*back2,*assign;/*head-空闲区队列首指针back-指向释放区 Node 结构的指针assign-指向申请的内存分区 Node 结构的指针*/int request; /用户申请存储区的大小（由用户输入）int check(int add,int siz,char c)/用于检查指定的释放块（由用户键入）的合法性Node *p,*head;int check=1;if(addnext;while(p!=N
4、ULL)elsep=p-next;if(check=0)printf(“t 输入释放区地址或大小有错误！n“);return check; /*返回检查结果*/void init()/初始化，生成两个带头节点的空闲队列指针， /head1 指向 first-fit 的空闲队列头，head2 指向 best-fit的空闲队列头Node *p,*q;head1=(Node*)malloc(sizeof(Node);head2=(Node*)malloc(sizeof(Node);p=(Node*)malloc(sizeof(Node);q=(Node*)malloc(sizeof(Node);he
5、ad1-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* assignment1(int num,int req)/实现首次适应算法的分配Node *before,*after,*ass;ass=(Node*)malloc(sizeof(Node);before=head1;after=head1-next;ass-id=num;ass-size=req;while(after-sizenext;after=after-next;if(after=NULL)
6、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 acceptment1(int address,int siz,int rd)/实现首次适应算法的回收Node *before,*after;int insert=0;back1=(Node*)malloc(sizeof(Node);bef
7、ore=head1;after=head1-next;back1-adr=address;back1-size=siz;back1-id=rd;back1-next=NULL;while(!insertback1-next=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(afterback1-n
8、ext=after-next;back1-id=after-id;free(after);after=back1;printf(“t 首先分配算法回收内存成功！n“);elseprintf(“t 首先分配算法回收内存失败！n“);Node* assignment2(int num,int 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=r
9、eq;while(after-sizenext;after=after-next;/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
10、;/printf(“nzphzph4n“);before=head2;after=head2-next;/printf(“nzphzph4n“);if(after=NULL)/printf(“nzphzph5n“);before-next=q;q-next=NULL;after=q;else/printf(“nzphzph6n“);while(afterbefore=before-next;after=after-next;/printf(“nzphzph8n“);before-next=q;q-next=after;after=q;return (ass);void acceptment2(
11、int address,int siz,int rd)/实现最佳适应算法的回收Node *before,*after;int insert=0;/是否被回收的标志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(ba
12、ck2-adr=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-n
13、ext;elsebefore=before-next;after=after-next;before=head2;after=head2-next;while(!insert)/将被回收的块插入到恰当的位置（按分区大小从小到大）if(after=NULL|(after-sizeback2-size)back2-next=after;insert=1;break;elsebefore=before-next;after=after-next;if(insert)printf(“t 最佳适应算法回收内存成功！n“);elseprintf(“t 最佳适应算法回收内存失败！n“);void print
14、(char choice)/输出空闲区队列信息Node *p;if(choice=f|choice=F)p=head1-next;elsep=head2-next;if(p)printf(“n 空闲区队列的情况为：n“);printf(“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 menu()/菜单及主要过程char chose;int ch,num,r,add,rd;while(1)system(“cls“);printf(“tt 存储管理
15、动态分区分配及回收算法模拟nn“);printf(“tF.最先适应算法(First-Fit)nn“);printf(“tB.最佳适应算法(Best-Fit)nn“);printf(“tE.退出程序nn“);printf(“t 你选择（f/b）:“);scanf(“%c“,if(chose=e|chose=E)exit(0);elsesystem(“cls“);while(1)if(chose=f|chose=F)printf(“tt 最先适应算法(First-Fit)模拟nn“);if(chose=b|chose=B)printf(“tt 最佳适应算法(Best-Fit)模拟nn“);printf(“t1.分配内存tt2.回收内存nn“);printf(“t3.查看内存tt4.返回nn“);printf(“t 你选择（1/2/3/4）:“);scanf(“%d“,fflush(stdin);switch(ch)
