操作系统实验四报告主存空间分配和回收含源码教材.docx
《操作系统实验四报告主存空间分配和回收含源码教材.docx》由会员分享，可在线阅读，更多相关《操作系统实验四报告主存空间分配和回收含源码教材.docx（35页珍藏版）》请在冰点文库上搜索。
操作系统实验四报告主存空间分配和回收含源码教材
计算机学院计算机科学与技术专业班学号
姓名教师评定_________________
实验题目主存空间的分配和回收
一、实验目的
熟悉主存的分配与回收。
理解在不同的存储管理方式下，如何实现主存空间的分配与回收。
掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。
二、实验内容和要求
主存的分配和回收的实现是与主存储器的管理方式有关的。
所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。
所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。
可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。
当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。
随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。
实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、最佳适应算法、最差适应算法三种算法来实现主存的分配与回收。
同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。
同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。
三、实验主要仪器设备和材料
实验环境
硬件环境：
IBM-PC或兼容机
软件环境：
VC++6.0
四、实验原理及设计分析
某系统采用可变分区存储管理，在系统运行当然开始，假设初始状态下，可用的内存空间为640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB）。
（作业1申请130KB、作业2申请60KB、作业3申请100KB、作业2释放60KB、
作业4申请200KB、作业3释放100KB、作业1释放130KB、作业5申请140KB、
作业6申请60KB、作业7申请50KB）
当作业1进入内存后，分给作业1（130KB），随着作业1、2、3的进入，分别分配60KB、100KB，经过一段时间的运行后，作业2运行完毕，释放所占内存。
此时，作业4进入系统，要求分配200KB内存。
作业3、1运行完毕，释放所占内存。
此时又有作业5申请140KB，作业6申请60KB，作业7申请50KB。
为它们进行主存分配和回收。
1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。
空闲分区链：
使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为“1”。
设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时，系统优先使用空闲低端的空间。
设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。
初始化空间区和已分配区说明链的值，设计作业申请队列以及作业完成后释放顺序，实现主存的分配和回收。
要求每次分配和回收后显示出空闲内存分区链的情况。
把空闲区说明链的变化情况以及各作业的申请、释放情况显示打印出来。
2.采用可变分区存储管理，分别采用首次适应算法、最佳适应算法和最坏适应算法实现主存分配和回收。
3、主存空间分配
（1）首次适应算法
在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。
在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。
（2）最佳适应算法
在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。
在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中
（3）最坏适应算法
在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。
在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都大，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。
4、主存空间回收
当一个作业执行完成撤离时，作业所占的分区应该归还给系统。
归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的合并问题，要求考虑四种情况：
（1）释放区下邻空闲区（低地址邻接）
（2）释放区上邻空闲区（高地址邻接）
（3）释放区上下都与空闲区邻接
（4）释放区上下邻都与空闲区不邻接
五、程序流程图
main函数里的流程图
分配空间里的流程图
回收空间里的流程图
六、相关数据结构及关键函数说明
本程序采用了一个structfree_table数据结构，里面包含分区序号（num）、起始地址（address）、分区长度（length）和分区状态（state）。
还用了线性表的双性链表存储结构（structNode），里面包含前区指针（prior）和后继指针（next）。
一开始定义一条（含有first和end）的链，用开始指针和尾指针开创空间链表。
然后分别按三种算法进行分配和回收。
在该程序中关键函数有，sort（）、allocation（）、recovery（）、和First_fit（）、Best_fit（）、Worst_fit（）；其中sort（）函数是用来整理分区序号的，如在删序号3时，她与前面序号2相连在一起了，然后序号2中的长度总满足申请的内存大小，就会在序号2中分配，然后序号在2的基础上加1，一直加，加到与原本序号3的下一个序号也就是4相等，这时sort（）就开始有明显的工作了；allocation（）是分配空间的，也是过渡到三个算法中的，当三个算法中满足或者不满足分配请求，都会又返回值给allocation（）；recovery（）是用来回收内存的，里面包含了四种情况相连结果，即释放区上与空闲区邻接、释放区下与空闲区邻接、释放区上下都与空闲区邻接、释放区上下都与空闲区不邻接这四种情况的结果。
七、源代码
#include
#include
#defineOK1//完成
#defineERROR0//出错
typedefintStatus;
typedefstructfree_table//定义一个空闲区说明表结构
{
intnum;//分区序号
longaddress;//起始地址
longlength;//分区大小
intstate;//分区状态
}ElemType;
typedefstructNode//线性表的双向链表存储结构
{
ElemTypedata;
structNode*prior;//前趋指针
structNode*next;//后继指针
}Node,*LinkList;
LinkListfirst;//头结点
LinkListend;//尾结点
intflag;//记录要删除的分区序号
StatusInitblock（）//开创带头结点的内存空间链表
{
first=（LinkList）malloc（sizeof（Node））;
end=（LinkList）malloc（sizeof（Node））;
first->prior=NULL;
first->next=end;
end->prior=first;
end->next=NULL;
end->data.num=1;
end->data.address=40;
end->data.length=600;
end->data.state=0;
returnOK;
}
voidsort（）//分区序号重新排序
{
Node*p=first->next,*q;
q=p->next;
for（;p!
=NULL;p=p->next）
{
for（q=p->next;q;q=q->next）
{
if（p->data.num>=q->data.num）
{
q->data.num+=1;
}
}
}
}
//显示主存分配情况
voidshow（）
{intflag=0;//用来记录分区序号
Node*p=first;
p->data.num=0;
p->data.address=0;
p->data.length=40;
p->data.state=1;
sort（）;
printf（"\n\t\t》主存空间分配情况《\n"）;
printf（"**********************************************************\n\n"）;
printf（"分区序号\t起始地址\t分区大小\t分区状态\n\n"）;
while（p）
{
printf（"%d\t\t%d\t\t%d",p->data.num,p->data.address,p->data.length）;
if（p->data.state==0）printf（"\t\t空闲\n\n"）;
elseprintf（"\t\t已分配\n\n"）;
p=p->next;
}
printf（"**********************************************************\n\n"）;
}
//首次适应算法
StatusFirst_fit（intrequest）
{
//为申请作业开辟新空间且初始化
Node*p=first->next;
LinkListtemp=（LinkList）malloc（sizeof（Node））;
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while（p）
{
if（（p->data.state==0）&&（p->data.length==request））
{//有大小恰好合适的空闲块
p->data.state=1;
returnOK;
break;
}
elseif（（p->data.state==0）&&（p->data.length>request））
{//有空闲块能满足需求且有剩余
temp->prior=p->prior;
temp->next=p;
temp->data.address=p->data.address;
temp->data.num=p->data.num;
p->prior->next=temp;
p->prior=temp;
p->data.address=temp->data.address+temp->data.length;
p->data.length-=request;
p->data.num+=1;
returnOK;
break;
}
p=p->next;
}
returnERROR;
}
//最佳适应算法
StatusBest_fit（intrequest）
{
intch;//记录最小剩余空间
Node*p=first;
Node*q=NULL;//记录最佳插入位置
LinkListtemp=（LinkList）malloc（sizeof（Node））;
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while（p）//初始化最小空间和最佳位置
{
if（（p->data.state==0）&&（p->data.length>=request））
{
if（q==NULL）
{
q=p;
ch=p->data.length-request;
}
elseif（q->data.length>p->data.length）
{
q=p;
ch=p->data.length-request;
}
}
p=p->next;
}
if（q==NULL）returnERROR;//没有找到空闲块
elseif（q->data.length==request）
{
q->data.state=1;
returnOK;
}
else
{
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
temp->data.num=q->data.num;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.length=ch;
q->data.num+=1;
returnOK;
}
returnOK;
}
//最差适应算法
StatusWorst_fit（intrequest）
{
intch;//记录最大剩余空间
Node*p=first->next;
Node*q=NULL;//记录最佳插入位置
LinkListtemp=（LinkList）malloc（sizeof（Node））;
temp->data.length=request;
temp->data.state=1;
p->data.num=1;
while（p）//初始化最大空间和最佳位置
{
if（p->data.state==0&&（p->data.length>=request））
{
if（q==NULL）
{
q=p;
ch=p->data.length-request;
}
elseif（q->data.lengthdata.length）
{
q=p;
ch=p->data.length-request;
}
}
p=p->next;
}
if（q==NULL）returnERROR;//没有找到空闲块
elseif（q->data.length==request）
{
q->data.length=1;
returnOK;
}
else
{
temp->prior=q->prior;
temp->next=q;
temp->data.address=q->data.address;
temp->data.num=q->data.num;
q->prior->next=temp;
q->prior=temp;
q->data.address+=request;
q->data.length=ch;
q->data.num+=1;
returnOK;
}
returnOK;
}
//分配主存
Statusallocation（inta）
{
intrequest;//申请内存大小
printf（"请输入申请分配的主存大小（单位:
KB）:
"）;
scanf（"%d",&request）;
if（request<0||request==0）
{
printf（"分配大小不合适，请重试！
"）;
returnERROR;
}
switch（a）
{
case1:
//默认首次适应算法
if（First_fit（request）==OK）printf（"\t****分配成功！
****"）;
elseprintf（"\t****内存不足，分配失败！
****"）;
returnOK;
break;
case2:
//选择最佳适应算法
if（Best_fit（request）==OK）printf（"\t****分配成功！
****"）;
elseprintf（"\t****内存不足，分配失败！
****"）;
returnOK;
break;
case3:
//选择最差适应算法
if（Worst_fit（request）==OK）printf（"\t****分配成功！
****"）;
elseprintf（"\t****内存不足，分配失败！
****"）;
returnOK;
break;
}
}
Statusdeal1（Node*p）//处理回收空间
{
Node*q=first;
for（;q!
=NULL;q=q->next）
{
if（q==p）
{
if（q->prior->data.state==0&&q->next->data.state!
=0）
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=q->prior;
q->data.state=0;
q->data.num=flag-1;
}
if（q->prior->data.state!
=0&&q->next->data.state==0）
{
q->data.length+=q->next->data.length;
q->next=q->next->next;
q->next->next->prior=q;
q->data.state=0;
q->data.num=flag;
}
if（q->prior->data.state==0&&q->next->data.state==0）
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=q->prior;
q->data.state=0;
q->data.num=flag-1;
}
if（q->prior->data.state!
=0&&q->next->data.state!
=0）
{
q->data.state=0;
}
}
}
returnOK;
}
Statusdeal2（Node*p）//处理回收空间
{
Node*q=first;
for（;q!
=NULL;q=q->next）
{
if（q==p）
{
if（q->prior->data.state==0&&q->next->data.state!
=0）
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=p->prior;
q->data.state=0;
q->data.num=flag-1;
}
if（q->prior->data.state!
=0&&q->next->data.state==0）
{
q->data.state=0;
}
if（q->prior->data.state==0&&q->next->data.state==0）
{
q->prior->data.length+=q->data.length;
q->prior->next=q->next;
q->next->prior=q->prior;
q=q->prior;
q->data.state=0;
q->data.num=flag-1;
}
if（q->prior->data.state!
=0&&q->next->data.state!
=0）
{
q->data.state=0;
}
}
}
returnOK;
}
//主存回收
Statusrecovery（intflag）
{
Node*p=first;
for（;p!
=NULL;p=p->next）
{
if（p->data.num==flag）
{
if（p->prior==first）
{
if（p->next!
=end）//当前P指向的下一个不是最后一个时
{
if（p->next->data.state==0）//与后面的空闲块相连
{
p->data.length+=p->next->data.length;
p->next->next->prior=p;
p->next=p->next->next;
p->data.state=0;
p->data.num=flag;
}
elsep->data.state=0;
}
if（p->next==end）//当前P指向的下一个是最后一个时
{
p->data.state=0;
}
}//结束if（p->prior==block_first）的情况
elseif（p->prior!
=first）
{
if（p->next!
=end）
{
deal1（p）;
}
else
{
deal2（p）;
}
}//结束if（p->prior!
=block_first）的情况
}//结束if（p->data.num==flag）的情况
}
printf（"\t****回收成功****"）;
returnOK;
}
//主函数
voidmain（）
{
inti;//操作选择标记
inta;//算法选择标记
printf（"**********************************************************\n"）;
printf（"\t\t用以下三种方法实现主存空间的分配\n"）;
printf（"\t
（1）首次适应算法\t
（2）最佳适应算法\t（3）最差适应算法\n"）;
printf（"**********************************************************\n"）;
printf（"\n"）;
printf（"请输入所使用的内存分配算法:
"）;
scanf（"%d",&a）;
w
升级会员 