实验目的：
了解动态分区分配方式中的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。
算法了解：
- 首次适应算法（first-fit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法的目的在于减少查找时间。
- 最佳适应算法（best-fit）：从全部空闲区中找出能满足作业要求的，且大小最小的空闲分区，这种方法能使碎片尽量小。
- 最差适应算法（worst-fit）：它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的节点大小趋于均匀。
实验内容：
- 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程和回收过程。其中，空闲分区通过空闲分区链（表）来管理；在进行内存分配时，系统优先使用空闲区低端的空间。
- 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列： •作业1申请130KB •作业2申请60KB •作业3申请100KB •作业2释放60KB •作业4申请200KB •作业3释放100KB •作业1释放130KB •作业5申请140KB •作业6申请60KB •作业7申请50KB •作业8申请60KB 请分别采用首次适应算法和最佳适应算法进行内存的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。
算法思路：
- FF算法中空闲分区的排序是按照分区地址来排序的，在分配过程中，按内存地址从低到高依次查询符合条件的分区，并将符合条件的分区分配出去。当分配后，原有分区剩余内存
==0时，释放该分区（释放C语言中的指针），否则，将该分区的起始地址设置成node->start + size，大小设置为node->size - size - 而BF算法主要的区别是其空闲分区的排序是按照分析大小排序的，其余过程基本和FF算法一致
以下附本程序源代码：
#include <stdio.h>
#include <stdlib.h>
#define getpch(type) (type*)malloc(sizeof(type))
struct LNode
{
int size;
int start;
int end;
struct LNode *next;
struct LNode *front;
}*L; /*空闲区头指针 */
struct WNode
{
int size;
int start;
int end;
int id;
struct WNode *next;
struct WNode *front;
}*Work; /*作业区头指针 */
typedef struct LNode LN; /*别名*/
typedef struct WNode WN; /*别名*/
WN* FineNode; /*用于寻找的指针*/
int n; /*空闲区个数*/
int workCount = 1; /*作业ID*/
void addNode(int size,int start) /*添加结点到空闲分区*/
{
LN *p,*s,*t;
p = L;
t = p->next;
s = getpch(LN); //生成新结点
s->size = size;
s->start = start;
s->end = start + size ;
s->next = t; //插入 L 中
p->next = s;
if(t)
{
t->front = s;
}
s->front = p;
}
void addWorkNode(int id, int size,int start) /*添加结点到作业分区*/
{
WN *p,*s,*t;
p = Work;
t = p->next;
s = getpch(WN); //生成新结点
s->size = size;
s->start = start;
s->end = start + size ;
s->id = id;
s->next = t; //插入 Work 中
p->next = s;
if(t)
{
t->front = s;
}
s->front = p;
}
void PrintList() /* 打印 */
{
LN *p; int i;
WN *w;
p = L->next;
w = Work->next;
printf("|------------------------------------|\n");
printf("|空闲区号 长度 起始位置 终止位置 |\n");
for(i=1;i<=n;i++)
{
printf("| %3d\t %3d\t%3d\t %4d |\n",i,p->size, p->start,p->end);
p=p->next;
}
printf("|-------------------------------------\n");
printf("|作业ID 长度 起始位置 终止位置 |\n");
while(w)
{
printf("| %3d\t %3d\t%3d\t %4d |\n",w->id,w->size, w->start,w->end);
w=w->next;
}
printf("|-------------------------------------\n");
}
void BFSortList() /* 最佳适应算法的排序 */
{
LN *p,*s,*t;
int min_size,i;
int size,start,end;
t=L->next;
p=L->next;
for(i=0;i<n;i++)
{
s=p->next;
min_size = p->size;
while(s)
{
if(min_size > s->size)
{
min_size=s->size;
t=s;
}
s=s->next;
}
size=t->size;
start=t->start;
end=t->end;
t->size=p->size;
t->start=p->start;
t->end=p->end;
p->size=size;
p->start=start;
p->end=end;
t=p->next;
p=p->next;
}
}
void FFSortList() /*首次适应算法的排序 */
{
LN *p,*s,*t;
int min_start,i;
int size,start,end;
t = L->next;
p = L->next;
for(i=0;i < n;i++)
{
s = p->next;
min_start = p->start;
while(s)
{
if(min_start > s->start)
{
min_start = s->start;
t = s;
}
s=s->next;
}
size = t->size;
start = t->start;
end = t->end;
t->size = p->size;
t->start = p->start;
t->end = p->end;
p->size = size;
p->start = start;
p->end = end;
t = p->next;
p = p->next;
}
}
void FreeMalloc() /* 生成空闲分区链 */
{
int size,start,i;
L = getpch(LN); /* 生成一个表头结点 */
L->next = NULL;
L->front = NULL;
printf("请输入空闲区个数:");
scanf("%d",&n);
for(i = 1;i <= n;i++)
{
printf("请输入第%d空闲区的大小和始址 :",i);
scanf("%3d %3d",&size,&start);
addNode(size,start);
}
}
void WorkMalloc() /* 生成作业分区链 */
{
int size,start,i;
Work = getpch(WN); /* 生成一个表头结点 */
Work->next = NULL;
Work->front = NULL;
FineNode = getpch(WN); /* 生成一个表头结点 */
FineNode->next = NULL;
FineNode->front = NULL;
}
void Assign(int size, int id) /* 最佳适应算法和首次适应算法空闲分区的分配 */
{
LN *p,*t;
p = L->next;
t = L;
while(p)
{
if(size > p->size)
{
p = p->next;
t = t->next;
if(!p)
{
printf(" 空闲内存不足，分配不成功 ");
}
}
else
{
addWorkNode(id,size,p->start);/* 将该内存块放入作业表 */
p->size = p->size - size;
p->start = p->start + size ;
if( p->size == 0)
{
t->next = p->next ;
if(p->next)
{
p->next->front = t;
}
n--;
free(p);
}
printf(" 分配成功！ \n");
workCount++;
PrintList();
break;
}
}
}
void DelWorkNode(int id) /* 在作业表中删除指定id作业 */
{
WN *p,*t;
p = Work->next;
t = Work;
while(p)
{
if( p->id == id)
{
t->next = p->next ;
if(p->next)
{
p->next->front = t;
}
printf(" 回收成功！ \n");
free(p);
PrintList();
break;
}
p = p->next;
t = t->next;
}
}
void Recover(int start, int end) /* 回收回调函数 */
{
LN *p,*t;
int size,flag=0;
size = end - start;
p = L->next;
t = p->next;
while(p)
{
if(t && (p->end == start) && (t->start == end))// 待回收的上下面都有空闲区
{
p->size = p->size + size + t->size;
p->end = t->end;
p->next = t->next;
t->next->front = p;
free(t);
n--;
FFSortList(L);
flag=1;
break;
}
else if(p->end == start)// 待回收的上面有空闲区
{
flag=1;
p->size = p->size + size;
p->end = p->end + size ;
FFSortList(L);
break;
}
else if( p->start == end)// 待回收的下面有空闲区
{
p->size = p->size +size;
p->start = start;
FFSortList(L);
flag=1;
break;
}
p=p->next;
if(p)
{
t=p->next;
}
}
if(flag==0)// 待回收的上下面都没有空闲区
{
addNode(size,start);
n++;
}
}
void FindID(int id) /* 在作业表中寻找特定id号的作业 */
{
WN *p;
p = Work->next;
while(p)
{
if((p->id) == id)
{
FineNode = p;
break;
}
p = p->next;
}
}
int WorkRecover(int id) /* 作业内存回收 */
{
FineNode = NULL;
FindID(id);
if(FineNode == NULL)
{
printf("不存在该作业ID\n");
return 0;
}
else
{
Recover(FineNode->start,FineNode->end);
DelWorkNode(FineNode->id);
return 1;
}
}
void CleanStdin()
{
int ch;
while( (ch=getchar()) != '\n' && ch!=EOF);/*清除键盘输入缓冲区*/
}
void Menu() /*显示菜单*/
{
printf("请选择服务类型 :\n");
printf("1: 首次适应算法 \n");
printf("2: 最佳适应算法 \n");
printf("3: 回收内存 \n");
printf("0: 退出 \n");
printf("输入您要的选项 :");
}
int main(void) /*main函数*/
{
int start,end,size;
int id;
int choice;
FreeMalloc(); /*开辟空闲区*/
WorkMalloc(); /*开辟作业区*/
CleanStdin(); /*清除输入缓冲区*/
Menu(); /*显示菜单*/
scanf("%d",&choice); /*输出操作选项*/
while(choice)
{
switch(choice)
{
case 1:
{
FFSortList(); /*对空闲区进行排序*/
PrintList(); /*输出空闲区和作业区*/
printf(" 请输入进程%d所需要的空闲区大小 :",workCount);
scanf("%d",&size);
Assign(size,workCount); /*空闲区的分配*/
break;
}
case 2:
{
BFSortList(); /*对空闲区进行排序*/
PrintList(); /*输出空闲区和作业区*/
printf(" 请输入进程%d所需要的空闲区大小 :",workCount);
scanf("%d",&size);
Assign(size,workCount); /*空闲区的分配*/
break;
}
case 3:
{
PrintList(); /*输出空闲区和作业区*/
printf("请输入需要回收到的作业ID：");
scanf("%d",&id);
WorkRecover(id); /*回收内存*/
break;
}
case 0: exit(0); /*退出*/
default : printf("输入错误 ,请重新输入\n");
}
CleanStdin(); /*清除输入缓冲区*/
Menu(); /*显示菜单*/
scanf("%d",&choice);
}
return 0;
}