C++ 操作系统内存分配算法的实现详解

2024-04-02 19:04:59 421人浏览安东尼

摘要

目录一、实验目的二、实验内容三、实验要求四、代码实现五、测试样例一、实验目的通过本实验帮助学生理解在动态分区管理方式下应怎样实现主存空间的分配和回收。二、实验内容在动态分区管

一、实验目的

通过本实验帮助学生理解在动态分区管理方式下应怎样实现主存空间的分配和回收。

二、实验内容

在动态分区管理方式下采用不同的分配算法实现主存分配和实现主存回收。

三、实验要求

（1）可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离、主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：

为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空区说明表，格式如下：

其中
起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲区的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。
由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。

上述的这张说明表的登记情况是按提示

（1）中的例所装入的三个作业占用的主存区域后填写的

（2）当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一个部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的“碎片”，在作业请求装入时，尽可能地利用主存的低地址部分的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。

（3）采用首次适应算法或循环首次算法或最佳适应算法分配主存空间。由于本实验是模拟主存的分配，所以当把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。（即输出当时的空闲区说明表及其内存分配表）

（4）当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示（1）中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。

（5）请分别按首次适应算法、循环首次算法和最佳适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装入三个作业，且形成两个空闲区，确定空闲说明表的初值。现有一个需要主存量为6K的作业4 申请装入主存；然后作业3 撤离；再作业2 撤离。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。

四、代码实现

MemoryAllocation.cpp


#include <iOStream>
#include <windows.h>
#include <fstream>
#include <string>
#include <queue>
using namespace std;
int MemorySize = 0;
int OSSize = 0;
int Memory[1000] = { 0 };

struct Struct1{
 	int begin;
	int length;
	string state;//值为未分配或者空条目
}; 
queue<Struct1> WORK;//作业集合
queue<Struct1> EMPTY;//空区集合

//更新EMPTY队列，空区集合
void UpdateEMP(){
	while (!EMPTY.empty()) {
		EMPTY.pop();
	}

	for (int i = 0; i < MemorySize; i++) {
		if (Memory[i] == 0) {
			for (int j = i + 1; j < MemorySize; j++) {
				if (Memory[j] == 1 || j == MemorySize - 1) {
					Struct1 emp1;
					emp1.begin = i;
					if (j == MemorySize - 1) {
						emp1.length = j - i + 1;
					}
					else {
						emp1.length = j - i;
					}
					emp1.state = "未分配";
					EMPTY.push(emp1);
					i = j;
					break;
				}
			}
		}
	}
	cout << "现有的空区说明表为：" << endl;
	int s = EMPTY.size();
	cout << s << "块空区" << endl;
	for (int i = 0; i < s; i++) {
		Struct1 emp1;
		emp1 = EMPTY.front();
		EMPTY.push(emp1);
		EMPTY.pop();
		cout  << " 起始：" << emp1.begin << " 长度：" << emp1.length << " 状态：" << emp1.state << endl;
	}
}

//首次适应算法(FF)
void FF(int applyNum) {
	if (EMPTY.empty()) {
		cout << "没有足够的主存空间！！" << endl;
		exit(0);
	}
	bool flag = false;
	while (!EMPTY.empty()) {
		Struct1 emp1 = EMPTY.front();
		if (emp1.length > applyNum) {
			for (int i = emp1.begin; i< applyNum + emp1.begin ;i++) {
				Memory[i] = 1;
			}
			Struct1 work3;
			work3.begin = emp1.begin;
			work3.length = applyNum;
			work3.state = "作业4";
			WORK.push(work3);
			UpdateEMP();
			flag = true;
			break;
		}
		EMPTY.pop();

	}
	if (!flag) {
		cout << "没有足够的主存空间！！" << endl;
		exit(0);
	}
	Sleep(2000);
	//作业三撤离
	for (int i = 0; i < WORK.size(); i++) {
		Struct1 work1;
		work1 = WORK.front();
		if (work1.state == "作业3") {
			for (int i = work1.begin; i < work1.begin+ work1.length;i++) {
				Memory[i] = 0;
			}
			WORK.pop();
			cout << endl << "作业三撤离！" << endl;
			UpdateEMP();
			break;
		}
		else {
			WORK.pop();
			WORK.push(work1);
		}
	}
	Sleep(2000);
	//作业二撤离
	for (int i = 0; i < WORK.size(); i++) {
		Struct1 work1;
		work1 = WORK.front();
		if (work1.state == "作业2") {
			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
				Memory[i] = 0;
			}
			WORK.pop();
			cout << endl << "作业二撤离！" << endl;
			UpdateEMP();
			break;
		}
		else {
			WORK.pop();
			WORK.push(work1);
		}
	}

}

//循环首次适应算法（NF）
void NF(int applyNum) {
	if (EMPTY.empty()) {
		cout << "没有足够的主存空间！！" << endl;
		exit(0);
	}
	bool flag = false;
	while (!EMPTY.empty()) {
		Struct1 emp1 = EMPTY.front();
		if (emp1.length > applyNum) {
			for (int i = emp1.begin; i < applyNum + emp1.begin; i++) {
				Memory[i] = 1;
			}
			Struct1 work3;
			work3.begin = emp1.begin;
			work3.length = applyNum;
			work3.state = "作业4";
			WORK.push(work3);
			UpdateEMP();
			flag = true;
			break;
		}
		EMPTY.pop();

	}
	if (!flag) {
		cout << "没有足够的主存空间！！" << endl;
		exit(0);
	}
	Sleep(2000);
	//作业三撤离
	for (int i = 0; i < WORK.size(); i++) {
		Struct1 work1;
		work1 = WORK.front();
		if (work1.state == "作业3") {
			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
				Memory[i] = 0;
			}
			WORK.pop();
			cout << endl << "作业三撤离！" << endl;
			UpdateEMP();
			break;
		}
		else {
			WORK.pop();
			WORK.push(work1);
		}
	}
	Sleep(2000);
	//作业二撤离
	for (int i = 0; i < WORK.size(); i++) {
		Struct1 work1;
		work1 = WORK.front();
		if (work1.state == "作业2") {
			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
				Memory[i] = 0;
			}
			WORK.pop();
			cout << endl << "作业二撤离！" << endl;
			UpdateEMP();
			break;
		}
		else {
			WORK.pop();
			WORK.push(work1);
		}
	}
}

//最佳适应算法(BF)
void BF(int applyNum) {
	if (EMPTY.empty()) {
		cout << "没有足够的主存空间！！" << endl;
		exit(0);
	}
	bool flag = false;
	int col = 10000000;//记录每一个空区与请求大小的差值
	string e = "";
	int em = EMPTY.size()*2;
	for (int i = 0; i < em; i++) {
		Struct1 emp1 = EMPTY.front();
		if (emp1.length > applyNum) {
			if (col == (emp1.length - applyNum) && e==emp1.state) {
				for (int i = emp1.begin; i < applyNum + emp1.begin; i++) {
					Memory[i] = 1;
				}
				Struct1 work3;
				work3.begin = emp1.begin;
				work3.length = applyNum;
				work3.state = "作业4";
				WORK.push(work3);
				UpdateEMP();
				flag = true;
				break;
			}
			if (col > (emp1.length - applyNum)) {
				col = (emp1.length - applyNum);
				e = emp1.state;
			}
		}
		EMPTY.pop();
		EMPTY.push(emp1);
	}
	if (!flag) {
		cout << "没有足够的主存空间！！" << endl;
		exit(0);
	}
	Sleep(2000);
	//作业三撤离
	for (int i = 0; i < WORK.size(); i++) {
		Struct1 work1;
		work1 = WORK.front();
		if (work1.state == "作业3") {
			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
				Memory[i] = 0;
			}
			WORK.pop();
			cout << endl << "作业三撤离！" << endl;
			UpdateEMP();
			break;
		}
		else {
			WORK.pop();
			WORK.push(work1);
		}
	}
	Sleep(2000);
	//作业二撤离
	for (int i = 0; i < WORK.size(); i++) {
		Struct1 work1;
		work1 = WORK.front();
		if (work1.state == "作业2") {
			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
				Memory[i] = 0;
			}
			WORK.pop();
			cout << endl << "作业二撤离！" << endl;
			UpdateEMP();
			break;
		}
		else {
			WORK.pop();
			WORK.push(work1);
		}
	}
}

//主函数
int main() {
	//打印提示信息
	cout << "************************************************\n";
	cout << "        操作系统实验内存分配算法\n";
	cout << "        作者：CSDN Carmelo_7 主页： https://blog.csdn.net/Carmelo_7?spm=1000.2115.3001.5343 \n";
	cout << "************************************************\n";
	ifstream inFile;
	inFile.open("MemoryAllocation.dat");
	if (!inFile.is_open())
		cout << "文件打开时候出错！！" << endl;
	inFile >> MemorySize >> OSSize;
	cout << "请输入主存的现有状态" << endl;
	cout << "正在读取数据文件..." << endl;
	Sleep(2000);
	//打印空闲区说明表的初始状态
	cout << "主存总大小：" << MemorySize << endl <<"操作系统占用空间：" << OSSize <<endl;
	for (int i = 0;i<OSSize; i++) {
		Memory[i] = 1;
	}
	int n = 0;
	while (!inFile.eof()) {
		n++;
		Struct1 work1;
		inFile >> work1.begin >> work1.length;
		work1.state = "作业"+to_string(n);
		WORK.push(work1);
	}
	int s = WORK.size();
	for (int i = 0; i < s; i++) {
		Struct1 work2;
		work2 = WORK.front();
		WORK.push(work2);
		WORK.pop();
		cout << work2.state << " 起始：" << work2.begin << " 长度：" << work2.length << endl;
		for (int i = work2.begin; i < work2.length + work2.begin; i++) {
			Memory[i] = 1;
		}
	}
	

	UpdateEMP();

	cout << "请输入新的作业的申请主存数量：" << endl;
	//打印作业4的申请量
	int applyNum = 0;
	cin >> applyNum;
	cout << "作业" << n << "申请了"<< applyNum <<"主存空间" << endl;

	cout << "===================================================================================" << endl;
	cout << "1.首次适应算法(FF) :将所有空闲分区按照地址递增的次序链接，在申请内存分配时，从链首开始查找，将满足需求的第一个空闲分区分配给作业。" << endl;
	cout << "2.循环首次适应算法（NF）：将所有空闲分区按照地址递增的次序链接，在申请内存分配时，总是从上次找到的空闲分区的下一个空闲分区开始查找，将满足需求的第一个空闲分区分配给作业" << endl;
	cout << "3.最佳适应算法(BF) : 将所有空闲分区按照从小到大的顺序形成空闲分区链，在申请内存分配时，总是把满足需求的、最小的空闲分区分配给作业。" << endl;
	cout << "===================================================================================" << endl;
	cout << "请输入对应的序号选择算法：" << endl;
	int choose = 0;
	cin >> choose;
	switch (choose)	{
		case 1:
			FF(applyNum);
			break;
		case 2:
			NF(applyNum);
			break;
		case 3:
			BF(applyNum);
			break;
		default:
			cout << "你输入的序号有误！！！" << endl;
			exit(0);
			break;
	}


}

MemoryAllocation.dat