动态分区分配方式首次适应算法.docx

动态分区分配方式首次适应算法.docx

《动态分区分配方式首次适应算法.docx》由会员分享，可在线阅读，更多相关《动态分区分配方式首次适应算法.docx（22页珍藏版）》请在冰点文库上搜索。

动态分区分配方式首次适应算法

计算机科学专业课程设计任务书

学生姓名

专业班级

学号

题目

动态分区分配方式的模拟1

课题性质

其它

课题来源

自拟课题

指导教师

马宏琳

同组姓名

无

主要内容

1）用C语言实现采用首次适应算法的动态分区分配过程alloc（）和回收过程free（）。

其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。

2）假设初始状态如下，可用的内存空间为640KB，并有下列的请求序列；

作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200KB；作业3释放100KB；作业1释放130KB；作业5申请140KB；作业6申请60KB；作业7申请50KB；作业6释放60KB

请采用首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。

任务要求

了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。

参考文献

任满杰等《操作系统原理实用教程》电子工业出版社2006

汤子瀛《计算机操作系统》（修订版）西安电子科技大学出版社2001

张尧学史美林《计算机操作系统教程》实验指导清华大学出版社2000

罗宇等《操作系统课程设计》机械工业出版社2005

审查意见

指导教师签字：

教研室主任签字：

年月日

1需求分析

了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。

采用首次适应算法的动态分区分配过程alloc（）和回收过程free（）。

空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小分配给作业。

作业完成时，需要释放作业所占空间，此时要考虑到四种情况：

（1）回收区与插入点的前一个空闲分区相邻接。

此时将二者合并，修改前一分区的大小。

（2）回收区与插入点的后一空闲分区相邻接，将二者合并，用回收区的首址作为新空闲区的首址。

（3）回收区同时与插入点的前后两个空闲分区相邻接，三者合并，使用前一空闲分区的表项和首址。

（4）回收区单独存在。

由于该算法的实现相对简单，仅由我一人完成。

2概要设计

typedefstructfreearea{}ElemType;

定义一个空闲区说明表结构，每申请一个作业，改作业便具有此结构体

typedefstructDuLNode{}DuLNode,*DuLinkList;

定义一个双向链表

StatusInitblock（）{}

开创带头结点的内存空间链表,通过双向链表把申请的作业链接起来，作业的插入和删除，和链表中节点的插入和删除类似。

双向链表如图1所示

StatusFirst_fit（intID,intrequest）{}

传入作业名及申请量采用首次适应算法实现动态内存分区分配的模拟，初始态640KB，只是一个虚态，每申请成功一个作业，便相应的640KB做相应的减少，同过双向链表模拟主存的分配情况。

内存分配流程如图2所示

Statusfree（intID）

传过来需要回收的分区号实现分区的回收，对不同情况采取不同的处理

voidshow（）显示当前主存的分配情况

3运行环境

硬件环境：

Cpu:

P2.4GHDRR:

0.98GBWINDOWSXP。

软件环境：

在VC++6.0下编译、调试。

4开发工具和编程语言

开发工具:

Microsortvisualc++6.0中文版

编程语言:

c++

5详细设计

1）空闲区数据结构

typedefstructfreearea//定义一个空闲区说明表结构

{

intID;

longsize;

longaddress;

intstate;

}ElemType;

2）双向链表数据结构

typedefstructDuLNode//双向链表结构体

{

ElemTypedata;

structDuLNode*prior;//前趋指针

structDuLNode*next;//后继指针

}DuLNode,*DuLinkList;

3）创建内存空间链表

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;

}

4）分配主存

Statusalloc（）

{

intID,request;

cout<<"请输入作业（分区号）：

";

cin>>ID;

cout<<"请输入需要分配的主存大小（单位:

KB）：

";

cin>>request;

if（request<0||request==0）

{

cout<<"分配大小不合适，请重试！

"<

returnERROR;

}

if（First_fit（ID,request）==OK）调用函数First_fit（ID,request）才是真正实现首次适应算法

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;

}

5）主存回收

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;

}

6）显示主存分配情况

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;

}

}

7）主函数

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;

}

}

}

6调试分析

调试问题结果如图3所示

调试问题结果如图4所示

本实验要实现的功能是用首次适应算法来实现动态分区分配，通过不断调试，程序中出现了多处不足之处，首先是程序的运行结果不够清晰，不便于用户进行观察，不过这个比较容易优化，其次就是在内存回收功能上不够完善，开始的时候每次回收最后一个作业时都会出现问题，如图3所示，回收别的作业都很成功，原因就在与在回收情况的判断上少了一种情况后来，后来增加了if（p->next->next==NULL）p->next=null;else{}满足了要求，得到了正确

结果，还有就是程序允许回收内存中不存在的作业，如图4所示这是不符合要求的，因为才程序中少了对用户输入作业号的判断不符合情况的处理。

7测试结果

作业1申请30KB

作业5申请70KB

作业2申请600KB

作业2申请-80KB

作业2申请30KB

作业2回收30KB

作业3申请78KB

测试分区分配如图5所示

测试分区分配如图6所示

测试分区分配如图7所示

测试分区回收如图8所示

测试主存当前分配情况如图9所示

程序运行结果如图10所示

参考文献

[1]任满杰等《操作系统原理实用教程》电子工业出版社2006

[2]汤子瀛《计算机操作系统》（修订版）西安电子科技大学出版社2001

[3]张尧学史美林《计算机操作系统教程》实验指导清华大学出版社2000

[4]罗宇等《操作系统课程设计》机械工业出版社2005

[5]曾平，曾林《操作系统》清华大学出版社2006

心得体会

由于已经学过动态分区分配，我也了解了什么是首次适应算法，以及首次适应算法的实现过程，刚开始以为会很顺利的做完此次课程设计，但往往会出现眼高手低的情况，先是因为很久都没用过C++来编写代码了，以致刚开始时，出现了很多小问题，真是把头都搞大了，如具体的格式，以及链表的具体使用等等出现问题，还得拿出原来的课本学习查看，费了点时间，不过让我再次回味了曾经的C++编程，加深了原来的记忆。

经过网上搜材料以及整体平时的学习材料，后来程序的大体框架算是出来了，不过在不断调试过程中我发现了很多不完善的地方，比如在回收内存方面，少了一种情况的处理，以致每次要回收最后一个作业时都会出现错误的框子；还有就是若要删除内存中不存在的作业，程序却允许执行，这个问题难为了我好久，改完后又接着出现新的问题，成了内存中存在的作业在删除时也提示用户重新输入，原因在于判断条件加的地方不合适。

通过本次课程设计我学到了很多东西，也增加了我不断摸索和学习的兴趣，由原来的书本知识演化成了真的动手实践，获益匪浅。

实验代码

//********动态分区分配方式的模拟一首次适应算法*********

#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（