《操作系统实验四 主存空间的分配与回收-首次适应算法和循环首次适应算法》由会员分享，可在线阅读，更多相关《操作系统实验四 主存空间的分配与回收-首次适应算法和循环首次适应算法（12页珍藏版）》请在金锄头文库上搜索。
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.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); retu
