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

*** 实验报告 【实验名称】 【实验目的】 理解在连续分区动态的存储管理方式下，如何实现主存空间的分配与回收。 首次适应算法和循环首次适应算法 【实验原理】 首次适应（ first fit ，FF）算法 FF 算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开 始顺序查找， 直至找到一个大小能满足要求的空闲分区即可。然后再按照作业的 大小，从该分区中划出一块内存空间，分配给请求者， 余下的空闲分区仍留在空 闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表明系统中已 经没有足够大的内存分配给该进程，内存分配失败，返回。 循环首次适应（ next fit，NF）算法 为避免低址部分留下许多很小的空闲分区，以及减少查找可用空闲分区的开 销，循环首次适应算法在为进程分配内存空间时， 不再是每次都从链首开始查找， 而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要 求的空闲分区，从中划出一块玉请求大小相等的内存空间分配给作业。 【实验内容】 实现主存空间的分配与回收 1. 采用可变式分区管理，使用首次适应算法实现主存空间的分配与回收； 2. 采用可变式分区管理，使用循环首次适应算法实现主存空间的分配与回 收。 数据结构和符号说明 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; }; 算法流程图 //进程开始地址 //进程大小 //进程状态 //空闲区结构体 //空闲区名称 //空闲区开始地址 //空闲区结束地址 //空闲区大小 首次适应算法 开始 空闲区登记 插入作业 空闲区指针指向第 一个空闲区 空闲区指针指向下 一个空闲区 否 是否为最后一 个空闲区 当前空闲区是 否满足要求 否 是 是是 插入作业，修改内 插入失败 表 存信息和作业信息 是否继续插 入 否 结束 *** *** 循环首次适应算法 *** *** 开始 空闲区登记 是否为最后一 个空闲区 否 空闲区指针指向第 一个空闲区 是 空闲区指针指向 第一个空闲区， 标记当前空闲区 P 空闲区指针加一 是否小于所标 记的空闲区 P 否 是 插入作业 否 当前空闲区是 否满足 是 当前指针所指 向区域是否满 足 否 是 否 当前空闲区是 否 否满足 是 空闲区指针指向下 一个空闲区 插入当前作业，修 改内存信息和作业 信息表信息 空闲区指针指向下 一个空闲区，标记 当前空闲区 P 是 继续插入作业插入失败 输出信息 结束 程序代码及截图 include include include include 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// 初始化操作 { forint i0; iN; i ROM[i] 0; } void showProgressPCB printf“ 进程名 \t\t 开始地址 \t\t 大小\t\t 结束地址 \n“;// 输出内存信息 printf“----------------------------------------------------------------------\n“; forint i0; icount-1; i forint ji; jnum[j1].Startaddress { a num[j]; num[j] num[j1]; num[j1] a; } forint i0; icount; i ifnum[i].ProgressState0 printf“s\t\td\t\t\td\t\td\t\t\n“,num[i].ProgressName,num[i].Startaddress,num[i].ProgressSiz e,num[i].ProgressSizenum[i].Startaddress-1; printf“----------------------------------------------------------------------\n“; } void showFree// 打印空闲区的情况 { printf“----------------------------------------------------------------------\n“; printf“空闲区名 \t|开始地址 \t|大小\t|结束地址 \n“; printf“----------------------------------------------------------------------\n“; for int i1; i FREE_counter; i { printf“\t1d\t8d\t11d\t FREE[i].Free_Space,FREE[i].Endaddress; printf“----------------------------------------------------------------------\n“; d\n“,FREE[i].Free_num,FREE[i].Startaddress, *** *** } } void find_FREE { int i,j,p;//计数值 FREE_counter 0;// 预设空闲区数为0 fori 0; i N; i ifROM[i] 0 { p i; forj i; j N; j { ifROM[j]0//未找到空闲区，则将j 赋值给 i 后继续循环