主存储器空间的分配和回收。
一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。
三、实验原理
模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。
(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：
为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：
其中，起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。
(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。
(3) 采用最先适应算法（顺序分配算法）分配主存空间。
按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。
(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。
(5) 请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业，现按下面序列进行内存的申请与释放：
作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K，
作业4申请30K， 作业5申请40K， 作业6申请60K， 作业4释放30K。
请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。
#include <iostream>
using namespace std;
#define COUNT 512
//定义作业结构体代表作业状态
typedef struct Task
{
char name;//名称
int start;//起始位置
int end;//大小
int flag;//是否分配的标志
}Task;
//定义结构体数组存储各项作业状态，代表作业表
Task OS[COUNT];
int counts;//被分成的块数统计
char c;//作业名
int num;//资源申请量
//初始化
void init()
{
counts = 1;
OS[0].name = 'P';//未分配命名为P
OS[0].start = 0;//初始位置0
OS[0].end = COUNT;
OS[0].flag = 1;//分配标志未分配 = 1
}
//插入数组数据
void insert(int m, int st, int en)
{
int i;
counts++;//数组长度加一
for (i = counts; i > m ; i--)//从插入位由后往前后移数据
{
OS[i] = OS[i - 1];
}
OS[m].start = st;//插入数据
OS[m].end = en;
}
//删除数组数据
void move(int m)
{
int i;
for (i = m; i < counts - 1; i++)//从删除位由前往后前移数据
{
OS[i] = OS[i + 1];
}
counts--;//数组长度减一
}
//合并没有分配的相邻块
void remove(int m, int st, int en)
{
if (!OS[m - 1].flag && !OS[m + 1].flag)
//如果m位置前后标志都已分配则正常处理，不分配
{
OS[m].name = 'P';
OS[m].flag = 1;
}
if (OS[m - 1].flag)
//如果m位置前标志未分配，后标志已分配则与前一个合并
{
OS[m - 1].end = OS[m - 1].end + en;
move(m);
}
if (OS[m + 1].flag)
//如果m位置后标志未分配，前标志已分配则与后一个合并
{
OS[m].end = OS[m].end + OS[m + 1].end;
OS[m].name = 'P';
OS[m].flag = 1;
move(m + 1);
}
}
//打印输出
void show()
{
int i;
cout << "(名称 标识 起址 长度 状态)" << endl;
for (i = 0; i < counts; i++)
{
if (OS[i].flag)//未分配
cout << "P ";
else//已分配
cout << OS[i].name << " ";
cout << i << " " << OS[i].start << " " << OS[i].end << " ";
//依次输出块的编号，起始位置，长度
if (OS[i].flag)
cout << "未分配" << endl;
else
cout << "已分配" << endl;
}
}
//录入数据
void put()
{
cout << "输入申请或者释放的进程名称及资源数：" << endl;
cin >> c;
cin >> num;
}
//申请资源
int apply()
{
int i = 0;
int applyflag = 0;//标记
while (!applyflag && i < counts)//遍历数组查找连续的可分配资源是否存在
{
if (OS[i].end >= num && OS[i].flag)//通过比较块大小和是否已分配来找资源 空间
{
if (OS[i].end == num)//大小相等则直接修改信息
{
OS[i].name = c;
OS[i].flag = 0;
}
else//若偏大则修改信息同时更新原先块为已分配和未分配两部分
{
insert(i + 1, OS[i].start + num, OS[i].end - num);
OS[i + 1].flag = 1;
OS[i + 1].name = 'P';
OS[i].start = OS[i].start;
OS[i].name = c;
OS[i].end = num;
OS[i].flag = 0;
}
applyflag = 1;//申请成功更改标记
}
i++;
}
if (applyflag)
{
cout << "申请成功" << endl;
return 1;
}
else
{
cout << "没有足够大的空闲空间" << endl;
return 0;
}
}
//释放资源
int free()
{
int i = 0;
int freeflag = 0;//标记
while (!freeflag && i < counts)//遍历数组查找所对应作业是否存在
{
if (OS[i].name == c)//找到作业
{
if (OS[i].end == num)//释放大小相等，合并未分配区
{
remove(i, OS[i].start, OS[i].end);
}
else
{
if (OS[i].end >num)//释放大小不足，将已分配区拆分为未分配和已分 配两个区
{
insert(i + 1, OS[i].start + num, OS[i].end - num);
OS[i + 1].name = 'P';
OS[i + 1].flag = 0;
OS[i].end = num;
OS[i].flag = 1;
if (OS[i - 1].flag)//合并未分配区
{
remove(i, OS[i].start, OS[i].end);
}
}
else
{
cout << "正使用的数量小于释放的数量" << endl;
return 0;
}
}
freeflag = 1;//修改标记
}
i++;
}
if (freeflag)
{
cout << "释放成功" << endl;
return 1;
}
else
{
cout << "未找到匹配的进程名称" << endl;
return 0;
}
}
//菜单函数
void menu()
{
int code;
while (1)
{
cout << "输入选择" << endl <<
"1.初始化" << endl <<
"2.输出" << endl <<
"3.申请" << endl <<
"4.释放" << endl <<
"0.退出" << endl;
cin >> code;
//初始化
if (code == 1)
{
init();
}
//显示输出
else if (code == 2)
{
show();
}
//申请
else if (code == 3)
{
put();
apply();
show();
}
//释放
else if (code == 4)
{
put();
free();
show();
}
//退出操作
else if (code == 0)
{
return;
}
else
cout << "命令无效，请重新输入" << endl;
}
}
int main()
{
menu();
return 0;
}
