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

1、实验报告实验名称首次适应算法和循环首次适应算法【实验目的】理解在连续分区动态的存储管理方式下，如何实现主存空间的分配与回收。【实验原理】首次适应(firstfit,FF)算法FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区即可。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已经没有足够大的内存分配给该进程，内存分配失败，返回。循环首次适应(nextfit,NF)算法为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲

2、分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块玉请求大小相等的内存空间分配给作业。【实验内容】实现主存空间的分配与回收：1 .采用可变式分区管理，使用首次适应算法实现主存空间的分配与回收；2 .采用可变式分区管理，使用循环首次适应算法实现主存空间的分配与回收。数据结构和符号说明：typedefstructPCB/®程控制块(charProgressName10;/进程名称intStartaddress;intProgressSize;intProgress

3、State=0;)；typedefstructFREE(intFree_num;intStartaddress;intEndaddress;intFree_Space;);一/进程开始地址/进程大小/进程状态/空闲区结构体空闲区名称/空闲区开始地址/空闲区结束地址/空闲区大小算法流程图:首次适应算法厂-"开始循环首次适应算法/进程名称进程开始地址/进程大小/进程状态空闲区结构体程序代码及截图:#include<stdio.h>#include<string.h>#include<stdlib.h>#include<io.h>#defin

4、eN1024typedefstructPCB进程控制块charProgressName10;intStartaddress;intProgressSize;intProgressState=0;);typedefstructFREEintFree_num;intStartaddress;intEndaddress;intFree_Space;空闲区名称空闲区开始地址空闲区结束地址空闲区大小);intcount=0;/当前内存中进程个数boolROMN;/设置内存块intp=0;/循环首次使用需要标记当前的空闲区块FREEFREE100;/设置空闲区数组为100个intFREE_counter=

5、0;/空闲区的个数PCBnum20;作业队列voidinit()/初始化操作for(inti=0;i<N;i+)ROMi=0;voidshowProgress(PCB&a)printf("n");printf("进程名tt开始地址tt大小tt结束地址n");输出内存信息printf("n");for(inti=0;i<count-1;i+)for(intj=i;j<count-1;j+)if(numj.Startaddress>numj+1.Startaddress)a=numj;numj=numj+1

6、;numj+1=a;for(inti=0;i<count;i+)if(numi.ProgressState!=0)printf("%stt%dttt%dtt%dttn",numi.ProgressName,numi.Startaddress,numi.ProgressSize,numi.ProgressSize+numi.Startaddress-1);printf("n");voidshowFree()打印空闲区的情况printf("n");printf("空闲区名t|开始地址t|大小t|结束地址n");p

7、rintf("n");for(inti=1;i<=FREE_counter;i+)printf("t%1dt%8dt%11dt%dn",FREEi.Free_num,FREEi.Startaddress,FREEi.Free_Space,FREEi.Endaddress);printf("n");)voidfind_FREE()寻找空闲区(inti,j,p;/计数值FREE_counter=0;/预设空闲区数为0for(i=0;i<N;i+)if(ROMi=0)(p=i;for(j=i;j<N;j+)(if(ROMj

8、=0)/未找到空闲区，则将j赋值给i后继续循环(i=j;continue;)if(ROMj=1)/找到空闲区(FREE_counter+;/空闲区个数+1;FREEFREE_counter.Free_num=FREE_counter;/设置空闲区编号FREEFREE_counter.Startaddress=p;FREEFREE_counter.Endaddress=j-1;FREEFREE_counter.Free_Space=j-p;i=j+1;break;)if(j=N&&ROMj-1=0)/对最后一个内存进行特殊操作(FREE_counter+;FREEFREE_cou

9、nter.Free_num=FREE_counter;/对空闲区进行处理FREEFREE_counter.Startaddress=p;FREEFREE_counter.Endaddress=j-1;FREEFREE_counter.Free_Space=j-p;)voidFirst_Fit(PCB&a)/首次适应算法inti,j,k;for(i=0;i<N;i+)if(ROMi=0)(for(j=i;j<=(i+a.ProgressSize)&&j<N;j+)查询第一个空闲区，并判断是否适合插入作业if(ROMj=1)(i=j+1;break;if(

10、j=i+a.ProgressSize+1)(a.Startaddress=i;/设置作业的开始地址a.ProgressState=1;/标记作业在内存中for(k=i;k<i+a.ProgressSize&&j<N;k+)ROMk=1;printf("进程s插入成功，进程s的初始地址为d,结束地址%dn",a.ProgressName,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1);return;if(i=N)/未查询到合适的区域printf("插入失败，无可

11、用空间！n");voidNext_Fit(PCB&a)/循环首次适应算法来实现作业调度(inti,j,k;for(i=p;i<N;i+)/从所标记的当前区域开始查询，查询到末内存(if(ROMi=0)(for(j=i;j<=(i+a.ProgressSize)&&j<N;j+)if(ROMj=1)(i=j+1;break;if(j=i+a.ProgressSize+1)/找到合适的空闲区(a.Startaddress=i;a.ProgressState=1;for(k=i;k<i+a.ProgressSize&&j<

12、;N;k+)ROMk=1;printf("插入成功，进程s的初始地址为d,结束地址/%dn",a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1);p=i+a.ProgressSize;return;for(i=0;i<p;i+)/当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的Pif(ROMi=0)for(j=i;j<=(i+a.ProgressSize)&&j<p;j+)if(ROMj=1)i=j+1;break;if(j=i+a.ProgressSize

13、+1)/成功找到结束，并标记当前P为现在的作业的尾部a.Startaddress=i;a.ProgressState=1;for(k=i;k<i+a.ProgressSize&&j<p;k+)ROMk=1;printf("插入成功，进程s的初始地址/%dn",a.ProgressName,a.Startaddress);p=i+a.ProgressSize;break;if(i=p)查询两部分都未找到合适的区域，输出插入失败语句printf("插入失败，无可用空间n");voidDelete(PCB&a)删除作业，修改

14、内存信息和初始化该作业信息inti;for(i=a.Startaddress;i<a.Startaddress+a.ProgressSize;i+)ROMi=0;a.ProgressState=0;/l犬态标记为未使用printf("进程$删除成功n",a.ProgressName);intmain()(intchoose1,choose;charProgressName10;PCBa;init();printf("t主存空间的分配与回收n");printf("n");printf("t1、首次适应算法n")

15、;printf("t2、循环首次适应算法n");printf("n");printf("请选择分配算法：");scanf("%d",&choose1);system("cls");while(1)(w:system("cls");printf("当前分配算法：")；if(choose1=1)printf("首次适应算法n");elseprintf("循环首次适应算法n");printf("n&quo

16、t;);printf("t1、插入进程n");printf("t2、删除进程n");printf("t3、显示进程的信息n");printf("t4、显示空闲区n");printf("n");printf("请输入：");scanf("%d",&choose);system("cls");switch(choose)(case 1:printf("请输入进程名：")；scanf("%s",

17、&a.ProgressName);printf("请输入进程的大小：");scanf("%d",&a.ProgressSize);for(inti=0;i<count;i+)if(strcmp(numi.ProgressName,a.ProgressName)=0)printf("已存在同名进程，无法插入。n");system("pause");gotow;)if(choose1=1)/首次适应算法First_Fit(a);elseNext_Fit(a);/循环首次适应算法numcount+=

18、a;break;case 2:if(count=0)(printf("当前没有进程在内存中，无法删除！n");system("pause");gotow;)printf("输入删除的进程名字：");scanf("%s",&ProgressName);for(inti=0;i<count;i+)if(!strcmp(numi.ProgressName,ProgressName)Delete(numi);elseprintf("没有找到对应进程，请重新输入。n");break;case 3:showPr