操作系统实验四主存空间的分配与回收

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

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

3、ze;int ProgressState = 0;；typedef struct FREEint Free_ num;int Startaddress;int En daddress;int Free_Space; 一/进程开始地址/进程大小/进程状态/空闲区结构体/空闲区名称空闲区开始地址/空闲区结束地址/空闲区大小否空闲区指针指向下 一个空闲区否是否为最后一个空闲区?开始1空闲区登记1F插入作业F空闲区指一个空针指向第:闲区首次适应算法f前空闲区是否满足要求?插入失败插入作业，修改内 存信息和作业信息表是结束循环首次适应算法算法流程图:开始程序代码及截图:#in clude#in clud

4、e#in elude #i nclude #defi ne N 1024typedef struct PCB 进程控制块 char ProgressName10;int Startaddress;int ProgressSize;int ProgressState = 0; ;typedef struct FREEint Free_ num;int Startaddress;int En daddress;int Free_Space;/进程名称进程开始地址/进程大小/进程状态/空闲区结构体/空闲区名称/空闲区开始地址/空闲区结束地址/空闲区大小;int count = 0; /当前内存中进程

5、个数bool ROMN;设置内存块int p = 0;/循环首次使用需要标记当前的空闲区块FREE FREE100;设置空闲区数组为 100个int FREE_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(i nt i=0; ico un t-1; i+)for(i nt j=i; jnu mj+1.Star

6、taddress)a = nu mj;nu mj = nu mj+1;nu mj+1 = a;for(i nt i=0; ico unt; i+)if(nu mi. ProgressState!=0)prin tf(%stt%dttt%dtt%dtt n, numi.ProgressName ,n umi.Startaddress, nu mi.ProgressSiz e,nu mi.ProgressSize+nu mi.Startaddress-1);printf(”n);void showFree()/打印空闲区的情况printf(”n);printf(空闲区名t|开始地址t|大小 t|结

7、束地址n);printf(”n);for (int i=1; i= FREE_co un ter; i+)prin tf(t%1dt%8dt%11dt%dn,FREEi.Free_num,FREEi.Startaddress,FREEi.Free_Space,FREEi.E ndaddress);printf(”n ”)；void fin d_FREE()寻找空闲区int i,j,p;计数值FREE_cou nter = 0;/预设空闲区数为 0for(i = 0; i N; i+)if(ROMi = 0)p = i;for(j = i; j N; j+)if(ROMj=0)/未找到空闲区，则

8、将 j赋值给i后继续循环i = j;con ti nue;if(ROMj=1)/找到空闲区FREE_counter+; 空闲区个数 +1 ；FREEFREE_counter.Free_num = FREE_counter;/ 设置空闲区编号FREEFREE_cou nter.Startaddress = p;FREEFREE_cou nter.E ndaddress = j-1;FREEFREE_co un ter.Free_Space = j-p;i=j+1;break;if(j = N & ROMj-1 = 0)/对最后一个内存进行特殊操作FREE_co un ter+;FREE FREE

9、_counter.Free_num = FREE_counter;/ 对空闲区进行处理FREE FREE_cou nter.Startaddress = p;FREE FREE_cou nter.E ndaddress =j-1;FREE FREE_co un ter.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;brea

10、k;if(j=i+a.ProgressSize+1)a.Startaddress = i;设置作业的开始地址a.ProgressState = 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_Fi

11、t(PCB &a)/循环首次适应算法来实现作业调度int i,j,k;for(i=p; iN; 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; ki+a.ProgressSize&jN; k+)R0Mk=1;printf(”插入成功，进程%s的初始地址为d,结束地址为 dn ,a.Progress

12、Name,a.Startaddress,a.Startaddress+a.ProgressSize-1);p=i+a.ProgressSize;return;for(i=0; ip; i+)/当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的Pif(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.Progress

13、Size&jp; k+)ROMk=1;printf(”插入成功，进程 %s 的初始地址为 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=O;a.ProgressState=0;/状态标记为未使用printf(进程

14、 %s 删除成功 n,a.ProgressName);int mai n()int choose1,choose;char ProgressName10;PCB a;ini t();printf(t主存空间的分配与回收n);printf(”-n ”);printf(t1、首次适应算法n);printf(t2、循环首次适应算法n);printf(-n ”);printf(请选择分配算法：”)；scan f(%d,&choose1);system(cls);while(1)w:system(cls);printf(当前分配算法：);if(choose1 = 1)printf(首次适应算法n);el

15、seprintf(循环首次适应算法n);printf(n);printf(t1、插入进程 n);printf(t2、删除进程 n);printf(t3、显示进程的信息n);printf(t4、显示空闲区 n);printf(n);printf(请输入:);scan f(%d, &choose);system(cls);switch(choose)case 1:printf(请输入进程名:);scan f(%s, &a.P rogressName);printf(请输入进程的大小：);scan f(%d,&a.P rogressSize);for(i nt i = 0; i count; i+)

16、if(strcmp( nu mi.ProgressName,a.ProgressName)=0) printf(已存在同名进程，无法插入。n);system(pause);goto w;if(choose仁=1)/首次适应算法First_Fit(a);elseNext_Fit(a);循环首次适应算法nu mco un t+=a;break;case 2:if(co unt = 0)printf(当前没有进程在内存中，无法删除！n);system(pause);goto w;printf(输入删除的进程名字：);scan f(%s,&ProgressName);for(i nt i=0; ico unt; i+)if(!strcmp( nu mi .P rogressName,ProgressName) Delete( nu mi);elseprintf(”没有找到对应进程，请重新输入。n);break;case 3:showProgress(a);break;case 4:fin d_FREE();showFree();break;default:printf(n 无效的输入。n”);system(pause);return 0;主界面:首次适应算法，初始空闲区:插入进程:E;l启如=1I