动态分区存储管理(操作系统课设)

动态分区存储管理

因为代码使用C++写的，虽然自己之前自学过C++，代码看起来还是有一点困难，这篇博客就是我的课程设计，本次课程设计利用VS和MFC构造图形化界面更加直观。

1 设计任务

1.1 设计目的

●加深理解动态分区分配存储管理的过程；
● 建立描述内存分配状况的数据结构；
● 建立描述进程的数据结构；
● 使用两种方式产生进程：（a）自动产生， （b）手工输入；
● 在屏幕上显示内存的分配状况、每个进程的执行情况；
● 建立分区的分配与回收算法，支持紧凑算法；
● 时间的流逝可用下面几种方法模拟：
(a) 按键盘，每按一次可认为过一个时间单位；
(b) 响应WM_TIMER；
● 将一批进程的执行情况存入磁盘文件，以后可以读出并重放；

●实现动态分区分配算法:
首次适应算法
循环首次适应算法
最佳适应算法
最坏适应算法；
●加深对碎片处理方法——内存回收算法，以及紧凑算法的理解，认识其作用，并予以实现。
1.2 设计内容
（1）动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区存储管理时，将涉及到分区中所用的数据结构、分区分配算法和分区的分配和回收操作三个问题。
（2）设计一个动态分区存储管理程序，并模拟实现分区的分配和回收过程。
（3）要求所设计程序采用的分配算法必须同时包括以下四种算法：首次适应算法、循环首次适应算法、最佳适应算法、最差适应算法
（4）分区回收时必须具备能对相邻空闲分区合并。测试时请根据所定义的内存大小随机给出多组分区请求进行分配，并依据测试结果对所用各分配算法的优缺点加以分析比较。

2 总体设计

2.1 总体结构

2.2 开发环境

Visual studio 2019（简称VS）是美国微软公司的开发工具包系列产品。VS是一个基本完整的开发工具集，它包括了整个软件生命周期中所需要的大部分工具，如UML工具、代码管控工具、集成开发环境 (IDE)等等。所写的目标代码适用于微软支持的所有平台。

微软基础类库（英语：Micorsoft Foundation Classes，简称MFC）是微软公司提供的一个类库（class libraries），以C++的形式封装了Windows API，并且包含一个应用程序框架，以减少应用程序开发人员的工作量。其中包含大量Windows句柄封装类和很多Windows的内建控件和组件的封装类。

3 数据结构以及算法设计：

1. 内存分配状况 (Memory.h)：
   空闲分区表：
   (1) 描述：
   在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个
   空闲分区占一个表目，表目中包括进程序号、分区始址及分区的大小等数据项。

(2) 实现：

1. 内存分区：

// 内存分区
struct Partition {
	int ID; // 进程标识
	int Address; // 分区地址
	int Size; // 分区大小
	bool Status; // 忙：true 闲：false
	Partition() {
		ID = -1; // 进程ID默认初值
	}
};

2. 内存空间：

deque<Partition> deqMem; // 定义一个名为‘deqMem’的双端队列
	//队中的每一个元素都是一个结构体Partition来保存整个内存的状态，
	//也就是说这个双端队列是memory类的数据成员

3. 内存总体设计：

struct myNode
{
	int Index; // 空闲的内存分区在内存空间的位置
	int Size; // 空闲的内存分区的大小
};
class Memory
{
private:
	const int totalSize = 100; // 总共的内存空间大小
	const int beginIndex = 0; // 内存空间起始地址
	const int endIndex = 100; // 内存空间结束地址
	int unusedSize; // 内存空间未使用的大小
	int searchPtrForNF; // next fit 查询指针
	deque<Partition> deqMem; // 定义一个名为‘deqMem’的双端队列
	//队中的每一个元素都是一个结构体Partition来保存整个内存的状态，
	//也就是说这个双端队列是memory类的数据成员
	vector<myNode> vecNode; // 保存按空闲内存空间大小排序后的结果
	Partition Ptn; // 内存分区临时变量
	myNode Nd; // 空闲的内存分区临时变量
	bool FirstFit(int Size, int ID); // 首次适应算法
	bool NextFit(int Size, int ID); // 循环首次适应算法
	bool BestFit(int Size, int ID); // 最佳适应算法
	bool WorstFit(int Size, int ID); // 最坏适应算法
	void CreateVec();
	void Increse(); // 递增排序
	void Decrese(); // 递减排序
	
	// 比较函数
	static bool CmpIncrese(const myNode &N1, const myNode &N2);
	static bool CmpDecrese(const myNode &N1, const myNode &N2);

	void Merge(int Index); // 合并连续的空闲内存分区
	const string Filelog = "MemLog"; // 内存动态分配日志（为了回放）
	ofstream outFile;
	void getLog(); // 获取内存动态分配日志
public:
	Memory();
	~Memory();
	bool Allocate(int Size, int algType, int ID); // 分配空间
	deque<Partition> getMemStatus(); // 获取内存空间状态
	void ReleaseSpace(int ID, int Size); // 释放内存空间（并完成连续的空闲内存分区的回收）
	deque<Partition> Compact(); // 紧凑算法（碎片整理）
	string getFileName();  // 获取日志文件名
	void Distroy(); // 将内存状态重置
	int getMaxSize(); // 获取总共的内存空间大小
};

2. 进程 (Process.h)
   (1) 描述：
   1）手工输入：
   进程具有： 进程标识 + 进程所需空间大小
   2）自动产生：
   进程具有： 进程标识 + 进程所需空间大小 + 进程所需运行时间
   (2) 实现：

class Process
{
private:
	/*
	注：
	（1）手工输入：
		进程具有： 进程标识 + 进程所需空间大小
	（2）自动产生：
		进程具有： 进程标识 + 进程所需空间大小 + 进程所需运行时间
	*/
	int PID; // 进程标识
	int PSize; // 进程所需空间大小
	int PTime; // 进程所需运行时间
	int PselType; 
	// 区分进程产生方式：
	// 手工输入：PselType = 0; 
	// 自动产生：PselType = 1;
	int nextID; // 下一个产生进程的标识
public:
	Process();
	~Process();
	void CreateProcess(int Size); //手工输入进程
	void CreateProcess(int Size, int Time);//自动产生进程
	int getPID(); // 获取进程ID
	int getPSize(); // 获取进程大小
	int getPTime(); // 获取进程运行时间
	int getPselType(); // 获取进程产生类型
	void ChangeSize(int ChangeSize); // 改变进程空间大小
	void decrease(); // 纠正进程标识（使进程标识从0连续递增产生）
};

3.1首次适应算法（First Fit）
(1) 描述：
FF 算法要求空闲分区表以地址递增的次序生成。在分配内存时，从首地址开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者， 余下的空闲分区仍留在空闲表中。若从首地址直至尾地址都不能找到一个能满足要求的分区，则此次内存分配失败，返回。
(2) 特点：
1）优点：
该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。
2）缺点：
低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是 从低址部分开始，这无疑会增加查找可用空闲分区时的开销。
(3) 实现：

在这里插入代码片

3.2循环首次适应算法（Next Fit）
(1) 描述：
在为进程分配内存空间时，不再是每次都从首址开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针
(2) 特点：
1） 优点：
该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销。
2） 缺点：
缺乏大的空闲分区。
(3) 实现：

bool Memory::NextFit(int Size, int ID) {
	bool isSuccess = false;
	int i = searchPtrForNF;
	int flag = searchPtrForNF;
	// 从查询指针开始，遍历内存空间
	do 
	{
		if ((!deqMem[i].Status) && (Size <= deqMem[i].Size)) {
			// 如果空间没被使用，并且大小满足进程所需空间，则使用此空间，否则继续遍历
			if (Size != deqMem[i].Size) {
				// 如果空闲区间大于进程所需空间，则可以将剩下的空间作为一个分区
				Ptn.Address = deqMem[i].Address + Size;
				Ptn.Size = deqMem[i].Size - Size;
				Ptn.Status = false;
				deqMem.insert(deqMem.begin() + i + 1, Ptn);
				// 由于在进程分配内存时可以任意选择动态分区分配算法，所以对查询指针进行更新。
				searchPtrForNF = (i + 1)%deqMem.size();
			}
			// 改变内存状态：已用
			deqMem[i].ID = ID;
			deqMem[i].Size = Size;
			deqMem[i].Status = true;
			isSuccess = true;
			break;
		}
		// 遍历下一个内存分区
		i = (i + 1) % deqMem.size();
	} while (i != flag);
	// 返回进程是否已成功得到其申请的空间
	return isSuccess;
}

3.3最佳适应算法
(1) 描述：
每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成张一空闲分区表。这样，第一次找到的能满足要求的空闲区，必然是最佳的。
(2) 特点：
1） 优点：
孤立地看，最佳适应算法似乎是最佳的
2） 缺点：
在宏观上，因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区。
(3) 实现：

bool Memory::BestFit(int Size, int ID) {
	bool isSuccess = false;
	// 对空闲内存分区，按照空间大小递增顺序进行排序
	Increse();
	for (int m = 0; m < vecNode.size(); ++m) {
		// 遍历空闲内存空间
		int i = vecNode[m].Index;
		if ((!deqMem[i].Status) && (Size <= deqMem[i].Size)) {
			// 如果空间没被使用，并且大小满足进程所需空间，则使用此空间，否则继续遍历
			if (Size != deqMem[i].Size) {
				// 如果空闲区间大于进程所需空间，则可以将剩下的空间作为一个分区
				Ptn.Address = deqMem[i].Address + Size;
				Ptn.Size = deqMem[i].Size - Size;
				Ptn.Status = false;
				deqMem.insert(deqMem.begin() + i + 1, Ptn);
				// 由于在进程分配内存时可以任意选择动态分区分配算法，所以对查询指针进行更新
				searchPtrForNF = (i + 1) % deqMem.size();
			}
			// 改变内存状态：已用
			deqMem[i].ID = ID;
			deqMem[i].Size = Size;
			deqMem[i].Status = true;
			isSuccess = true;
			break;
		}
	}
	vecNode.clear();
	// 返回进程是否已成功得到其申请的空间
	return isSuccess;
}

3.4最坏首次适应算法
(1) 描述：
扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。
(2) 特点：
1） 优点:
可使剩下的空闲区不至于太小，产生碎片的几率最小，对中、小作业 有利，同时最坏适应分配算法查找效率很高。
2） 缺点：
会使存储器中缺乏大的空闲分区
(3) 实现：

bool Memory::WorstFit(int Size, int ID){
	bool isSuccess = false;
	// 对空闲内存分区，按照空间大小递减顺序进行排序
	Decrese();
	for (int m = 0; m < vecNode.size(); ++m) {
		// 遍历空闲内存空间
		int i = vecNode[m].Index;
		if ((!deqMem[i].Status) && (Size <= deqMem[i].Size)) {
			// 如果空间没被使用，并且大小满足进程所需空间，则使用此空间，否则继续遍历
			if (Size != deqMem[i].Size) {
				// 如果空闲区间大于进程所需空间，则可以将剩下的空间作为一个分区
				Ptn.Address = deqMem[i].Address + Size;
				Ptn.Size = deqMem[i].Size - Size;
				Ptn.Status = false;
				deqMem.insert(deqMem.begin() + i + 1, Ptn);
				// 由于在进程分配内存时可以任意选择动态分区分配算法，所以对查询指针进行更新
				searchPtrForNF = (i + 1) % deqMem.size();
			}
			// 改变内存状态：已用
			deqMem[i].ID = ID;
			deqMem[i].Size = Size;
			deqMem[i].Status = true;
			isSuccess = true;
			break;
		}
	}
	vecNode.clear();
	// 返回进程是否已成功得到其申请的空间
	return isSuccess;
}

3.5回收算法 (void ReleaseSpace(int ID, int Size))：
(1) 描述：
当进程释放内存时，系统根据回收区的首址，从空闲区表中找到相应的插入点，此时可能出现以下四种情况之一：

1. 回收区与插入点的前一个空闲分区 F1相邻接，见图 4-8(a)。此时应将回收区与插入 点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区 F1的大小。
2. 回收分区与插入点的后一空闲分区 F2相邻接，见图 4-8(b)。此时也可将两分区合并， 形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。
3. 回收区同时与插入点的前、后两个分区邻接，见图 4-8(c)。此时将三个分区合并， 使用 F1的表项和 F1的首址，取消 F2的表项，大小为三者之和。
4. 回收区既不与 F1邻接，又不与 F2邻接。这时应为回收区单独建立一新表项，填写 回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。
   

(2) 实现:

void Memory::ReleaseSpace(int ID, int Size) {
	for (int i = 0; i < deqMem.size(); ++i) {
		// 遍历内存空间，根据内存空间是否使用，以及进程标识确定回收的内存分区
		if (deqMem[i].Status && (deqMem[i].ID == ID)) {
			if (Size == deqMem[i].Size) {
				// 进程回收的内存空间大小 == 当前存储此进程内存分区的空间大小
				// 直接回收
				deqMem[i].Status = false;
				Merge(i); // 对于邻接的空闲内存分区进行合并
				unusedSize += Size;
				break;
			}
			if (Size > deqMem[i].Size) {
				// 进程回收的内存空间大小 > 当前存储此进程内存分区的空间大小
				// 回收此内存分区的空间，并继续寻找需要回收的下一个内存分区
				deqMem[i].Status = false;
				Merge(i); // 对于邻接的空闲内存分区进行合并
				unusedSize += deqMem[i].Size;
				--i;
				continue;
			}
			// 进程回收的内存空间大小 < 当前存储此进程内存分区的空间大小
			// 内存空间中加入新回收的内存分区
			deqMem[i].Size -= Size;
			Ptn.Address = deqMem[i].Address + deqMem[i].Size;
			Ptn.Size = Size;
			Ptn.Status = false;
			deqMem.insert(deqMem.begin() + i + 1, Ptn);
			Merge(i + 1); // 对于邻接的空闲内存分区进行合并
			unusedSize += Size;
			break;
		}
	}
	getLog(); // 记入日志
}

void Memory::Merge(int Index) {
	int beginAddress = deqMem[Index].Address;
	int beginIndex = Index, endIndex = Index;
	int j = Index;
	int sizeTmp = 0;
	// 向地址递减方向进行搜索，判断可以合并的空闲内存分区最小地址
	while (j >= 0 && !deqMem[j].Status) {
		beginAddress = deqMem[j].Address;
		beginIndex = j;
		sizeTmp += deqMem[j].Size;
		--j;
	}
	j = Index + 1;
	// 向地址递增方向进行搜索，判断可以合并的空闲内存分区最大地址
	while (j < deqMem.size() && !deqMem[j].Status) {
		endIndex = j;
		sizeTmp += deqMem[j].Size;
		++j;
	}
	// 对查询指针进行更新。
	searchPtrForNF -= (endIndex - beginIndex);
	// 对连续的空闲内存分区进行合并。
	deqMem.erase(deqMem.begin() + beginIndex, deqMem.begin() + endIndex + 1);
	Ptn.Address = beginAddress;
	Ptn.Size = sizeTmp;
	Ptn.Status = false;
	deqMem.insert(deqMem.begin() + beginIndex, Ptn);
}

3.6紧凑算法 (deque Memory::Compact())：
(1) 描述：
在连续分配方式中，必须把一个系统或用户程序装入一个连续的内存空间。如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻 接，也无法把该程序装入内存。
若想把作业装入，可采用的一种方法是：将内存中的所有作业进行移动，使它们全都相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该 区。这种通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方 法，称为“拼接”或“紧凑”，见图 4-9(b)。由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改(变换)，则程序必将无法执行。为此， 在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。

(2) 实现：

deque<Partition> Memory::Compact() {
	deque<Partition> deqTmp;
	int mergeSize = 0;
	// 获取需要紧凑的总的空间大小
	for (int i = 0; i < deqMem.size(); ++i) {
		if (!deqMem[i].Status) {
			mergeSize += deqMem[i].Size;
		}
	}
	// 重定位
	Ptn.Address = 0;
	Ptn.Size = mergeSize;
	Ptn.Status = false;
	deqTmp.push_back(Ptn);
	int deqTmpSize = 0;
	for (int i = 0; i < deqMem.size(); ++i) {
		if (deqMem[i].Status) {
			Ptn.ID = deqMem[i].ID;
			Ptn.Address = deqTmp[deqTmpSize].Address + deqTmp[deqTmpSize].Size;
			Ptn.Size = deqMem[i].Size;
			Ptn.Status = true;
			deqTmp.push_back(Ptn);
			++deqTmpSize;
		}
	}
	deqMem.clear();
	deqMem = deqTmp;
	deqTmp.clear();
	getLog();
	return deqMem;
}

4 系统实现

4.1执行模块实现

void CDynamicMemoryManagementDlg::OnBnClickedExecute()		//点击“执行”按钮
{
	// 
	if (m_operatingMode.GetCurSel() == 0 && m_ProcessID.GetCurSel() == 0) {//手动输入模式但是没有输入进程
		//判断调用此函数来确定哪些项目在组合框中被选中，0是手动输入，1是自动输入
		//进程选择列表和选择进程的输入方式都没有选中
		CString str;	//定义字符串类的一个对象
		m_ChangeSize.GetWindowTextW(str);
		if (str.IsEmpty() || 0 >= _ttoi(str)) {
			MessageBox(_T("尚未分配所要创建进程空间大小"), _T("警告！"), MB_OK);//弹出警告窗口内容为“尚未分配所要创建进程空间大小”
			return;
		}
		ProTmp.CreateProcess(_ttoi(str));
		if (!Mem.Allocate(ProTmp.getPSize(), m_SelectAlgorithm.GetCurSel(), ProTmp.getPID())) {//输入的进程大小大于内存空间100
			MessageBox(_T("内存空间不足"), _T("警告！"), MB_OK);
			ProTmp.decrease();
			return;
		}
		deqProcess.push_back(ProTmp);
		InsertProcessList(ProTmp.getPID(), ProTmp.getPSize());
		mapIDtoSize.insert(make_pair(ProTmp.getPID(), ProTmp.getPSize()));
		str.Format(_T("%d"), ProTmp.getPID());
		m_ProcessID.AddString(str);
	} 
	
	if (m_operatingMode.GetCurSel() == 0 && m_ProcessID.GetCurSel() != 0) {//手动输入进程的一般情况
		CString str;
		m_ChangeSize.GetWindowTextW(str);
		int toChangeSize = _ttoi(str);
		if (str.IsEmpty() || 0 == toChangeSize) {
			MessageBox(_T("尚未输入需要改变进程空间的大小"), _T("警告！"), MB_OK);
			return;
		}

		CString CStringtoChangeID;
		((CComboBox*)GetDlgItem(IDC_ProcessID))->GetWindowText(CStringtoChangeID);
		int toChangeID = _ttoi(CStringtoChangeID);
		if (toChangeSize < 0) {
			toChangeSize = -toChangeSize;			
			if (mapIDtoSize[toChangeID] < toChangeSize){
				MessageBox(_T("释放的空间过大"), _T("警告！"), MB_OK);
				return;
			}
			else{

				// 处理 Process
				if (mapIDtoSize[toChangeID] == toChangeSize){
					m_ProcessID.DeleteString(m_ProcessID.FindString(0, CStringtoChangeID));
				}
				for (int i = 0; i < deqProcess.size(); ++i) {
					if (deqProcess[i].getPID() == toChangeID) {
						if (deqProcess[i].getPSize() == toChangeSize) {
							DeleteProcessList(toChangeID);
							deqProcess.erase(deqProcess.begin() + i);
							mapIDtoSize[toChangeID] -= toChangeSize;
							break;
						}
						if (deqProcess[i].getPSize() < toChangeSize) {
							ChangeProcessList(toChangeID, -deqProcess[i].getPSize());
							deqProcess.erase(deqProcess.begin() + i);
							mapIDtoSize[toChangeID] -= deqProcess[i].getPSize();
							--i;
							continue;
						}
						ChangeProcessList(toChangeID, -toChangeSize);
						deqProcess[i].ChangeSize(-toChangeSize);
						mapIDtoSize[toChangeID] -= toChangeSize;
						break;
					}
				}
				// 处理 deqMem
				Mem.ReleaseSpace(toChangeID, toChangeSize);
				if (mapIDtoSize[toChangeID] == 0) {
					mapIDtoSize.erase(mapIDtoSize.find(toChangeID));
				}
			}
		}
		else {
			if (!Mem.Allocate(toChangeSize, m_SelectAlgorithm.GetCurSel(), toChangeID)) {
				MessageBox(_T("内存空间不足"), _T("警告！"), MB_OK);
				return;
			}
			int ans = -1;
			for (int i = 0; i < deqProcess.size(); ++i) {
				if (deqProcess[i].getPID() == toChangeID) {
					ans = i;
					break;
				}
			}
			if (ans == -1) {
				MessageBox(_T("查找进程ID失败"), _T("警告！"), MB_OK);
				return;
			}
			deqProcess[ans].ChangeSize(toChangeSize);
			mapIDtoSize[toChangeID] += toChangeSize;
			ChangeProcessList(deqProcess[ans].getPID(), toChangeSize);
		}
	}

	if (m_operatingMode.GetCurSel() == 1) {//自动生成进程的方式
		SetTimer(1, 1500, NULL);
		int totalSize = Mem.getMaxSize();
		int ChangeSize;
		srand((unsigned)(time(NULL)));//产生随机数
		if (deqProcess.size() == 0) {
			slcAlg = rand() % 4;//这个数它属于0~3，因为是用4取余数的
			m_SelectAlgorithm.SetCurSel(slcAlg);
			//0是首次适应算法；1是循环首次适应算法...
			//所以这个if语句就是在选择随机的算法
		}
		while (true) {
			ChangeSize = 1 + rand() % 100;  //随机选择进程的大小（小于100）
			if (ChangeSize > totalSize){
				break;//如果随机选到的数大于100则跳出
			}
			else totalSize -= ChangeSize;//totalSize = totalSize - ChangeSize
			int setTime = 1 + rand() % 10;
			ProTmp.CreateProcess(ChangeSize, setTime);//进程对象创造进程函数
			if (!Mem.Allocate(ProTmp.getPSize(), m_SelectAlgorithm.GetCurSel(), ProTmp.getPID())) {
				//分配到内存空间
				ProTmp.decrease();
				break;
			}
			deqProcess.push_back(ProTmp);
			InsertProcessList(ProTmp.getPID(), ProTmp.getPSize(), setTime);//将进程插入到界面右边的进程列表中
		}
		CString strTime;
		int timeTmp;
		int toChangeSize;
		for (int i = 0; i < m_ProcessLIST.GetItemCount(); ++i) {
			strTime = m_ProcessLIST.GetItemText(i, 2);//检索列表视图项或子项的文本(其文本的项，其文本的子项)，
			//并返回字符串给strTime
			timeTmp = _ttoi(strTime);//将string转换成整形
			--timeTmp;
			if (0 == timeTmp) {
				CString strID = m_ProcessLIST.GetItemText(i, 0);
				for (int j = 0; j < deqProcess.size(); ++j) {
					if (deqProcess[j].getPID() == _ttoi(strID)) {
						toChangeSize = deqProcess[j].getPSize();
						deqProcess.erase(deqProcess.begin() + j);
						getLogForAuto();
					}
				}
				Mem.ReleaseSpace(_ttoi(strID), toChangeSize);
				totalSize += toChangeSize;
				m_ProcessLIST.DeleteItem(i);
				--i;
				continue;
			}
			strTime.Format(_T("%d"), timeTmp);
			m_ProcessLIST.SetItemText(i, 2, strTime);
		}
	}
	Display(Mem.getMemStatus());
}

4.2 对话框模块实现

class CDynamicMemoryManagementDlg : public CDialogEx		//定义本项目的对话框，派生于CDialogEx类
{
// 构造，公有继承于CDialogEx类
public:
	CDynamicMemoryManagementDlg(CWnd* pParent = NULL);	// 标准构造函数

// 对话框数据
	enum { IDD = IDD_DYNAMICMEMORYMANAGEMENT_DIALOG };

	protected:
	virtual void DoDataExchange(CDataExchange* pDX);	// DDX/DDV 支持


// 实现
protected:
	HICON m_hIcon;

	// 生成的消息映射函数
	virtual BOOL OnInitDialog();
	afx_msg void OnSysCommand(UINT nID, LPARAM lParam);
	afx_msg void OnPaint();
	afx_msg HCURSOR OnQueryDragIcon();
	DECLARE_MESSAGE_MAP()
public:
	afx_msg void OnCbnSelchangeoperatingmode();
	CComboBox m_operatingMode;		// 定义选择进程产生方式的一个对象
	CComboBox m_SelectAlgorithm;	// 定义选择分配算法方式的一个对象
	afx_msg void OnBnClickedExecute();
	// 手工创建进程空间大小
	//CEdit m_InitialSize;
private:
	Memory Mem;		//定义一个memory的对象，也就是这个类中的数据成员是一个对象，而我们又知道对象是一个类的实体
	int slcAlg;
	ofstream outFile;		//字符类型
	const string FileProcessLog = "ProcessLog";
public:
	afx_msg void OnCbnSelchangeProcessid();
public:
	deque<Process> deqProcess;	//定义双端队列，其中的每一个元素都是Process类的对象
	//也就是说到目前已经发现了两个双端队列一个是进程类对象的，另一个是内存分区的
	//deque是一个双端队列，它其中的一个元素有多大就用：队列名.size来表示
	Process ProTmp;
	
	CComboBox m_ProcessID;		// 定义进程ID对象，因为CComboBox是一个派生于cwnd类的类
	void Display(deque<Partition> deqMem);
	void DisplayProcessList(deque<ProcessMemVar> deqProcessVar);
	void InsertProcessList(int ID, int Size);
	void DeleteProcessList(int ID);
	void ChangeProcessList(int ID, int Size);
	int Cbmm_ProcessIDIndex;

	CEdit m_ChangeSize;	// 改变进程空间大小
	map<int, int> mapIDtoSize;	//相当于int数组
	afx_msg void OnBnClickedDefrag();
	//afx_msg void OnLvnItemchangedList1(NMHDR *pNMHDR, LRESULT *pResult);

	CListCtrl m_ProcessLIST;	// 显示进程情况
	afx_msg void OnLvnItemchangedProcesslist(NMHDR *pNMHDR, LRESULT *pResult);
	afx_msg void OnBnClickedProcessstop();
	afx_msg void OnBnClickedReplay();
	afx_msg void OnBnClickedReset();//声明mfc类的函数afx_msg
	void OnDraw(CDC* pDC, CRect rt, int x, int y, int z);

	CButton m_ProcessStop;	// 终止进程
	void CDynamicMemoryManagementDlg::InsertProcessList(int ID, int Size, int Time);
	afx_msg void OnTimer(UINT_PTR nIDEvent);

	CButton m_RePlay;	// 回放
	void getLog();
	void getLogForAuto();
	void initListControl();
};

4.3 进程终止按钮模块实现

void CDynamicMemoryManagementDlg::OnBnClickedProcessstop()//进程终止按钮
{
	
	CString toStopID;//选中需要终止的进程ID
	m_ProcessID.GetWindowTextW(toStopID);
	if (toStopID == "创建ID中...") {
		MessageBox(_T("请选中ID"), _T("警告！"), MB_OK);
		return;
	}
	int toChangeID = _ttoi(toStopID), toChangeSize = mapIDtoSize[_ttoi(toStopID)];//通过返回的ID值找到其大小
	//因为map<int,int>左边是键，右边是值，只能由左边找到右边
	for (int i = 0; i < deqProcess.size(); ++i) {
		if (deqProcess[i].getPID() == toChangeID) {//要删除的ID是否相等
			if (deqProcess[i].getPSize() == toChangeSize) {//要删除的大小是否相等
				DeleteProcessList(toChangeID);//若两者都相等就调用DeleteProcessList函数进行删除
				deqProcess.erase(deqProcess.begin() + i);
				mapIDtoSize.erase(mapIDtoSize.find(toChangeID));
				break;
			}
		}
	}
	// 处理 deqMem
	m_ProcessID.DeleteString(m_ProcessID.FindString(0, toStopID));
	Mem.ReleaseSpace(toChangeID, toChangeSize);
	Display(Mem.getMemStatus());
}

5 系统测试

进程手工输入：
1、创建7个进程，所需空间大小分别为：5、10、15、20、5,、10、15

2、终止进程2：

3、算法结果验证与对比：（注：总内存大小为100）
（1）首次适应算法
理论分析：从“内存变化”的视图中我们可以看出来，左边有15的内存空间可以使用，右边有20的内存空间可以使用，如果此时我们再输入一个大小为7的进程并且采用首次适应算法，那这个进程应该在左边的15的内存处，而不是右边20的内存处。
实际结果：

（2）循环首次适应算法
理论分析：此时左边的空闲大小为8，如果此时再输入一个大小为9的进程，根据循环首次适应算法，它应该在右边，因为按理来说上次分配是在左边分配的，但是左边不够，只能再向后寻找，若再输入一个大小为5的进程，它应该在大小为9的进程右边，因为上次分配内存就是在这儿分配的，并且大小也够用。
实际结果：

（3）最佳适应算法
理论分析：删除若干进程以便再次输入进程验证， 若此时分配一个大小为5的进程，那就应该刚好在中间那个大小为10的空闲区域分配，因为最佳适应算法是把所有的空闲分区进行从小到大排序的。
实际结果：

（4）最坏适应算法：
理论分析：在上图的基础上进行创建大小为10的进程，此进程应该位于最右边大小为20的空闲区当中，因为最坏适应算法是将所有空闲区域从大到小排列的，并且总是把大空间最先分配出去。
实际结果：

4、相邻空闲区合并：
对上图进行终止若干进程，进行空闲区合并，终止ID为0的进程：

再终止ID为1的进程：

发现已经对空闲区进行了合并。
5、碎片整理：

6 设计小结

在使用MFC设计图形应用程序时遇到过很多问题，例如将程序界面的按钮和相关函数关联起来的方法所知甚少，不得不求助与一些博客论坛还有B站相关教学视频，学到了很多东西，总体感觉下来MFC的使用还是挺简单的，没有什么太难的地方，大多都是些知识性的东西，只要熟练掌握就可以写出来。
对于四个适应算法的代码自己写出来还是有许多BUG，通过在网上求助，以及和同学讨论之后都一一解决，在这过程中又一次理解了这四种适应算法的优点以及缺点。

参考文献
[1] 汤小丹、梁红兵、哲凤屏、汤子瀛 编著.计算机操作系统（第四版）.西安：西安电子科技大学出版社，2014.05
[2] Randal E. Bryant，David R.O Hallaren 著.深入理解计算机系统（第二版）.北京:机械工业出版社，2015.04
[3] 侯俊杰编著. 深入浅出MFC.松岗工业出版社，1997

7 如何运行项目？

用vs打开文件夹中的DynamicMemoryManagement.sln直接运行就可以得到结果