.
实验报告
【实验名称】 【实验目的】
理解在连续分区动态的存储管理方式下，如何实现主存空间的分配与回收。
首次适应算法和循环首次适应算法
【实验原理】
首次适应（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()//初始化操作 { for(int i=0; inum[j+1].Startaddress) { a = num[j]; num[j] = num[j+1]; num[j+1] = a; } for(int i=0; i.printf(\" 空闲区名\| 开始地址\| 大小 \| 结束地址\\n\"); printf(\"----------------------------------------------------------------------\\n\"); for (int i=1; i<= FREE_counter; i++) { printf(\"\%1d\%8d\%11d\ %d\\n\FREE[i].Free_Space,FREE[i].Endaddress); printf(\"----------------------------------------------------------------------\\n\"); } } void find_FREE() //寻找空闲区 { int i,j,p; //计数值 FREE_counter = 0;//预设空闲区数为0 for(i = 0; i < N; i++) if(ROM[i] == 0) { p = i; for(j = i; j < N; j++) { if(ROM[j]==0)//未找到空闲区，则将j赋值给i后继续循环 { i = j; continue; } if(ROM[j]==1)//找到空闲区 { FREE_counter++;//空闲区个数+1； 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; i=j+1; break; } } if(j == N && ROM[j-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_Fit(PCB &a)//首次适应算法 { int i,j,k; for(i=0; i.{ if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j.} } if(i==p)//查询两部分都未找到合适的区域，输出插入失败语句 printf(\"插入失败，无可用空间\\n\"); } void Delete(PCB &a)//删除作业，修改内存信息和初始化该作业信息 { int i; for(i=a.Startaddress; i.printf(\"请输入：\"); scanf(\"%d\ system(\"cls\"); switch(choose) { case 1: printf(\"请输入进程名:\"); scanf(\"%s\ printf(\"请输入进程的大小：\"); scanf(\"%d\ for(int i = 0; i < count; i++) if(strcmp(num[i].ProgressName,a.ProgressName)==0) { printf(\"已存在同名进程，无法插入。\\n\"); system(\"pause\"); goto w; } if(choose1==1)//首次适应算法 First_Fit(a); else Next_Fit(a);//循环首次适应算法 num[count++]=a; break; case 2: if(count == 0) { printf(\"当前没有进程在内存中，无法删除！\\n\"); system(\"pause\"); goto w; } printf(\"输入删除的进程名字：\"); scanf(\"%s\ for(int i=0; i.break; default: printf(\"\\n无效的输入。\\n\"); } system(\"pause\"); } return 0; }
主界面：
首次适应算法，初始空闲区：
插入进程：
.
.
插入3个进程：
空闲区信息：
删除进程2：
删除后空闲区状况：
.
.
再插入一个进程，可以看到其其初始地址为100：
循环首次适应算法,插入3个进程
删除进程2后：
.
.
再插入进程A，发现其从上次找到的空闲分区的下一个空闲分区开始查找，其初始地址为750而不是200：
.
