操作系统实验报告实验题目:首次适应算法学生学号:学生姓名:专业年级:开课学期:指导教师:1、实验名:首次适应算法2、实验目的采用可变式分区管理,使用首次适应算法实现内存分配与回收。FF算法要求空闲分区链以地址递增的次序连接。在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止;然后再按照作业的大小,从该分区中划出一块内存空间给请求者,余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个满足要求的分区,则此次内存分配失败,返回。该算法倾向于优先利用内存中的低址部分的空闲分区,从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。3、设计思想数据结构为:(1)进程数量:number(2)内存块大小:neicun(3)已使用分区数目:fqNum(4)开始位置:start(5)结束位置:end(6)进程名称:name(7)进程大小:capactity(8)分区使用标记flag设计思路:(1)程序首先定义了进程数目number=100,以及对内存块大小和分区数目进行了初始化。(2)从main函数开始,并分别定义了功能菜单menu()函数,内存初始化init-neicun()函数,内存分配fenpei()函数,首次适应算法first-fit()函数,内存回收memory-recovery()函数,进程显示showit()函数,以及退出系统exit()函数,这些算法函数对内存的查看、分配和回收等进行了计算。4、主要功能模块(1)main()函数(2)menu()函数(3)init-neicun()函数(4)fenpei()函数(5)first-fit()函数(6)memory-recovery()函数(7)showit()函数(8)exit()函数5、模块的输入输出(1)main()函数:整型输入,调用两个函数,返回0;(2)menu()函数:功能菜单,输入对功能菜单的选择select(1-4),它们分别是1添加进程,2回收内存,3查看内存分配,4退出。并通过switch方法实现对各函数的调用。(3)init-neicun()函数:输入内存大小,并对第i个进程的名称name、开始位置start、结束位置end、大小capactity以及标记位flag等进行了初始化。(4)fenpei()函数:为内存分配内存,输入所需添加进程的名称和大小,并调用first-fit()算法。(5)first-fit()函数:当某一分区不在使用时,如果内存空间大于进程长度,则分配内存,并输出该内存的名称name和大小size,并通过检验标记位flag是否等于1来输出是否能为该进程成功分配内存。(6)memory-recovery()函数:回收之前分配给进程的内存,输入需回收内存的进程名称,标记位flag表示回收是否成功,0代表失败,1代表成功,根据flag的值输出内存是否回收成功。此外,将连续的已回收的内存区合并。(7)showit()函数:显示进程情况,即输出各个进程的名称,开始位置,结束位置,进程大小。并根据flag的值来判断一进程是已使用、未使用还是尾部。(8)exit()函数:整型输入,返回0;通过exit(0)方法来退出程序。6、程序流程图开始main函数init-neicun()函数menu()函数7、实验截图fenpei()函数Memory_recovery()函数showit()函数exit()函数first_fit()函数结束8、源代码#includestdio.h#includestring.h#includeiostream#definenumber100//进程数量intneicun=200;//内存块默认大小intfqNum=1;//已使用分区数目,进程数目=fqNum-1//结构类型structfqinfo//分区信息{intstart;//开始位置intend;//结束位置charname;//进程名称intcapactity;//进程大小或者分区块大小intflag;//分区使用标记,0:未使用1:已使用2:回收或者合并的分区3:尾部}fqlist[number];//fqlist[]分区列表//函数定义intmenu();//功能菜单intinit_neicun();//初始化内存大小intfenpei();//为进程分配内存intfirst_fit(charname,intsize);//首次适应算法intMemory_recovery();//内存回收intshowit();//显示进程intexit();//退出系统//功能菜单menuintmenu(){intselect;printf(\n---------------------------------------\n);printf(1:添加进程2:回收内存\n);printf(3:查看内存分配4:退出\n);printf(\n---------------------------------------\n);printf(pleaseinputyourchoice:);scanf(%d,&select);switch(select){case1:fenpei();break;case2:Memory_recovery();break;case3:showit();break;case4:exit();break;}menu();return0;}//初始化内存大小intinit_neicun(){for(inti=0;inumber;i++){fqlist[i].name='n';fqlist[i].start=0;fqlist[i].end=0;fqlist[i].capactity=0;fqlist[i].flag=0;}printf(请输入内存大小:);scanf(%d,&neicun);printf(内存大小neicun=%d\n,neicun);fqlist[0].capactity=neicun;fqlist[0].start=0;fqlist[0].end=neicun-1;fqlist[0].flag=3;//标志位flag=3return0;}//为进程分配内存intfenpei(){getchar();charm;intn;printf(请输入进程的名称和大小(空格分隔):);scanf(%c%d,&m,&n);first_fit(m,n);//调用first_fit算法return0;}//首次适应算法intfirst_fit(charjname,intsize){printf(name=%c,size=%d\n,jname,size);intflag=0;//默认flag=0情况分配失败,而flag=1时分配成功intsum=0;//对sum的初始化for(inti=0;inumber&&flag==0;i++){//number为已定义的进程数量if(fqlist[i].flag!=1){//当某一分区不在使用时if(fqlist[i].capactitysize)//如果内存空间大于进程长度{if(inumber-1){//分配内存,已使用内存块增加for(intj=number-1;ji;j--){fqlist[j]=fqlist[j-1];}fqlist[i+1].name='n';fqlist[i+1].start=sum+size;fqlist[i+1].end=fqlist[i].end;fqlist[i+1].capactity=fqlist[i].capactity-size;fqlist[i+1].flag=fqlist[i].flag;}fqlist[i].name=jname;fqlist[i].start=sum;fqlist[i].end=sum+size-1;fqlist[i].capactity=size;fqlist[i].flag=1;fqNum++;//进程数目增1//需要把以后的分区块往后一个位置flag=1;}else{//当未使用的分区块大小不足时sum=sum+fqlist[i].capactity;}}else{//当该分区块在使用时sum=sum+fqlist[i].capactity;}}if(flag==1)printf(已为进程%c分配内存区!\n,jname);elseprintf(为进程%c分配内存区失败!\n,jname);return0;}//回收内存intMemory_recovery(){intflag=0;//标记回收是否成功0:失败1:成功intsflag=0;//inttflag=0;//charjname='z';getchar();//吸收空白键printf(请输入进程名称:);scanf(%c,&jname);for(inti=0;inumber;i++){if(fqlist[i].name==jname){fqlist[i].name='n';fqlist[i].flag=2;//表示为回收的内存区flag=1;fqNum--;}}if(flag==1)printf(进程%c结束,内存回收成功!\n,jname);elseprintf(进程%c无法结束,内存回收失败!\n,jname);//将连续的已回收的内存区合并while(flag3){for(i=0;inumber-1;i++){if(fqlist[i].flag==0||fqlist[i].flag==2){if(fqlist[i+1].flag!=1){if(fqlist[i+1].flag==3){fqlist[i].end=fqlist[i+1].end;fqlist[i].capactity=fqlist[i].capactity+fqlist[i+1].capactity;fqlist[i].flag=fqlist[i+1].flag;for(intj=i+1;jnumber-1;j++){fqlist[j]=fqlist[j+1];}i=number;flag++;}else{fqlist[i].end=fqlist[i+1].end;fqlist[i].capactity=fqlist[i].capactity+fqlist[i+1].capactity;fqlist[i].flag=fqlist[i+1].flag;for(intj=i+1;jnumber-1;j++){fqlist[j]=fqlist[j+1];}}}}}flag++;}return0;}//显示进程情况intshowit(){intcount=0;printf(进程名称开始位置结束位置进程大小状态\n);for(inti=0;inumber-1&&countfqNum;i++){printf(%5c%10d%12d%10d,fqlist[i].name,fqlist[i].start,fqlist[i].end,fqlist[i].capactity);if(fqlist[i].flag==1){printf(已使用\n);count++;}elseif(fqlist[i].flag==3){printf(尾部\n);count++;}elseif(fqlist[i].flag==2){printf(未使用\n);}elseif(fqlist[i].flag==0){printf(未使用\n);}}return0;}//退出intexit(){printf(按任意键退出.....\n);exit(0);return0;}//主函数intmain(){init_neicun();//初始化内存大小menu();return0;}