C++实现银行家算法（操作系统课设）

目录

银行家算法步骤

安全性检查算法步骤

数据结构

代码?

?补充

---

银行家算法步骤

（1）如果Requesti＜or=Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。

（2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。

（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值：Available=Available-Request[i];

Allocation=Allocation+Request;

Need=Need-Request;

(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

安全性检查算法步骤

（1）设置两个向量

①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;

②布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。

（2）从进程集合中找到一个能满足下述条件的进程：

①Finish[i]=false

②Need< =Work;如找到，执行步骤（3）；否则，执行步骤（4）。

（3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work=Work+Allocation;

Finish[i]=true; 转向步骤（2）。

（4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。

数据结构

(1)用一个类process来保存其属性，在该类中，用容器vector来设置最大需求资源vector<int> Max,已分配资源vector<int> Allocation,最多还需要的资源

vector<int> Need，一个标志位 Finish 用来表示该进程资源是否得到满足

（2）用一个process类型的容器来管理所有的进程类vector<process>,

vector<int> Avaliable保存可用资源序列，vector<int> Request保存请求分配的资源序列

（3）用两个静态变量static int N，static int M来记录用户所输入的进程数量，资源种类数量

代码?

#include<iostream>
#include<vector>
static int N;//进程数
static int M;///资源种类数
using namespace std;
class process
{
public:
	vector<int> Max;//最大需求资源
	vector<int> Allocation;//已分配资源
	vector<int> Need;//最多还需要的资源
	//int M;//资源种类个数
	bool Finish;
public:
	process(vector<int>& _Max, vector<int>& _Allocation, vector<int>& _Need, int _M, int _Finish = false)
		:Max(_Max), Allocation(_Allocation), Need(_Need), Finish(_Finish)
	{}
	void print()
	{
		for (int i = 0; i < M; i++)
		{
			cout << Max[i] << " ";
		}
		cout << "    ";
		for (int i = 0; i < M; i++)
		{
			cout << Allocation[i] << " ";
		}
		cout << "       ";
		for (int i = 0; i < M; i++)
		{
			cout << Need[i] << " ";
		}
		cout << endl;
	}
};
void show(vector<process>& A, vector<int> Avaliable)
{
	cout << "      Max" << "    Allocation    " << " Need" << endl;
	for (int i = 0; i < N; i++)
	{
		cout << "P" << i << ":  ";
		A[i].print();
	}
	cout << "    Avaliable:";
	for (auto x : Avaliable)
	{
		cout << x << " ";
	}
	cout << endl;
}

int cp_Need_Work(int i, vector<process>& A, vector<int> Avaliable)
{
	for (int j = 0; j < M; j++)
	{
		if (A[i].Need[j] > Avaliable[j])
		{
			return 0;
		}
	}
	return 1;
}
void ReFinish(vector<process>& A, int N)
{
	for (int j = 0; j < N; j++)
	{
		A[j].Finish = false;
	}
}

bool IsSafe(vector<process>& A, vector<int> Work, vector<int>& seq)//安全性算法,检查是否安全
{
	int cnt = 0;//用来记录满足条件的进程数
	for (int a = 0; a < N; a++)
	{
		for (int i = 0; i < N; i++)
		{
			if (A[i].Finish == true)
			{
				continue;
			}
			else
			{
				if (cp_Need_Work(i, A, Work))//Need小于Work返回1
				{
					for (int m = 0; m < M; m++)
					{
						Work[m] += A[i].Allocation[m];
					}
					A[i].Finish = true;
					seq[cnt++] = i;
					break;//每加入一个安全序列，就重新从第一个开始循环遍历
				}
			}

		}
	}

	if (cnt != N)
	{
		cout << "找不到安全序列，可能发生死锁！" << endl;
		ReFinish(A, N);
		return false;
	}
	cout << "系统处于安全状态" << endl;
	ReFinish(A, N);
	return true;
}
void Safe_Sequence(vector<process>& A, vector<int> Avaliable)
{
	vector<int> seq;
	seq.resize(N);
	if (IsSafe(A, Avaliable, seq))//如果适分配后安全，返回安全序列的数组并打印
	{
		cout << "安全序列为: ";
		for (auto e : seq)
		{
			cout << "p" << e << "->";
		}
		cout << "p" << seq[N - 1] << endl;
	}
}
int cp_Req_Need(vector<process>& A, int p, vector<int> Request, vector<int> Avaliable)//比较Request和Need
{
	for (int i = 0; i < M; i++)
	{
		if (Request[i] > A[p].Need[i])
		{
			return 0;
		}
	}
	return 1;
}
int cp_Req_Ava(vector<process>& A, int p, vector<int> Request, vector<int> Avaliable)//比较Request和Avaliable
{
	for (int i = 0; i < M; i++)
	{
		if (Request[i] > Avaliable[i])
		{
			return 0;
		}
	}
	return 1;
}
void Check_Request(vector<process>& A, vector<int>& Avaliable)
{
	vector<int> Work(Avaliable);
	vector<process> Temp(A);
	vector<int> Request;
	int p;//进程号
	vector<int> seq;
	seq.resize(N);
	cout << "请输入请求分配的进程号:" << endl;
	cin >> p;
	cout << "请输入Request序列:" << endl;
	for (int x, i = 0; i < M; i++)
	{
		cin >> x;
		Request.push_back(x);
	}
	if (cp_Req_Need(A, p, Request, Work))
	{
		if (cp_Req_Ava(A, p, Request, Work))
		{
			for (int i = 0; i < M; i++)//适分配
			{
				Work[i] -= Request[i];
				Temp[p].Allocation[i] += Request[i];
				Temp[p].Need[i] -= Request[i];
			}
			if(IsSafe(Temp,Work,seq))	//如果适分配后安全，返回安全序列的数组并打印
			{
				cout << "将会为其分配资源！" << endl;
				for (int i = 0; i < M; i++)//确认安全分配资源
				{
					Avaliable[i] -= Request[i];
					A[p].Allocation[i] += Request[i];
					A[p].Need[i] -= Request[i];
				}
				Safe_Sequence(A, Avaliable);
			}
		}
		else
		{
			cout << "尚无足够资源 " << "P" << p << "进程必须等待" << endl;
		}
	}
	else
	{
		cout << "请求资源超过宣布的Need最大值！" << endl;
	}
}
int Iint(vector<process>& A, vector<int>& Avaliable)
{
	int x = 0;  int y = 0;//x为进程数量 y为资源种类个数
	cout << "请分别输入进程数量 资源资源种类个数：";
	cin >> x;
	cin >> y;
	for (int i = 0; i < x; i++) { N++; }
	for (int j = 0; j < y; j++) { M++; }
	for (int i = 0; i < N; i++)
	{
		vector<int> max; vector<int> allocation; vector<int> need;
		cout << "请分别输入P" << i << "进程的Max Allocation Need：" << endl;
		for (int a = 0; a < M; a++)
		{
			int x; cin >> x;
			max.push_back(x);
		}
		for (int b = 0; b < M; b++)
		{
			int x; cin >> x;
			allocation.push_back(x);
		}
		for (int c = 0; c < M; c++)
		{
			int x; cin >> x;
			need.push_back(x);
		}

		A.push_back(process(max, allocation, need, M));

	}

	cout << "请输入Avaliable资源序列：" << endl;
	for (int i = 0; i < M; i++)
	{
		int x; cin >> x;
		Avaliable.push_back(x);
	}
	return 1;
}
void menu()
{
	cout << "--------------------------------" << endl;
	cout << "-----1.资源分匹初始化     ------" << endl;
	cout << "-----2.查看此时资源       ------" << endl;
	cout << "-----3.安全性算法        -------" << endl;
	cout << "-----4.银行家算法        -------" << endl;
	cout << "-----0.  退出             ------" << endl;
	cout << "--------------------------------" << endl;
}
int main()
{

	vector<int> Avaliable;//用来安全性算法
	vector<int> Request;
	vector<process> A;
	int flag = 0;
	int x;
	do
	{
		menu();
		cout << "请选择->";
		cin >> x;
		switch (x)
		{
		case 1:
		{
			if (flag)
			{
				cout << "已经初始化！" << endl;
			}
			else { flag = Iint(A, Avaliable); }
			break;
		}
		case 2:
			if (flag)
			{
				show(A, Avaliable);
			}
			else { cout << "未初始化！" << endl; }
			break;
		case 3:
			if (flag)
			{
				Safe_Sequence(A, Avaliable);
			}
			else { cout << "未初始化！" << endl; }
			break;
		case 4:
			if (flag)
			{
				Check_Request(A, Avaliable);
			}
			else { cout << "未初始化！" << endl; }
			break;
		case 5:
			if (flag)
			{
				cout << "    Avaliable:";
				for (int x : Avaliable)
				{
					cout << x << " ";
				}
				cout << endl;
			}
			else { cout << "未初始化！" << endl; }
			break;
		case 0:
			cout << "退出程序" << endl;
			break;
		default:
			cout << "输入错误，请重新输入" << endl;
			break;
		}
	} while (x);
}

?

?补充

这里的安全序列可以用DFS全部找出来，我嫌麻烦没弄，有精力的可以将这部分优化一下，本文的代码只能找一个安全序列