操作系统课程设计报告最佳适应算法模拟实现内存分配与回收.docx

操作系统课程设计报告最佳适应算法模拟实现内存分配与回收.docx

《操作系统课程设计报告最佳适应算法模拟实现内存分配与回收.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计报告最佳适应算法模拟实现内存分配与回收.docx（24页珍藏版）》请在冰点文库上搜索。

操作系统课程设计报告最佳适应算法模拟实现内存分配与回收

实验题目：

最佳适应算法模拟实现内存分配与回收

目录 

一、概述……………………………………………………………………………………………3

1．设计目的………………………………………………………………………………………3

2．开发环境………………………………………………………………………………………3

3．任务分配………………………………………………………………………………………3

二、需求分析…………………………………………………………………………………3

三、实验基本原理…………………………………………………………………………4

1．可变分区存储管理之最优适应分配算法的概念……………………………………………4

2．关于最优适应分配算法的一些基本原理……………………………………………………4

四、数据结构设计……………………………………………………………………………4

1．内存块与作业块………………………………………………………………………………4

2．程序流程图……………………………………………………………………………………5

2.1．整体程序流程图…………………………………………………………………………5

2.2．内存分配allocate（）流程图………………………………………………………………6

2.3．内存回收callback（）流程图………………………………………………………………7

五、算法的实现………………………………………………………………………………7

1．程序主要功能函数设计思想……………………………………………………………7

2．源程序清单……………………………………………………………………………8

3．测试用例与程序运行结果截图………………………………………………………18

六、总结……………………………………………………………………………………………21

1．经验总结……………………………………………………………………………………21

2．心得与体会…………………………………………………………………………………21

七、参考文献……………………………………………………………………………………22

一、概述

1、设计目的

（1）了解多道程序系统中，多个进程并发执行的内存资源分配。

（2）模拟可变分区存储管理算法实现分区管理的最佳适应分配算法

（3）利用最佳适应算法动态实现内存分配与回收

（3）通过实现最佳算法来进一步了解动态分区模式的优缺点。

（4）掌握最佳适应分配算法，深刻了解各进程在内存中的具体分配策略。

2、开发环境

PC机

DOS;WINDOWS环境

VisualC++6.0forWindows

3、任务分配

设计人员

设计任务

王果

程序总体设计，部分内存回收的实现，上机编码和调试，程序后期优化

刘芳麟

部分内存分配的实现，编写文档，设计测试用例

何超英

部分内存分配的实现，编写文档，数据结构设计

高超

部分内存回收的实现，资料收集，需求分析

二、需求分析

克服固定分区中的主存资源的浪费，有利于多道程序设计，提高主存资源的利用率。

三、实验基本原理

１、可变分区存储管理之最优适应算法分配的概念：

分区存储管理是给内存中的进程划分适当大小的存储区，以连续存储各进程的程序和数据，使各进程能并发地执行。

最优适应分配算法扫描整个未分配区表或链表，从空闲区中挑选一个能满足用户进程要求的最小分区进行分配。

2、关于最优适应的一些基本原理：

在可变分区模式下，在系统初启且用户作业尚未装入主存储器之前，整个用户区是一个大空闲分区，随着作业的装入和撤离，主存空间被分成许多分区，有的分区被占用，而有的分区时空闲的。

为了方便主存空间的分配和去配，用于管理的数据结构可由两张表组成：

“已分配区表”和“未分配区表”。

在“未分配表中”将空闲区按长度递增顺序排列，当装入新作业时，从未分配区表中挑选一个能满足用户进程要求的最小分区进行分配。

这时从已分配表中找出一个空栏目登记新作业的起始地址和占用长度，同时修改未分配区表中空闲区的长度和起始地址。

当作业撤离时已分配区表中的相应状态变为“空”，而将收回的分区登记到未分配区表中，若有相邻空闲区再将其连接后登记。

可变分区的回收算法较为复杂，当一个作业撤离时，可分为4种情况：

其临近都有作业（A和B）,其一边有作业（A或B），其两边均为空闲区。

尤其重要的是，在程序中利用“new类型T（初值列表）”申请分配用于存放T类型数据的内存空间，利用“delete指针名”释放指针所指向的内存空间。

四、数据结构设计

1、

（1）内存块

structspace//定义内存空间结构体

{

longstartaddress;

longlength;

structspace*next;

};

space*pbc;

（2）作业块

structwork//定义进程结构体

{

charname[20];

longstartaddress;

longlength;

structwork*next;

};

work*S;

2、程序流程图

2.1、整体程序流程图

2.2、内存分配allocate（）流程图

2.3、内存回收callback（）流程图

五、算法的实现

1、程序主要功能函数设计思想

allocate（）：

实现内存分配，并在当中调用display（pbc），以及display（S）两个函数显示内存分配完后的空闲块链表和进程链表情况。

requireback（）：

实现内存回收，在满足情况的条件下调用allocate（）对用户申请的内存块进行回收并在当中调用display（pbc），以及display（S）显示内存回收完后的空闲块链表和进程链表情况。

callback（）：

按内存回收时的四种情况对内存进行回收。

display（pbc）：

对空闲块链表中的空闲块进行从小到大排序并显示空闲链情况。

display（S）：

对进程链表中的进程进行从小到大排序并显示进程链情况。

main（）：

创建并初始化空闲块链表和进程链链表，用户选择操作功能

2、程序清单

#include

#include

#include

structspace//定义内存空间结构体

{

longstartaddress;

longlength;

structspace*next;

};

space*pbc;//申明结构体指针

structwork//定义进程结构体

{

charname[20];

longstartaddress;

longlength;

structwork*next;

};

work*S;//申明结构体指针

voidcallback（work*r）;//申明callback（）函数原型

voiddisplay（space*pbc）;//申明display（）函数原型

voiddisplay（work*S）;

voidallocate（）//内存分配函数实现

{

work*q,*w;

q=newwork;//申请分配用于存放work类型的数据的内存空间

cout<<"请输入进程名和占用空间大小:

"<

cin>>q->name>>q->length;

if（q->length<=0）//判断输入进程的合法性

{

cout<<"进程错误."<

deleteq;//进程错误，释放内存空间

return;

}

w=S;

while（w->next!

=NULL）//进程链不为空

{

if（strcmp（w->next->name,q->name）==0）//判断进程名是否已经存在

{

cout<<"此进程名已经存在!

"<

return;

}

w=w->next;

}

if（w->next==NULL）//进程名不存在，继续进行内存分配

{space*p,*r;

p=pbc;

r=p;

while（p->next!

=NULL&&p->next->lengthlength）//在空间链中寻找第一个大于所输入的进程大小的空闲块

{

r=p;

p=p->next;

}

if（p->next==NULL）//空闲链中无大于所输入进程空间大小的空闲块

{

cout<<"空间不足，分配失败！

"<

deleteq;//空间不足，分配失败，释放空间

return;

}

else//找到第一个满足要求的空闲块

{

q->startaddress=p->next->startaddress;//将该空闲块的起始地址赋给所输入的进程

q->next=S->next;

S->next=q;//将所输入的进程插入work链首。

p->next->length-=q->length;

if（p->next->length!

=0）//该空闲块空间有剩余，改变该空闲块的起始地址

p->next->startaddress+=q->length;

else//该空闲块空间无剩余

{

if（p->next->next!

=NULL）//该空闲块不处于空闲链链尾

p->next=p->next->next;//删除该空闲块，修改空闲链

else

{

r->next=NULL;//该空闲块处于空闲链链尾，修改空闲链

deletep->next;//释放该空闲块的空间

}

}

}

}

display（pbc）;//显示空闲链情况

display（S）;//显示进程链情况

}

voidrequireback（）{//用户申请进程回收函数

charname[20];

cout<<"输入要回收的进程名：

";

cin>>name;

work*p;

p=S;

while（p->next!

=NULL）//进程链不为空

{

if（strcmp（p->next->name,name）==0）//寻找与用户要求回收的进程名相同的进程

{

callback（p）;//调用进程回收函数，回收进程

return;

}

p=p->next;

}

if（p->next==NULL）

cout<<"此进程不存在!

"<

}

voidcallback（work*t）//利用最佳适应算法实现进程回收

{

work*w;

w=t->next;

space*p=NULL,*q=NULL;

longn;

n=w->length;

if（pbc->next==NULL）//空闲链为空

{

space*f=newspace;//申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针f

f->startaddress=0;//初始该空间首地址

f->length=n;//将所要回收的进程大小赋给该空间

f->next=NULL;

pbc->next=f;//将该空间块插入空闲链中

t->next=w->next;

deletew;//释放空间

cout<<"回收完毕!

"<

display（pbc）;//显示回收完后的空闲链

display（S）;//显示回收完后的进程链

return;

}

p=pbc->next;

while（p!

=NULL&&p->startaddressstartaddress）//在空闲链表中寻找插入新的空闲区的合适位置

{

q=p;

p=p->next;

}

if（（q==NULL）&&（w->startaddress+n==p->startaddress））

{

p->startaddress-=n;//修改下邻起始地址

p->length+=n;//将该空闲块与下邻合并

t->next=w->next;//修改进程链，删除进程链中所要回收的进程

deletew;//释放空间

cout<<"回收完毕!

"<

display（pbc）;//显示回收后的空闲链

display（S）;//显示回收后的进程链

return;

}

if（（q==NULL）&&（w->startaddress+n!

=p->startaddress））//q为空，且该空间的结束地址不是下临的结束地址

{

space*sp=newspace;//申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针sp

sp->startaddress=w->startaddress;//将该空间的起始地址赋给sp

sp->length=n;//将该空间的大小赋给sp

sp->next=pbc->next;//将sp插入空闲链中

pbc->next=sp;

t->next=w->next;//修改进程链，删除所回收的进程

deletew;

cout<<"回收完毕!

"<

display（pbc）;//显示回收后的空闲链

display（S）;//显示回收后的进程链

return;

}

if（（q!

=NULL）&&（q->startaddress+q->length==w->startaddress）&&（w->startaddress+n==p->startaddress））//上下均空

{

q->next=p->next;//修改空闲链

q->length=q->length+p->length+n;//将该空闲块与上下邻合并

t->next=w->next;//修改进程链，删除所回收的进程

deletew;//释放空间

}

elseif（（q!

=NULL）&&（w->startaddress+n==p->startaddress））//下邻空

{

p->startaddress-=n;//修改下邻起始地址

p->length+=n;//将该空闲快与下邻合并

t->next=w->next;

deletew;

}

elseif（（q!

=NULL）&&（q->startaddress+q->length==w->startaddress））//上邻为空

{

q->length+=n;//改变上邻的大小，将两个空闲块合并

t->next=w->next;//修改进程链，删除所回收的进程

deletew;//释放空间

}

else//上下邻都不为空

{

space*sp=newspace;//申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针sp

sp->startaddress=w->startaddress;//将所回收的进程首地址赋给sp

sp->length=n;//将缩回收的进程大小赋给sp

sp->next=pbc->next;

pbc->next=sp;//将sp插入空闲链链首

t->next=w->next;//修改进程链，删除所回收的进程

deletew;//释放空间

}

cout<<"回收完毕!

"<

display（pbc）;//显示回收后的空闲块

display（S）;//显示回收后的进程链

space*sa,*sd,*sf,*sk;

sa=pbc->next;//空闲块从小到大排序

pbc->next=NULL;

while（sa!

=NULL）

{sd=pbc;sf=pbc->next;

while（（sf!

=NULL）&&（sf->lengthlength））

{sd=sf;sf=sf->next;}

sk=sa->next;

if（sf==NULL）

{sd->next=sa;sa->next=NULL;}

else{sa->next=sf;sd->next=sa;}

sa=sk;}

}

voiddisplay（space*pbc）//空闲链显示函数实现

{

space*p,*q,*r,*e;

p=pbc->next;//空闲块从小到大排序

pbc->next=NULL;

while（p!

=NULL）

{r=pbc;q=pbc->next;

while（（q!

=NULL）&&（q->startaddressstartaddress））

{r=q;q=q->next;}

e=p->next;

if（q==NULL）

{r->next=p;p->next=NULL;}

else{p->next=q;r->next=p;}

p=e;}

space*t=pbc->next;

cout<

"<

if（t==NULL）

{cout<<"无空闲区了."<

while（t!

=NULL）

{

cout<<"起始地址:

"<startaddress<<"长度:

"<length<

t=t->next;

}

}

voiddisplay（work*S）//进程链显示函数实现

{

work*p,*q,*r,*f;

p=S->next;//进程链表排序

S->next=NULL;

while（p!

=NULL）

{r=S;q=S->next;

while（（q!

=NULL）&&（q->startaddressstartaddress））//按从小到大

{r=q;q=q->next;}

f=p->next;

if（q==NULL）

{r->next=p;p->next=NULL;}

else{p->next=q;r->next=p;}

p=f;}

work*t=S->next;

cout<

"<

if（t==NULL）

{cout<<"内存中无进程."<

while（t!

=NULL）

{

cout<<"进程名:

"<name<<"起始地址:

"<startaddress<<"长度:

"<length<

t=t->next;

}

cout<

}

voidmain（）

{

pbc=newspace;//申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针pbc

space*p=newspace;//申请分配用于存放space类型的数据的内存空间,并将首地址赋给指针p

p->startaddress=0;//初始化p的起始地址

p->length=130;//初始花p的大小

p->next=NULL;

pbc->next=p;//将pbc作为p的头指针，创建空闲链

S=newwork;//创建进程链头指针

S->next=NULL;

intb;

cout<<""<<""<<""<<""<<""<<""<<""<<""<<""<<""

<<""<<""<<""<<""<<""<<"·"<<"最佳适应算法模拟内存分配与回收"<<"·"<

cout<

cout<<"·····························"<

cout<<"功能选项:

"<<""<<""<<""<<""<<""<<""<<"0:

分配内存"<<""<<""

<<""<<""<<""<<"1:

回收内存"<<""<<""<<""<<""<<""<<"2:

退出"<

cout<<"·····························"<

while

（1）{//循环选择功能

cout<

";

cin>>b;

switch（b）

{

case0:

allocate（）;break;//功能0：

进行内存分配

case1:

requireback（）;break;//功能1:

进行内存回收

case2:

;break;//功能2:

退出

}

}

}

2、测试用例与程序运行结果截图

2.1、内存分配错误测试用例

用例：

（w,-20）

图1程序运行结果：

输入进程占用空间大小小于零

用例：

（w,20）（w,20）

图2程序运行结果：

所输入的进程名已经存在

用例：

（s,200）

图3程序运行结果：

所申请的空间过大，空间不足

2.2、内存分配正确测试用例

用例：

（w,20）

图4程序运行结果：

分配成功

2.3、内存回收错误测试用例

用例：

（d）

图5程序运行结果：

所要回收的进程不存在

2.4、内存回收正确测试用例

用例：

回收d

图6程序运行结果：

上下邻均不为空

用例：

回收m

图7程序运行结果：

下邻为空

用例：

回收w

图8程序运行结果：

上邻为空

用例：

回收f

图9程序运行结果：

上下邻均为空

六、总结

1、经验总结：

设计程序时，最好将不同的功能用不同的函数实现。

在本程序中，就将排序

功能单独放在了显示函数中，这样在用最佳适应算法实现内存分配与回收时，就只要调用该函数即可，而不必再考虑链表的排序。

2、心得与体会：

通过小组成员的共同努力，实现了可变分区存储管理的最优适应分配算法，能够较好的掌握内存的分配与回收。

通过资料查询，巩固了《数据结构》、《软件工程》、《C++程序设计》以及《操作系统》的部分专业知识，增强了我们的实际操作能力。

测试用例的运行，让我们更好的了解了最优适应算法的优缺点。

七、参考文献

1、孙钟秀《操作系统教程》

2、清华大学出版社出版的《数据结构》（c语言版）

3.、清华大学出版社出版的《c++语言程序设计》（第3版）

4、郑人杰《软件工程》（第6版）