2020-12-17

目录

 

1.需求分析

2.概要设计

2.1算法数据结构

2.2银行家算法

2.3安全性算法

3.C++代码实现

4.测试分析


1.需求分析

银行家算法是最具代表性的避免死锁的算法,由Dijkstra提出。该算法原本是为银行系统设计的,以确保银行在发放现金贷款时,不会发生不能满足所有客户需要的情况。在OS中也可以用他来实现避免死锁。

为实现此算法,每一个新进程在进入系统时,必须声明在运行过程中可能需要每种资源类型的最大单元数目,其数目不应该超过系统所拥有的资源总量。当进程请求某资源时,系统必须首先确定是否有足够的资源分配给该进程。如果有再进一步计算在将这些资源分配给进程后,是否会使系统处于不安全状态。如果不会,才会将资源分配给他。

2.概要设计

2.1算法数据结构

为了实现银行家算法,在系统中必须设置四个数据结构,分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配,以及所有进程还需要多少资源的情况。

  1. Avaliable:可利用资源向量。这是一个含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。
  2. Max:最大需求矩阵。这是一个n*m的矩阵,他定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i][j]=K,则表示进程i需要Rj类资源的最大数目是K。
  3. Allocation:分配矩阵。这也是一个n*m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i][j]=K,则表示进程i当前已经分得Rj类资源的数目为K。
  4. Need:需求矩阵。这是一个n*m的矩阵,它表示每一进程尚需的各类资源数目。如果Need[i][j]=K,则表示进程i还需要K个Rj类资源,才能完成其任务。

上述三个矩阵间存在下述关系:

 Need[i,j]=Max[i,j]-Allocation[i,j]

2.2银行家算法

设Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后,系统将按照下述步骤进行检查:

  1. 如果Requesti[j]<=Need[i][j],便转向Step(2);否则认为出错,因为它所需要的资源数已经超过它所宣布的最大值。
  2. 如果Requesti[j]<=Available[j],便转向Step(3);否则,表示尚无足够资源,Pi必须等待。
  3. 系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:

Available[j]=Available[j]-Requesti[j];

Allocation[i][j]=Allocation[i][j]+Requesti[j];

Need[i][j]=Need[i][j]-Requesti[j];

  1. 系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

2.3安全性算法

系统所执行的安全性算法可描述如下:

  1. 设置两个向量:①工作向量Work,它表示系统可提供给进程继续执行所需的各类资源数目,它含有吗m个元素,在执行安全算法开始时,Work=Available;②Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时Finish[i]=false;当有足够资源分配给进程时,再令Finish[i]=true。
  2. 从进程集合中找到一个能满足下述条件的进程:
    •  Finish[i]=false;
    • Need[i][j]<=Work[j];若找到,执行Step(3),否则,执行步骤(4)。
  3. 当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:Work[i]=Work[j]+Allocation[i][j];

Finish[i]=true;

go to step 2;

  1. 如果所有进程的Finish[i]=true都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

3.C++代码实现

// 银行家算法.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include<vector>
#include<algorithm>
#include <iomanip>

using namespace std;
int num_Process = 0;
int num_Source = 0;
vector<int>TotalSource;
vector<int>Available ;
vector<int>Request;
vector<char> nameSource;
vector<int>SucceesName;
vector<int> work;
vector<int> workallocation;

class BankObject
{
private:
	char name;
	vector<int> max;
	vector<int> allocation;
	vector<int> need;
	bool finish;
public:
	BankObject(char pname,vector<int>pmax, vector<int>pallocation,vector<int>pneed) :
		name(pname),max(pmax), allocation (pallocation),need(pneed)
	{
		finish = 0;
	}
	operator vector<int>() const
	{
		return need;
	}
	vector<int>& Max()
	{
		return max;
	}
	const vector<int>& Max()const 
	{
		return max;
	}
	char& Name()
	{
		return name;
	}
	const char& Name()const
	{
		return name;
	}
	vector<int>& Allocation()
	{
		return allocation;
	}
	const vector<int>& Allocation()const
	{
		return allocation;
	}
	vector<int>& Need()
	{
		return need;
	}
	const vector<int>& Need()const
	{
		return need;
	}
	bool & Finish()
	{
		return finish;
	}
	const  bool & Finish()const
	{
		return finish;
	}
};
class Manage
{
private:
	vector<BankObject> 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, vector<int>work)
	{
		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"<<processi<<"进程须等待!" << endl;
				}
			}
		}
		//Step3:系统试分配
		if (success)
		{
			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<int> num_Max;
	vector<int> num_Allocation;
	vector<int> num_Need;
	int requestsourcenum = 0;
	cout<<"现在开始进行初始化:"<<endl;
	cout << "请输入进程的数量:";
	cin >> 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;
		}
	}

}

4.测试分析

2020-12-17

2020-12-17

2020-12-17


 

 

上一篇:kubernetes部署Ubuntu pod提示CrashLoopBackOff


下一篇:8.StatefulSet控制器