采用可变式分区管理，使用首次适应算法实现主存的分配与回收（C++实现）

算法思想：

1. 采用可变式分区管理，使用首次适应算法实现主存的分配与回收

要求采用分区表进行。

1. 可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要，并且分区个数是可以调整的。当要装入一个作业时。根据作业需要的主存量。查看是否有足够的空闲空间。若有，则按需求量分割一部分给作业。若无，则作业等待。随着作业的装入、完成。主存空间被分隔成许多大大小小的分区，有的分区被作业占用。有的分区空闲。为了说明哪些分区是空闲的，可以用来装入新作业，必须要有一张空闲区分说明表。其中，起始地址指出各空闲区的主存起始地址，长度指出空闲区大小。由于分区个数不定，所以空闲区说明表中应有足够的空表目项，否则造成溢出，无法登记。同样再设一个已分配分区表，记录作业或进程的主存占用情况。
2. 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需求量，这是应将空闲区一分为二，一个分给作业，另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽可能分配低地址部分的空闲区。将较大空闲区留在高地址端，以利于大作业的装入。为此在空闲区表中，按空闲区首地址从低到高进行登记。
3. 当一个作业执行完成时，作业所占用的空闲区应归还给系统，在归还时要考虑相邻空闲区合并的问题，作业的释放区与空闲区的邻接分以下四种情况考虑：

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;
}

结果：