采用可变式分区管理，使用空闲区链实现主存的分配与回收（C++实现）

算法思想：

采用可变式分区管理，使用空闲区链实现主存的分配与回收

要求采用首次适应法管理空闲区链来进行。

1. 可变式分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需要。而且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量，查看是否有足够的空闲空间。若有，则按需求量分割一部分给作业，若无则作业等待，随着作业的装入、完成，主存空间被分割成许多大大小小的分区，有些分区被作业占用，有的分区空闲。
2. 空闲区链，记录主存空间使用情况的一种较好方法是将表格信息，附加在每个已分配区和未分配区空闲区表中。
3. 当有进程要求分配主存时，首先根据首次适应算法从链头开始，沿链查找一个足够容纳该进程的空闲区，若这个空闲分区比较大，则一分为二，一部分分配给进程，另一部分作为空闲区链仍在链中当前位置，但修改它的上一个空闲区的前向指针加上分配作业的大小，下一个空闲区的后向指针加上分配作业的大小，使链保持完整。若这个分区的大小正好等于作业大小，则该空闲分区全部分配给作业，并将该空闲分区从链中摘除。

 代码：

#include<iostream>
#include<string>
#include<list>
using namespace std;
typedef struct freeArea {
	int startingAddress;
	int length;
}freeArea;
typedef struct alreadyAssignedArea {
	int startingAddress;
	int length;
	string remark;
}alreadyAssignedArea;
void initFreeAreaTable(list<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(list<freeArea> p) {
	cout << "空闲区表如下:" << endl;
	cout << "起始地址\t" << "长度\t" << "状态" << endl;
	for (list<freeArea>::iterator it = p.begin(); it != p.end(); it++) {
		cout << it->startingAddress << "K\t\t" << it->length << "KB\t" << "未分配" << endl;
	}
	cout << endl;
}
void initAlreadyAssignedAreaTable(list<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(list<alreadyAssignedArea> p) {
	cout << "已分配分区表如下:" << endl;
	cout << "起始地址\t" << "长度\t" << "备注" << endl;
	for (list<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(list<freeArea> &p, list<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 (list<freeArea>::iterator it = p.begin(); it != p.end(); it++) {
			if (length > it->length)
				continue;
			else if (it->length == length) {
				cout << "分配成功" << endl;
				for (list<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 (list<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(list<freeArea> &p, list<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;
		list<alreadyAssignedArea>::iterator itprer;
		list<alreadyAssignedArea>::iterator it = q.begin();
		list<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;
			list<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);
			list<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 == "空闲区") {
			list<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 {
			list<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() {
	list<freeArea> p;
	list<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;
}

结果：