实验报告
【实验名称】
首次适应算法和循环首次适应算法
【实验目的】
理解在连续分区动态的存储管理方式下，如何实现主存空间的分配与回收。
【实验原理】
首次适应（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;
//空闲区大小
};
算法流程图：
首次适应算法
循环首次适应算法
程序代码及截图：
#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;
i i++) ROM[i] = 0; } void showProgress(PCB &a) { printf(“----------------------------------------------------------------------＼n“); printf(“进程名＼t＼t开始地址＼t＼t大小＼t＼t结束地址＼n“);//输出内存信息 printf(“----------------------------------------------------------------------＼n“); for(int i=0; i i++) for(int j=i; j j++) if(num[j].Startaddress>num[j+1].Startaddress) { a = num[j]; num[j] = num[j+1]; num[j+1] = a; } for(int i=0; i i++) if(num[i].ProgressState!=0) printf(“%s＼t＼t%d＼t＼t＼t%d＼t＼t%d＼t＼t＼n“,num[i].ProgressName,num[i].Startaddress,num[i].ProgressSize,num[i].ProgressSize+num[i].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%1d＼t%8d＼t%11d＼t %d＼n“,FREE[i].Free_num,FREE[i].Startaddress,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 i++) if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j j++)//查询第一个空闲区，并判断是否适合插入作业 if(ROM[j]==1) { i = j + 1; break; } if(j==i+a.ProgressSize+1) { a.Startaddress = i;//设置作业的开始地址 a.ProgressState = 1;//标记作业在内存中 for(k=i; k k++) ROM[k]=1; printf(“进程%s插入成功，进程%s的初始地址为%d,结束地址为%d＼n“,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 i++)//从所标记的当前区域开始查询，查询到末内存 { if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j j++) if(ROM[j]==1) { i = j+1; break; } if(j==i+a.ProgressSize+1)//找到合适的空闲区 { a.Startaddress=i; a.ProgressState=1; for(k=i; k k++) ROM[k]=1; printf(“插入成功，进程%s的初始地址为%d,结束地址为%d＼n“,a.ProgressName,a.Startaddress,a.Startaddress+a.ProgressSize-1); p=i+a.ProgressSize; return; } } } for(i=0; i i++)//当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的P if(ROM[i]==0) { for(j=i; j<=(i+a.ProgressSize)&&j j++) if(ROM[j]==1) { i=j+1; break; } if(j==i+a.ProgressSize+1)//成功找到结束，并标记当前P为现在的作业的尾部 { a.Startaddress=i; a.ProgressState=1; for(k=i; k ROM[k]=1; printf(“插入成功，进程%s的初始地址为%d＼n“,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 i++) ROM[i]=0; a.ProgressState=0;//状态标记为未使用 printf(“进程%s删除成功＼n“,a.ProgressName); } int main() { int choose1,choose; char ProgressName[10]; PCB a; init(); printf(“＼t主存空间的分配与回收＼n“); printf(“---------------------------------------＼n“); printf(“＼t1、首次适应算法＼n“); printf(“＼t2、循环首次适应算法＼n“); printf(“---------------------------------------＼n“); printf(“请选择分配算法：“); scanf(“%d“,&choose1); system(“cls“); while(1) { w:system(“cls“); printf(“当前分配算法：“); if(choose1 == 1) printf(“首次适应算法＼n“); else printf(“循环首次适应算法＼n“); printf(“---------------------------------------＼n“); printf(“＼t1、插入进程＼n“); printf(“＼t2、删除进程＼n“); printf(“＼t3、显示进程的信息＼n“); 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 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“,&ProgressName); for(int i=0; i i++) if(!strcmp(num[i].ProgressName,ProgressName)) Delete(num[i]); else printf(“没有找到对应进程，请重新输入。＼n“); break; case 3: showProgress(a); break; case 4: find_FREE(); showFree(); break; default: printf(“＼n无效的输入。＼n“); } system(“pause“); } return 0; } 主界面： 首次适应算法，初始空闲区： 插入进程： 插入3个进程： 空闲区信息： 删除进程2： 删除后空闲区状况： 再插入一个进程，可以看到其其初始地址为100： 循环首次适应算法,插入3个进程 删除进程2后： 再插入进程A，发现其从上次找到的空闲分区的下一个空闲分区开始查找，其初始地址为750而不是200：
点击咨询