计算机操作系统内存分配实验报告文档格式.docx
《计算机操作系统内存分配实验报告文档格式.docx》由会员分享,可在线阅读,更多相关《计算机操作系统内存分配实验报告文档格式.docx(36页珍藏版)》请在冰点文库上搜索。
在为作业分配存储空间时,从上次找到的空闲分区的下一个空闲分区开始查找,直到找到第一个能满足要求的空闲区,从中划出与请求的大小相等的存储空间分配给作业,余下的空闲区仍留在空闲区链中。
(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<
stdio.h〉
#include<
stdlib.h>
#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;
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—>
{
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;
data.state=1;
sort();
printf("
\n\t\t》主存空间分配情况《\n”);
**********************************************************\n\n"
);
分区序号\t起始地址\t分区大小\t分区状态\n\n"
);
while(p)
printf(”%d\t\t%d\t\t%d”,p-〉data.num,p—〉data.address,p->
length);
if(p->
data.state==0)printf(”\t\t空闲\n\n”);
elseprintf(”\t\t已分配\n\n”);
p=p->
printf(”**********************************************************\n\n”);
//首次适应算法
StatusFirst_fit(intrequest)
//为申请作业开辟新空间且初始化
Node*p=first—〉next;
LinkListtemp=(LinkList)malloc(sizeof(Node));
temp-〉data.length=request;
temp-〉data。
state=1;
num=1;
if((p—〉data.state==0)&
&(p->
data.length==request))
{//有大小恰好合适的空闲块
p—〉data。
state=1;
break;
elseif((p—〉data.state==0)&
&
(p—〉data。
length>
request))
{//有空闲块能满足需求且有剩余
temp—>
prior=p—>
prior;
temp-〉next=p;
temp—〉data。
address=p->
data.address;
num=p-〉data.num;
p—〉prior->
next=temp;
p-〉prior=temp;
p->
data.address=temp—>
data.address+temp->
data.length;
length-=request;
p-〉data.num+=1;
p=p—〉next;
returnERROR;
//最佳适应算法
StatusBest_fit(intrequest)
intch;
//记录最小剩余空间
Node*p=first;
Node*q=NULL;
//记录最佳插入位置
LinkListtemp=(LinkList)malloc(sizeof(Node));
p->
num=1;
while(p)//初始化最小空间和最佳位置
if((p->
data.state==0)&&(p—〉data.length〉=request))
if(q==NULL)
q=p;
ch=p—>
length-request;
elseif(q—>
length〉p-〉data.length)
ch=p->
next;
if(q==NULL)returnERROR;
//没有找到空闲块
elseif(q-〉data.length==request)
q—>
returnOK;
else
prior=q—〉prior;
temp—〉next=q;
data.address=q—>
temp—〉data.num=q->
num;
q—>
prior-〉next=temp;
q—〉prior=temp;
address+=request;
q—〉data。
length=ch;
q-〉data.num+=1;
//最差适应算法
StatusWorst_fit(intrequest)
intch;
//记录最大剩余空间
Node*p=first—〉next;
Node*q=NULL;
length=request;
p—〉data.num=1;
while(p)//初始化最大空间和最佳位置
if(p—〉data。
state==0&&
(p->
data.length〉=request))
q=p;
ch=p—〉data。
length—request;
data.length〈p-〉data。
length)
data.length—request;
p=p-〉next;
q-〉data.length=1;
temp-〉prior=q—>
prior;
temp-〉next=q;
address=q—〉data.address;
num;
q—〉prior-〉next=temp;
prior=temp;
address+=request;
q->
data.length=ch;
num+=1;
//分配主存
Statusallocation(inta)
intrequest;
//申请内存大小
请输入申请分配的主存大小(单位:
KB):
"
scanf(”%d”,&request);
if(request<
0||request==0)
分配大小不合适,请重试!
returnERROR;
switch(a)
case1:
//默认首次适应算法
if(First_fit(request)==OK)printf(”\t****分配成功!
****”);
elseprintf(”\t****内存不足,分配失败!
****”);
break;
case2:
//选择最佳适应算法
if(Best_fit(request)==OK)printf("
\t****分配成功!
****"
elseprintf("
\t****内存不足,分配失败!
****”);
case3:
//选择最差适应算法
if(Worst_fit(request)==OK)printf("
\t****分配成功!
elseprintf(”\t****内存不足,分配失败!
****"
break;
Statusdeal1(Node*p)//处理回收空间
Node*q=first;
for(;
q!
=NULL;
if(q==p)
if(q->
prior—>
state==0&
&q-〉next—>
data.state!
=0)
q—〉prior-〉data.length+=q-〉data.length;
prior—〉next=q->
next-〉prior=q->
q=q—>
state=0;
num=flag—1;
if(q—〉prior-〉data.state!
=0&&q->
next—〉data.state==0)
length+=q—>
next-〉data.length;
q-〉next=q->
next->
q-〉next—〉next->
prior=q;
data.state=0;
q-〉data.num=flag;
if(q->
prior-〉data.state==0&&
q-〉next->
data.state==0)
data.length+=q-〉data.length;
prior-〉next=q—>
next—>
prior=q-〉prior;
q-〉data.state=0;
data.num=flag-1;
if(q—〉prior—>
=0&&q—〉next—〉data。
state!
=0)
q-〉data.state=0;
Statusdeal2(Node*p)//处理回收空间
Node*q=first;
q!
q=q-〉next)
prior->
data.state==0&
q->
state!
q-〉prior->
length+=q->
q—〉prior->
next=q-〉next;
q-〉next—〉prior=q-〉prior;
q=p->
state=0;
q—〉data.num=flag-1;
if(q—〉prior—〉data.state!
=0&
q—>
next—〉data。
state==0)
state==0&&q—〉next-〉data。
state==0)
q—〉prior—>
length;
q-〉prior->
next=q—〉next;
q-〉next->
prior=q->
q-〉data.state=0;
num=flag—1;
if(q—〉prior->
=0&&q-〉next-〉data.state!
q—〉data。
//主存回收
Statusrecovery(intflag)
Node*p=first;
p!
p=p-〉next)
if(p->
num==flag)
{
if(p—〉prior==first)
{
next!
=end)//当前P指向的下一个不是最后一个时
if(p—>
state==0)//与后面的空闲块相连
length+=p—〉next->
prior=p;
next=p->
p—〉data.num=flag;
}
elsep—>
}
if(p-〉next==end)//当前P指向的下一个是最后一个时
}//结束if(p—〉prior==block_first)的情况
elseif(p—>
prior!
=first)
=end)
deal1(p);
else
deal2(p);
}//结束if(p->
=block_first)的情况
}//结束if(p—〉data.num==flag)的情况
printf(”\t****回收成功****"
//主函数
voidmain()
inti;
//操作选择标记
inta;
//算法选择标记
printf(”**********************************************************\n"
\t\t用以下三种方法实现主存空间的分配\n”);
\t
(1)首次适应算法\t
(2)最佳适应算法\t(3)最差适应算法\n”);
**********************************************************\n"
printf(”\n"
printf(”请输入所使用的内存分配算法:
scanf("
%d"
&a);
while(a<
1||a〉3)
printf(”输入错误,请重新输入所使用的内存分配算法:
\n"
&a);