快捷導(dǎo)航

C++ 操作系統(tǒng)內(nèi)存分配算法的實(shí)現(xiàn)詳解

更新時(shí)間：2021年11月18日 09:00:28 作者：Carmelo_7

本文主要介紹了在動(dòng)態(tài)分區(qū)管理方式下采用不同的分配算法實(shí)現(xiàn)主存分配和實(shí)現(xiàn)主存回收，旨在幫助學(xué)生理解在動(dòng)態(tài)分區(qū)管理方式下應(yīng)怎樣實(shí)現(xiàn)主存空間的分配和回收。感興趣的可以了解一下

一、實(shí)驗(yàn)?zāi)康?/h2>
通過本實(shí)驗(yàn)幫助學(xué)生理解在動(dòng)態(tài)分區(qū)管理方式下應(yīng)怎樣實(shí)現(xiàn)主存空間的分配和回收。

二、實(shí)驗(yàn)內(nèi)容

在動(dòng)態(tài)分區(qū)管理方式下采用不同的分配算法實(shí)現(xiàn)主存分配和實(shí)現(xiàn)主存回收。

三、實(shí)驗(yàn)要求

（1）可變分區(qū)方式是按作業(yè)需要的主存空間大小來分割分區(qū)的。當(dāng)要裝入一個(gè)作業(yè)時(shí)，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個(gè)分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入。隨著作業(yè)的裝入、撤離、主存空間被分成許多個(gè)分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。例如：

為了說明哪些區(qū)是空閑的，可以用來裝入新作業(yè)，必須要有一張空區(qū)說明表，格式如下：

其中
起址——指出一個(gè)空閑區(qū)的主存起始地址。
長度——指出從起始地址開始的一個(gè)連續(xù)空閑區(qū)的長度。
狀態(tài)——有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對(duì)應(yīng)的由起址指出的某個(gè)長度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示表中對(duì)應(yīng)的登記項(xiàng)目是空白（無效），可用來登記新的空閑區(qū)（例如，作業(yè)撤離后，它所占的區(qū)域就成了空閑區(qū)，應(yīng)找一個(gè)“空表目”欄登記歸還區(qū)的起址和長度且修改狀態(tài)）。
由于分區(qū)的個(gè)數(shù)不定，所以空閑區(qū)說明表中應(yīng)有適量的狀態(tài)為“空表目”的登記欄目，否則造成表格“溢出”無法登記。

上述的這張說明表的登記情況是按提示

（1）中的例所裝入的三個(gè)作業(yè)占用的主存區(qū)域后填寫的

（2）當(dāng)有一個(gè)新作業(yè)要求裝入主存時(shí)，必須查空閑區(qū)說明表，從中找出一個(gè)足夠大的空閑區(qū)。有時(shí)找到的空閑區(qū)可能大于作業(yè)需要量，這時(shí)應(yīng)把原來的空閑區(qū)變成兩部分：一個(gè)部分分給作業(yè)占用；另一部分又成為一個(gè)較小的空閑區(qū)。為了盡量減少由于分割造成的“碎片”，在作業(yè)請(qǐng)求裝入時(shí)，盡可能地利用主存的低地址部分的空閑區(qū)，而盡量保存高地址部分有較大的連續(xù)空閑區(qū)域，以利于大型作業(yè)的裝入。為此，在空閑區(qū)說明表中，把每個(gè)空閑區(qū)按其地址順序登記，即每個(gè)后繼的空閑區(qū)其起始地址總是比前者大。為了方便查找還可使表格“緊縮”，總是讓“空表目”欄集中在表格的后部。

（3）采用首次適應(yīng)算法或循環(huán)首次算法或最佳適應(yīng)算法分配主存空間。由于本實(shí)驗(yàn)是模擬主存的分配，所以當(dāng)把主存區(qū)分配給作業(yè)后并不實(shí)際啟動(dòng)裝入程序裝入作業(yè)，而用輸出“分配情況”來代替。（即輸出當(dāng)時(shí)的空閑區(qū)說明表及其內(nèi)存分配表）

（4）當(dāng)一個(gè)作業(yè)執(zhí)行結(jié)束撤離時(shí)，作業(yè)所占的區(qū)域應(yīng)該歸還，歸還的區(qū)域如果與其它空閑區(qū)相鄰，則應(yīng)合成一個(gè)較大的空閑區(qū)，登記在空閑區(qū)說明表中。例如，在提示（1）中列舉的情況下，如果作業(yè)2撤離，歸還所占主存區(qū)域時(shí)，應(yīng)與上、下相鄰的空閑區(qū)一起合成一個(gè)大的空閑區(qū)登記在空閑區(qū)說明表中。

（5）請(qǐng)分別按首次適應(yīng)算法、循環(huán)首次算法和最佳適應(yīng)算法設(shè)計(jì)主存分配和回收的程序。然后按（1）中假設(shè)主存中已裝入三個(gè)作業(yè)，且形成兩個(gè)空閑區(qū)，確定空閑說明表的初值?，F(xiàn)有一個(gè)需要主存量為6K的作業(yè)4 申請(qǐng)裝入主存；然后作業(yè)3 撤離；再作業(yè)2 撤離。請(qǐng)你為它們進(jìn)行主存分配和回收，把空閑區(qū)說明表的初值以及每次分配或回收后的變化顯示出來或打印出來。

四、代碼實(shí)現(xiàn)

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;//作業(yè)集合
queue<Struct1> EMPTY;//空區(qū)集合

//更新EMPTY隊(duì)列，空區(qū)集合
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 << "現(xiàn)有的空區(qū)說明表為：" << endl;
	int s = EMPTY.size();
	cout << s << "塊空區(qū)" << endl;
	for (int i = 0; i < s; i++) {
		Struct1 emp1;
		emp1 = EMPTY.front();
		EMPTY.push(emp1);
		EMPTY.pop();
		cout  << " 起始：" << emp1.begin << " 長度：" << emp1.length << " 狀態(tài)：" << emp1.state << endl;
	}
}

//首次適應(yīng)算法(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 = "作業(yè)4";
			WORK.push(work3);
			UpdateEMP();
			flag = true;
			break;
		}
		EMPTY.pop();

	}
	if (!flag) {
		cout << "沒有足夠的主存空間?。? << endl;
		exit(0);
	}
	Sleep(2000);
	//作業(yè)三撤離
	for (int i = 0; i < WORK.size(); i++) {
		Struct1 work1;
		work1 = WORK.front();
		if (work1.state == "作業(yè)3") {
			for (int i = work1.begin; i < work1.begin+ work1.length;i++) {
				Memory[i] = 0;
			}
			WORK.pop();
			cout << endl << "作業(yè)三撤離！" << endl;
			UpdateEMP();
			break;
		}
		else {
			WORK.pop();
			WORK.push(work1);
		}
	}
	Sleep(2000);
	//作業(yè)二撤離
	for (int i = 0; i < WORK.size(); i++) {
		Struct1 work1;
		work1 = WORK.front();
		if (work1.state == "作業(yè)2") {
			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
				Memory[i] = 0;
			}
			WORK.pop();
			cout << endl << "作業(yè)二撤離！" << endl;
			UpdateEMP();
			break;
		}
		else {
			WORK.pop();
			WORK.push(work1);
		}
	}

}

//循環(huán)首次適應(yīng)算法（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 = "作業(yè)4";
			WORK.push(work3);
			UpdateEMP();
			flag = true;
			break;
		}
		EMPTY.pop();

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

//最佳適應(yīng)算法(BF)
void BF(int applyNum) {
	if (EMPTY.empty()) {
		cout << "沒有足夠的主存空間?。? << endl;
		exit(0);
	}
	bool flag = false;
	int col = 10000000;//記錄每一個(gè)空區(qū)與請(qǐng)求大小的差值
	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 = "作業(yè)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);
	//作業(yè)三撤離
	for (int i = 0; i < WORK.size(); i++) {
		Struct1 work1;
		work1 = WORK.front();
		if (work1.state == "作業(yè)3") {
			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
				Memory[i] = 0;
			}
			WORK.pop();
			cout << endl << "作業(yè)三撤離！" << endl;
			UpdateEMP();
			break;
		}
		else {
			WORK.pop();
			WORK.push(work1);
		}
	}
	Sleep(2000);
	//作業(yè)二撤離
	for (int i = 0; i < WORK.size(); i++) {
		Struct1 work1;
		work1 = WORK.front();
		if (work1.state == "作業(yè)2") {
			for (int i = work1.begin; i < work1.begin + work1.length; i++) {
				Memory[i] = 0;
			}
			WORK.pop();
			cout << endl << "作業(yè)二撤離！" << endl;
			UpdateEMP();
			break;
		}
		else {
			WORK.pop();
			WORK.push(work1);
		}
	}
}

//主函數(shù)
int main() {
	//打印提示信息
	cout << "************************************************\n";
	cout << "        操作系統(tǒng)實(shí)驗(yàn)內(nèi)存分配算法\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 << "文件打開時(shí)候出錯(cuò)！！" << endl;
	inFile >> MemorySize >> OSSize;
	cout << "請(qǐng)輸入主存的現(xiàn)有狀態(tài)" << endl;
	cout << "正在讀取數(shù)據(jù)文件..." << endl;
	Sleep(2000);
	//打印空閑區(qū)說明表的初始狀態(tài)
	cout << "主存總大小：" << MemorySize << endl <<"操作系統(tǒng)占用空間：" << 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 = "作業(yè)"+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;
		}
	}
	/*for (int i : Memory) {
		cout << i;
	}*/

	UpdateEMP();

	cout << "請(qǐng)輸入新的作業(yè)的申請(qǐng)主存數(shù)量：" << endl;
	//打印作業(yè)4的申請(qǐng)量
	int applyNum = 0;
	cin >> applyNum;
	cout << "作業(yè)" << n << "申請(qǐng)了"<< applyNum <<"主存空間" << endl;

	cout << "===================================================================================" << endl;
	cout << "1.首次適應(yīng)算法(FF) :將所有空閑分區(qū)按照地址遞增的次序鏈接，在申請(qǐng)內(nèi)存分配時(shí)，從鏈?zhǔn)组_始查找，將滿足需求的第一個(gè)空閑分區(qū)分配給作業(yè)。" << endl;
	cout << "2.循環(huán)首次適應(yīng)算法（NF）：將所有空閑分區(qū)按照地址遞增的次序鏈接，在申請(qǐng)內(nèi)存分配時(shí)，總是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，將滿足需求的第一個(gè)空閑分區(qū)分配給作業(yè)" << endl;
	cout << "3.最佳適應(yīng)算法(BF) : 將所有空閑分區(qū)按照從小到大的順序形成空閑分區(qū)鏈，在申請(qǐng)內(nèi)存分配時(shí)，總是把滿足需求的、最小的空閑分區(qū)分配給作業(yè)。" << endl;
	cout << "===================================================================================" << endl;
	cout << "請(qǐng)輸入對(duì)應(yīng)的序號(hào)選擇算法：" << 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 << "你輸入的序號(hào)有誤！??！" << endl;
			exit(0);
			break;
	}


}

MemoryAllocation.dat