实验报告

　【实验名称】

　 首次适应算法和循环首次适应算法

　 【实验目的】 理解在连续分区动态的存储管理方式下，如何实现主存空间的分配与回收。

　【实验原理】 首次适应（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<stdio.h> #include<string.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; i<N; 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<count-1; i++)

　 for(int j=i; j<count-1; 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<count; 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<N; i++)

　 if(ROM[i]==0)

　 {

　 for(j=i; j<=(i+a.ProgressSize)&&j<N; 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<i+a.ProgressSize&&j<N; 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<N; i++)//从所标记的当前区域开始查询，查询到末内存

　 {

　 if(ROM[i]==0)

　 {

　 for(j=i; j<=(i+a.ProgressSize)&&j<N; 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<i+a.ProgressSize&&j<N; 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<p; i++)//当未找到时，从第一个空闲区开始查询，结束条件为小于所标记的P

　 if(ROM[i]==0)

　 {

　for(j=i; j<=(i+a.ProgressSize)&&j<p; 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<i+a.ProgressSize&&j<p; 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<a.Startaddress+a.ProgressSize; 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<count; 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：