动态分区分配方式首次适应算法.docx
《动态分区分配方式首次适应算法.docx》由会员分享，可在线阅读，更多相关《动态分区分配方式首次适应算法.docx（9页珍藏版）》请在冰点文库上搜索。
动态分区分配方式首次适应算法
动态分区分配方式首次适应算法
•算法思路
使用动态分区分配中的数据结构和分配算法，编辑动态分区存储管理方式并实现。
本程序主要采用首次适应算法的动态分区分配过程alloc（）和回收过程free（）。
空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小分配给作业。
二、算法流程图
检查完否？
从头开始查表
Yes
No
与要求内存是否一致？
继续查找下一个表
No
Yes
三、函数代码
#include
#include
#defineFree0//空闲状态
#defineBusy1//已用状态
#defineOK1//完成
#defineERROR0//出错
#defineMAX_length640//最大内存空间为640KB
typedefintStatus;
typedefstructfreearea//定义一个空闲区说明表结构
{
intID;
longsize;
longaddress;
intstate;
}ElemType;
typedefstructDuLNode//doublelinkedlist
{
ElemTypedata;
structDuLNode*prior;//前趋指针
structDuLNode*next;//后继指针
}DuLNode,*DuLinkList;
DuLinkListblock_first;//头结点
DuLinkListblock_last;//尾结点
Statusalloc（）;//内存分配
Statusfree（int）;//内存回收
StatusFirst_fit（int,int）;//首次适应算法
voidshow（）;//查看分配
StatusInitblock（）;//开创空间表
StatusInitblock（）//开创带头结点的内存空间链表
{
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;
block_last->data.size=MAX_length;
block_last->data.ID=0;
block_last->data.state=Free;
returnOK;
}
//-----------------------分配主存-------------------------
Statusalloc（）
{
intID,request;
cout<<"请输入作业（分区号）：
";
cin>>ID;
cout<<"请输入需要分配的主存大小（单位:
KB）：
";
cin>>request;
if（request<0||request==0）
{
cout<<"分配大小不合适，请重试！
"<returnERROR;
}
if（First_fit（ID,request）==OK）
cout<<"分配成功！
"<else
cout<<"内存不足，分配失败！
"<}
//------------------首次适应算法-----------------------
StatusFirst_fit（intID,intrequest）//传入作业名及申请量
{
//为申请作业开辟新空间且初始化
DuLinkListtemp=（DuLinkList）malloc（sizeof（DuLNode））;
temp->data.ID=ID;
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;
p->data.ID=ID;
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（intID）
{
DuLNode*p=block_first;
while（p）
{
if（p->data.ID==ID）
{
p->data.state=Free;
p->data.ID=Free;
if（p->prior->data.state==Free）//与前面的空闲块相连
{
p->prior->data.size+=p->data.size;
p->prior->next=p->next;
p->next->prior=p->prior;
}
if（p->next->data.state==Free）//与后面的空闲块相连
{
p->data.size+=p->next->data.size;if（p->next->next==NULL）p->next=NULL;else{
p->next->next->prior=p;
p->next=p->next->next;}
}
break;
}
p=p->next;
}
cout<<"分区：
"<returnOK;
//
}
//---------------显示主存分配情况------------------
voidshow（）
{
cout<<"++++++++++++++++++++++++++++++++++++++++++++\n";
cout<<"+++++主存分配情况++++++\n";
cout<<"++++++++++++++++++++++++++++++++++++++++++++\n";
DuLNode*p=block_first->next;
while（p）
{
cout<<"分区号：
";
if（p->data.ID==Free）
cout<<"Free"<else
cout<data.ID<cout<<"起始地址：
"<data.address;
cout<<"分区大小：
"<data.size<<"KB";
cout<<"状态：
";
if（p->data.state==Free）
cout<<"空闲"<else
cout<<"已分配"<p=p->next;
}
}
//-----------------------主函数---------------------------
voidmain（）
{
Initblock（）;
intchoice;
inti;
for（i=0;;i++）
{cout<<"++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
cout<<"+++++++++++++++动态分区分配方式的模拟一+++++++++++++++++\n";
cout<<"++++++++++++++++++++首次适应算法++++++++++++++++++++++++\n";
cout<<"++++++++++++++++++++++++++++++++++++++++++++\n";
cout<<"++1:
分配内存2:
回收内存++\n";
cout<<"++3:
查看分配0:
退出++\n";
cout<<"++++++++++++++++++++++++++++++++++++++++++++\n";
cout<<"请输入您的操作：
";
cin>>choice;
if（choice==1）//分配内存
alloc（）;
elseif（choice==2）//内存回收
{intID;
cout<<"请输入您要释放的分区号：
";
cin>>ID;
free（ID）;
}
elseif（choice==3）//显示主存
show（）;
elseif（choice==0）//退出
break;
else//输入操作有误
{
cout<<"输入有误，请重试！
"<continue;
}
}
}
四、案例测试
初始空闲区
作业1进入空闲区后的状态
作业2进入空闲区后的状态
作业3进入空闲区后的状态
作业4进入空闲区后的状态
100k
20K
1K
1K
1K
50k
50k
50k
50k
14k
60k
60k
60k
0k
0k
18k
18k
18k
18k
18k
180k
180k
180k
180k
180k
45k
45k
45k
45k
45k
升级会员 