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