动态分区分配算法要点Word下载.docx
《动态分区分配算法要点Word下载.docx》由会员分享,可在线阅读,更多相关《动态分区分配算法要点Word下载.docx(22页珍藏版)》请在冰点文库上搜索。
![动态分区分配算法要点Word下载.docx](https://file1.bingdoc.com/fileroot1/2023-5/4/7f9b0a56-0fac-4eee-bbb6-7d4435477a7a/7f9b0a56-0fac-4eee-bbb6-7d4435477a7a1.gif)
三、概要设计
动态分区常用的数据结构有空闲分区表和空闲分区链,用来记录内存的使用情况,此题中我采用的是空闲分区链的结构,用链指针将所有的分区链接成一条链,每个分区的结构如下所示:
typedefstructfreearea//定义一个空闲区说明表结构
{
intID;
//分区号
longsize;
//分区大小
longaddress;
//分区地址
intstate;
//状态
}ElemType;
typedefstructDuLNode//doublelinkedlist
ElemTypedata;
structDuLNode*prior;
//前趋指针
structDuLNode*next;
//后继指针
}DuLNode,*DuLinkList;
前向指针和后向指针分别用于与当前分区的前后分区相链接,address用于说明当前分区的起始地址,状态字为0时表示当前分区空闲,为1时表示已分配,id为分配的作业号,size表示分配的内存大小。
流程图:
四、详细设计
#include<
iostream>
#include<
stdio.h>
fstream>
stdlib.h>
usingnamespacestd;
#defineFree0//空闲状态
#defineBusy1//已用状态
#defineOK1//完成
#defineERROR0//出错
#defineMAX_length640//最大内存空间为640KB
typedefintStatus;
intID;
longsize;
longaddress;
intstate;
//----------线性表的双向链表存储结构------------
ElemTypedata;
structDuLNode*prior;
structDuLNode*next;
DuLinkListblock_first;
//头结点
DuLinkListblock_mid;
DuLinkListblock_last;
//尾结点
Statusalloc(int);
//内存分配
Statusalloc2(int);
//内存分配2
Statusfree(int);
//内存回收
StatusFirst_fit(int,int);
//首次适应算法
StatusCycleFirst_fit(int,int);
//循环首次适应算法
StatusBest_fit(int,int);
//最佳适应算法
voidshow();
//查看分配
StatusInitblock();
//开创空间表
intID,request;
longadds=0;
StatusInitblock()//开创带头结点的内存空间链表
block_first=(DuLinkList)malloc(sizeof(DuLNode));
block_last=(DuLinkList)malloc(sizeof(DuLNode));
block_mid=(DuLinkList)malloc(sizeof(DuLNode));
block_first->
prior=NULL;
next=block_mid;
block_mid->
next=block_last;
prior=block_first;
block_last->
prior=block_mid;
next=NULL;
data.address=0;
data.size=MAX_length;
data.ID=0;
data.state=Free;
returnOK;
}
//-----------------------分配主存-------------------------
Statusalloc(intch)
if(request<
0||request==0)
{
cout<
<
"
分配大小不合适,请重试!
endl;
returnERROR;
}
switch(ch)
case1:
if(First_fit(ID,request)==OK)cout<
分配成功!
elsecout<
内存不足,分配失败!
ID=0;
request=0;
returnOK;
break;
case2:
if(CycleFirst_fit(ID,request)==OK)cout<
case3:
if(Best_fit(ID,request)==OK)cout<
default:
********ERROR!
********"
;
Statusalloc2(intch)
intID,request;
cout<
请输入作业(分区号):
cin>
>
ID;
请输入需要分配的主存大小(单位:
KB):
request;
//------------------首次适应算法-----------------------
StatusFirst_fit(intID,intrequest)//传入作业名及申请量
//为申请作业开辟新空间且初始化
DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));
temp->
data.ID=ID;
data.size=request;
data.state=Busy;
DuLNode*p=block_first->
next;
while(p)
if(p->
data.state==Free&
&
p->
data.size==request)
{//有大小恰好合适的空闲块
p->
returnOK;
break;
}
data.size>
request)
{//有空闲块能满足需求且有剩余"
temp->
prior=p->
prior;
next=p;
data.address=p->
data.address;
prior->
next=temp;
prior=temp;
data.address=temp->
data.address+temp->
data.size;
data.size-=request;
p=p->
returnERROR;
//------------------循环首次适应算法-----------------------
StatusCycleFirst_fit(intID,intrequest)//传入作业名及申请量
request&
p->
data.address==adds)
adds=p->
cout<
adds<
if(request>
next->
data.size&
data.state==Free)
{
if(First_fit(ID,request)==OK)
returnOK;
//--------------------最佳适应算法------------------------
StatusBest_fit(intID,intrequest)
intch;
//记录最小剩余空间
DuLNode*q=NULL;
//记录最佳插入位置
while(p)//初始化最小空间和最佳位置
(p->
request||p->
data.size==request))
q=p;
ch=p->
data.size-request;
{//空闲块大小恰好合适
{//空闲块大于分配需求
if(p->
data.size-request<
ch)//剩余空间比初值还小
{
ch=p->
//更新剩余最小值
q=p;
//更新最佳位置指向
}
if(q==NULL)returnERROR;
//没有找到空闲块
else
{//找到了最佳位置并实现分配
temp->
prior=q->
next=q;
data.address=q->
q->
data.address+=request;
data.size=ch;
//-----------------------主存回收--------------------
Statusfree(intID)
DuLNode*p=block_first;
data.ID==ID)
data.ID=Free;
data.state==Free&
data.state==Free)//前后都有空闲块
p->
data.size+=p->
next=p->
adds=p->
cout<
回收成功\n"
break;
data.state==Free)//与前面的空闲块相连
data.state==Free)//与后面的空闲块相连
prior=p;
//---------------显示主存分配情况------------------
voidshow()
+++++++++++++++++++++++++++++++++++++++\n"
+++主存分配情况+++\n"
分区号:
data.ID==Free)cout<
Free"
data.ID<
起始地址:
data.address<
分区大小:
data.size<
KB"
状态:
data.state==Free)cout<
空闲"
已分配"
——————————————"
if(p==block_last)
//-----------------------主函数---------------------------
voidmain()
intOpNum;
intSqe[100][100];
FILE*fp;
fp=fopen("
input.txt"
"
r"
);
if(!
fp)
无法打开文件input.txt"
exit
(1);
fscanf(fp,"
%d"
&
OpNum);
for(intii=0;
ii<
OpNum;
ii++)
for(intjj=0;
jj<
3;
jj++)
fscanf(fp,"
Sqe[ii][jj]);
//算法选择标记
动态分区分配方式的模拟\n"
************************************\n"
**1.首次适应算法**\n"
**2.循环首次适应算法**\n"
**3.最佳适应算法**\n"
**0.退出程序**\n"
请选择分配算法:
ch;
if(ch==0)
exit(0);
Initblock();
//开创空间表
intchoice;
//操作选择标记
for(intnn=0;
nn<
nn++)
**1.下一操作**\n"
**2.查看分配**\n"
请输入您的操作:
cin>
choice;
if(choice==1)
ID=Sqe[nn][0];
request=Sqe[nn][2];
if(Sqe[nn][1]==0)
作业"
ID<
申请"
request<
KB内存"
alloc(ch);
//操作符为0,则开始分配内存
i