操作系统实验-首次适应算法与循环首次适应算法

学号P71514032专业计算机科学与技术姓名实验日期2017.11.16教师签字成绩实验报告【实验名称】首次适应算法和循环首次适应算法【实验目的】学会主存空间分配与回收的基本方法首次适应算法和循环首次适应算法。【实验原理】理解在连续分区动态的存储管理方式下，如何实现贮存空间的分配与回收。采用可变式分区管理，使用最佳适应算法实现主存空间的分配与回收。采用可变式分区管理，使用最坏适应算法实现主存空间的分配与回收。数据结构：1、boolROM[N];//定义主存信息，如果内存被占用，则标记为1，否则标记为0，设置内存单元为10242、pcbnum[20];//定义作业数组，最大支持20个作业3、typedefstructPcb//定义作业结构体，包括名称，开始时间，大小，是否执行状态{charname[10];intstart;intsize;intstate=0;}pcb;typedefstructFree_rom//空闲区结构体{intnum;intstart;intend;intspace;}Free_room;Free_romfree_rom[100];//设置空闲区数组为100个主要函数voidinit()；//初始化信息，包括初始化内存信息，和初始化作业队列voidinsert_pcb1(pcb&a)；插入作业函数，首次适应算法，如果有适合的就插入，无合适输出‘插入失败’voidinsert_pcb1(pcb&a)；插入作业函数，循环首次适应算法，如果有适合的就插入，无合适输出‘插入失败’voidDelete(pcb&a)//删除作业信息，包括修改内存状态修改作业状态并对作业进行初始化voidshow();//显示信息voidfind_free_rom()//寻找空闲区算法流程图首次适应算法开始空闲区登记插入作业信息当前空闲区是否满足空闲区指针指向第一个空闲区插入当前作业，修改内存信息和作业信息表信息是否为最后一个空闲区空闲区指针指向下一个空闲区作业插入失败继续插入？结束整理输出是否否是是否循环首次适应算法开始作业插入失败空闲区登记插入作业信息空闲区指针指向第一个空闲区，标记当前空闲区P当前空闲区是否满足插入当前作业，修改内存信息和作业信息表信息结束继续插入？空闲区指针指向下一个空闲区，标记当前空闲区P空闲区指针加一是否为最后一个空闲区空闲区指针指向第一个空闲区当前空闲区是否满足是否小于所标记的空闲区P当前指针所指向区域是否满足空闲区指针指向下一个空闲区是否否是否是否是否是输出信息否是程序代码及截图：#includestdio.h#includestring.h#defineN1024boolROM[N];//设置内存块intp=0;//循环首次使用需要标记当前的空闲区块typedefstructPcb//作业数据结构{charname[10];intstart;intsize;intstate=0;}pcb;intfree_rom_counter=0;pcbnum[20];//作业队列typedefstructFree_rom//空闲区结构体{intnum;intstart;intend;intspace;}Free_room;Free_romfree_rom[100];//设置空闲区数组为100个voidfind_free_rom()//寻找空闲区{free_rom_counter=0;inti,j,p;for(i=0;iN;i++)if(ROM[i]==0){p=i;for(j=i;jN;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;}}}voidinit()//初始化{for(inti=0;iN;i++)ROM[i]=0;}voidshow(){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);}voidinsert_pcb1(pcb&a)//首次适应算法来实现作业调度{inti,j,k;for(i=0;iN;i++)if(ROM[i]==0){for(j=i;j=(i+a.size)&&jN;j++)//查询第一个空闲区，并判断是否适合插入作业if(ROM[j]==1){i=j+1;break;}if(j==i+a.size+1){a.start=i;//设置作业的开始内存a.state=1;//标记作业在内存中for(k=i;ki+a.size&&jN;k++)ROM[k]=1;printf(插入成功，进程%s的初始地址为%d,结束地址为%d\n,a.name,a.start,a.start+a.size-1);return;}}if(i==N)//未查询到合适的区域printf(插入失败，无可用空间\n);}voidinsert_pcb2(pcb&a)//循环首次适应算法来实现作业调度{inti,j,k;for(i=p;iN;i++)//从所标记的当前区域开始查询，查询到末内存{if(ROM[i]==0){for(j=i;j=(i+a.size)&&jN;j++)if(ROM[j]==1){i=j+1;break;}if(j==i+a.size+1)//找到合适的空闲区{a.start=i;a.state=1;for(k=i;ki+a.size&&jN;k++)ROM[k]=1;printf(插入成功，进程%s的初始地址为%d,结束地址为%d\n,a.name,a.start,a.start+a.size-1);p=i+a.size;return;}}}for(i=0;ip;i++)//当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的Pif(ROM[i]==0){for(j=i;j=(i+a.size)&&jp;j++)if(ROM[j]==1){i=j+1;break;}if(j==i+a.size+1)//成功找到结束，并标记当前P为现在的作业的尾部{a.start=i;a.state=1;for(k=i;ki+a.size&&jp;k++)ROM[k]=1;printf(插入成功，进程%s的初始地址为%d\n,a.name,a.start);p=i+a.size;break;}}if(i==p)//查询两部分都未找到合适的区域，输出插入失败语句printf(插入失败，无可用空间\n);}voidDelete(pcb&a)//删除作业，修改内存信息和初始化该作业信息{inti;for(i=a.start;ia.start+a.size;i++)ROM[i]=0;a.state=0;//状态标记为未使用printf(删除成功\n);}intmain(){init();intcount=0;intchoose1,choose;charname[10];pcba;printf(1、首次适应算法\n);printf(2、循环首次适应算法\n);scanf(%d,&choose1);do{printf(\n\n1、插入进程\n);printf(2、删除进程\n);printf(3、显示进程的信息\n);printf(4、显示空闲区\n);scanf(%d,&choose);if(choose==1){printf(输入进程名\n);scanf(%s,&a.name);printf(输入进程大小\n);scanf(%d,&a.size);if(choose1==1)insert_pcb1(a);elseinsert_pcb2(a);num[count++]=a;}elseif(choose==2){printf(输入删除进程的名字\n);scanf(%s,&name);for(inti=0;icount;i++)if(!strcmp(num[i].name,name))Delete(num[i]);}elseif(choose==3){printf(进程名\t\t开始地址\t\t大小\t\t结束地址\t\t\n);//输出内存信息for(inti=0;icount-1;i++)for(intj=i;jcount-1;j++)if(num[j].startnum[j+1].start){a=num[j];num[j]=num[j+1];num[j+1]=a;}for(inti=0;icount;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);}elseif(choose==4){find_free_rom();show();}elsebreak;}while(1);return0;}首次适应算法：本实验共采用1024个内存进行模拟，首先对内存初始化，得到一个大的空闲区：相继插入3个进程：分别插入进程ABC,大小分别为100,200,300此时查询进程信息和查询空闲区信息有一块大小为424起始地址为600的空闲区在进行插入D删除B此时有两块空闲区插入一个150大小的进程，他的起始地址应为100此时空闲区只有2块，一块大小为50，删除C进程，构造一块大空闲区再插入一个进程为100大小,此时两块空闲区都满足，此时应从第一块插入再插入一个大于两块空闲区大小的进程，此时无可用空间首次适应算法完成。循环首次适应算法此时有三块空闲区，由于先前插入的是E进程，此时空闲区指针指向3，插入一个小于15的内存，会插入到3空间，再插入一个5的内存，由于采用循环首次适应，此时插入的也是3再插入一个小于200的进程，此时扫描到最后，没找到，转而从低地址开始查找循环首次适应算法正确【小结或讨论】1、首次适应算法倾向于利用内存中低地址部分的空闲区域，从而保留了高地址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。其缺点是低地址部分不断被划分，会留下许多难以利用的、很小的空闲分区碎片。每次查找都是从低地址部分开始的，这样会增加查找可用空闲分区的开销。2、为了避免低地址部分留下的许多很小的空闲分区以及减少查找可用空间区的开销，循环首次适应算法在为作业分配时，从上次找到的空闲区的下一个空闲区开始查找，找不到再从头开始查找，实现该算法，在程序中设置了一个指针P，用于指示下一个起始查询的空闲分区。该算法能够使内存中分配的分布区域更均匀，从而减少了查找空闲区的开销，但这样也会导致缺乏大的空闲区。3、根据经验，如果作业的大小较为均为，使用循环首次适应算法实现较好。4、本实验对两种算法进行模拟时，并未采