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

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

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

3、Size; /进程大小 int ProgressState = 0; /进程状态;typedef struct FREE /空闲区结构体 int Free_num; /空闲区名称 int Startaddress; /空闲区开始地址 int Endaddress; /空闲区结束地址 int Free_Space; /空闲区大小;算法流程图：首次适应算法循环首次适应算法程序代码及截图：#include#include#include #include #define N 1024typedef struct PCB/进程控制块 char ProgressName10; /进程名称 int Sta

4、rtaddress; /进程开始地址 int ProgressSize; /进程大小 int ProgressState = 0; /进程状态;typedef struct FREE /空闲区结构体 int Free_num; /空闲区名称 int Startaddress; /空闲区开始地址 int Endaddress; /空闲区结束地址 int Free_Space; /空闲区大小;int count = 0; /当前内存中进程个数bool ROMN;/设置内存块int p = 0;/循环首次使用需要标记当前的空闲区块FREE FREE100;/设置空闲区数组为100个int FREE_

5、counter = 0;/空闲区的个数PCB num20; /作业队列void init()/初始化操作 for(int i=0; iN; i+) ROMi = 0;void showProgress(PCB &a) printf(-n); printf(进程名tt开始地址tt大小tt结束地址n);/输出内存信息 printf(-n); for(int i=0; icount-1; i+) for(int j=i; jnumj+1.Startaddress) a = numj; numj = numj+1; numj+1 = a; for(int i=0; icount; i+) if(num

6、i.ProgressState!=0) printf(%stt%dttt%dtt%dttn,numi.ProgressName,numi.Startaddress,numi.ProgressSize,numi.ProgressSize+numi.Startaddress-1); printf(-n);void showFree()/打印空闲区的情况 printf(-n); printf( 空闲区名t| 开始地址t| 大小 t| 结束地址n); printf(-n); for (int i=1; i= FREE_counter; i+) printf(t%1dt%8dt%11dt %dn,FRE

7、Ei.Free_num,FREEi.Startaddress, FREEi.Free_Space,FREEi.Endaddress); printf(-n); void find_FREE() /寻找空闲区 int i,j,p; /计数值 FREE_counter = 0;/预设空闲区数为0 for(i = 0; i N; i+) if(ROMi = 0) p = i; for(j = i; j N; j+) if(ROMj=0)/未找到空闲区，则将j赋值给i后继续循环 i = j; continue; if(ROMj=1)/找到空闲区 FREE_counter+;/空闲区个数+1； FREE

8、FREE_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+; FREE FREE_counter.Free_num = FREE_counter;/对空闲区进行处理 FREE FREE_counter.Startaddress

9、= p; FREE FREE_counter.Endaddress =j-1; FREE FREE_counter.Free_Space = j-p; void First_Fit(PCB &a)/首次适应算法 int i,j,k; for(i=0; iN; i+) if(ROMi=0) for(j=i; j=(i+a.ProgressSize)&jN; j+)/查询第一个空闲区，并判断是否适合插入作业 if(ROMj=1) i = j + 1; break; if(j=i+a.ProgressSize+1) a.Startaddress = i;/设置作业的开始地址 a.ProgressSt

10、ate = 1;/标记作业在内存中 for(k=i; ki+a.ProgressSize&jN; k+) ROMk=1; printf(进程%s插入成功，进程%s的初始地址为%d,结束地址为%dn,a.ProgressName,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1); return; if(i=N)/未查询到合适的区域 printf(插入失败，无可用空间！n);void Next_Fit(PCB &a)/循环首次适应算法来实现作业调度 int i,j,k; for(i=p; iN; i+)/从所标记的当前区域

11、开始查询，查询到末内存 if(ROMi=0) for(j=i; j=(i+a.ProgressSize)&jN; j+) if(ROMj=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+) ROMk=1; printf(插入成功，进程%s 的初始地址为%d,结束地址为%dn,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1);

12、 p=i+a.ProgressSize; return; for(i=0; ip; i+)/当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的P if(ROMi=0) for(j=i; j=(i+a.ProgressSize)&jp; j+) if(ROMj=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+) ROMk=1; printf(插入成功，进程%s 的初始地

13、址为%dn,a.ProgressName,a.Startaddress); p=i+a.ProgressSize; break; if(i=p)/查询两部分都未找到合适的区域，输出插入失败语句 printf(插入失败，无可用空间n);void Delete(PCB &a)/删除作业，修改内存信息和初始化该作业信息 int i; for(i=a.Startaddress; ia.Startaddress+a.ProgressSize; i+) ROMi=0; a.ProgressState=0;/状态标记为未使用 printf(进程%s删除成功n,a.ProgressName);int main

14、() int choose1,choose; char ProgressName10; PCB a; 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); else printf(循环首次适应算法n); prin

15、tf(-n); 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,&a.ProgressName); printf(请输入进程的大小：); scanf(%d,&a.ProgressSize); for(int i = 0; i count; i+) if(strcmp(numi.Pr

16、ogressName,a.ProgressName)=0) printf(已存在同名进程，无法插入。n); system(pause); goto w; if(choose1=1)/首次适应算法 First_Fit(a); else Next_Fit(a);/循环首次适应算法 numcount+=a; break; case 2: if(count = 0) printf(当前没有进程在内存中，无法删除！n); system(pause); goto w; printf(输入删除的进程名字：); scanf(%s,&ProgressName); for(int i=0; icount; i+) if(!strcmp(numi.ProgressName,ProgressName) Delete(numi); else printf(没有找到对应进程，请重新输入。n); break; case 3: sh