本次博客目录

一、实验要求
二、运行截图
三、代码结构
四、完整源代码
五、Last but not least

一、实验要求

1.基础知识

掌握内存管理的相关内容，对内存分配与回收有深入的理解。

2.具体要求

（1）选择1~3种内存分配算法（最先适应、最佳适应、最坏适应）实现内存分配

（2）能够输入给定的内存大小、进程个数、每个进程申请的内存空间

（3）能够选择分配、回收操作

（4）能够显示进程在内存的存储地址、大小

（5）显示每次内存分配、回收后内存空间的使用情况

二、运行截图

图一初始内存情况

图二选择回收部分内存

图三显示分配后的内存情况

图四分配示例

三、代码结构

（1）项目结构

图五项目结构

（2）文件说明

为了简便起见，头文件中包含函数说明和函数定义！

初始时从文件Input.txt中读取了内存大小、初始进程数、初始进程请求大小。以下是Input.txt文件的内容：

图六 input.txt

ConsoleApplication.cpp:程序入口

Allocation.h:分配函数

Recycle.h:回收函数

InputAction.h:有关输入的操作，比如输入功能选项等

OutputAction.h:有关输出的操作

Memory.h:模拟内存的相关结构体定义

四、完整源代码

（1）ConsoleApplication.cpp

/*
 * @ author W-nut
 */


#include <iostream>
#include <string>
#include "OutputAction.h"
#include "Allocation.h"
using namespace std;

const int ALLOCATE = 1;
const int RECYCLE = 2;
const int SHOWMEMORY = 3;
const int SHOWAVAILABLE = 4;
const int EXIT = 5;

int main()
{
	cout << "这是动态分区管理的模拟实现程序！" << endl;
	
	InputData();//从文件读取内存大小，请求进程数，请求进程大小
	cout << "初始内存分配情况如下：" << endl;
	InitMemoryArea();//初始化内存
	cout << "初始可用表如下：" << endl;
	InitAvailable();//初始化可用表

	string selection;
	while (true)
	{
		OutputMemu();
		cin >> selection;
		if (selection.empty())
		{
			cout << "还没选择！" << endl;
			continue;
		}
		else
		{
			int sel=stoi(selection);
			switch (sel)
			{
			case ALLOCATE: {
				Allocation();
				break;
			}
			case RECYCLE: {
				cout << "请选择结束进程！" << endl << "当前已分配进程如下：" << endl;
				vector<string>recycleProcess;
				InputRecycle(recycleProcess);
				for (string s : recycleProcess)
					Recycle(s);
				break;
			}
			case SHOWMEMORY: {
				OutputMemory();
				break;
			}
			case SHOWAVAILABLE: {
				OutputAvaiableMemory();
				break;
			}
			case EXIT:{
				cout << "退出程序" << endl;
				exit(0);
				break;
			}
			default: {
				break;
				exit(0);
			}
			}
		}
	}

	return 0;


}

（2）Allocation.h

/*
 * @ author W-nut
 */

#pragma once

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include "Memory.h"
#include "InputAction.h"
#include "OutputAction.h"
#include "Recycle.h"
using namespace std;

const int FIRSTFIT = 1;
const int BESTFIT = 2;
const int WORSTFIT = 3;

void UpdateMemory(const Process current_Process,const Memory before,const Memory after);

bool SortAvailable(const Memory m1, const Memory m2)//对可用表按起始大小递增排序
{
	return m1.m_AreaBaseAddress < m2.m_AreaBaseAddress;
}
bool SortAvailableINC(const Memory m1,const Memory m2)//对可用表按大小递增排序
{
	return m1.m_AreaLength < m2.m_AreaLength;
}
bool SortAvailableDEC(const Memory m1, const Memory m2)//对可用表按大小递减排序
{
	return m1.m_AreaLength > m2.m_AreaLength;
}


//函数说明：分配内存
//参数说明：选择的分配算法
void Allocation()
{
	newRequestProcess.clear();
	InputRequestProcess();//输入新的请求进程

	//选择分配算法
	OutputALgorithm();
	string selection;
	cin >> selection;
	

	Process current_Process;//当前进程
	Memory before_Memory;//修改前可用表记录
	Memory after_Memory;//修改后可用表的记录

	//对每个新进程进行分配
	for (Process p : newRequestProcess)
	{
		//如果可用表为空，请求回收空闲区
		if (availableMemory.empty())
		{
			cout << "进程" << p.m_ProcessNum << ",在可用表中没有空闲区可用了！" << endl;
			cout << "请选择结束进程！" << endl << "当前已分配进程如下：" << endl;
			vector<string>recycleProcess;
			InputRecycle(recycleProcess);
			for (string s : recycleProcess)
				Recycle(s);
		}
		//如果可用表最大空闲区长度不够，请求回收空闲区
		sort(availableMemory.begin(), availableMemory.end(), SortAvailableDEC);
		if (availableMemory.begin()->m_AreaLength < p.m_RequestLength)
		{
			cout << "进程" << p.m_ProcessNum << "请求的长度大于可用表中所有空闲区！" << endl;
			cout << "请选择结束进程！" << endl << "当前已分配进程如下：" << endl;
			vector<string>recycleProcess;
			InputRecycle(recycleProcess);
			for (string s : recycleProcess)
				Recycle(s);
		}

		//选择分配算法
		while (true)
		{
			switch (stoi(selection))
			{
			case FIRSTFIT: {
				sort(availableMemory.begin(), availableMemory.end(), SortAvailable);
				break;
			}
			case BESTFIT: {
				sort(availableMemory.begin(), availableMemory.end(), SortAvailableINC);
				break;
			}
			case WORSTFIT: {
				sort(availableMemory.begin(), availableMemory.end(), SortAvailableDEC);
				break;
			}
			}
			break;
		}
		
		vector< Memory>::iterator m_current = availableMemory.begin();//当前迭代器所指向的可用表记录
		for (Memory& m : availableMemory)
		{
			if (m.m_AreaLength >= p.m_RequestLength)
			{
				//当前空闲区长度 >= 当前进程请求长度
				if (m.m_AreaLength == p.m_RequestLength)
				{
					//当前空闲区长度 = 当前进程请求长度时，从可用表移除当前空闲区记录
					current_Process = p;
					before_Memory = m;
					availableMemory.erase(m_current);
					after_Memory = m;
					break;
				}
				else
				{
					//当前空闲区长度 > 当前进程请求长度时，从当前空闲区截取所需大小，修改可用表		
					current_Process = p;
					before_Memory = m;
					m.m_AreaBaseAddress += p.m_RequestLength;
					m.m_AreaLength -= p.m_RequestLength;
					after_Memory = m;
					break;
				}
			}
			else
			{
				//当前空闲区长度 < 当前进程请求长度时，取下一空闲区
				continue;
			}
			++m_current;
		}
		//每个进程分配结束后，根据更新后的可用表更新内存情况
		//新进程分配成功，添加到已分配进程
		requestProcess.push_back(current_Process);
		UpdateMemory(current_Process, before_Memory, after_Memory);
	}
}


//函数说明：根据可用表修改内存使用状况
//函数参数：新分配成功的进程,修改前后的可用表记录
void UpdateMemory(const Process current_Process, const Memory before_Memory, const Memory after_Memory)
{
	if (availableMemory.empty())
	{
		//可用表为空
		for (MemoryArea & mA : memoryArea)
		{
			if (mA.m_MemoryStart == before_Memory.m_AreaBaseAddress)
			{
				mA.m_IsAllocated = true;
				mA.m_ProcessNum = current_Process.m_ProcessNum;
			}			
		}
	}
	else
	{
		//可用表非空
		vector<MemoryArea>::iterator current = memoryArea.begin();
		vector<MemoryArea>::iterator after;
		for (MemoryArea& mA : memoryArea)
		{
			if (mA.m_MemoryStart == before_Memory.m_AreaBaseAddress)
			{
				MemoryArea new_mA;
				new_mA.m_IsAllocated = true;
				new_mA.m_MemoryStart = mA.m_MemoryStart;
				new_mA.m_MemoryEnd = new_mA.m_MemoryStart + current_Process.m_RequestLength;
				new_mA.m_ProcessNum = current_Process.m_ProcessNum;
				after = memoryArea.erase(current);

				after = memoryArea.insert(after, new_mA) + 1;
				new_mA.m_IsAllocated = false;
				new_mA.m_MemoryStart = after_Memory.m_AreaBaseAddress;
				new_mA.m_MemoryEnd = new_mA.m_MemoryStart + after_Memory.m_AreaLength;
				new_mA.m_ProcessNum = "free";
				memoryArea.insert(after, new_mA);

				break;
			}
			++current;
		}
	}
	//每次分配进程内存后输出内存情况
	cout << "分配进程" << current_Process.m_ProcessNum << "后的内存情况为：" << endl;
	OutputMemory();
	cout << "分配进程" << current_Process.m_ProcessNum << "后的可用表情况为：" << endl;
	OutputAvaiableMemory();
}

（3）Recycle.h

/*
 * @ author W-nut
 */

#pragma once

#include <string>
#include "Memory.h"

//函数说明：回收空闲区,合并空闲区
//函数参数：选择结束的进程号
void Recycle(string num)
{
	vector<MemoryArea>::iterator current = memoryArea.begin();
	vector<MemoryArea>::iterator before;
	vector<MemoryArea>::iterator after;

	MemoryArea currentMA;//当前内存区域
	MemoryArea beforeMA;//前一个内存区域
	MemoryArea afterMA;//后一个内存区域

	//默认输入的进程号是有效且存在的
	for (MemoryArea mA : memoryArea)
	{
		if (mA.m_ProcessNum._Equal(num))
		{
			//在内存中寻找新释放的进程区的前后区域
			currentMA = mA;
			if (current == memoryArea.begin())
			{
				//找到的内存区是第一个元素
				before = current;
				after = current + 1;

				beforeMA.m_IsAllocated = true;
				afterMA = *(current + 1);
			}
			else if (current == (memoryArea.end() - 1))
			{
				//找到的内存区是最后一个元素
				before = current - 1;
				after = memoryArea.end();

				beforeMA = *(current - 1);
				afterMA.m_IsAllocated = true;
			}
			else
			{
				//找到的空闲区前后均有元素
				before = current - 1;
				after = current + 1;

				beforeMA = *(current - 1);
				afterMA = *(current + 1);
			}
			break;//找到后直接退出
		}
		else
		{
			++current;
			continue;
		}

	}

	//判断前后区域是否空闲
	if (afterMA.m_IsAllocated == false && beforeMA.m_IsAllocated == false)
	{
		//前后均为空闲区
		MemoryArea new_mA;
		new_mA.m_IsAllocated = false;
		new_mA.m_MemoryStart = beforeMA.m_MemoryStart;
		new_mA.m_MemoryEnd = afterMA.m_MemoryEnd;
		new_mA.m_ProcessNum = "free";

		vector<MemoryArea>::iterator newOne = memoryArea.insert(after, new_mA);
		current = newOne - 1;
		before = current - 1;
		after = newOne + 1;
		current=memoryArea.erase(before);
		after=memoryArea.erase(current);
		memoryArea.erase(after);
	}
	else if (beforeMA.m_IsAllocated == true && afterMA.m_IsAllocated == false)
	{
		//前忙碌，后空闲
		MemoryArea new_mA;
		new_mA.m_IsAllocated = false;
		new_mA.m_MemoryStart = currentMA.m_MemoryStart;
		new_mA.m_MemoryEnd = afterMA.m_MemoryEnd;
		new_mA.m_ProcessNum = "free";

		vector<MemoryArea>::iterator newOne = memoryArea.insert(current, new_mA);
		current = newOne + 1;	
		after=memoryArea.erase(current);
		//after = newOne + 1;
		memoryArea.erase(after);
	}
	else if (beforeMA.m_IsAllocated == false && afterMA.m_IsAllocated == true)
	{
		//前空闲，后忙碌
		MemoryArea new_mA;
		new_mA.m_IsAllocated = false;
		new_mA.m_MemoryStart = beforeMA.m_MemoryStart;
		new_mA.m_MemoryEnd = currentMA.m_MemoryEnd;
		new_mA.m_ProcessNum = "free";

		vector<MemoryArea>::iterator newOne = memoryArea.insert(after, new_mA);
		current = newOne - 1;
		before = current - 1;
		current=memoryArea.erase(before);
		memoryArea.erase(current);
	}
	else
	{
		//前后都忙碌
		MemoryArea new_mA;
		new_mA.m_IsAllocated = false;
		new_mA.m_MemoryStart = currentMA.m_MemoryStart;
		new_mA.m_MemoryEnd = currentMA.m_MemoryEnd;
		new_mA.m_ProcessNum = "free";

		vector<MemoryArea>::iterator newOne = memoryArea.insert(after, new_mA);
		current = newOne - 1;//新增后原来的迭代器失效了

		memoryArea.erase(current);
	}

	//根据内存更新后的情况更新可用表
	int index = 0;
	availableMemory.clear();
	for (MemoryArea mA : memoryArea)
	{
		
		if (mA.m_IsAllocated == false)
		{
			Memory m;
			m.m_AreaNum = "可用区" + to_string(++index);
			m.m_AreaBaseAddress = mA.m_MemoryStart;
			m.m_AreaLength = mA.m_MemoryEnd - mA.m_MemoryStart;
			availableMemory.push_back(m);
		}
	}

	//更新已分配进程
	vector<Process>::iterator current_process = requestProcess.begin();
	for (Process p : requestProcess)
	{
		if ((p.m_ProcessNum)._Equal(num))
		{
			requestProcess.erase(current_process);
			break;
		}
		++current_process;
	}
	

	/*cout << "释放进程"<<num<<"后的内存为：" << endl;
	OutputMemory();

	cout << "释放进程" << num << "后的可用表为：" << endl;
	OutputAvaiableMemory();	*/
}

（4）InputAction.h


/*
 * @ author W-nut
 */


#pragma once
#include <iostream>
#include <fstream>
#include "Memory.h"
using namespace std;

//输入新的请求进程
void InputRequestProcess()
{
	int request_Num = 0;
	cout << "请输入请求分配内存的进程个数：";
	cin >> request_Num;

	int request_PerSize = 0;
	vector<int>request_Size;
	cout << "请输入各个进程请求的内存大小（限定为正整数，单位默认为KB,以O结束）:";
	while (cin >> request_PerSize)
	{
		if (request_PerSize == 0)
			break;
		else
			request_Size.push_back(request_PerSize);
	}
		
	if (request_Num == request_Size.size())
	{
		//requestProcess.clear();
		//获取请求进程表最后一个进程
		vector<Process>::iterator end = requestProcess.end();
		string last = (end - 1)->m_ProcessNum;

		Process process;

		//新的申请进程号
		int new_num = stoi(last.substr(1, last.length() - 1));
		
		for (int num : request_Size)
		{
			process.m_ProcessNum = "P" + to_string(++new_num);
			process.m_RequestLength = num;
			newRequestProcess.push_back(process);
		}	
	}
	else
		cout << "输入的进程数与请求进程数不一致!" << endl;
	

}

//从文件读取数据
void InputData()
{
	ifstream file;
	file.open("input.txt", ios::in);
	if (!file)
	{
		cout << "打开文件失败!" << endl;
	}
	requestProcess.clear();
	while (!file.eof())
	{
		file >> MEMORY_SIZE;
		file >> PROCESS_NUM;
		for (int i=1;i<= PROCESS_NUM;++i)
		{
			Process p;
			p.m_ProcessNum = "P" + to_string(i);
			file >> p.m_RequestLength;
			requestProcess.push_back(p);
		}
	}
}

//函数说明：初始化内存
void InitMemoryArea()
{
	//初始化OS内存
	MemoryArea mA;
	mA.m_MemoryStart = 0;
	mA.m_MemoryEnd = 20;
	mA.m_ProcessNum = "OS";
	mA.m_IsAllocated = true;
	if (!memoryArea.empty())
		memoryArea.clear();
	else
		memoryArea.push_back(mA);

	for (Process p : requestProcess)
	{
		mA.m_MemoryStart = mA.m_MemoryEnd;
		mA.m_MemoryEnd += p.m_RequestLength;
		mA.m_ProcessNum = p.m_ProcessNum;
		mA.m_IsAllocated = true;
		memoryArea.push_back(mA);
	}
	vector<MemoryArea>::iterator last = memoryArea.end();
	mA.m_IsAllocated = false;
	mA.m_MemoryStart = (last - 1)->m_MemoryEnd;
	mA.m_MemoryEnd = MEMORY_SIZE;
	mA.m_ProcessNum = "free";
	memoryArea.push_back(mA);

	OutputMemory();

	
}

//初始化可用表
void InitAvailable()
{
	//初始化可用表
	int index = 1;
	for (MemoryArea mA : memoryArea)
	{
		if (mA.m_IsAllocated == false)
		{
			Memory m;
			m.m_AreaNum = "可用区" + to_string(index);
			m.m_AreaLength = mA.m_MemoryEnd - mA.m_MemoryStart;
			m.m_AreaBaseAddress = mA.m_MemoryStart;
			availableMemory.push_back(m);
		}
		else
		{
			continue;
		}
		++index;
	}

	OutputAvaiableMemory();
}

//输入选择结束回收的进程
void InputRecycle(vector<string>& recycle)
{
	string sel_num;
	//展示当前已分配进程
	OutputHadProcess();
	cout << "请输入要结束的进程号（以O结束）：";
	while (cin >> sel_num)
	{
		if (sel_num == "0")
			break;
		else
			recycle.push_back(sel_num);
	}
	

}

（5）OutputAction.h

/*
 * @ author W-nut
 */


#ifndef OUTPUTACTION
#define OUTPUTACTION


#include "Memory.h"
using namespace std;

//输出选择菜单
void OutputMemu()
{
	cout << "\t请选择功能：" << endl;
	cout << "\t1.分配内存\n\t2.回收内存\n\t3.显示内存\n\t4.显示可用表\n\t5.退出" << endl;
	cout << "\t请输入选项：";
}

//输出分配算法
void OutputALgorithm()
{
	cout << "\t请选择分配算法：" << endl;
	cout << "\t1.最先适应法\n\t2.最佳适应法\n\t3.最坏适应法\n" << endl;
	cout << "\t请输入分配算法选项：";
}

//输出内存分配情况
void OutputMemory()
{
	cout << endl << endl << "\t\t内存分配情况" << endl;
	cout << "内存地址（单位：KB）\t" << "分配进程\t" << "是否分配（1:已分配；0:未分配）" << endl;
	cout << 0 << endl;
	for (MemoryArea mA : memoryArea)
	{		
		cout << "\t\t\t"<<mA.m_ProcessNum << "\t\t\t"
			<< mA.m_IsAllocated << "\n"<< mA.m_MemoryEnd << endl;
	}
	auto end = memoryArea.end();
	MemoryArea last = *(end - 1);
	if (last.m_MemoryEnd == MEMORY_SIZE)
		return;
	else
		cout << endl<<endl<<MEMORY_SIZE << endl << endl;
}


//输出可用表
void OutputAvaiableMemory()
{
	cout << "\t\t可用表如下：\n";
	cout << "分区号\t" << "分区起始地址\t" << "分区大小\n";
	for (Memory m : availableMemory)
	{
		cout << m.m_AreaNum << "\t\t" << m.m_AreaBaseAddress << "\t" << m.m_AreaLength << endl;
	}

	cout << endl;
}


//输出已分配进程
void OutputHadProcess()
{
	cout << "进程号" << "\t" << "请求大小" << endl;
	for (Process p : requestProcess)
		cout << p.m_ProcessNum << "\t" << p.m_RequestLength << endl;
}
#endif

（6）Memory.h

/*
 * @ author W-nut
 */

#pragma once

#include <string>
#include <vector>
using namespace std;


//内存某一分区结构体
struct MemoryArea
{
	int m_MemoryStart ;//某一分区起始
	int m_MemoryEnd;//某一分区结束
	bool m_IsAllocated;//该分区分配状态（true:已分配；false:未分配）
	string m_ProcessNum;//该区域已分配的进程号
};

//内存情况
vector<MemoryArea>memoryArea;

//内存大小(单位为KB)
int MEMORY_SIZE = 0;


//可用表结构体
struct Memory
{
	string m_AreaNum;       //分区区号
	int m_AreaLength;       //分区长度
	int m_AreaBaseAddress;  //分区起始地址
};
	
//内存可用表
vector<Memory>availableMemory;


//进程结构体
struct Process
{
	string m_ProcessNum;  //进程号
	int m_RequestLength;  //请求内存长度
};

//已分配进程表
vector<Process>requestProcess;

//输入的新进程请求表
vector<Process>newRequestProcess;

//请求进程个数
int PROCESS_NUM = 0;

五、Last but not least

传说五大秘术：点赞、评论、分享、收藏、打赏！

mua~~

原文链接：https://blog.csdn.net/weixin_44666217/article/details/111042115