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

实验报告 【实验名称】 首次适应算法和循环首次适应算法 【实验目的】 理解在连续分区动态的存储管理方式下，如何实现主存空间的分配与回收。 【实验原理】 首次适应（first fit，FF）算法 FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区即可。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已经没有足够大的内存分配给该进程，内存分配失败，返回。 循环首次适应（next fit，NF）算法 为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开销，循环首次适应算法在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块玉请求大小相等的内存空间分配给作业。 【实验内容】 实现主存空间的分配与回收： 采用可变式分区管理，使用首次适应算法实现主存空间的分配与回收； 采用可变式分区管理，使用循环首次适应算法实现主存空间的分配与回收。 数据结构和符号说明： typedef struct PCB//进程控制块 { char ProgressName[10]; //进程名称 int Startaddress; //进程开始地址 int ProgressSize; //进程大小 int ProgressState = 0; //进程状态 }; typedef struct FREE //空闲区结构体 { int Free_num; //空闲区名称 int Startaddress; //空闲区开始地址 int Endaddress; //空闲区结束地址 int Free_Space; //空闲区大小 }; 算法流程图： 首次适应算法 循环首次适应算法 程序代码及截图： #includestdio.h #includestring.h #include stdlib.h #include io.h #define N 1024 typedef struct PCB//进程控制块 { char ProgressName[10]; //进程名称 int Startaddress; //进程开始地址 int ProgressSize; //进程大小 int ProgressState = 0; //进程状态 }; typedef struct FREE //空闲区结构体 { int Free_num; //空闲区名称 int Startaddress; //空闲区开始地址 int Endaddress; //空闲区结束地址 int Free_Space; //空闲区大小 }; int count = 0; //当前内存中进程个数 bool ROM[N];//设置内存块 int p = 0;//循环首次使用需要标记当前的空闲区块 FREE FREE[100];//设置空闲区数组为100个 int FREE_counter = 0;//空闲区的个数 PCB num[20]; //作业队列 void init()//初始化操作 { for(int i=0; iN; i++) ROM[i] = 0; } void showProgress(PCB a) { printf(----------------------------------------------------------------------\n); printf(进程名\t\t开始地址\t\t大小\t\t结束地址\n);//输出内存信息 printf(----------------------------------------------------------------------\n); for(int i=0; icount-1; i++) for(int j=i; jcount-1; j++) if(num[j].Startaddressnum[j+1].Startaddress) {