操作系统实验四-主存空间的分配与回收-首次适应算法和循环首次适应算法

实验报告【实验名称】首次适应算法和循环首次适应算法【实验目的】理解在连续分区动态的存储管理方式下，如何实现主存空间的分配与回收。【实验原理】首次适应（firstfit，FF）算法FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区即可。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已经没有足够大的内存分配给该进程，内存分配失败，返回。循环首次适应（nextfit，NF）算法为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块玉请求大小相等的内存空间分配给作业。【实验内容】实现主存空间的分配与回收：1.采用可变式分区管理，使用首次适应算法实现主存空间的分配与回收；2.采用可变式分区管理，使用循环首次适应算法实现主存空间的分配与回收。数据结构和符号说明：typedefstructPCB//进程控制块{charProgressName[10];//进程名称intStartaddress;//进程开始地址intProgressSize;//进程大小intProgressState=0;//进程状态};typedefstructFREE//空闲区结构体{intFree_num;//空闲区名称intStartaddress;//空闲区开始地址intEndaddress;//空闲区结束地址intFree_Space;//空闲区大小};算法流程图：首次适应算法开始空闲区登记插入作业空闲区指针指向第一个空闲区当前空闲区是否满足要求？插入作业，修改内存信息和作业信息表是是否继续插入？结束否是否为最后一个空闲区？否插入失败是空闲区指针指向下一个空闲区否是循环首次适应算法开始作业插入失败空闲区登记插入作业空闲区指针指向第一个空闲区，标记当前空闲区P当前空闲区是否满足插入当前作业，修改内存信息和作业信息表信息结束继续插入？空闲区指针指向下一个空闲区，标记当前空闲区P空闲区指针加一是否为最后一个空闲区空闲区指针指向第一个空闲区当前空闲区是否满足是否小于所标记的空闲区P当前指针所指向区域是否满足空闲区指针指向下一个空闲区是否否是否是否是否是输出信息否是程序代码及截图：#includestdio.h#includestring.h#includestdlib.h#includeio.h#defineN1024typedefstructPCB//进程控制块{charProgressName[10];//进程名称intStartaddress;//进程开始地址intProgressSize;//进程大小intProgressState=0;//进程状态};typedefstructFREE//空闲区结构体{intFree_num;//空闲区名称intStartaddress;//空闲区开始地址intEndaddress;//空闲区结束地址intFree_Space;//空闲区大小};intcount=0;//当前内存中进程个数boolROM[N];//设置内存块intp=0;//循环首次使用需要标记当前的空闲区块FREEFREE[100];//设置空闲区数组为100个intFREE_counter=0;//空闲区的个数PCBnum[20];//作业队列voidinit()//初始化操作{for(inti=0;iN;i++)ROM[i]=0;}voidshowProgress(PCB&a){printf(----------------------------------------------------------------------\n);printf(进程名\t\t开始地址\t\t大小\t\t结束地址\n);//输出内存信息printf(----------------------------------------------------------------------\n);for(inti=0;icount-1;i++)for(intj=i;jcount-1;j++)if(num[j].Startaddressnum[j+1].Startaddress){a=num[j];num[j]=num[j+1];num[j+1]=a;}for(inti=0;icount;i++)if(num[i].ProgressState!=0)printf(%s\t\t%d\t\t\t%d\t\t%d\t\t\n,num[i].ProgressName,num[i].Startaddress,num[i].ProgressSize,num[i].ProgressSize+num[i].Startaddress-1);printf(----------------------------------------------------------------------\n);}voidshowFree()//打印空闲区的情况{printf(----------------------------------------------------------------------\n);printf(空闲区名\t|开始地址\t|大小\t|结束地址\n);printf(----------------------------------------------------------------------\n);for(inti=1;i=FREE_counter;i++){printf(\t%1d\t%8d\t%11d\t%d\n,FREE[i].Free_num,FREE[i].Startaddress,FREE[i].Free_Space,FREE[i].Endaddress);printf(----------------------------------------------------------------------\n);}}voidfind_FREE()//寻找空闲区{inti,j,p;//计数值FREE_counter=0;//预设空闲区数为0for(i=0;iN;i++)if(ROM[i]==0){p=i;for(j=i;jN;j++){if(ROM[j]==0)//未找到空闲区，则将j赋值给i后继续循环{i=j;continue;}if(ROM[j]==1)//找到空闲区{FREE_counter++;//空闲区个数+1；FREE[FREE_counter].Free_num=FREE_counter;//设置空闲区编号FREE[FREE_counter].Startaddress=p;FREE[FREE_counter].Endaddress=j-1;FREE[FREE_counter].Free_Space=j-p;i=j+1;break;}}if(j==N&&ROM[j-1]==0)//对最后一个内存进行特殊操作{FREE_counter++;FREE[FREE_counter].Free_num=FREE_counter;//对空闲区进行处理FREE[FREE_counter].Startaddress=p;FREE[FREE_counter].Endaddress=j-1;FREE[FREE_counter].Free_Space=j-p;}}}voidFirst_Fit(PCB&a)//首次适应算法{inti,j,k;for(i=0;iN;i++)if(ROM[i]==0){for(j=i;j=(i+a.ProgressSize)&&jN;j++)//查询第一个空闲区，并判断是否适合插入作业if(ROM[j]==1){i=j+1;break;}if(j==i+a.ProgressSize+1){a.Startaddress=i;//设置作业的开始地址a.ProgressState=1;//标记作业在内存中for(k=i;ki+a.ProgressSize&&jN;k++)ROM[k]=1;printf(进程%s插入成功，进程%s的初始地址为%d,结束地址为%d\n,a.ProgressName,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1);return;}}if(i==N)//未查询到合适的区域printf(插入失败，无可用空间！\n);}voidNext_Fit(PCB&a)//循环首次适应算法来实现作业调度{inti,j,k;for(i=p;iN;i++)//从所标记的当前区域开始查询，查询到末内存{if(ROM[i]==0){for(j=i;j=(i+a.ProgressSize)&&jN;j++)if(ROM[j]==1){i=j+1;break;}if(j==i+a.ProgressSize+1)//找到合适的空闲区{a.Startaddress=i;a.ProgressState=1;for(k=i;ki+a.ProgressSize&&jN;k++)ROM[k]=1;printf(插入成功，进程%s的初始地址为%d,结束地址为%d\n,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1);p=i+a.ProgressSize;return;}}}for(i=0;ip;i++)//当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的Pif(ROM[i]==0){for(j=i;j=(i+a.ProgressSize)&&jp;j++)if(ROM[j]==1){i=j+1;break;}if(j==i+a.ProgressSize+1)//成功找到结束，并标记当前P为现在的作业的尾部{a.Startaddress=i;a.ProgressState=1;for(k=i;ki+a.ProgressSize&&jp;k++)ROM[k]=1;printf(插入成功，进程%s的初始地址为%d\n,a.ProgressName,a.Startaddress);p=i+a.ProgressSize;break;}}if(i==p)//查询两部分都未找到合适的区域，输出插入失败语句printf(插入失败，无可用空间\n);}voidDelete(PCB&a)//删除作业，修改内存信息和初始化该作业信息{inti;for(i=a.Startaddress;ia.Startaddress+a.ProgressSize;i++)ROM[i]=0;a.ProgressState=0;//状态标记为未使用printf(进程%s删除成功\n,a.ProgressName);}intmain(){intchoose1,choose;charProgressName[10];PCBa;init();printf(\t主存空间的分配与回收\n);printf(---------------------------------------\n);printf(\t1、首次适应算法\n);printf(\t2、循环首次适应算法\n);printf(---------------------------------------\n);printf(请选择分配算法：);scanf(%d,&choose1);system(cls);while(1){w:system(cls);printf(当前分配算法：);if(choose1==1)printf(首次适应算法\n);e