C++ 操作系统内存管理模拟：最优分配算法与空闲区合并

这是一个模拟操作系统中内存管理的程序，主要包括三个功能：分配主存、回收主存和显示主存。其中，分配主存采用最优分配算法，回收主存则采用合并相邻空闲区的策略。

程序中定义了三个结构体，分别为已分配区表、空闲区表和指针结构。已分配区表用于存储已经分配出去的内存块的信息，包括起始地址、长度、是否可用等；空闲区表用于存储未分配出去的内存块的信息，包括起始地址、长度、是否可用等；指针结构则用于记录已分配区表和空闲区表的头尾指针，方便后续操作。

分配主存函数中，采用最优分配算法，即从空闲区表中寻找空间大于需求大小的最小空闲区登记项k，然后将其划分为一个已分配区，并将其添加到已分配区表中。如果空闲区大小与要求分配的空间差小于'minisize'，则整个空闲区全部分配；否则从空闲区划出一部分分配。

回收主存函数中，根据作业名寻找已分配区表中对应的登记项，然后将其修改为'空表目'，取得归还分区的起始地址和长度。接着寻找回收分区的上下邻空闲区，进行合并或直接填充空闲区表。

最后，程序中还提供了显示主存的功能，即输出空闲区表和已分配区表中的信息。

此程序可用于帮助学生理解操作系统中内存管理的基本原理和实现方法。

#include<iostream>
#include<string>
#include<iomanip>
#define n 10//假定系统允许的最大作业数量为n
#define m 10//假定系统允许的空闲区表最大为m
# define minsize 100 
using namespace std;
struct use
{
	float address;//已分分区起始地址
	float length;//已分分区长度,单位为字节
	string flag;//已分分区是否可用标志
	char uname;//作业名
	int next;//指向下一个已用分区的指针
}usetable[n];//已分配区表
struct ok
{
	int uhead;//已分分区头指针
	int utail;//已分分区尾指针
	int fhead; //空闲区头指针
	int ftail;//空闲区头指针
}point; //定义指针结构
struct free
{
	float address;//空闲区起始地址
	float length;//空闲区长度单位为字节
	string flag;//空闲区表登记栏标志
	char fname;
	int next;//指向下一个空闲分区的指针
}freetable[m];//空闲区表

void allocate(char j, float xk) //采用最优分配算法分配xk大小的空间
{
	int i, k, p, c;
	float ad;
	k = -1;
	i = point.fhead;
	c = i;
	do//寻找空间大于xk的最小空闲区登记项k 
	{
		if (freetable[i].length >= xk && freetable[i].flag == "可用")
			if (k == -1 || freetable[i].length < freetable[k].length)
			{
				k = i;
				p = c;
			}
		c = i;
		i = freetable[i].next;
	} while (i != -1);//寻找最优空闲区
	if (k == -1)
	{
		cout << "无可用空闲区" << endl;
		return;
	}
	//找到可用空闲区,开始分配:若空闲区大小与要求分配的空间差小于minisize, 则空闲区全部分配;若空闲区大小与要求分配的空间差大于minisize,则从空闲区划出一部分分配
	if (freetable[k].length - xk <= minsize)
	{
		freetable[k].flag = "空表目";
		xk = freetable[k].length;
		ad = freetable[k].address;
		freetable[k].fname = ' ';
		freetable[k].length = 0;
		freetable[k].address = 0;
		if (k == point.fhead)
		{
			point.fhead = freetable[k].next;
		}
		if (k == point.ftail)
		{
			point.ftail = p;
		}
		if (k != point.fhead && k != point.ftail)
		{
			freetable[p].next = freetable[k].next;
		}
	}
	else
	{
		freetable[k].length = freetable[k].length - xk;
		ad = freetable[k].address;
		freetable[k].address = freetable[k].address + xk;
		freetable[k].fname = ' ';
		freetable[k].flag = "可用";
	}//修改已分配区表
	i = 0;
	while (usetable[i].flag != "空表目" && i < n) //寻找空表目.
		i++;
	if (i >= n)//无表目填写已分分区
	{
		cout << "无表目填写已分分区，错误" << endl; //修正空闲区表
		if (freetable[k].flag == "空表目")//前面找到的是整个空闲区
			freetable[k].flag = "已分配";
		else
			//前面找到的是某个空闲区的一部分
			freetable[k].length = freetable[k].length + xk;
		return;
	}
	else//修改已分配区表
	{
		usetable[i].address = ad;
		usetable[i].length = xk;
		usetable[i].flag = "已分配";
		usetable[i].uname = j;
		if (point.uhead == -1)
		{
			point.uhead = point.utail = i;
		}
		else
		{
			usetable[point.utail].next = i;
			usetable[i].next = -1;
			point.utail = i;
		}
	}
	return;
}//主存分配函数结束

void reclaim(char J)
{
	int i, k, j, s, t, p;
	float S, L;
	//寻找已分配区表中对应登记项
	s = point.uhead;
	t = s;
	if (s == -1)
	{
		cout << "没有找到该作业\n" << endl;
		return;
	}
	while (s != -1)
	{
		if (usetable[s].uname == J && s < n)
		{
			p = t;
			k = s;
			break;
		}
		t = s;
		s = usetable[s].next;
	}
	s = k;
	if (s == -1)
	{
		cout << "没有找到该作业\n" << endl;
		return;
	}
	if (s >= n)//在已分配区表中找不到名字为J的作业
	{
		cout << " 找不到该作业" << endl;
		return;
	}
	//修改已分配区表
	usetable[s].flag = "空表目";
	usetable[s].uname = ' ';
	//取得归还分区的起始地址S和长度L
	S = usetable[s].address;
	L = usetable[s].length;
	usetable[s].address = 0;
	usetable[s].length = 0;
	//usetable[s]. next= -1;
	if (s == point.uhead)
	{
		point.uhead = usetable[s].next;
		usetable[s].next = -1;
	}
	if (s == point.utail)
	{
		point.utail = p;
		usetable[s].next = -1;
		usetable[p].next = -1;
	}
	if (s != point.uhead && s != point.utail)
	{
		usetable[p].next = usetable[s].next;
		usetable[s].next = -1;
	}
	//寻找回收分区的上下邻空闲区，上邻表目k,下邻表目j
	j = -1; k = -1; i = 0;
	while (i < m && (j == -1 || k == -1))
	{
		if (freetable[i].flag == "可用")
		{
			if (freetable[i].address + freetable[i].length == S)k = i;//找到上邻
			if (freetable[i].address == S + L)j = i;//找到下邻
		}
		i++;
	}//查找符合条件的可用单元。
	if (k != -1)
		if (j != -1) //. 上邻空闲区，下邻空闲区,三项合并
		{
			freetable[k].length = freetable[j].length + freetable[k].length + L;
			freetable[k].flag = "可用";
			freetable[k].fname = ' ';
			freetable[j].length = freetable[j].address = 0;
			freetable[j].fname = ' ';
		}
		else//.上邻非空闲区，下邻为空闲区，与下邻合并
		{
			freetable[k].length = freetable[k].length + L;
			freetable[k].fname = ' ';
		}
	else
		if (j != -1)
		{
			freetable[j].address = S;
			freetable[j].length = freetable[j].length + L;
			freetable[j].fname = ' ';
		}
		else//上下邻均为非空闲区,回收区域直接填人
		{
			//在空闲区表中寻找空栏目
			t = 0;
			while (freetable[t].flag == "可用" && t < m)
				t++;
			if (t > m) //空闲区表满,回收空间失败,将已分配区表复原
			{
				cout << "主空闲表没有空闲空间回收失败" << endl;
				return;
			}
			freetable[t].address = S;
			freetable[t].length = L;
			freetable[t].flag = "可用";
			freetable[t].fname = ' ';
			freetable[point.ftail].next = t;
			point.ftail = t;
			freetable[t].next = -1;
		}
	return;
}//主存归还函数结束
void main()
{
	char name;
	float xk;
	//空闲区表初始化
	freetable[0].address = 10240;//假定空闲区表内存起始地址   10240+102400
	freetable[0].length = 102400; //假定空闲区表的空间大小
	freetable[0].flag = "可用";
	freetable[0].next = -1;
	int i, a;
	point.uhead = point.utail = -1;
	point.fhead = 0;
	point.ftail = 0;
	for (i = 1; i < m; i++)
	{
		freetable[i].flag = "空表目";
		freetable[i].length = 0;
		freetable[i].address = 0;
		freetable[i].fname = ' ';
		freetable[i].next = -1;
	}
	//已分配区表初始化
	for (i = 0; i < n; i++)
	{
		usetable[i].flag = "空表目";
		usetable[i].length = 0;
		usetable[i].address = 0;
		usetable[i].uname = ' ';
		usetable[i].next = -1;
	}
	while (1)
	{
		cout << endl << "选择功能项(0-退出,1-分配主存,2-回收主存,3-显示主存)" << endl;
		cout << "选择功能项(0-3):";
		cin >> a;
		switch (a)
		{
		case 0: exit(0);//a=0程序结束
		case 1: cout << "输入作业名和作业所需长度:";
			cin >> name >> xk;
			allocate(name, xk);
			break;
		case 2: cout << "输人要回收的作业名:";
			cin >> name;
			reclaim(name);
			break;
		case 3: cout << endl << "输出空闲表区:
 项名 起始地址 分区长度 标志\n";
			i = point.fhead;
			while (i != -1 && i < m)
			{
				cout << setiosflags(ios::left) << setw(7) << i << setw(8) << setiosflags(ios::left)
					<< freetable[i].address << setw(8) << setiosflags(ios::left) << freetable[i].length <<
					setw(8) << setiosflags(ios::left) << freetable[i].flag << endl;
				i = freetable[i].next;
			}
			cout << endl << "输出已分配区表:
";
			cout << "项名 起始地址 分区长度 标志\n";
			i = point.uhead;
			while (i != -1 && i < n)
			{
				cout << setiosflags(ios::left) << setw(7) << usetable[i].uname << setiosflags(ios::left) << setw(8) << usetable[i].address << setiosflags(ios::left) << setw(8) << usetable[i].length << setiosflags(ios::left) << setw(8) << usetable[i].flag << endl;
				i = usetable[i].next;
			}
			break;
		default: cout << "没有这个选项" << endl;
		}
	}
}