首次适应算法（C语言实现）

首次适应算法（C语言实现）"/>

首次适应算法（C语言实现）

1、实验目的

（1）掌握动态分区分配算法原理；

（2）熟悉首次适应算法，掌握连续分配内存内存分配的过程、内存回收的方法。

2、实验内容

编程实现首次适应算法。已知作业名、作业大小、内存容量、碎片大小，要求使用首次适应分配算法给每次到来的作业分配内存，输出内存分配情况；给完成的作业回收内存，输出回收后内存分配情况。显示内存的分配情况，格式如下：

分区号    作业号（名）   分区始址    分区大小   分区状态

    已知主存256K，碎片大小为2K，OS占用低位16K，现有一作业序列如下：

    作业1要求134K，作业2要求30K，作业3要求64K，作业1完成，作业3完成，作业4要求60K，作业5要求62K，作业2完成，作业6要求12K，作业7要求32K。

3、算法描述

首次适应算法(first fit)：

空闲分区按地址递增的次序排列。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；如果分区大小-作业大小<=碎片，则直接分配，否则，按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。

 4、源程序代码

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>#define FREE 0
#define BUSY 1
#define Max_length 256//主存typedef struct freearea//空闲区的结构体
{int ID;//作业号int size;//分区大小int address;//分区始址bool isUsed;//使用状态，0为未占用，1为已占用
} freearea;typedef struct DuNode//首尾不互连的双向链表结点
{freearea data;//数据域struct DuNode *prior;//指针域struct DuNode *next;
} DuNode, *DuLinkList;DuLinkList m_rid;
DuLinkList m_last;void init()//空闲区队列初始化
{m_rid = (DuLinkList)malloc(sizeof(DuNode));m_last = (DuLinkList)malloc(sizeof(DuNode));m_rid->prior = NULL;m_rid->next = m_last;m_last->prior = m_rid;m_last->next = NULL;m_rid->data.size = 0;m_rid->data.isUsed = BUSY; //首结点不会被使用，定义为占用状态防止分区合并失败m_last->data.address = 0;m_last->data.size = Max_length;m_last->data.ID = 0;m_last->data.isUsed = 0;
}int first_fit(int ID,int size)//首次适应算法，以低地址分配
{int msize = 2;//碎片DuNode *p = m_rid->next;while(p){if(p->data.ID == ID)//不允许存在同名作业{printf("该作业号对应的作业已经在内存中！");return 0;}if (p->data.size < size || p->data.isUsed == BUSY){p=p->next;continue;}if (p->data.size - size <= msize)//请求大小刚好满足或者小于碎片大小{p->data.isUsed=BUSY;p->data.ID=ID;return 1;}else//空闲区比所需内存大，则需要将多的内存作回收处理{DuLinkList temp = (DuLinkList)malloc(sizeof(DuNode));temp->data.ID=ID;temp->data.size=size;temp->data.isUsed=BUSY;temp->next=p;temp->prior=p->prior;temp->data.address=p->data.address;p->prior->next=temp;p->prior=temp;p->data.address=temp->data.address+temp->data.size;p->data.size-=size;return 1;}p=p->next;}return 0;
}void alloc()//分配内存
{int ID,size1;printf("请输入作业号：");scanf("%d", &ID);printf("请输入所需内存大小：");scanf("%d", &size1);if (ID<=0 || size1<=0)printf("错误！请输入正确的作业号和请求的内存大小");if(first_fit(ID,size1))printf("分配内存成功！\n");elseprintf("分配内存失败！\n");
}void freeNode()//释放内存
{int ID;DuNode *p = m_rid->next, *s;printf("输入需要释放内存的作业号：");scanf("%d", &ID);while (p){if (p->data.ID == ID){p->data.ID = 0;p->data.isUsed = FREE;if (!p->prior->data.isUsed && (p->next == NULL || p->next->data.isUsed))//与前一个空闲区相邻，则合并{p->prior->data.size += p->data.size;p->prior->next = p->next;if (p->next != NULL)p->next->prior = p->prior;free(p);printf("释放内存成功！\n");break;}if (p->next!=NULL && (!p->next->data.isUsed && p->prior->data.isUsed)) //与后一个空闲区相邻，则合并{s = p->next;p->data.size += p->next->data.size;if(p->next->next){p->next->next->prior = p;}p->next = p->next->next;free(s);printf("释放内存成功！\n");break;}if(p->next!=NULL && (!p->prior->data.isUsed && !p->next->data.isUsed)) //前后的空闲区均为空{p->prior->data.size += p->data.size + p->next->data.size;p->prior->next = p->next->next;if(p->next->next != NULL){p->next->next->prior = p->prior;}free(p->next);free(p);printf("释放内存成功！\n");break;}printf("释放内存成功！\n");break;}p = p->next;if(!p)printf("内存中没有作业%d！",ID);}
}void show()
{printf("************************************************************\n");printf("内存分配情况如下：\n");printf("分区号   作业号    分区始址    分区大小    分区状态\n");DuNode *p = m_rid->next;int k=1;while (p != NULL) {printf("%5d ", k++);if (p->data.ID == FREE) {printf("   NULL");} else {printf("%5d ", p->data.ID);}printf("%10d%12d", p->data.address, p->data.size);if (p->data.isUsed == 0) {printf("         空闲\n");}else {printf("         已分配\n");}p = p->next;}printf("************************************************************\n");
}void main()
{printf("------------------");printf("首次适应算法");printf("------------------\n");init();int tag = 1;while(tag < 3 && tag > 0){printf("输入要进行的操作");printf("（1-分配内存，2-内存释放，其他-退出程序）：");scanf("%d", &tag);switch(tag){case 1:alloc();show();break;case 2:freeNode();show();break;default:printf("程序已退出！");}}
}

5、运行结果