存储管理——动态分区分配回收算法的模拟.doc

齐齐哈尔大学
操作系统课程综合实践
题目：存储管理——动态分区分配/
回收算法的模拟
班级： 0
姓名： 0
学号：0
指导教师：0
2011年 12 月
综合实践评分表
班级
0
姓名
0
指导教师
0
题目： 存储管理———动态分区分配/回收算法的模拟
评分标准
评分标准
分数权重
评分的依据
得分
A
C
选题
10
选题符合大纲要求,题目较新颖，工作量大
选题基本符合大纲要求，工作量适中

工作态度
10
态度端正,能主动认真完成各个环节的工作,不迟到早退，出勤好。
能够完成各环节基本工作,出勤较好。

存储结构、算法描述
20
能正确选择存储结构，定义准确，算法流程图或类C语言描述的算法准确无误
能正确选择存储结构,算法流程图或类C语言描述的算法基本准确

独立解决问题的能力
10
具有独立分析、解决问题能力,有一定的创造性,能够独立完成软件的设计与调试工作,程序结构清晰，逻辑严谨,功能完善.
有一定的分析、解决问题能力。能够在老师指导下完成软件的设计与调试工作，程序功能较完善。

答辨问题回答
20
能准确回答老师提出的问题
能基本准确回答老师提出的问题

程序运行情况
10
程序运行正确、界面清晰，测试数据设计合理.
程序运行正确、界面较清晰，能给出合适的测试数据。

综合实践报告
20
格式规范，层次清晰，设计思想明确,解决问题方法合理，体会深刻.
格式较规范,设计思想基本明确，解决问题方法较合理.

总分

指导教师(签字）：
注：介于A和C之间为B级,低于C为D级和E级。按各项指标打分后，总分在90~100为优，80～89为良，70～79为中，60～69为及格，60分以下为不及格。
存储管理—--动态分区分配/回收算法的模拟
摘要：主存的分配和回收的实现是与住存储器的管理方式有关的。解决多进程如何共享主存空间的问题.当进程运行完时将进程所占的主存空间归还给系统。可变分区存储管理方式，分区分配中所用的数据就够采用空闲分区说明表和空闲分区链表来进行。
关键字:内存分配,空闲分区表,进程申请队列
一、【实践目的】:
1、熟悉主存分配与回收
2、理解在不同的存储管理方式，如何实现主存空间的分配与回收
3、掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方
式及其实现过程。
二、【实践内容和要求】：
主存的分配和回收的实现是与住存储器的管理方式有关的。所谓分配，就是解决多进程如何共享主存空间的问题。所谓回收,就是当进程运行完时将进程所占的主存空间归还给系统。
实验要求使用可变分区存储管理方式,分区分配中所用的数据就够采用空闲分区说明表和空闲分区链表来进行，分区分配中所用的算法采用首次适应算法、循环首次适应算法、最佳适应算法、三种算法来实现主存的分配与回收。
同时要求设计一个实用友好的可视化用户界面，并显示分配与回收过程。
仿真实现动态可变分区存储管理模拟系统。内存调度策略可采用首次适应算法、循环首次适应算法和最佳适应法等,并对各种算法进行性能比较。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况,为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。
三、【实践原理】
操作系统是最重要的计算机系统软件，同时也是最活跃的学科之一。计算机系统由硬件和软件两部分组成。操作系统是配置在计算机硬件上的第一层软件,是对硬件的首次扩充。本次课程设计的主要目的是在学习操作系统理论知识的基础上，对操作系统整体的一个模拟.也是对本学期所学知识的一个总体的检测，使理论知识应用到实际的编程中,根据理论的算法来实现具体的编程操作。同时通过本次课程设计加深对操作系统理论知识各个部分管理功能的感性认识,进一步分析和理解各个部分之间的联系和功能,最后达到对完整系统的理解。同时,可以提高运用操作系统知识和解决实际问题的能力；并且锻炼自己的编程能力、创新能力以及开发软件的能力;还能提高自己的调查研究、查阅文献、资料以及编写软件设计文档的能力并提高分析问题的能力。
实验中为有效地对内存进行管理，实验中应设计一些数据结构，能有效地进行分配和回收,具体分析如下：
1． 设计一个空闲分区表，空闲分区表通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲分区低端的空间。
2． 设计一个内存分区表，可用链表管理，用以表示当前以内存使用情况.
3． 设计一个进程申请队列以及进程完成后的释放顺序，实现主存的分配和回收。
4． 要求每次分配和回收后把空闲分区的变化情况以及各进程的申请、释放情况以及各进程的申请、释放情况以图形方式显示、打印出来。
循环首次适应算法的alloc（)函数与首次适应算法的alloc（）函数区别在于从哪里开始找是否有满足作业要求的空闲区，它是从上次找到的空闲区的下一个空闲分区开始找,只需要改变for循环的条件即可。
for（i=s；i<N;i++)
最佳适应算法：该算法总是把满足要求、又是最小的空闲区分配给作业。检查空闲区说明表是否有满足作业要求的空闲区,也分为三种情况:大于，等于，小于。若检查到有“等于”的情况，就可以直接分配，若没有，则继续检查是否有“大于"的情况：
if（freeblock[i]。state==1＆＆freeblock［i］.size==applyarea）
{
freeblock［i］。state=0;
tag=1；
return freeblock［i]。startaddress;
}
检查“大于"的情况：先把所有大于所要求的空闲区放入数组,
for(i=0；i〈N；i++)
{
if(freeblock[i］.state==1＆＆freeblock[i］.size〉applyarea）a［j++］=i;
｝
再从数组中挑出最小的那个：
果数组中的元素大于一个，则需要一个个比较过去，然后取出最小的那个分配给作业：
if（j〉1）
｛
h=a［0］；
min=freeblock［h]；
for(k=1;k〈j；k++）
｛
h=a［k］;
if（freeblock［h］.size〈min。size)
{
mid.size=freeblock［h］。size；
mid。state=freeblock［h］。state；
mid.startaddress=freeblock［h］。startaddress；
freeblock［h]。size=min。size；
freeblock[h］。state=min.state；
freeblock［h］.startaddress=min。startaddress；
min.size=mid。size；
min。state=mid。state；
min。startaddress=mid.startaddress；
｝
｝
min。startaddress=min。startaddress+applyarea;
min。size=min。size-applyarea;
tag=1;
return min。startaddress—applyarea；
}
如果数组中只有一个元素,则直接分配给作业：
if（j==1)
{
h=a［0］；
min=freeblock[h］；
min.startaddress=min。startaddress+applyarea；
min.size=min。size-applyarea；
tag=1；
return min.startaddress—applyarea;
｝
如果没有满足条件的空闲区,分配不成功，返回-1
if(tag==0）return —1;
四、【实践环境】（使用的软件)
Microsoft Visual C++ 6。0
五、【实践设计分析】：
内存分配:
①动态输入构造空闲区表，并显打印示构造好的空闲分区表。
②键盘接收内存申请.
③根据申请，实施内存分配，并返回分配所得内存首址。
④分配完后，调整空闲分区表（即扣除分配部分），并显示调整后的空闲分区表。
⑤若分配失败，返回分配失败信息。
内存回收：
①显示当前的空闲分区表和内存分区表。
②从键盘接收回收分区的首址与大小，按内存回收的四种情况进行内存回收。
③显示回收后已调整好的的空闲分区表
六、【实践过程和步骤】:
●数据结构设计
①　 空闲分区表的设计，该空闲分区表记录内存中未使用的各个分区，记录内容有未使用分区的大小、首地址,用链表就行管理；相关代码如下：
Typedef struct free
｛
Int size; //分区大小
Int address；//首地址
free ＊next；
｝；
②内存分区表设计，用以表示当前内存的使用情况，记录内容已使用分区的大小、首地址，用链表进行管理,相关数据结构如下:
Typedef struct map
｛
Int size； //分区大小
Int address；//首地址
map ＊next；
}；
③进程申请队列的设计,用作进程到达的缓冲队列，记录各进程的相关信息,如进程的所需内存的大小、进程名,相关数据结构如下:
Typedef struct pro
{
Int size； //分区大小
sring name;
pro ＊next;
｝；
l 内存分配
当有进程进行内存申请时,我们利用首次适应算法从空闲分区链表、找出一块做够大的空间进行分配并对空闲分区和内存分区的相关结点进行处理,若未找到则返回错误信息，相关示意图如下：
图一：内存分配示意图
l 内存回收
内存的回收存在以下几种情况：
①上邻空闲区：合并两分区,删除正回收的节点，改变上邻分区大小为两分区之和
②下邻空闲区：合并两分区，删除下邻分区节点,改变正回收节点大小为两分区之和，改变正回收节点的首址。
③上、下邻空闲区:合并三分区,删除下邻分区和正在回收节点，改变上分区节点大小为三分区之和，改变上分区收节点的首址
④不邻接,则建立一新表项.
相关的示意图如下:

空闲区
回收区

空闲区
回收区
空闲区

回收区
空闲区

①②③
图二：内存回收示意图
l 相关代码
1。采用最优分配算法分配作业空间，主要代码如下:
void allocate(char J,float xk）//采用最优分配算法分配xk大小的空间
｛
int i，k，l；
float ad；
k=-1;
for（i=0；i<m；i++) //寻找空间大于xk的最小空闲区登记项k
if（free_table［i]。length>=xk &＆ free_table[i].flag==1）
if(k==-1 ｜｜ free_table[i］。length<free_table［k］。length)
k=i；
if(k==—1) //未找到可用空闲区，返回
｛
AfxMessageBox(“有效空间不足！”)；
return；
}
//找到可用空闲区,开始分配：若空闲区大小与要求分配的空间差小于minisize大小,则空闲区全部分配;若空闲区大小与要求分配的空间差大于minisize大小，则从空闲区划出一部分分配
if（free_table［k].length—xk<=minisize)
｛
free_table［k］。flag=0;
ad=free_table［k]。address;
xk=free_table［k].length;
｝
else
｛
free_table[k］。length=free_table［k］.length—xk；
ad=free_table［k]。address+free_table［k].length;
｝
//修改已分配区表
l=0；
for(i=0;i<n；i++）
｛
while（used_table［i］.flag==’0'＆＆i〈n) //寻找空表目
｛
if(i〉=n） //无表目填写已分分区
{
AfxMessageBox("无表目填写已分分区错误！”）；//修正空闲区表
if（free_table［k］.flag==0) //前面找到的是整个空闲区
free_table[k］.flag=1；
else //前面找到的是某个空闲区的一部分
｛
free_table[k]。length=free_table［k］.length+xk；
return;
｝
}
else //修改已分配区表
{
used_table［i].address=ad；
used_table［i].length=xk;
used_table［i]。flag=J；
}
l=1;
}
if(l==1） break；
}
return;
｝//主存分配函数结束
2.作业的回收
bool reclaim(char J)//回收作业名为J的作业所占主存空间
｛
int i,k,j, s，t；
float S，L；
//寻找已分配区表中对应登记项
s=0;
while(（used_table[s］。flag！=J ｜| used_table［s］.flag=='0’)＆＆s<=n）
｛
if(s〉=n) //在已分配区表中找不到名字为J的作业
{
AfxMessageBox（"找不到该作业”）；
return (false）；
｝
s++；
}
//修改已分配区表
if(used_table[s].flag==J）
｛ used_table［s］。flag='0’;
//取得归还分区的起始地址S和长度L
S=used_table［s］。address;
L=used_table［s］.length；
j=—1；k=—1；i=0；
//寻找回收分区的上下邻空闲区,上邻表目k，下邻表目J
while（i〈m＆&（j==—1|｜k==—1）)
{
if（free_table[i］。flag==1）
{ if（free_table［i］。address+free_table[i］.length==S）k=i；//找 到上邻
if(free_table［i].address==S+L）
j=i； //找到下邻
｝
i++；
｝
if(k!=-1)
if（j!=—1） //上邻空闲区,下邻空闲区，三项合并
{free_table［k］。length=free_table[j]。length+free_table［k］。length+L; free_table[j］。flag=0;
}
else //上邻空闲区，下邻非空闲区,与上邻合并
free_table［k]。length=free_table［k]。length+L;
else
if（j！=—1） //上邻非空闲区，下邻为空闲区，与下邻合并
｛ free_table[j］。address=S；
free_table[j］。length=free_table［j］.length+L;
｝
else //上下邻均为非空闲区，回收区域直接填入
｛ //在空闲区表中寻找空栏目
t=0;
while（free_table［t]。flag==1 ＆& t〈=m）
｛
if(t>=m) //空闲区表满，回收空间失败，将已分配区表复原
｛
AfxMessageBox(”主存空闲表没有空间,回收空间失！");
used_table［s］.flag=J；
return （false)；
}
t++；
｝
free_table[t]。address=S;
free_table［t］.length=L;
free_table［t].flag=1；
｝
}
return（true)；
｝//主存归还函数结束
/＊动态分区的分配与回收演示程序*/
＃include 〈iostream.h〉
＃include 〈stdio。h>
#define N 5
int start；//存放首址
struct freearea/＊定义一个空闲区说明表结构，并初始化变量＊/
｛
int ID;/*分区号＊/
int startaddress；/＊空闲区始址*/
int size;/＊空闲区大小*/
int state；/＊空闲区状态:0为空表目，1为可用空闲块*/
｝freeblock[N]={{1，20，20，1},｛2,80，50，1}，｛3,150,30,1}，{4，300,30,1｝,｛5，500，10，1}｝；
/*定义为作业分配主存空间的函数alloc（）,给首次适应算法调用*/
int alloc（int applyarea)
｛
int i，tag=0;/＊applyarea为作业申请量，tag为检查是否有满足作业需要的空闲区的标志＊/
for(i=0；i〈N；i++）/*检查空闲区说明表是否有满足作业要求的空闲区＊/
if（freeblock[i］。state==1＆＆freeblock［i］。size〉applyarea）
{
freeblock［i］。startaddress=freeblock[i］。startaddress+applyarea；
freeblock[i].size=freeblock［i］。size-applyarea；
tag=1;/*有满足条件的空闲区时，tag置1＊/
return freeblock［i］.startaddress—applyarea； /＊返回为作业分配的主存地址＊/
}
else
if（freeblock［i］。state==1&&freeblock［i].size==applyarea）
｛
freeblock[i]。state=0;
tag=1；/＊有满足条件的空闲区时，tag置1*/
return freeblock［i］.startaddress;/＊返回为作业分配的主存地址＊/
}
if(tag==0）
return -1；/＊没有满足条件的空闲区，分配不成功，返回—1＊/
｝
/＊定义为作业分配主存空间的函数alloc2(）,给循环首次适应算法调用＊/
int alloc2(int applyarea,int s）/*applyarea为作业申请量*/
｛
int i，tag=0；/＊tag为检查是否有满足作业需要的空闲区的标志＊/
for（i=s；i〈N;i++)/＊检查空闲区说明表是否有满足作业要求的空闲区,从上次找到的空闲去的下一个空闲分区开始找＊/
if（freeblock［i].state==1＆&freeblock［i］.size>applyarea）
｛
freeblock［i]。startaddress=freeblock［i］。startaddress+applyarea；
freeblock［i］。size=freeblock[i］。size-applyarea;
tag=1;/＊有满足条件的空闲区时，tag置1＊/
start=freeblock［i］。startaddress—applyarea；
return i；
｝
else
if（freeblock［i].state==1＆&freeblock［i].size==applyarea)
｛
freeblock［i].state=0;
tag=1；/＊有满足条件的空闲区时，tag置1＊/
start=freeblock［i].startaddress；/＊返回为作业分配的主存地址＊/
return i；
｝
if（tag==0）
return —1；/＊没有满足条件的空闲区,分配不成功,返回—1＊/
｝
/＊定义为作业分配主存空间的函数alloc3（)，给最佳适应算法调用*/
int alloc3（int applyarea）/＊applyarea为作业申请量*/
{
int i，k，h,flag,tag=0，j=0；/＊tag为检查是否有满足作业需要的空闲区的标志＊/
int a[N］；
struct freearea min；
struct freearea mid；
for（i=0；i〈N；i++)/＊检查空闲区说明表是否有满足作业要求的空闲区＊/
{
if（freeblock［i］.state==1＆＆freeblock[i].size==applyarea)//大小刚好相等
{
freeblock[i]。state=0;
tag=1；/＊有满足条件的空闲区时，tag置1*/
return freeblock［i].startaddress；/＊返回为作业分配的主存地址*/
}
｝
for（i=0;i<N；i++）//把所有大于所要求的空闲区放入数组,挑出最小的那个
｛
if（freeblock［i］.state==1＆&freeblock［i］.size>applyarea）a［j++]=i；
｝
if（j〉1)
｛
h=a［0];
min=freeblock［h];
//min。startaddress=freeblock［h］。startaddress;
//min。size=freeblock［h］.size；
//min。state=freeblock［h].stat
for（k=1;k〈j;k++）
{
h=a[k];
if(freeblock[h］。size<min。size）
｛
mid.size=freeblock［h］。size；
mid。state=freeblock[h].state；
mid。startaddress=freeblock［h]。startaddress；
freeblock［h].size=min.size;
freeblock［h].state=min.state；
freeblock［h］.startaddress=min。startaddress；
min。size=mid。size；
min.state=mid。state;
min。startaddress=mid.startaddress;
｝
｝
min。startaddress=min.startaddress+applyarea；
min。size=min。size—applyarea；
tag=1;/*有满足条件的空闲区时,tag置1*/
return min。startaddress-applyarea；
｝
else if(j==1)
{
h=a［0]；
min=freeblock［h]；
min。startaddress=min。startaddress+applyarea;
min。size=min。size-applyarea;
tag=1;/*有满足条件的空闲区时，tag置1*/
return min。startaddress—applyarea；
}
if（tag==0)
return —1；/＊没有满足条件的空闲区，分配不成功,返回—1*/
｝
/*定义主存回收函数：setfree（)
tag1代表释放区的高地址是否邻接一个空闲区，
tag2代表释放区的高低地址是否都邻接一个空闲区，
tag3代表释放区的低地址是否邻接一个空闲区＊/
void setfree（)
｛
int s，l，tag1=0,tag2=0,tag3=0，i,j;
printf（"请输入释放区的起始地址：”）；
scanf（"%d”，＆s）；/*输入释放区的开始地址＊/
printf（”请输入释放区的大小:"）；
scanf（"％d”,＆l）；/*输入释放区的大小＊/
printf（”＊*＊＊＊＊*＊＊＊＊*回收内存后空闲区表的状态如下＊＊＊＊＊＊＊＊＊*\n”）;
for（i=0；i<N;i++）
{
if（freeblock［i]。startaddress==s+l&＆freeblock［i］。state==1）
{
l=l+freeblock[i］。size;
tag1=1;/*有与释放区高地址邻接的空闲区,tag1置1*/
for(j=0；j<N;j++）
if（freeblock［j]。startaddress+freeblock［j］.size==s&&freeblock[j].state==1)
｛
freeblock[i］。state=0；
freeblock［j]。size=freeblock［j］.size+l；
tag2=1;/＊有与释放区上下都邻接的空闲区，tag2置1*/
break；
｝
if（tag2==0）/*无与释放区高低地址邻接的空闲区*/
｛
freeblock［i］。startaddress=s;
freeblock［i].size=l；
break;
｝
｝
}
if(tag1==0）/＊无与释放区高地址邻接的空闲区，并检查是否低地址有邻接空闲区＊/
｛
for（i=0；i〈N；i++）
if（freeblock［i］.startaddress+freeblock［i］.size==s＆＆freeblock［i］。state==1)
｛
freeblock［i].size=freeblock［i］.size+l；
tag3=1；/*有与释放区低地址邻接的空闲区＊/
break；
｝
if(tag3==0)/＊无与释放区低地址邻接的空闲区*/
for(j=0；j<N；j++)
if(freeblock[j］.state==0）/＊找一个空表目，将释放区放入表中＊/
{
freeblock［j].startaddress=s;
freeblock［j］。size=l;
freeblock［j］.state=1；
break；
｝
}
｝
/＊定义对空闲区表中的空闲区调整的函数adjust(），
使空闲区按始地址从小到大排列，空表目放在最后面＊/
void adjust(）
｛
int i，j；
struct freearea middata；
for（i=0;i<N；i++)/*将空闲区按始地址顺序在表中排列＊/
for(j=0；j〈N；j++）
if(freeblock[j］。startaddress>freeblock［j+1].startaddress）
{
middata。startaddress=freeblock[j］.startaddress；
middata。size=freeblock[j］。size；
middata。state=freeblock[j].state;
freeblock［j］。startaddress=freeblock［j+1］。startaddress;
freeblock［j］。size=freeblock[j+1］。size；
freeblock［j］.state=freeblock［j+1］。state；
freeblock［j+1］。startaddress=middata.startaddress；
freeblock［j+1］.size=middata。size；
freeblock[j+1].state=middata.state;
}
for（i=0;i<N；i++)/*将空表目放在表后面＊/
for（j=0；j〈N；j++)
if（freeblock[j］。state==0＆&freeblock［j+1］。state==1）
｛
middata。startaddress=freeblock[j］.startaddress;
middata.size=freeblock［j］。size;
middata.state=freeblock［j].state；
freeblock[j］.startaddress=freeblock［j+1］。startaddress；
freeblock［j］。size=freeblock［j+1］。size;
freeblock［j]。state=freeblock［j+1］.state;
freeblock［j+1］.startaddress=middata.startaddress;
freeblock［j+1]。size=middata。size；
freeblock［j+1］.state=middata。state；
｝
}
/＊定义打印空闲区说明表函数：print(）＊/
void print（)
｛
int i；
printf（"|-———---———-——-—————---—--———-——-—-——--——---—-—-—————-—-———————-|\n”)；
printf（"｜ ID start size state ｜\n”)；
printf（"｜--—--——-———-———-—-——---———-————---—-———-——-—-—--—--—-——-——--——-｜\n");
for（i=0;i〈N；i++）
｛
printf("｜ %3d %3d ％3d %3d |\n”,
freeblock[i]。ID,freeblock[i］。startaddress,freeblock［i］。size,freeblock[i］。state）；
printf("｜———--—---—-----————--——---—-—--—————--———---——-——-———-----—--——｜\n"）；
｝
}
//首次
void First_fit（）
｛
int applyarea，start;
｛
printf(”请输入作业的申请量：”）;
scanf（"%d”，&applyarea）;/＊输入作业的申请量＊/
start=alloc(applyarea)；/*调用alloc(）函数为作业分配空间,start为返回的始地址＊/
if（start==-1）/*alloc(）分配不成功时，返回-1*/
printf（”作业申请量过大，空闲区表中的存储空间无法满足,分配失败\n"）；
else
｛
adjust()；
printf（”申请作业的起始地址为:%d\n"，start）;
printf（”作业的申请量为:%d\n”,applyarea）;
printf("内存分配成功\n")；
}
｝
}
//循环首次
void Next_fit（）
｛
int applyarea，i=0；
printf（"请输入作业的申请量:”);
scanf（"%d”，&applyarea）；/*输入作业的申请量＊/
if（i==N—1)
{
i=alloc2（applyarea,i)；
if（i==-1）i=0；
}
else if(i〈N-1）
i=alloc2(applyarea,i);
//start=alloc2(applyarea，start）；/＊调用alloc2（)函数为作业分配空间，start为返回的始地址＊/
if（i==—1)/＊alloc2()分配不成功时，返回—1＊/
printf(”作业申请量过大，空闲区表中的存储空间无法满足，分配失败\n");
else
｛
adjust(）;
printf(”申请作业的起始地址为:%d\n”,start）；
printf（”作业的申请量为：%d\n”，applyarea)；
printf（"内存分配成功\n")；
｝
｝
//最佳
void Best_fit（）
{
int applyarea，st