操作系统实验-最佳适应算法最坏适应算法

学号 专业 计算机科学与技术 姓名 实验日期2017/11/23教师签字 成绩 实验报告【实验名称】 基于顺序搜索的动态分区分配算法(二) 【实验目的】理解在连续分区动态的存储管理方式下，如何实现贮存空间的分配与回收。采用可变式分区管理，使用最佳适应算法实现主存空间的分配与回收。采用可变式分区管理，使用最坏适应算法实现主存空间的分配与回收。【实验原理】C++语言程序设计 数据结构 最佳适应算法最坏适应算法数据结构和符号说明1、boolROM[N];//定义主存信息，如果内存被占用，则标记为1，否则标记为0，设置内存单元为10242、pcbnum[20];//定义作业数组，最大支持20个作业3、typedefstructPcb//定义作业结构体，包括名称，开始时间，大小，是否执行状态{charname[10];intstart;intsize;intstate=0;}pcb;主要函数：voidfind_free_rom()；//寻找空闲区voidsort1()；//对空闲区进行排序从小到大voidsort1()；//对空闲区进行排序从大到小voidshow()；//显示函数voidinsert_pcb1(pcb&a)；//最佳适应算法voidinsert_pcb2(pcb&a)；//最坏适应算法voidinit();//初始化函数算法流程图：最佳适应算法：最坏适应算法：#include<stdio.h>#include<string.h>#defineN1024boolROM[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;i<N;i++)if(ROM[i]==0){p=i;for(j=i;j<N;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;i<free_rom_counter;i++)for(intj=1;j<free_rom_counter;j++)if(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;i<free_rom_counter;i++)for(intj=1;j<free_rom_counter;j++)if(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;}}voidinit()//初始化{for(inti=0;i<N;i++)ROM[i]=0;}voidinput(pcb&a)//输入{charname[10];printf("输入进程名\n");scanf("%s",&);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;j<free_rom[i].start+a.size;j++)ROM[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;j<free_rom[i].start+a.size;j++)//寻找ROM[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;i<a.start+a.size;i++)ROM[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;i<count;i++)if(!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;i<count;i++)if(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的进程，插入到第三块空闲区。最坏适应算法成立。【小结或讨论】本次实验涉及到两个表，空闲区登记表和进程分配表，分配空间需要进程所需空间的大小，给出过分配后进程的起始地址；回收空间除了需要进程所需空间的大小以外，还需要知道进程的起始地址，再进行一系列判断然后回收。本次实验的两个算法是在首次适应算法的基础上进行的改进，最佳适应算法是将所有区按照区的大小进行升序排列，再从第一个区即最小的