操作系统实验二：银行家算法

• • 操作系统实验二：银行家算法
• 一、实验目的
• 二、实验要求及内容
• 三、实验代码
• 四、实验结果截图
• 五、实验总结

1. 了解死锁避免的原理。
2. 研究银行家算法的实现方法。

1. 编程实现银行家算法，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁的避免死锁的具体实施方案。
2. 列出调试通过程序的清单，并附上文档说明。
3. 总结上机调试过程中遇到的问题和解决方法及感想。

// 银行家算法.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include 
#include
#include
#include 
 
using namespace std;
int num_Process = 0;
int num_Source = 0;
vectorTotalSource;
vectorAvailable ;
vectorRequest;
vector nameSource;
vectorSucceesName;
vector work;
vector workallocation;
 
class BankObject
{
private:
	char name;
	vector max;
	vector allocation;
	vector need;
	bool finish;
public:
	BankObject(char pname,vectorpmax, vectorpallocation,vectorpneed) :
		name(pname),max(pmax), allocation (pallocation),need(pneed)
	{
		finish = 0;
	}
	operator vector() const
	{
		return need;
	}
	vector& Max()
	{
		return max;
	}
	const vector& Max()const 
	{
		return max;
	}
	char& Name()
	{
		return name;
	}
	const char& Name()const
	{
		return name;
	}
	vector& Allocation()
	{
		return allocation;
	}
	const vector& Allocation()const
	{
		return allocation;
	}
	vector& Need()
	{
		return need;
	}
	const vector& Need()const
	{
		return need;
	}
	bool & Finish()
	{
		return finish;
	}
	const  bool & Finish()const
	{
		return finish;
	}
};
class Manage
{
private:
	vector ProList;
public:
	//初始化各个进程的Max，Allocation，Need向量
	void Add(BankObject process)
	{
		ProList.push_back(process);
	}
 
	void SetWorkAvailable()
	{
		for (int i = 0; i < num_Source; i++)
		{
			for (int j = 0; j < num_Process; j++)
			{
				Available[i] = Available[i] - ProList[j].Allocation()[i];
			}
		}		
		work = Available;
	}
	
	void CalTotolSource()
	{
		TotalSource = Available;
		for (int i = 0; i < num_Source; i++)
		{
			for (int j = 0; j < num_Process; j++)
			{
				TotalSource.push_back( TotalSource[i] + ProList[j].Allocation()[i]);
			}
		}
	}
	void CalMax()
	{
		for (int i = 0; i < num_Process; i++)
		{
			for (int j = 0; j < num_Source; j++)
			{
				ProList[i].Max()[j] = ProList[i].Allocation()[j] + ProList[i].Need()[j];
			}
		}
	}
	void CalNeed()
	{
		for (int i = 0; i < num_Process; i++)
		{
			for (int j = 0; j < num_Source; j++)
			{
				ProList[i].Need()[j] = ProList[i].Max()[j] - ProList[i].Allocation()[j];
			}
		}
	}
	void CalAllocation()
	{
		for (int i = 0; i < num_Process; i++)
		{
			for (int j = 0; j < num_Source; j++)
			{
				ProList[i].Allocation()[j] = ProList[i].Max()[j] - ProList[i].Need()[j];
			}
		}
	}
	bool Compare(BankObject obj1, vectorwork)
	{
		bool success = true;
		for (int i = 0; i < num_Source; i++)
		{
			if (obj1.Need()[i] > work[i])//安全性算法Step1：比较不成功
			{
				success = false;
			}
		}
		return success;
	}
 
	bool SafeCheak()
	{
		cout << "资源  " << setw(2) << "Work" << setw(8) << "Need" << setw(13) << "Allocation" << setw(17) << "Work+Allocation" << setw(8) << "Finish" << endl;
		cout << "进程" << setw(4);
		for (int j = 0; j < 4; j++)
		{
			cout << setw(3);
			if (j == 2)
			{
				cout << setw(4);
			}
			if (j == 3)
			{
				cout << setw(8);
			}
			for (int i = 0; i < num_Source; i++)
			{
				cout << nameSource[i] << " ";
			}
		}
		cout << endl;
		bool success = 0;
		int tag = 0;
		//Step1：设置两个工作向量（已完成）
		//Step2：从进程集合中找满足条件的进程
		for (int k = 0, count = 0; k < num_Process; k++)
		{
			for (int i = 0; i < num_Process; i++)
			{
				if (ProList[i].Finish() == 0 && Compare(ProList[i], work))
				{
					//打印通过安全检查进程的Work，Need，Allocation
					SucceesName.push_back(i);
					cout << "P" << i << setw(4) << "|";
					for (int j = 0; j < num_Source; j++)
					{
						cout << work[j];
						if (j + 1 == num_Source)
						{
							cout << "|";
							break;
						}
						cout << " ";
					}
					cout << setw(2) << "|";
					for (int j = 0; j < num_Source; j++)
					{
						cout << ProList[i].Need()[j];
						if (j + 1 == num_Source)
						{
							cout << "|";
							break;
						}
						cout << " ";
					}
 
					ProList[i].Finish() = 1;
 
					//打印Work+Allocation矩阵，
					cout << setw(3) << "|";
					for (int j = 0; j < num_Source; j++)
					{
						cout << ProList[i].Allocation()[j];
						if (j + 1 == num_Source)
						{
							cout << "|";
							break;
						}
						cout << " ";
					}
					for (int j = 0; j < num_Source; j++)
					{
						work[j] = work[j] + ProList[i].Allocation()[j];
					}
					cout << setw(7) << "|";
					for (int j = 0; j < num_Source; j++)
					{
						cout << work[j];
						if (j + 1 == num_Source)
						{
							cout << "|";
							break;
						}
						cout << " ";
					}
					cout << setw(10) << "|" << ProList[i].Finish() << "|" << endl;
					count++;//找到一个安全序列
					if (count == num_Process)//找到所有的安全序列
					{
 
						success = 1;
						//打印安全序列
						cout << "------------***^*^***-------------" << endl;
						cout << "系统处于安全状态，可以找到一个安全序列{";
						for (int j = 0; j < num_Process; j++)
						{
							cout << "P";
							cout << SucceesName[j] << "，";
						}
						cout << "}" << endl;
						cout << "------------***^*^***-------------" << endl;
						goto end;
					}
				}
			}
		}
		if (success == 0)//没有找到安全序列
		{
			cout << "------------***^*^***-------------" << endl;
			cout << "该系统未处于安全状态！" << endl;
			cout << "------------***^*^***-------------" << endl;
		}
		
	end:
		for (int i = 0; i < num_Process; i++)
		{
			ProList[i].Finish() = 0;
		}
		return success;
	}
	//processi是要请求的进程序列
	void BankAlgorithm(int processi)
	{
		//Step1：
		bool success = 1;
		for (int j = 0; j < num_Source; j++)
		{
			if (Request[j] > ProList[processi].Need()[j])
			{
				success = 0;
				cout << "该进程所申请的资源数量已经超过他所宣布的最大值！" << endl;
			}
		}
		//其余步骤都是在step1执行成功的条件下执行的
		//Step2：
		if (success)
		{
			for (int j = 0; j < num_Source; j++)
			{
				if (Request[j] > Available[j])
				{
					success = 0;
					cout << "系统尚无足够资源！P"<
			for (int j = 0; j < num_Source; j++)
			{
				Available[j] = Available[j] - Request[j];
				ProList[processi].Allocation()[j] = ProList[processi].Allocation()[j] + Request[j];
				ProList[processi].Need()[j] = ProList[processi].Need()[j] - Request[j];
			}
			work = Available;
			success = SafeCheak();
			if (success == 0)//安全性检查未通过
			{
				//回收刚才试分配的资源
				for (int j = 0; j < num_Source; j++)
				{
					Available[j] = Available[j] + Request[j];
					ProList[processi].Allocation()[j] = ProList[processi].Allocation()[j] - Request[j];
					ProList[processi].Need()[j] = ProList[processi].Need()[j] + Request[j];
				}
				work = Available;
			}
		}
	}
	void Print_T0()
	{
		cout << "资源  " << setw(3) << "Max" << setw(13) << "Allocation" << setw(6) << "Need" << setw(11) << "Available" << endl;
		cout << "进程" << setw(4);
		for (int j = 0; j < 4; j++)
		{
			cout << setw(3);
			if (j == 2)
			{
				cout << setw(4);
			}
			if (j == 3)
			{
				cout << setw(5);
			}
			for (int i = 0; i < num_Source; i++)
			{
				cout << nameSource[i] << " ";
			}
		}
 
		cout << endl;
		for (int i = 0; i < num_Process; i++)
		{
 
			cout << "P" << i << setw(4) << "|";
			for (int j = 0; j < num_Source; j++)
			{
				cout << ProList[i].Max()[j];
				if (j + 1 == num_Source)
				{
					cout << "|";
					break;
				}
				cout << " ";
			}
			cout << setw(2) << "|";
			for (int j = 0; j < num_Source; j++)
			{
				cout << ProList[i].Allocation()[j];
				if (j + 1 == num_Source)
				{
					cout << "|";
					break;
				}
				cout << " ";
			}
			cout << setw(3) << "|";
			for (int j = 0; j < num_Source; j++)
			{
				cout << ProList[i].Need()[j];
				if (j + 1 == num_Source)
				{
					cout << "|";
					break;
				}
				cout << " ";
			}
			if (0 == i)
			{
				cout << setw(3) << "|";
				for (int j = 0; j < num_Source; j++)
				{
					cout << Available[j] << setw(2);
				}
				cout << "|";
			}
			cout << endl;
		}
	}
	
	void Menu()
	{
		cout << "**********^^^*^^^********" << endl;
		cout << "1.显示当前资源情况" << endl;
		cout << "2.安全性检查" << endl;
		cout << "3.请求资源" << endl;
		cout << "4.退出本系统" << endl;
		cout << "**********^^^*^^^********" << endl;
	}
	void InitMenu()
	{
		cout << "1.输入Max，allocation，totalsource" << endl;
		cout << "2.输入allocation，need，available" << endl;
		cout << "3.输入Max，Need，available" << endl;
	}
};
void CharName()
{
	for (int i = 0; i < num_Source; i++)
	{
		nameSource.push_back(i + 65);
	}
}
 
int main()
{
	Manage process;
	bool success;
	int choose = 0;
	int processi = 0;
	char end = 'y';
	vector num_Max;
	vector num_Allocation;
	vector num_Need;
	int requestsourcenum = 0;
	cout<<"现在开始进行初始化："<> num_Process;
	cout << "请输入资源的数量：";
	cin >> num_Source;
	CharName();
	int valueAvailable = 0;
	int valueMax = 0, valueAllocation = 0, valueNeed = 0;
	int init = 0;
	process.InitMenu();
	way:
	cout << "请选择初始化方式：";
	cin >> init;
	if (1 == init)
	{
		for (int i = 0; i < num_Source; i++)
		{
			cout << "请输入资源" << nameSource[i] << "的总量：";
			cin >> valueAvailable;
			TotalSource.push_back(valueAvailable);
		}
		for (int i = 0; i < num_Process; i++)
		{
			cout << "请输入进程P" << i << "的Max：";
			for (int j = 0; j < num_Source; j++)
			{
				cin >> valueMax;
				num_Max.push_back(valueMax);
			}
			cout << "请输入进程P" << i << "的Allocation：";
			for (int j = 0; j < num_Source; j++)
			{
				cin >> valueAllocation;
				num_Allocation.push_back(valueAllocation);
				num_Need.push_back(0);
			}
			BankObject obj1(i, num_Max, num_Allocation,num_Need);
			process.Add(obj1);
			num_Max.clear();
			num_Allocation.clear();
			num_Need.clear();
		}		
		Available = TotalSource;
		process.CalNeed();
		process.SetWorkAvailable();
	}
	else if(2==init)
	{
		for (int i = 0; i < num_Process; i++)
		{
			
			cout << "请输入进程P" << i << "的Allocation：";
			for (int j = 0; j < num_Source; j++)
			{
				cin >> valueAllocation;
				num_Allocation.push_back(valueAllocation);
			}
			cout << "请输入进程P" << i << "的Need：";
			for (int j = 0; j < num_Source; j++)
			{
				cin >> valueNeed;
				num_Need.push_back(valueNeed);
				num_Max.push_back(0);
			}
			BankObject obj1(i, num_Max, num_Allocation,num_Need);
			process.Add(obj1);
			num_Max.clear();
			num_Allocation.clear();
			num_Need.clear();
		}
		for (int i = 0; i < num_Source; i++)
		{
			cout << "请输入资源" << nameSource[i] << "的available：";
			cin >> valueAvailable;
			Available.push_back(valueAvailable);
		}
		//计算各资源的总数
		process.CalTotolSource();
		process.CalMax();
		work = Available;
	}
	else if (3 == init)
	{
		for (int i = 0; i < num_Process; i++)
		{
 
			cout << "请输入进程P" << i << "的Max：";
			for (int j = 0; j < num_Source; j++)
			{
				cin >> valueMax;
				num_Max.push_back(valueMax);
			}
			cout << "请输入进程P" << i << "的Need：";
			for (int j = 0; j < num_Source; j++)
			{
				cin >> valueNeed;
				num_Need.push_back(valueNeed);
				num_Allocation.push_back(0);
			}
			BankObject obj1(i, num_Max, num_Allocation, num_Need);
			process.Add(obj1);
			num_Max.clear();
			num_Allocation.clear();
			num_Need.clear();
		}
		for (int i = 0; i < num_Source; i++)
		{
			cout << "请输入资源" << nameSource[i] << "的available：";
			cin >> valueAvailable;
			Available.push_back(valueAvailable);
		}
		//计算各资源的总数
		process.CalTotolSource();
		process.CalAllocation();
		work = Available;
	}
	else
	{
		cout << "请重新输入初始化方式！" << endl;
		goto way;
	}
	while (1)
	{
		process.Menu();
		cout << "请输入你的选择：";
		cin >> choose;
		if (choose < 0 || choose>4)
		{
			cout << "请重新输入你的选择！" << endl;
		}
		switch (choose)
		{
		case 1:
			process.Print_T0();
			break;
		case 2:
			process.SafeCheak();
			break;
		case 3:
			cout << "进程列表：" << endl;
			for (int i = 0; i < num_Process; i++)
			{
				cout << "P" << i << "-->" << i << endl;
			}
 
		process:
			cout << "请输入要申请资源的进程：";
			cin >> processi;
			if (processi<0 || processi>num_Process)
			{
				cout << "对不起，请重新输入进程！！！" << endl;
				goto process;
			}
 
			cout << "请输入要申请的各种资源数量：";
			for (int i = 0; i < num_Source; i++)
			{
				cin >> requestsourcenum;
				Request.push_back(requestsourcenum);
			}
 
			process.BankAlgorithm(processi);
			Request.clear();
			break;
		case 4:
			return 0;
			break;
		}
	}
 
}

1.初始化

2、 显示当前资源情况：

3、 安全性检查：

4、 P1请求资源

5、 P4请求资源：

6、 P3请求资源：

通过此次实验，我对银行家算法的理解更加深入，了解死锁避免的基本思想是动态地检测资源分配状态，以确保循环等待条件不成立，从而确保系统处于安全状态。认识到所谓安全状态是指：如果系统能按某个顺序为每个进程分配资源（不超过其最大值），那么系统状态是安全的，换句话说就是，如果存在一个安全序列，那么系统处于安全状态。
在这次实验过程中我遇到了代码运行不出来的情况，为此我十分焦虑，不过在不断查阅资料的和翻看书本的情况下我用c++实现了银行家算法；这次实验让我了解和如何避免死锁，系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配。这是一种保证系统不进入死锁状态的动态策略。总之，我学到了很多。