操作系统实验最佳适应算法最坏适应算法.docx
《操作系统实验最佳适应算法最坏适应算法.docx》由会员分享，可在线阅读，更多相关《操作系统实验最佳适应算法最坏适应算法.docx（20页珍藏版）》请在冰点文库上搜索。
操作系统实验最佳适应算法最坏适应算法
操作系统实验-最佳适应算法最坏适应算法
学号P7*******专业计算机科学与技术姓名
实验日期2017/11/23教师签字成绩
实验报告
【实验名称】基于顺序搜索的动态分区分配算法
（二）
【实验目的】
理解在连续分区动态的存储管理方式下，如何实现贮存空间的分配与回收。
采用可变式分区管理，使用最佳适应算法实现主存空间的分配与回收。
采用可变式分区管理，使用最坏适应算法实现主存空间的分配与回收。
【实验原理】
C++语言程序设计
最坏适应算法：
#include
#include
#defineN1024
boolROM[N];
intp=0;
intcount=0;
intfree_rom_counter=0;//空闲区数目
typedefstructPcb//进程结构体
{
charname[10];
intstart;
intsize;//大小
intstate=0;//状态
}pcb;
pcbnum[20];//进程数组
typedefstructFree_rom//空闲区结构体
{
intnum;
intstart;
intend;
intspace;//空闲区大小
}Free_room;
Free_romfree_rom[100];//空闲区数组
voidshow（）//显示空闲区信息
{
printf（"****************************************************************\n\n"）;
printf（"空闲区名\t开始地址\t\t大小\t\t结束地址\t\t\n"）;
for（inti=1;i<=free_rom_counter;i++）
printf（"%d\t\t%d\t\t\t%d\t\t%d\t\t\n",free_rom[i].num,free_rom[i].start,free_rom[i].space,free_rom[i].end）;
printf（"\n"）;
printf（"****************************************************************\n\n"）;
}
voidfind_free_rom（）//寻找空闲区，更新空闲区数组
{
free_rom_counter=0;
inti,j,p;
for（i=0;iif（ROM[i]==0）
{
p=i;
for（j=i;j{
if（ROM[j]==0）
{
i=j;
continue;
}
if（ROM[j]==1）//找到就更新信息
{
free_rom_counter++;
free_rom[free_rom_counter].num=free_rom_counter;
free_rom[free_rom_counter].start=p;
free_rom[free_rom_counter].end=j-1;
free_rom[free_rom_counter].space=j-p;
i=j+1;
break;
}
}
if（j==N&&ROM[j-1]==0）//对最后一个内存进行特殊处理
{
free_rom_counter++;
free_rom[free_rom_counter].num=free_rom_counter;
free_rom[free_rom_counter].start=p;
free_rom[free_rom_counter].end=j-1;
free_rom[free_rom_counter].space=j-p;
}
}
}
voidsort1（）//最佳适应算法对空闲区从小到大排序
{
find_free_rom（）;
Free_roma;
for（inti=1;ifor（intj=1;jif（free_rom[j].space>free_rom[j+1].space）
{
a=free_rom[j];
free_rom[j]=free_rom[j+1];
free_rom[j+1]=a;
}
}
voidsort2（）//最坏适应算法对空闲区从大到小排序
{
find_free_rom（）;
Free_roma;
for（inti=1;ifor（intj=1;jif（free_rom[j].space{
a=free_rom[j];
free_rom[j]=free_rom[j+1];
free_rom[j+1]=a;
}
}
voidinit（）//初始化
{
for（inti=0;iROM[i]=0;
}
voidinput（pcb&a）//输入
{
charname[10];
printf（"输入进程名\n"）;
scanf（"%s",&a.name）;
printf（"输入进程大小\n"）;
scanf（"%d",&a.size）;
}
voidinsert_pcb1（pcb&a）//最佳适应算法插入进程
{
find_free_rom（）;
sort1（）;
inti,j,k;
for（i=1;i<=free_rom_counter;i++）//判断插入
if（a.size<=free_rom[i].space）
{
for（j=free_rom[i].start;jROM[j]=1;
a.state=1;
a.start=free_rom[i].start;
num[count++]=a;
break;
}
if（i==free_rom_counter+1）//插入失败
printf（"可用空间不足!
\n"）;
}
voidinsert_pcb2（pcb&a）//最坏适应算法插入{
find_free_rom（）;
sort2（）;
inti,j,k;
for（i=1;i<=free_rom_counter;i++）
if（a.size<=free_rom[i].space）
{
for（j=free_rom[i].start;jROM[j]=1;
a.state=1;
a.start=free_rom[i].start;
num[count++]=a;
break;
}
if（i==free_rom_counter+1）//插入失败
printf（"可用空间不足!
\n"）;
}
voidDelete（pcb&a）//内存中释放进程
{
inti;
for（i=a.start;iROM[i]=0;//更新内存信息，更新进程状态数组
a.state=0;
printf（"删除成功\n"）;
find_free_rom（）;
}
intmain（）//主函数
{
init（）;
find_free_rom（）;
intchoose1;
intchoose;
charname[10];
printf（"1、最佳适应算法\n"）;//主界面
printf（"2、最坏首次适应算法\n"）;
scanf（"%d",&choose1）;
pcba;
do
{
printf（"\n\n1、插入进程\n"）;
printf（"2、删除进程\n"）;
printf（"3、显示进程信息\n"）;
printf（"4、显示空余内存信息\n"）;
scanf（"%d",&choose）;
if（choose==1）//选择
{
input（a）;
if（choose1==1）
insert_pcb1（a）;
elseinsert_pcb2（a）;
}
elseif（choose==2）
{
printf（"输入删除进程的名字\n"）;
scanf（"%s",&name）;
for（inti=0;iif（!
strcmp（num[i].name,name））
Delete（num[i]）;
}
elseif（choose==3）
{
printf（"****************************************************************\n\n"）;
printf（"进程名\t\t开始地址\t\t大小\t\t结束地址\t\t\n"）;//输出内存信息
for（inti=0;iif（num[i].state!
=0）
printf（"%s\t\t%d\t\t\t%d\t\t%d\t\t\n",num[i].name,num[i].start,num[i].size,num[i].size+num[i].start-1）;
printf（"\n****************************************************************\n\n"）;
}
elseif（choose=4）
{
find_free_rom（）;
show（）;
}
elsebreak;
}
while
（1）;
return0;
}
截图：
构造如下空闲区：
此时插入一个进程G，大小为80H，应插入到第二块空闲区
再插入一个大小为30的进程H，应插入到第三块中
再插入一个小进程，大小为5，插入到第二块空闲区，查看进程信息和空闲区信息：
最佳适应算法成立。
最坏适应算法：
构造如下空闲区：
插入一个大小为80的进程G，插入到第一块空闲区。
在插入一个大小为20的进程H，插入到第三块空闲区。
再插入一个大小为20的进程，插入到第三块空闲区。
最坏适应算法成立。
【小结或讨论】
1、本次实验涉及到两个表，空闲区登记表和进程分配表，分配空间需要进程所需空间的大小，给出过分配后进程的起始地址；回收空间除了需要进程所需空间的大小以外，还需要知道进程的起始地址，再进行一系列判断然后回收。
2、本次实验的两个算法是在首次适应算法的基础上进行的改进，最佳适应算法是将所有区按照区的大小进行升序排列，再从第一个区即最小的区开始检索分配内存；最坏适应算法是将所有区按照区的大小进行降序排列，再直接将第一个区即最大的区给进程分配空间。
3、最坏适应算法较最佳适应算法简单一些，只需要一层for循环，只跟第一个区大小进行比较即可。
4、通过本次实验，我对于主存空间的动态分配与回收有了进步的理解。
掌握了最佳适应算法和最坏适应算法的中心思想。
最佳适应算法是首先将主存空闲空间大小进行排序，找到最适合的一个空间分配。
但看似充分利用了空闲空间，但导致剩余的空间过于小而导致无法使用。
而最坏适应算法与其恰恰相反。
升级会员 