实验四动态分区分配方式模拟答案外语学习

1/1实验四动态分区分配方式模拟答案-外语学习

试验四动态分区安排方式的模拟答案

动态分区安排方式的模拟

第一部分设计思想的说明

1设计目标

用C语言或C++语言分别实现采纳首次适应算法和最佳适应算法的动态分区安排过程alloc和回收过程free。其中，空闲分区通过空闲分区链表来管理，在进行内存安排时，系统优先使用空闲区低端空间。

预期结果：假设初始状态如下，可用的内存空间为640KB，并有下列恳求序列：

作业1申请130KB

作业2申请60KB

作业3申请100KB

作业2释放60KB

作业4申请200KB

作业3释放100KB

作业1释放130KB

作业5申请140KB

作业6申请60KB

作业7申请50KB

作业6释放60KB

分别用首次适应算法和最佳适应算法进行内存块的安排和回收，同时显示内存块安排和回收后空闲内存分区链的状况。

2、设计理论

首次适应算法（First-fit）：当要安排内存空间时，就查表，在各空闲区中查找满意大小要求的可用块。只要找到第一个足以满意要球的空闲块就停止查找，并把它安排出去；假如该空闲空间与所需空间大小一样，则从空闲表中取消该项；假如还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。

最佳适应算法（Best-fit）：当要安排内存空间时，就查找空闲表中满意要求的空闲块，并使得剩余块是最小的。然后把它安排出去，若大小恰好合适，则直按安排；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。

内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并推断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。

试验四动态分区安排方式的模拟答案

其次部分程序清单

//***************************************************************//********动态分区安排方式的模拟*********//***************************************************************

#includeiostream.h

#includestdlib.h

#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(int);//内存安排

Statusfree(int);//内存回收

StatusFirst_fit(int,int);//首次适应算法

StatusBest_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(intch)

{

intID,request;

cout请输入作业(分区号)：;

cinID;

cout请输入需要安排的主存大小(单位:KB)：;

cinrequest;

if(request0||request==0)

{

}

if(ch==2)//选择最佳适应算法

{

}

else//默认首次适应算法

{

}

}

//首次适应算法StatusFirst_fit(intID,intrequest)//传入作业名及申请量if(First_fit(ID,request)==OK)cout安排胜利！endl;elsecout内存不足，安排失败！endl;returnOK;if(Best_fit(ID,request)==OK)cout安排胜利！endl;elsecout内存不足，安排失败！endl;returnOK;cout安排大小不合适，请重试！endl;returnERROR;

试验四动态分区安排方式的模拟答案

//为申请作业开拓新空间且初始化

DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));temp-data.ID=ID;

temp-data.size=request;

temp-data.state=Busy;

DuLNode*p=block_first-next;

while(p)

{

}

returnERROR;

}

//最佳适应算法StatusBest_fit(intID,intrequest)

{

intch;//记录最小剩余空间

DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));temp-data.ID=ID;

temp-data.size=request;

temp-data.state=Busy;

DuLNode*p=block_first-next;

DuLNode*q=NULL;//记录最佳插入位置

while(p)//初始化最小空间和最佳位置if(p-data.state==Freep-data.size==request){//有大小恰好合适的空闲块}if(p-data.state==Freep-data.sizerequest){//有空闲块能满意需求且有剩余}p=p-next;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-data.state=Busy;p-data.ID=ID;returnOK;break;

试验四动态分区安排方式的模拟答案

}

while(p)

{

}

if(q==NULL)returnERROR;//没有找到空闲块

else

{//找到了最佳位置并实现安排

}

}

//主存回收temp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;returnOK;if(p-data.state==Freep-data.size==request){//空闲块大小恰好合适}if(p-data.state==Freep-data.sizerequest){//空闲块大于安排需求}p=p-next;if(p-data.size-requestch)//剩余空间比初值还小{}ch=p-data.size-request;//更新剩余最小值q=p;//更新最佳位置指向p-data.ID=ID;p-data.state=Busy;returnOK;break;if(p-data.state==Free{}p=p-next;q=p;ch=p-data.size-request;break;(p-data.sizerequest||p-data.size==request))

试验四动态分区安排方式的模拟答案

Statusfree(intID)

{

DuLNode*p=block_first;

while(p)

{

}

returnOK;

}

//显示主存安排状况voidshow

{

cout+++++++++++++++++++++++++++++++++++++++\n;

cout+++主存分配情况+++\n;

cout+++++++++++++++++++++++++++++++++++++++\n;

DuLNode*p=block_first-next;

while(p)

{

cout分区号：;if(p-data.ID==Free)coutFreeendl;elsecoutp-data.IDendl;cout起始地址：p-data.addressendl;cout分区大小：p-data.sizeKBendl;cout状态：;if(p-data.state==Free)cout空闲endl;if(p-data.ID==ID){}p=p-next;p-data.state=Free;p-data.ID=Free;if(p-prior-data.state==Free)//与前面的空闲块相连{}if(p-next-data.state==Free)//与后面的空闲块相连{}break;p-data.size+=p-next-data.size;p-next-next-prior=p;p-next=p-next-next;p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;

试验四动态分区安排方式的模拟答案

}

}

elsecout已安排endl;cout——————————————endl;p=p-next;

//主函数voidmain

{

intch;//算法选择标记

cout动态分区安排方式的模拟\n;

cout***********************************