一、实验内容
主存储器空间的分配和回收。
二、实验目的
一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。
三、实验原理
模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。
(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：
| 操作系统 |
| 作业1 |
| 作业3 |
| 空闲区 |
| 作业2 |
| 空闲区 |
|
为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：
| 起 址 |
长 度 |
状 态 |
|
| 第一栏 |
14 K |
12 K |
未 分 配 |
| 第二栏 |
32 K |
96 K |
未 分 配 |
| M |
M |
M |
M |
其中，起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。
(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。
(3) 采用最先适应算法分配主存空间。
按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。
(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。
(5) 请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业，现按下面序列进行内存的申请与释放：
作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K，
作业4申请30K， 作业5申请40K， 作业6申请60K， 作业4释放30K。
请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。
一、实验内容
主存储器空间的分配和回收。
二、实验目的
一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。
三、实验原理
模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。
(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：
| 操作系统 |
| 作业1 |
| 作业3 |
| 空闲区 |
| 作业2 |
| 空闲区 |
|
为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：
| 起 址 |
长 度 |
状 态 |
|
| 第一栏 |
14 K |
12 K |
未 分 配 |
| 第二栏 |
32 K |
96 K |
未 分 配 |
| M |
M |
M |
M |
其中，起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。
(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。
(3) 采用最先适应算法分配主存空间。
按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。
(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。
(5) 请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业，现按下面序列进行内存的申请与释放：
作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K，
作业4申请30K， 作业5申请40K， 作业6申请60K， 作业4释放30K。
请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。
四、算法流程图
1.最先适应分配算法流程图
2.归还主存时的回收算法流程图。
五、源程序及注释
//主存储器空间的分配和回收
#include<iostream>
#include<algorithm>
using namespace std;
struct Area{
int length; //长度
int start; //起址
int end; //终址 = 起址+长度
int num; //作业编号
};
Area OS_busy[100]; //工作区域区域
Area OS_free[100]; //空闲区域队列
int countBusy = 3; //工作区域的数量
int countFree = 2; //空闲区域的数量
int maxLength = 512; //最大工作长度
int osLength = 5;//操作系统工作长度
//自定义规则，对区域根据起始地址进行排序
bool Compare(Area a,Area b) {
return a.start < b.start;
}
//对工作的初始化的函数，防止函数的重复书写
void initBusy(int t_start,int t_length,int t_num) {
OS_busy[t_num].start = t_start;
OS_busy[t_num].length = t_length;
OS_busy[t_num].end = t_start + t_length;
OS_busy[t_num].num = t_num;
}
//显示工作区域信息
void showBusy() {
cout << "工作区域如下：" << endl;
cout << "---------------------------------" << endl;
cout << "序号\t 作业\t起址\t长度\t终址 " << endl;
for (int i = 1; i <= countBusy; i++)
{
cout << i << "\t";
cout <<"作业" << OS_busy[i].num << "\t";
cout << OS_busy[i].start << "k " << "\t ";
cout << OS_busy[i].length << "k " << "\t ";
cout << OS_busy[i].end << "k ";
cout << endl;
}
cout << "---------------------------------" << endl;
}
//显示空闲区域信息
void showFree() {
cout << "\n空闲区域如下：" << endl;
cout << "---------------------------------" << endl;
cout << "序号\t 作业\t起址\t长度\t终址 " << endl;
for (int i = 1; i <= countFree; i++)
{
cout << i << "\t";
cout << "作业" << OS_free[i].num << "\t";
cout << OS_free[i].start << "k " << "\t ";
cout << OS_free[i].length << "k " << "\t ";
cout << OS_free[i].end << "k ";
cout << endl;
}
cout << "---------------------------------" << endl;
}
//初始化区域
void init() {
//初始化主存中作业情况
initBusy(5, 5, 1);
initBusy(26, 6, 2);
initBusy(10, 4, 3);
sort(OS_busy + 1, OS_busy + 1 + countBusy, Compare);//利用自己建立的规则对工作序列按照起址升序排列
initBusy(0, 5, 0);
int t_count = 0;
for (int i = 0; i < countBusy; i++)
{
if (OS_busy[i].end < OS_busy[i + 1].start) {
t_count++;
//有空闲区域
OS_free[t_count].start = OS_busy[i].end;
OS_free[t_count].length = OS_busy[i + 1].start - OS_busy[i].end;
OS_free[t_count].end = OS_busy[i + 1].start;
OS_free[t_count].num = t_count;
}
}
if (OS_busy[3].end < maxLength) {
t_count++;
OS_free[t_count].start = OS_busy[countBusy].end;
OS_free[t_count].length = maxLength - OS_busy[countBusy].end;
OS_free[t_count].end = maxLength;
OS_free[t_count].num = t_count;
}
showBusy();
showFree();
return;
}
//分配任务
void Distri() {
cout << "开始分配任务:" << endl;
int tempCount = countBusy + 1;
cout << "请输入作业" << tempCount << "的长度" << endl;
cin >> OS_busy[tempCount].length;
OS_busy[tempCount].num = tempCount;
bool flag = 0;
for (int i = 1; i <= countFree; i++)
{
if (OS_free[i].length >= OS_busy[tempCount].length) {
//长度合适 可以分配
//添加工作区
OS_busy[tempCount].start = OS_free[i].start;
OS_busy[tempCount].end = OS_busy[tempCount].start + OS_busy[tempCount].length;
//修改空闲区
OS_free[i].start += OS_busy[tempCount].length;
OS_free[i].length -= OS_busy[tempCount].length;
if (OS_free[i].length == 0) {
countFree--;
for (int j = i; j<= countFree; j++)
{
OS_free[j] = OS_free[j + 1];
}
}
flag = 1;
break;
}
}
if (flag) {
//分配成功
countBusy++;
cout << "分配成功！起始地址为：" << OS_busy[tempCount].start << endl;
sort(OS_busy + 1, OS_busy + 1 + countBusy, Compare);
cout << "分配后主存情况如下：" << endl;
showBusy();
showFree();
system("pause");
}
else {
cout << "分配失败！" << endl;
system("pause");
}
return;
}
void Release() {
int choice;
cout << "请输入要释放的作业编号:";
cin >> choice;
bool flag1 = 0; //标志是否存在与内存
int pos; //所在位置
for (int i = 1; i <= countBusy; i++)
{
if (OS_busy[i].num == choice) {
flag1 = 1;
pos = i;
break;
}
}
if (flag1 == 0) {
cout << "主存中不存在此作业!" << endl;
cout << "=========================" << endl;
return;
}
bool flag2 = 0; //检查是否有下临界的空闲区
for (int i = 1; i <= countFree; i++)
{
if (OS_busy[pos].end == OS_free[i].start) {
flag2 = 1;
OS_free[i].start = OS_busy[pos].start;
OS_free[i].length += OS_busy[pos].length;
OS_free[i].num = i;
break;
}
}
bool flag3 = 0; //检查是否有上临界的空闲区
for (int i = 1; i <= countFree; i++)
{
if (OS_busy[pos].start == OS_free[i].end) {
flag3 = 1;
if (flag2 == 1) {
OS_free[i].length += OS_free[i+1].length;
OS_free[i].end += OS_free[i+1].end;
OS_free[i].num = i;
countFree--;
for (int j = i+1; j <= countFree; j++)
{
OS_free[j] = OS_free[j + 1];
}
}
if (flag2 == 0) {
//没有下相邻空闲区域
OS_free[i].length += OS_busy[pos].length;
OS_free[i].end = OS_busy[pos].end;
OS_free[i].num = i;
}
break;
}
}
if (flag2 == 0 && flag3 == 0) {
//表示无相邻空闲区 新建空闲区
countFree++;
OS_free[countFree].length = OS_busy[pos].length;
OS_free[countFree].end = OS_busy[pos].end;
OS_free[countFree].start = OS_busy[pos].start;
OS_free[countFree].num = countFree;
sort(OS_free + 1, OS_free + 1 + countFree, Compare);
}
OS_busy[pos].start = 0x3f3f3f;
sort(OS_busy + 1, OS_busy + 1 + countBusy, Compare);
countBusy--;
showBusy();
showFree();
return;
}
//主程序
int main() {
init();
int choice;
while (true) {
cout << "请输入您的操作：";
cout << "1.分配作业 2.回收作业 3.退出程序" << endl;
cin >> choice;
if (choice == 1) {
//分配作业
Distri();
}
else if (choice == 2) {
//回收作业
Release();
}
else {
exit(0);
}
}
}六、打印的程序运行时初值和运行结果
1.初始状态
2. 作业1申请300K
3.作业2申请100K
4.作业1释放300K
5.作业3申请150K
6.作业4申请30K
7.作业5申请40K
8.作业6申请60K
9.作业4释放30K
七、实验小结
1.对自己本次实验收获进行小结。
本次实验算法实现的难点在于作业分配与回收的设计。在作业装入主存时由于作业的长度和空闲区的长度很可能不一样，这样很可能导致每个作业按页装入主存中时，还存在一定的空间区域，利用算法将这些区域再分割成更小的区域，在释放作业时，若有相邻的空闲区，则将其合并。
2.如果在要申请一个100K的作业空间，能否满足？
答：如图，不能，此时主存中已经没有长度为100k的空间 若此时强行分配，会导致分配失败。
