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

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

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

3、rogressSize;int ProgressState = 0;；typedef struct FREE(int Free_num;int Startaddress;int Endaddress;int Free_Space;一进程开始地址进程大小进程状态空闲区结构体空闲区名称空闲区开始地址空闲区结束地址空闲区大小算法流程图:首次适应算法循环首次适应算法开始/进程名称进程开始地址/进程大小/进程状态空闲区结构体空闲区名称空闲区开始地址空闲区结束地址空闲区大小程序代码及截图:#include<stdio.h>#include<string.h>#include <

4、;stdlib.h> #include <io.h>#define N 1024typedef struct PCB/ 进程限制块char ProgressName10;int Startaddress;int ProgressSize;int ProgressState = 0;typedef struct FREEint Free_num;int Startaddress;int Endaddress;int Free_Space;int count = 0; /当前内存中进程个数bool ROMN;/设置内存块int p = 0;/循环首次使用需要标记当前的空闲区块FR

5、EE FREE100;/设置空闲区数组为100个int FREE_counter = 0;/ 空闲区的个数PCB num20;作业队列void init()/初始化操作 for(int i=0; i<N; i+) ROMi = 0; void showProgress(PCB &a) printf("n");printf("进程名tt开始地址tt大小tt结束地址n");/输出内存信息 printf("n");for(int i=0; i<count-1; i+) for(int j=i; j<count-1;

6、 j+) if(numj.Startaddress>numj+1.Startaddress) a = numj; numj = numj+1; numj+1 = a; for(int i=0; i<count; i+) if(numi.ProgressState!=0)printf("%stt%dttt%dtt%dttn,numi.ProgressName,numi.Startaddress,numi.ProgressSiz e,numi.ProgressSize+numi.Startaddress-1); printf("n");void showF

7、ree()/打印空闲区的情况 printf("n");printf(" 空闲区名t|开始地址t| 大小 t| 结束地址n");printf("n");for (int i=1; i<= FREE_counter; i+) printf("t%1dt%8dt%11dt%dn",FREEi.Free_num,FREEi.Startaddress,FREEi.Free_Space,FREEi.Endaddress); printf("n");void find_FREE()/寻找空闲区(int

8、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;FREEFREE_counter.Free_num = FREE_counter;/ 设置空闲区编号 FREEFREE_counter.Startaddress = p;FREEFREE_coun

9、ter.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 = p;FREE FREE_counter.Endaddress =j-1; FREE FREE_counter.Free_Space = j-p; void First_

10、Fit(PCB &a)/ 首次适应算法 int i,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(j=i+a.ProgressSize+1)(a.Startaddress = i;/设置作业的开始地址 a.ProgressState = 1;/标记作业在内存中 for(k=i; k<i+a.ProgressSize&&j&l

11、t;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("插入失败,无可用空间！ n");void Next_Fit(PCB &a)/循环首次适应算法来实现作业调度(int i,j,k;for(i=p; i<N; i+)/从所标记的当前区域开始查询,查询到末内存(if(ROMi=0

12、)(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<N; k+)ROMk=1;printf("插入成功,进程s的初始地址为d,结束地址 为 dn,a.ProgressName,a.Startaddress,a.Startaddress+a.Pr

13、ogressSize-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+1)/成功找到结束,并标记当前P为现在的作业的尾部a.Startaddress=i;a.ProgressState=1;for(k=i; k<i+a.ProgressSize&&

14、;j<p; 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; i<a.Startaddress+a.ProgressSize; i+)ROMi=0;a.Pr

15、ogressState=0;/l犬态标记为未使用printf("进程 %s 删除成功 n",a.ProgressName);int main()(int choose1,choose;char ProgressName10;PCB a;init();printf("t主存空间的分配与回收n");printf("n");printf("t1、首次适应算法n");printf("t2、循环首次适应算法n");printf("n");printf(-请选择分配算法：");

16、scanf("%d,&choose1);system("cls");while(1)(w:system("cls");printf(-当前分配算法:");if(choose1 = 1)printf("首次适应算法n");elseprintf("循环首次适应算法n");printf("n");printf("t1、插入进程 n");printf("t2、删除进程 n");printf("t3、显示进程的信息n"

17、);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 <

18、; count; i+)if(strcmp(numi.ProgressName,a.ProgressName)=0) (printf("已存在同名进程,无法插入.n");system("pause");goto w;if(choose1=1)/首次适应算法First_Fit(a);elseNext_Fit(a);/循环首次适应算法 numcount+=a;break;case 2:if(count = 0)(printf("当前没有进程在内存中,无法删除！n");system("pause");goto w;printf(-输入删除的进程名字：");scanf("%s,&ProgressName);for(int i=0; i<count; i+)if(!strcmp(numi.ProgressName,ProgressName) Delete(numi);elseprintf(-没有找到对应进程,请重新输入.n");break;case 3:showProgress(a);break;case 4:find_FREE();showFree();break;default:printf("n 无效的输入.n"