带有详细注释的操作系统首次适应法C++程序-创新互联

• • 内容简介
  • 程序代码
  • 运行效果

操作系统实验课程的任务，使用首次适应算法完成内存的分配与回收。
下面的代码可以实现用户指定的内存初始化、内存分配、内存回收和连续随机回收内存直到得到一个完整内存空间的操作。

#include#include#include#include#include#includeusing namespace std;

//前向引用声明
struct AllocMem;                      
struct FreeMem;

static unsigned Memspace;             //定义内存空间的总大小（以KB为单位）
static string errorMessage;           //记录创建内存分区时的错误信息的字符串
static listAllocted_List;  //借助C++STL的链表结构定义已分配分区链
static listFree_List;        //借助STL链表结构定义的空闲分区链

//以结构体的形式定义每一个已分配内存分区，内容包括起始地址、分区大小和程序号
struct AllocMem
{unsigned Start_Address;  //内存分区的开始地址（之所以用unsigned类型表示是为了突出地址只能为非负数），以KB为单位
	unsigned size;           //内存分区的大小（之所以用unsigned类型是为了表示分区大小只能为非负数）
	unsigned processID;      //内存分区对应的程序号，基于类似的原因仍然使用unsigned类型定义

	//结构体的显式构造函数，参数为起始地址、分区大小和程序号，采用内联形式以进一步提高执行效率
	explicit inline AllocMem(const unsigned& Start_Address, const unsigned& size, const unsigned& processID) :\
		                     Start_Address(Start_Address), size(size), processID(processID) {}
};

//同样以结构体的形式定义未分配内存分区，内容包括起始地址和大小
struct FreeMem
{unsigned Start_Address;  //内存分区的开始地址（之所以用unsigned类型表示是为了突出地址只能为非负数），以KB为单位
	unsigned size;           //内存分区的大小（之所以用unsigned类型是为了表示分区大小只能为非负数）

	//与已分配内存分区类似的显式构造函数
	explicit inline FreeMem(const unsigned& Start_Address, const unsigned& size) :Start_Address(Start_Address), size(size) {}
};

//用于判断新加入的内存分区是否有效的函数，根据已有的内存分区表和新加入的内存分区信息作为参数，返回布尔值
bool isValid(const list& Allocted_List, const unsigned& Start_Address, const unsigned& size, const unsigned& processID,const unsigned& Memspace)
{//通过C++STL的增强型for循环逐一检查新增加的内存分区是否与之前的内存分区存在矛盾
	for (auto& element : Allocted_List)
	{//第一种矛盾情况：发生进程号重复
		if (element.processID == processID)
		{	errorMessage = "进程号重复！";
			return false;
		}
		//第二种矛盾情况：发生内存分区空间重合
		if (!(Start_Address >= element.Start_Address + element.size || Start_Address + size<= element.Start_Address))
		{	errorMessage = "内存空间重合！";
			return false;
		}
		//第三种矛盾情况：分配空间高地址大于内存空间大地址
		if (Start_Address + size >Memspace)
		{	errorMessage = "超过内存空间大小！";
			return false;
		}
	}
	//不存在矛盾，因此返回true值
	return true;
}

//用于输出某一时刻的分区信息的函数
void print(void)
{cout<<"分区号      "<<  "起始地址    "<<  "分区大小    "<<  "进程号      "<< endl;

	list::iterator it1(Allocted_List.begin());  //记录已分配分区链的遍历位置的迭代器
	list::iterator it2 (Free_List.begin());      //记录空闲分区链的遍历位置的迭代器
	unsigned pos(1);                                      //记录当前的分区号

	//当两个链表都还未遍历完成时持续进行循环
	while (it1 != Allocted_List.end() && it2 != Free_List.end())
	{//通过比较两个链表中当前节点的起始地址属性，可以得知需要先按顺序输出哪一个节点的信息
		if (it1->Start_Address< it2->Start_Address)
		{	cout<< setw(6)<< setiosflags(ios::right)<< pos++<< setw(14)<< setiosflags(ios::right)<< it1->Start_Address \
				<< setw(12)<< setiosflags(ios::right)<< it1->size<< setw(10)<< setiosflags(ios::right)<< it1->processID<< endl;
			it1++;
		}
		else
		{	cout<< setw(6)<< setiosflags(ios::right)<< pos++<< setw(14)<< setiosflags(ios::right)<< it2->Start_Address \
				<< setw(12)<< setiosflags(ios::right)<< it2->size<< setw(10)<< setiosflags(ios::right)<< "无进程"<< endl;
			it2++;
		}
	}
	//循环结束时，已经完成遍历了一个链表，那么就继续将另一个链表中的信息输出（类似于数据结构中的归并排序中的归并过程）
	//第一种情况：已分配内存分区链表先完成遍历
	if (it1 == Allocted_List.end())
	{while (it2 != Free_List.end())
		{	cout<< setw(6)<< setiosflags(ios::right)<< pos++<< setw(14)<< setiosflags(ios::right)<< it2->Start_Address \
				<< setw(12)<< setiosflags(ios::right)<< it2->size<< setw(10)<< setiosflags(ios::right)<< "无进程"<< endl;
			it2++;
		}
	}
	//第二种情况：空闲分区链表先完成遍历
	else
	{while (it1 != Allocted_List.end())
		{	cout<< setw(6)<Start_Address \
				<< setw(12)<size<< setw(10)<< setiosflags(ios::right)<< it1->processID<< endl;
			it1++;
		}
	}
	cout<< endl;
}

//使用首次适应法进行内存分区分配的函数
void FF_Allocate(void)
{unsigned pid;   //记录进程号
	unsigned space; //记录空间大小

	//获取用户输入的进程号和空间大小
	cout<< "请输入所需分配内存的进程的进程号：";
	cin >>pid;
	cout<< "请输入分配空间的大小：";
	cin >>space;

	//遍历已分配进程表，判读进程号是否重复
	for (auto& e : Allocted_List)
	{if (e.processID == pid)
		{	cout<< "进程号重复，本次分配内存空间结束！"<< endl;
			return;
		}
	}

	//循环遍历空闲分区链，找到第一个可以容纳当前进程的内存分区
	list::iterator it = Free_List.begin();
	while (true)
	{//当前内存分区的容量足够容纳用户进程的情况
		if (it->size >= space)
		{	//记录分区的起始位置
			unsigned start = it->Start_Address;
			//首先修改空闲分区链中的相应内容
			//情况1：该内存分区的容量刚好与用户进程所需内存容量相同
			if (it->size == space)
			{		//从空闲分区表中删除当前的空闲分区，表示该分区已经被分配
				auto it2 = it;
				Free_List.erase(it2);
			}
			//情况2：该内存分区的容量大于用户，则将该分区的一部分分配给用户进程
			else
			{		it->Start_Address += space;  //修改分区的起始地址
				it->size -= space;           //修改分区的容量大小
			}

			//接下来修改已分配分区链中的相应内容，那么就需要找到插入节点的位置，通过遍历的方式进行
			auto pos = Allocted_List.begin();
			while (pos!=Allocted_List.end())
			{		//如果当前所遍历到的内存分区的起始地址小于插入新分区的起始地址，则继续向后遍历
				if (pos->Start_Address< start)
				{pos++;
				}
				//找到了一个合适的添加位置的情况，操作完成后函数直接返回
				else
				{//第一种情况：之前所有已分配分区的起始地址都小于当前分区的起始地址，则直接在尾部添加
					if (pos == Allocted_List.end())
					{AllocMem* tempSpace = new AllocMem(start, space, pid);
						Allocted_List.push_back(*tempSpace);
					}
					//第二种情况：新分配分区的位置在两个已有分配区域的中间，则从中间插入
					else
					{AllocMem* tempSpace = new AllocMem(start, space, pid);
						Allocted_List.insert(pos, *tempSpace);
					}
					cout<< "已经成功为新进程分配分区！"<< endl;
					cout<< endl;
					return;
				}
			}
			//迭代完成后如果没有找到插入位置，则在链表尾部进行添加
			if (pos == Allocted_List.end())
			{		AllocMem* tempSpace = new AllocMem(start, space, pid);
				Allocted_List.push_back(*tempSpace);
				cout<< "已经成功为新进程分配分区！"<< endl;
				cout<< endl;
				return;
			}
		}
		//当前内存分区不足以容纳用户进程，则继续考察下一个内存分区
		else
		{	it++;
		}
	}
	//循环退出，表示经过遍历后仍然没有找到足够用户进程的内存分区，则输出提示信息
	cout<< "没有找到满足大小的空闲分区，分区分配失败！"<< endl;
	return;
}

//用于释放进程的函数
void SetFree(const unsigned& pid)
{//通过遍历的方式来找到指定进程号的已分配分区
	auto it1 = Allocted_List.begin();
	while (it1 != Allocted_List.end())
	{//第一种情况：当前遍历到的进程对应的进程号和用户输入的不同，则继续考察下一个进程
		if (it1->processID != pid)
		{	it1++;
		}
		//第二种情况：当前遍历到的进程对应的进程号就是用户所输入的进程号，那么就处理这个进程
		else
		{	//首先记录当前分区的起始地址和大小
			unsigned start = it1->Start_Address;
			unsigned size = it1->size;
			//从已分配分区链表中将这个分区删除
			Allocted_List.erase(it1);

			//接下来处理空闲分区链表，找到将这块分区归还所应该存放的位置

			//首先考虑空闲分区链表为空的情况
			if (Free_List.size() == 0)
			{		FreeMem* tempSpace = new FreeMem(start, size);
				Free_List.push_back(*tempSpace);
				cout<< "已经成功删除指定进程的内容！"<< endl;
				cout<< endl;
				return;
			}
			auto it2 = Free_List.begin();
			while (it2!=Free_List.end())
			{		//对于当前迭代器所指示的内存分区首地址小于当前分区起始地址的情况，则继续向后遍历
				if (it2->Start_Address< start)
				{it2++;
				}
				//对于找到了合适的位置的情况，则需要分情况进行讨论（共有4种情况）
				else
				{//首先考虑从链表头部进行添加的情况
					if (it2 == Free_List.begin())
					{//第一种情况：归还分区与下一个分区右相邻，则修改下一个分区的起始地址和大小即可
						if (start + size == it2->Start_Address)
						{	it2->Start_Address = start;
							it2->size += size;
						}
						//第二种情况：归还分区与下一个分区不相邻，则需要创建一个新的节点从空闲分区链的头部插入
						else
						{	FreeMem* tempSpace = new FreeMem(start, size);
							Free_List.push_front(*tempSpace);
						}

						cout<< "已经成功删除指定进程的内容！"<< endl;
						cout<< endl;
						return;
					}

					//找到当前遍历位置的前一个位置进行分析
					auto temp0 = it2;
					auto temp1 = (--temp0);

					//第一种情况：当前新插入的分区与前后两个分区都不是紧邻的，则直接插入即可
					if (temp1->Start_Address + temp1->size< start&&it2->Start_Address>(start+size))
					{FreeMem* tempSpace = new FreeMem(start, size);
						Free_List.insert(it2,*tempSpace);
					}
					//第二种情况：当前新插入的分区与前一个分区紧邻，与后一个分区存在间隔，则修改前一个分区的大小即可
					else if(temp1->Start_Address+temp1->size==start&& start && it2->Start_Address >(start + size))
					{temp1->size += size;
					}
					//第三种情况：当前新插入的分区与后一个分区紧邻，与前一个分区存在间隔，则修改后一个分区的起始地址和大小即可
					else if (temp1->Start_Address + temp1->sizeStart_Address ==(start + size))
					{it2->Start_Address = start;
						it2->size += size;
					}
					//第四种情况：当前新插入的分区与前后两个分区都紧邻，则将三个分区进行合并
					else
					{temp1->size = temp1->size + size + it2->size;
						Free_List.erase(it2);
					}
					
					//操作完成，向用户输出提示信息
					cout<< "已经成功删除指定进程的内容！"<< endl;
					cout<< endl;
					return;
				}
			}
			//遍历完成后没有找到可以插入的地方，说明归还的内存分区位于内存空间的末尾，此时有两种情况
			it2--;
			//第一种情况：该内存分区与前一个内存分区紧邻，则修改前一个空闲内存分区的大小即可
			if (it2->Start_Address + it2->size == start)
			{		it2->size += size;
			}
			//第二种情况：该内存分区与前一个内存分区不紧邻，则向空闲分区链表中新增加一个节点
			else
			{		FreeMem* tempSpace = new FreeMem(start, size);
				Free_List.push_back(*tempSpace);
			}
			//输出结束提示信息
			cout<< "已经成功删除指定进程的内容！"<< endl;
			cout<< endl;
			return;
		}
	}
	//遍历完所有现存进程都没有找到指定进程号的进程，那么输出提示信息
	cout<< "不存在指定进程号的内存分区，本次释放进程过程结束！"<< endl;
	return;
}

//随机删除且进行过程展示的函数
void Multiple_Random_Delete(void)
{//首先记录链表长度
	size_t length = Allocted_List.size();
	for (; length >0; length--)
	{//记录随机删除的位置
		int randNum = rand() % length;

		list::iterator it = Allocted_List.begin();
		for (unsigned pos (0); pos< length - 1; ++pos)
		{	it++;
		}
		//将指定位置的元素删除
		cout<< "本次随机删除的进程的进程号为为："<< it->processID<< endl;
		SetFree(it->processID);
		
		//显式删除后的效果
		print();
	}
}

int main(void)
{//定义初始状态下内存分区的个数
	unsigned AllocMem_Num;         

	//获取用户输入的内存空间的总大小，此处为方便起见并考虑实际情况，选择使用KB作为单位
	cout<< "请输入内存空间的大小（单位为KB）：";
	cin >>Memspace;
	cout<< endl;

	//获取用户输入的初始状态下进程个数，接下来获取初始状态下每一个进程内存分区的信息
	cout<< "请输入初始状态下的进程个数：";
	cin >>AllocMem_Num;
	cout<< "接下来请按照起始地址的递增顺序逐一输入初始状态下每个内存分区的信息："<< endl;
	cout<< endl;
	for (unsigned i(0); i< AllocMem_Num; ++i)
	{unsigned startAddress;
		unsigned size;
		unsigned processID;

		//获取当前内存分区的起始地址
		cout<< "请输入第"<< (i + 1)<< "个内存分区的起始地址（以KB为单位）：";
		cin >>startAddress;
		//获取当前内存分区的分区大小
		cout<< "请输入第"<< (i + 1)<< "个内存分区的分区大小：";
		cin >>size;
		//获取当前内存分区的进程号
		cout<< "请输入第"<< (i + 1)<< "个内存分区对应的进程号：";
		cin >>processID;

		//首先通过自定义的函数判断输入的内存分区是否有效，即不存在分区重叠、进程号重名和超过空间大小
		if (isValid(Allocted_List,startAddress, size, processID,Memspace) == true)
		{	//以结构体的形式创建一个新的已分配内存分区
			AllocMem* tempSpace = new AllocMem(startAddress, size, processID);
			//将新创建的内存分区从尾部插入已分配内存分区链中
			Allocted_List.push_back(*tempSpace);
		}
		//如果内存分区无效，则输出无效原因的提示信息，同时程序终止
		else
		{	cout<< "程序错误信息："<< errorMessage<< endl;
			return 0;
		}
		cout<< endl;
	}

	//接下来对空闲分区链表进行初始化
	list::iterator it1 = Allocted_List.begin();
	//首先判断首地址为0的一段地址空间是否已经被分配
	if (it1->Start_Address != 0)
	{FreeMem* tempSpace = new FreeMem(0, it1->size);
		Free_List.push_back(*tempSpace);
	}
	//通过遍历的方式逐一获取每一段空闲分区的起始地址和大小
	list::iterator it2 = (--Allocted_List.end());
	for(; it1 != it2; it1++)
	{//上一个已分配内存分区的终止位置就是该空闲分区的起始位置
		unsigned start = it1->Start_Address + it1->size;
		//空闲分区的大小即下一个已分配内存分区的起始地址和该空闲分区的起始位置的差值
		list::iterator it3 = (++it1);
		it1--;
		unsigned size = it3->Start_Address-start;
		//如果差值为零则说明两个已分配的内存分区紧邻，此时两者之间不存在空闲分区，因此跳过本次循环
		if (size == 0)continue;
		//大小不为零时，创建一个新的未分配内存分区并将其放入空闲分区表中
		FreeMem* tempSpace = new FreeMem(start, size);
		Free_List.push_back(*tempSpace);
	}
	//判断最后一个已分配分区是否与内存大小的上界紧邻，如果不紧邻则再增加一个空闲分区进入空闲分区链中
	unsigned lastPos = it2->Start_Address + it2->size;
	if (lastPos< Memspace)
	{FreeMem* tempSpace = new FreeMem(lastPos, Memspace - lastPos);
		Free_List.push_back(*tempSpace);
	}

	//初始化工作完成，输出内存分区结果
	cout<< "初始化工作完成，下面输出内存分区的结果："<< endl;
	//通过调用自定义的print函数输出结果
	print();
	char ch = getchar();

	//接下来由用户通过键盘输入指定操作类型来完成对应类型的操作（包括进程的创建、删除、多次随机删除过程展示和退出程序）
	while (true)
	{char cmd; //记录用户的操作类型
		cout<< "请输入您需要进行的操作（C创建进程，D删除进程，M多次随机删除过程展示，P当前内存分区展示，Q退出程序）：";
		cmd = getchar();

		//根据用户的操作类型调用不同的函数处理
		switch (cmd)
		{//创建进程操作
		case 'C': {FF_Allocate(); break; }
		//删除进程操作
		case 'D': 
		{	unsigned pid;
			//获取用户输入的需要释放空间的进程号
			cout<< "请输入需要释放内存空间的进程号：";
			cin >>pid;

			SetFree(pid); 
			break; 
		}
		//多次随机删除过程展示
		case 'M': {Multiple_Random_Delete(); break; }
		//当前内存分区展示
		case 'P': {print(); break; }
		//退出程序
		case 'Q': {cout<< "程序退出！"<< endl; return 0; break; }
		//其余情况处理（充分考虑程序的鲁棒性）
		default: {cout<< "无法识别您的命令，请重新输入。"<< endl; cout<< endl; break; }
		}
		cmd = getchar();
	}
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧