操作系统-在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。

实验五
一、实验题目
在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。
二、实验内容
可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：

为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：

其中，起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。
上述的这张说明表的登记情况是按提示（1）中的例所装入的三个作业占用的主存区域后填写的。

(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。
(3) 采用最先适应算法（顺序分配算法）分配主存空间。
按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图4-1。
(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示（1）中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图4-2。
(5) 请按最先适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存；然后作业3撤离；再作业2撤离。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。
三、实验过程
1、实验原理
最先适应算法分配主存空间是按照作业的需要量，查空闲分区表，顺序查看长度栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分在空闲分区表中仍为空闲区。
当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲分区表中。
2、数据结构
作业进入内存：
根据作业大小，使用最先适应算法，从低地址空闲分区中依次判断是否有满足作业大小的空闲分区，若有则分配内存，修改空闲分区表，若无则不分配内存，提示没有合适空间，最后都输出空闲分区表情况。
作业撤出内存：
根据作业起始地址和大小，判断该作业上下是否相邻空闲分区，若只有上邻空闲分区，则释放内存后与其上邻空闲分区合并，若只有下邻空闲分区，则释放内存后与其下邻空闲分区合并，若上下都相邻空闲分区，则释放内存后与其上、下邻空闲分区都合并，若不相邻空闲分区，则释放内存后在空闲分区表内单独形成一个分区，最后输出空闲分区表情况。
3、算法设计
struct free
{
int start; ///空闲分区始址
int size; ///空闲分区长度
int state; ///标志位,1表示未分配,0表示分空表目
};
free free[N]={{14,12,1},{32,96,1},{128,120,0}};///初始化空闲分区

void setfree(int start,int size)
{
int flag1=0,flag2=0,flag3=0; ///flag1:表示回收区是否有下邻空闲区; flag2:表示回收区是否有上下邻空闲区; flag3:表示回收区是否有上邻空闲区;
int i,j;
for(i=0;i<N;i++)
{
if(free[i].start= =start+size && free[i].state= =1) ///回收区有下邻空闲区
{
size=size+free[i].size; ///向下合并空闲区
flag1=1;
for(j=0;j<N;j++)
if(free[j].start+free[j].size= =start && free[j].state= =1)
{
free[i].state=0;
free[i].start=free[N-1].start+free[N-1].size;
free[i].size=120;
free[j].size=free[j].size+size; ///向上合并空闲区
flag2=1; ///回收区有上下邻空闲区
break;
}
if(flag2= =0) ///回收区无上邻空闲区
{
free[i].start=start;
free[i].size=size;
break;
}
}
}
if(flag1= =0) ///回收区无下邻空闲区，检查其是否有上邻空闲区
{
for(i=0;i<N;i++)
if(free[i].start+free[i].size= =start && free[i].state= =1)
{
free[i].size=free[i].size +size;
flag3=1;
break;
}
if(flag3= =0) ///回收区无上邻空闲区
for(j=0;j<N;j++)
if(free[j].state= =0) ///将释放区放入空表目中
{
free[j].start=start;
free[j].size=size;
free[j].state=1;
break;
}
}
}
四、实验结果

五、体会与收获
通过本次操作系统实验，首先我的编程能力有了很大的提高，其次我对操作系统内存的分配，存储空间的回收都有了全新的认识和深刻的理解。
在这次操作系统课程设计中我使用了C语言编写程序，模拟在可变分区管理方式下采用最先适应算法实现主存分配与回收，通过自己动手编程和测试程序，让我对可变分区管理方式的原理理解的更加透彻，模拟过程中，也让我发现了自己以前的很多误区，修改程序的工程中再一次巩固了所学知识。
六、源代码
#include <stdio.h>
#include <String.h>
#define N 3 ///空闲区和空表目总块数

struct free
{
int start; ///空闲分区始址
int size; ///空闲分区长度
int state; ///标志位,1表示未分配,0表示分空表目
};
free free[N]={{14,12,1},{32,96,1},{128,120,0}};///初始化空闲分区

///给作业分配主存空间函数
int alloc(int n) ///为作业分配内存，满足返回1，不满足返回0
{
int i,flag=0; ///用来标识是否有满足作业的空闲空间,1表示有，0表示无
for(i=0;i<N;i++)
{
if(free[i].state= =1 && free[i].size>n)///空闲区空间大于作业需求
{
free[i].start=free[i].start+n;
free[i].size=free[i].size-n;
flag=1;
return 1;
}
if(free[i].state= =1 && free[i].size==n)///空闲分区刚好满足作业需求
{
free[i].state=0; ///调整状态位
flag=1;
return 1;
}

}
if(flag==0)
	return 0;

}

void setfree(int start,int size)
{
int flag1=0,flag2=0,flag3=0; ///flag1:表示回收区是否有下邻空闲区; flag2:表示回收区是否有上下邻空闲区; flag3:表示回收区是否有上邻空闲区;
int i,j;
for(i=0;i<N;i++)
{
if(free[i].start= =start+size && free[i].state= =1) ///回收区有下邻空闲区
{
size=size+free[i].size; ///向下合并空闲区
flag1=1;
for(j=0;j<N;j++)
if(free[j].start+free[j].size= =start && free[j].state= =1)
{
free[i].state=0;
free[i].start=free[N-1].start+free[N-1].size;
free[i].size=120;
free[j].size=free[j].size+size; ///向上合并空闲区
flag2=1; ///回收区有上下邻空闲区
break;
}
if(flag2= =0) ///回收区无上邻空闲区
{
free[i].start=start;
free[i].size=size;
break;
}
}
}
if(flag1= =0) ///回收区无下邻空闲区，检查其是否有上邻空闲区
{
for(i=0;i<N;i++)
if(free[i].start+free[i].size= =start && free[i].state= =1)
{
free[i].size=free[i].size +size;
flag3=1;
break;
}
if(flag3= =0) ///回收区无上邻空闲区
for(j=0;j<N;j++)
if(free[j].state= =0) ///将释放区放入空表目中
{
free[j].start=start;
free[j].size=size;
free[j].state=1;
break;
}
}
}
///对空闲分区表按地址顺序排序
void sort()
{
int i,j;
struct free f; //中间变量
for(i=0;i<N;i++) //将空闲区按始地址顺序在表中排列
for(j=0;j<N-1;j++)
if(free[j].start>free[j+1].start)
{
f=free[j];
free[j]=free[j+1];
free[j+1]=f;
}
for(i=0;i<N;i++) ///将空表目放在表后面
for(j=0;j<N-1;j++)
if(free[j].state= =0 && free[j+1].state==1)
{
f=free[j];
free[j]=free[j+1];
free[j+1]=f;
}
}

int main(void)
{
int i,flag;
///打印初始分区表
printf("\n初始空闲分区表为:\n");
sort();
printf(" | 起址 | 长度 | 状态 | \n");
for(i=0;i<N;i++)
{
printf(" |%8d |%8d |%8d | \n",free[i].start,free[i].size,free[i].state);
}
///作业四调入内存
printf("\n大小为6K的作业四进入内存\n");
flag=alloc(6);
printf("\n经过分配后，空闲分配表为:\n");
sort();
printf(" | 起址 | 长度 | 状态 | \n");
for(i=0;i<N;i++)
{
printf(" |%8d |%8d |%8d | \n",free[i].start,free[i].size,free[i].state);
}
if(flag==0)
{
printf(“没有合适的空闲区，请等待！”);
}
///作业三撤离
printf("\n起始地址为10，大小为4的作业三撤离\n");
setfree(10,4);
printf("\n作业三内存释放后，空闲分配表为:\n");
sort();
printf(" | 起址 | 长度 | 状态 | \n");
for(i=0;i<N;i++)
{
printf(" |%8d |%8d |%8d | \n",free[i].start,free[i].size,free[i].state);
}
///作业二撤离
printf("\n起始地址为26，大小为6的作业二撤离\n");
setfree(26,6);
printf("\n作业二内存释放后，空闲分配表为:\n");
sort();
printf(" | 起址 | 长度 | 状态 | \n");
for(i=0;i<N;i++)
{
printf(" |%8d |%8d |%8d | \n",free[i].start,free[i].size,free[i].state);
}
}