算法思想：
- 采用可变式分区管理，使用首次适应算法实现主存的分配与回收
要求采用分区表进行。
- 可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。当要装入一个作业时。根据作业需要的主存量。查看是否有足够的空闲空间。若有，则按需求量分割一部分给作业。若无，则作业等待。随着作业的装入、完成。主存空间被分隔成许多大大小小的分区，有的分区被作业占用。有的分区空闲。为了说明哪些分区是空闲的，可以用来装入新作业，必须要有一张空闲区分说明表。其中，起始地址指出各空闲区的主存起始地址，长度指出空闲区大小。由于分区个数不定，所以空闲区说明表中应有足够的空表目项，否则造成溢出，无法登记。同样再设一个已分配分区表，记录作业或进程的主存占用情况。
- 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需求量，这是应将空闲区一分为二，一个分给作业，另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽可能分配低地址部分的空闲区。将较大空闲区留在高地址端，以利于大作业的装入。为此在空闲区表中，按空闲区首地址从低到高进行登记。
- 当一个作业执行完成时，作业所占用的空闲区应归还给系统，在归还时要考虑相邻空闲区合并的问题，作业的释放区与空闲区的邻接分以下四种情况考虑：
A、释放区下临空闲区；
B、释放区上临空闲区；
C、释放区上下都与空闲区邻接；
D、释放区与空闲区不邻接。
代码：
#include<iostream>
#include<string>
#include<vector>
using namespace std;
typedef struct freeArea {
int startingAddress;
int length;
}freeArea;
typedef struct alreadyAssignedArea {
int startingAddress;
int length;
string remark;
}alreadyAssignedArea;
void initFreeAreaTable(vector<freeArea> &p) {
freeArea s;
int startingAddress[] = { 45,110 };
int length[] = { 20,146 };
for (int i = 0; i < 2; i++) {
s.startingAddress = startingAddress[i];
s.length = length[i];
p.push_back(s);
}
cout << endl;
}
void printFreeArea(vector<freeArea> p) {
cout << "空闲区表如下:" << endl;
cout << "起始地址\t" << "长度\t" << "状态" << endl;
for (vector<freeArea>::iterator it = p.begin(); it != p.end(); it++) {
cout << it->startingAddress << "K\t\t" << it->length << "KB\t" << "未分配" << endl;
}
cout << endl;
}
void initAlreadyAssignedAreaTable(vector<alreadyAssignedArea> &p) {
alreadyAssignedArea s;
int startingAddress[] = { 0,10,20,45,65,110 };
int length[] = { 10,10,25,20,45,146 };
string remark[] = { "操作系统","作业1","作业4","空闲区","作业2","空闲区" };
for (int i = 0; i < 6; i++) {
s.startingAddress = startingAddress[i];
s.length = length[i];
s.remark = remark[i];
p.push_back(s);
}
cout << endl;
}
void printAleadyAssignedArea(vector<alreadyAssignedArea> p) {
cout << "已分配分区表如下:" << endl;
cout << "起始地址\t" << "长度\t" << "备注" << endl;
for (vector<alreadyAssignedArea>::iterator it = p.begin(); it != p.end(); it++) {
cout << it->startingAddress << "K\t\t" << it->length << "KB\t" << it->remark << endl;
}
cout << endl;
}
void firstFitAllocation(vector<freeArea> &p, vector<alreadyAssignedArea> &q) {
int length;
string remark;
bool flag = false;
string choose;
cout << "你想要分配吗?,yes or no:";
cin >> choose;
while (choose == "yes") {
flag = false;
cout << "请输入要申请的作业的长度和备注，例如(20 作业1):";
cin >> length;
cin >> remark;
for (vector<freeArea>::iterator it = p.begin(); it != p.end(); it++) {
if (length > it->length)
continue;
else if (it->length == length) {
cout << "分配成功" << endl;
for (vector<alreadyAssignedArea>::iterator it2 = q.begin(); it2 != q.end(); it2++) {
if (it2->startingAddress == it->startingAddress) {
it2->remark = remark;
break;
}
}
p.erase(it);
flag = true;
break;
}
else {
cout << "分配成功" << endl;
alreadyAssignedArea t;
t.startingAddress = it->startingAddress + length;
t.length = it->length - length;
t.remark = "空闲区";
for (vector<alreadyAssignedArea>::iterator it2 = q.begin(); it2 != q.end(); it2++) {
if (it2->startingAddress == it->startingAddress) {
it2->length = length;
it2->remark = remark;
q.insert(++it2, t);
break;
}
}
it->length = it->length - length;
it->startingAddress = it->startingAddress + length;
flag = true;
break;
}
}
if (!flag) {
cout << "抱歉,没有适合的空间可以分配" << endl;
}
else {
printFreeArea(p);
printAleadyAssignedArea(q);
}
cout << "你还想要分配吗?,yes or no:";
cin >> choose;
}
}
void firstFitRecovery(vector<freeArea> &p, vector<alreadyAssignedArea> &q) {
freeArea s;
string remark;
string choose;
bool flag1, flag2;
cout << "你想要回收吗?,yes or no:";
cin >> choose;
while (choose == "yes") {
cout << "请输入需要回收的内存空间的备注:";
cin >> remark;
flag1 = true;
flag2 = true;
vector<alreadyAssignedArea>::iterator itprer;
vector<alreadyAssignedArea>::iterator it = q.begin();
vector<alreadyAssignedArea>::iterator itnext;
for (it = q.begin(); it != q.end(); it++)
if (it->remark == remark)
break;
itprer = it;
itnext = it;
if (it == q.begin()) {
flag1 = false;
itnext++;
}
else if (it == --q.end()) {
flag2 = false;
itprer--;
}
else {
itprer--;
itnext++;
}
if (flag1&&flag2&&itprer->remark == "空闲区"&&itnext->remark == "空闲区") {
itprer->length += it->length + itnext->length;
vector<freeArea>::iterator i;
for (i = p.begin(); i != p.end(); i++)
if (i->startingAddress == itprer->startingAddress)
break;
i->length += it->length + itnext->length;
q.erase(itnext);
q.erase(it);
p.erase(++i);
}
else if (flag1&&itprer->remark == "空闲区") {
itprer->length += it->length;
q.erase(it);
vector<freeArea>::iterator i;
for (i = p.begin(); i != p.end(); i++)
if (i->startingAddress == itprer->startingAddress)
break;
i->length = itprer->length;
}
else if (flag2&&itnext->remark == "空闲区") {
vector<freeArea>::iterator i;
for (i = p.begin(); i != p.end(); i++)
if (i->startingAddress == itnext->startingAddress)
break;
itnext->startingAddress = it->startingAddress;
itnext->length += it->length;
i->startingAddress = it->startingAddress;
i->length = itnext->length;
q.erase(it);
}
else {
vector<freeArea>::iterator i;
for (i = p.begin(); i != p.end(); i++)
if (i->startingAddress > it->startingAddress)
break;
it->remark = "空闲区";
s.startingAddress = it->startingAddress;
s.length = it->length;
p.insert(i, s);
}
printFreeArea(p);
printAleadyAssignedArea(q);
cout << "你还想要回收吗?,yes or no:";
cin >> choose;
}
}
int main() {
vector<freeArea> p;
vector<alreadyAssignedArea> q;
int choose;
initFreeAreaTable(p);
printFreeArea(p);
initAlreadyAssignedAreaTable(q);
printAleadyAssignedArea(q);
while (true) {
cout << "1:分配 2：回收 3:退出" << endl;
cout << "请输入:";
cin >> choose;
if (choose == 1)
firstFitAllocation(p, q);
else if (choose == 2)
firstFitRecovery(p, q);
else if (choose == 3)
break;
else
cout << "输入有误";
}
getchar();
getchar();
return 0;
}
结果：