操作操作系统大作业
题目：首次适应算法分配内存
学 号：
学生姓名：
班 级：计科121
首次适应算法分配内存
一、 问题描述
在内存分配中，动态分区是根据实际的进程需求，动态地为之分配空间。而首次适应算法分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分配给用户。可利用空间表本身既不按节点的初始地址有序，也不按节点的大小有序。用户释放内存，回收时只是将空闲块插入在链表的表头即可，此算法比较节省时间。
二、 运行环境 VC6.0
三、 算法思想。
首次适应算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始查找，直到找到一个大小能满足要求的空闲分区为止；然后按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲区仍留在空闲链中。若从链首到链尾都不能找到一个能满足要求的分区，则此次分配失败。
四、 实验目的
在计算机系统中，为了提高内存区的利用率，必须给电脑内存区进行合理的分配。本实验通过对内存区分配方法首次适应算法的使用，来了解内存分配的模式。
五、 首次适应算法分配内存算法概要
（1） 结构体
Typedef struct freearea//定义一个空闲区说明表结构
{ long size; //分区大小
long address; //分区地址
int state; //状态
}ElemType; // 线性表的双向链表存储结构
Typedef struct DuLNode
{ ElemType data;
structDuLNode *prior; //前趋指针
structDuLNode *next; //后继指针
} DuLNode,*DuLinkList;
Status Initblock(intMAX_length)//开创带头结点的内存空间链表
{ block_first=(DuLinkList)malloc(sizeof(DuLNode));
block_last=(DuLinkList)malloc(sizeof(DuLNode));
block_first-＞prior=NULL; //头结点的前驱指针指向空
block_first-＞next=block_last; //头结点的后继指针指向尾结点
block_last-＞prior=block_first; //尾结点的前驱指针指向头结点
block_last-＞next=NULL; //尾结点的后继指针指向空
block_last-＞data.address=0; //尾结点的地址是0
block_last-＞data.size=MAX_length; //分区大小是最大分区
block_last-＞data.state=Free; //状态是空
return OK; }
（2）主要函数说明：
void alloc()；进行内存分配的功能函数。
Status free(int flag)将地址为flag的分区的内存回收。
Status First_fit(int request)创建进程空间的子函数；其中，参数request表示空闲分区链的链首指针；要配合函数alloc（）使用。
void show()查看内存中的分区情况。
六、 流程图
七、 代码实现
#include
#include
#include
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1 //完成
#define ERROR 0 //出错
//#define MAX_length 640 //最大内存空间为640KB
typedefint Status;
int flag;
typedefstructfreearea//定义一个空闲区说明表结构
{
long size; //分区大小
long address; //分区地址
int state; //状态
}ElemType; // 线性表的双向链表存储结构
typedefstructDuLNode
{
ElemType data;
structDuLNode *prior; //前趋指针
structDuLNode *next; //后继指针
} DuLNode,*DuLinkList;
DuLinkListblock_first; //头结点
DuLinkListblock_last; //尾结点
Status alloc(int);//内存分配
Status free(int); //内存回收
Status First_fit(int);//首次适应算法
void show();//查看分配
Status Initblock();//开创空间表
Status Initblock(intMAX_length)//开创带头结点的内存空间链表
{
block_first=(DuLinkList)malloc(sizeof(DuLNode));
block_last=(DuLinkList)malloc(sizeof(DuLNode));
block_first-＞prior=NULL; //头结点的前驱指针指向空
block_first-＞next=block_last; //头结点的后继指针指向尾结点
block_last-＞prior=block_first; //尾结点的前驱指针指向头结点
block_last-＞next=NULL; //尾结点的后继指针指向空
block_last-＞data.address=0; //尾结点的地址是0
block_last-＞data.size=MAX_length; //分区大小是最大分区
block_last-＞data.state=Free; //状态是空
return OK;
}
//分配主存
Status alloc() {
int request = 0;
printf("请输入需要分配的主存大小(单位:KB)：");
scanf("%d",&request);
if(request＜0 ||request==0)
{
printf("配大小不合适，请重试！");
return ERROR;
}
{
if(First_fit(request)==OK)
printf("分配成功！");
else
printf("内存不足，分配失败！");
return OK;
}
}
//首次适应算法
Status First_fit(int request)
{ //为申请作业开辟新空间且初始化
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));
temp-＞data.size=request;
temp-＞data.state=Busy;
DuLNode *p=block_first-＞next;
while(p)
{
if(p-＞data.state==Free && p-＞data.size==request)
{//有大小恰好合适的空闲块
p-＞data.state=Busy;
return OK;
break;
}
if(p-＞data.state==Free && p-＞data.size＞request)
{//有空闲块能满足需求且有剩余
temp-＞prior=p-＞prior;
temp-＞next=p;
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-=request;
return OK;
break;
}
p=p-＞next;
}
return ERROR;
}
//主存回收
Status free(int flag) {
DuLNode *p=block_first;
for(inti= 0; i＜= flag; i++)
if(p!=NULL)
p=p-＞next;else
return ERROR;
p-＞data.state=Free;
if(p-＞prior!=block_first&& p-＞prior-＞data.state==Free)//与前面的空闲块相连
{
p-＞prior-＞data.size+=p-＞data.size;
p-＞prior-＞next=p-＞next;
p-＞next-＞prior=p-＞prior;
p=p-＞prior;
}
if(p-＞next!=block_last&& p-＞next-＞data.state==Free)//与后面的空闲块相连
{
p-＞data.size+=p-＞next-＞data.size;
p-＞next-＞next-＞prior=p;
p-＞next=p-＞next-＞next;
}
if(p-＞next==block_last&& p-＞next-＞data.state==Free)//与最后的空闲块相连
{
p-＞data.size+=p-＞next-＞data.size;
p-＞next=NULL;
}
return OK;
}
//显示主存分配情况
void show() {
int flag = 0;
printf("主存分配情况:\n");
DuLNode *p=block_first-＞next;
printf("分区号\t起始地址\t分区大小\t状态\n\n");
while(p)
{
printf("%d ",flag);
flag++;
printf("%d \t",p-＞data.address);
printf("%dKB \t",p-＞data.size);
if(p-＞data.state==Free)
printf("空闲\n\n");
else
printf("已分配\n\n");
p=p-＞next;
}
printf("++++++++++++++++++++++++++++++++++++++++++++++\n\n");
}
//主函数
void main()
{
int c=1;
intMAX_length;//算法选择标记
printf("首次适应算法内存分配算法：\n");
printf("input MAX_length:\n");
scanf("%d",&MAX_length);
Initblock(MAX_length); //开创空间表
int choice;//操作选择标记
while(c=1)
{
show();
printf("请输入您的操作：");
printf("\n1: 分配内存\n2: 回收内存\n0: 退出\n");
scanf("%d",&choice);
{
if(choice==1)
{
alloc(); // 分配内存
c=1;
}
else if(choice==2) // 内存回收
{
int flag;
printf("请输入您要释放的分区号：\n");
scanf("%d",&flag);
free(flag);
c=1;
}
else if(choice==0)
{break; //退出
}
else //输入操作有误
{
printf("输入有误，请重试！\n");
c=1;
}
}
printf("&&&&&&&\n");}
}
八、 运行截图
九、 思考
这次试验模拟内存分配，模拟了操作系统是如何通过作业调度选择作业进入内存以及系统是如何为进入内存的作业分配内存空间，实现多道作业同时驻留内存，就绪进程队列中的多个进程是如何以分式方式共享CPU，作业运行完成离开系统时，系统如何进行内存回收，采用的是首次适应算法，应用的数据结构是双向链表。实际上整个程序是比较简单的，但是由于自己对链表的应用不熟悉，查阅课本文库才实现内存分配这简单的功能，这个程序的缺陷就是在进行操作选择时没有进行分配空间的情况下回收空间会出现错误。本次试验使我对链表有了一定的了解但是还需继续学习。