投稿
  1. 首页
  2. 随笔

银行家算法——C++实现 [ 开源代码 + 详细解析 ]

178插件•2022-12-17•随笔•阅读28

银行家算法——C++实现 [ 开源代码 + 详细解析 ],第1张

银行家算法——C++实现 [ 开源代码 + 详细解析 ]

✅ (原创，纯手敲，开源免费，2021的最后一篇)

文章目录
  • 零、运行结果图
  • 一、银行家算法简介(Dijkstra在1965年提出)
  • 二、安全状态
  • 三、算法实质与思想
  • 四、算法所需的相关数据结构
  • 五、算法的设计思想
  • 六、算法样例 —— 代码测试也是用的这个
  • 七、完整代码 —— C++版本
  • 八、参考附录

Banker Algorithm 

零、运行结果图


◆ 说明：上述算法的核心实现采用了 “DFS + 回溯” 的方法，详见后文的源代码。另外，如果把 C++ 代码里面的 “p_num=1;” 注释掉，得到的是另一个结果。我虽然输入是“0”，但代码里后面我直接把p_num赋值为了1，所以程序上面这样。


一、银行家算法简介(Dijkstra在1965年提出)

● 银行家算法是著名的死锁避免算法：这是一个银行家给多个顾客分发贷款的算法，可以类比到 *** 作系统给进程分配资源。这时只要把银行家换成 *** 作系统，把顾客换成进程，把资金换成资源，把银行家决定是否放贷时所用的判断过程（即判断顾客是否有信誉和偿还能力）换成 *** 作系统决定是否分配资源时所用的判断过程（即判断进程是否能及时归还资源）即可。【简单了解一下即可】
  ① 银行家拥有一笔周转资金
  ② 客户要求分期贷款，如果能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款
  ③ 银行家应谨慎地贷款，防止出现坏账
  ④ 银行家采用的具体方法是看是否有足够的剩余资金满足某一客户，如此反复下去
  ⑤ 如果所有投资最终都被收回，则请求可以批准


二、安全状态

● 为了描述银行家算法，下面先介绍一下系统的安全状态的概念：
  ① 若在某一时刻，系统能按某种进程顺序，如 { P 1 ， P 2 ， … ， P n } {P_1，P_2，…，P_n} {P1​，P2​，…，Pn​} 为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成，则称此时系统的状态为安全状态。称这样的一个进程序列 { P 1 ， P 2 ， … ， P n } {P_1，P_2，…，P_n} {P1​，P2​，…，Pn​} 为安全序列。
  ② 安全序列的实质：序列中的每一个进程 P i ( i = 1 , 2 , … , n ) P_i(i= 1 ,2,… ,n) Pi​(i=1,2,…,n) 到运行完成尚需的资源量 ≤ 系统当前剩余的资源量 + 所有在序列中排在它前面的进程当前所占有的资源量。【这句话看不懂没关系，主要要理解后面的算法步骤】
  ③ 若在某一时刻，系统中不存在一个安全序列，则称系统处于不安全状态。

◆ 需要注意：
  ① 系统在某一时刻的安全状态可能不唯一，但这不影响对系统安全性的判断。
  ② 安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅是可能进入死锁状态。


三、算法实质与思想

● 银行家算法的实质：设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。

● 银行家算法的程序思想：【这是字面意思理解版】
  ① 系统中的所有进程进入进程集合。

  ② 在安全状态下系统收到进程的资源请求后，先把资源试探性地分配给它。

  ③ 系统用剩下的可用资源和进程集合中其他进程还需要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程，从而，保证这个进程运行完毕后并能归还全部资源。

  ④ 把这个进程从集合中去掉，系统的剩余资源更多了，然后反复执行上述步骤。

  ⑤ 最后，检查进程集合，若为空则表明本次申请可行，系统处于安全状态，可实施本次分配；否则，有进程执行不完，系统处于不完全状态，本次资源分配暂不实施，让申请进程等待。


四、算法所需的相关数据结构

● 考虑一个系统有 n 个进程和 m 种不同类型的资源，现定义包含以下向量和矩阵的数据结构：

  ① 可利用资源向量 R e s o u r c e = ( R 1 ， R 2 ， . . . ， R m ) Resource = (R_1，R_2，...，R_m) Resource=(R1​，R2​，...，Rm​)。这是一个含有 m m m 个元素的数组，其中的而每一个元素代表一类可利用资源数目，其初始值是系统中所配置的该类全部可用资源的数目。其数值随该类资源的分配和回收而动态的改变。如果 R e s o u r c e [ i ] = K Resource[i]=K Resource[i]=K，则表示系统中现有 R i R_i Ri​ 类资源 K K K 个。【注：后面，一开始初始化时用 Resource 来表示资源数，然后进行初始化分配后，剩余资源数用 Available 来表示 】

  ② 最大需求矩阵 M a x Max Max 。这是一个 n ∗ m n*m n∗m 的矩阵，它定义了系统中 n n n 个进程中的每一个进程对 m m m 类资源的最大需求。如果 M a x [ i , j ] = K Max[i,j]=K Max[i,j]=K ；则表示进程 i i i 需要 R j R_j Rj​ 类资源的最大数目为 K K K。

  ③ 分配矩阵 A l l o c a t i o n Allocation Allocation 。这也是一个 n ∗ m n*m n∗m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 A l l o c a t i o n [ i , j ] = K Allocation[i,j]=K Allocation[i,j]=K，则表示进程 i i i 当前已分得 R j R_j Rj​ 类资源的数目为 K K K。

  ④ 需求矩阵 N e e d Need Need。这也是一个 n ∗ m n*m n∗m 的矩阵，用以表示每一个进程尚需的各类资源数。如果 N e e d [ i , j ] = K Need[i,j]=K Need[i,j]=K，则表示进程 i i i 还需要 R j R_j Rj​ 类资源 K K K 个，方能完成任务。

  ⑤ 设 R e q u e s t [ i , j ] Request[i,j] Request[i,j] 是进程 P i P_i Pi​ 的申请向量，如果 R e q u e s t [ i , j ] = K Request [i,j]=K Request[i,j]=K，则表示进程 P i P_i Pi​ 需要 K K K 个 R j R_j Rj​ 类型的资源。

● 上述三个矩阵间存在下述关系： N e e d [ i , j ] = M a x [ i , j ] − A l l o c a t i o n [ i , j ] Need[i,j]=Max[i,j]-Allocation[i,j] Need[i,j]=Max[i,j]−Allocation[i,j]


五、算法的设计思想

● 设计思路如下：【这是简易理解版】

  第一部分：银行家算法模块
  ① 如果 R e q u e s t ≤ N e e d Request≤Need Request≤Need，则转向 ②；否则，出错
  ② 如果 R e q u e s t ≤ A v a i l a b l e Request≤Available Request≤Available，则转向 ③；否则等待
  ③ 系统试探性分配请求的资源给进程
  ④ 系统执行安全性算法

  第二部分：安全性算法模块
  ① 设置两个参数
    <1> 工 作 向 量 W o r k 工作向量Work 工作向量Work：值等于 R e s o u r c e Resource Resource
    <2> 标 志 变 量 F i n i s h 标志变量Finish 标志变量Finish：表示系统是否有足够资源分配给进程 ( T r u e ： 有 True：有 True：有， F a l s e ： 没 有 False：没有 False：没有) 。初始化为 F a l s e False False。
  ② 若 F i n i s h [ i ] = F a l s e    & &    N e e d < = W o r k Finish[i]=False,, && ,, Need<=Work Finish[i]=False&&Need<=Work，则执行 ③；否则执行 ④ ( i i i 为资源类别)
  ③ 进程 P P P 获得第 i i i 类资源，则顺利执行直至完成，并释放资源： W o r k = W o r k + A l l o c a t i o n Work=Work+Allocation Work=Work+Allocation； F i n i s h [ i ] = t r u e Finish[i]=true Finish[i]=true；转 ② 。
  ④ 若所有进程的 F i n i s h [ i ] = t r u e Finish[i]=true Finish[i]=true，则表示系统安全；否则，不安全！



● 扩展后的设计思路如下：【这是详细理解版——即简易版的展开】

  ● 当 P i P_i Pi​ 发出资源请求后，系统按下述步骤进行检查：（对标上面的第一部分）
  ① 如果 R e q u e s t [ i , j ] < = N e e d [ i , j ] Request [i,j]<=Need[i,j] Request[i,j]<=Need[i,j]，便转向步骤 ②；否则认为出错，因为它所需要的资源数已经超过它所申请的最大值。

  ② 如果 R e q u e s t [ i , j ] < = A v a i l a b l e [ i , j ] Request [i,j]<=Available[i,j] Request[i,j]<=Available[i,j]，便转向步骤 ③；否则，表示尚无足够资源， P i P_i Pi​ 需等待。

  ③ 系统试探着把资源分配给进程 P i P_i Pi​，并修改下面数据结构中的数值：
     A v a i l a b l e [ j ] = A v a i l a b l e [ j ] − R e q u e s t [ i , j ] ; Available[j]=Available[j]-Request [i,j]; Available[j]=Available[j]−Request[i,j];
     A l l o c a t i o n [ i , j ] = A l l o c a t i o n [ i , j ] + R e q u e s t [ i , j ] ; Allocation[i,j]=Allocation[i,j]+Request [i,j]; Allocation[i,j]=Allocation[i,j]+Request[i,j];
     N e e d [ i , j ] = N e e d [ i , j ] − R e q u e s t [ i , j ] ; Need[i,j]=Need[i,j]-Request [i,j]; Need[i,j]=Need[i,j]−Request[i,j];

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


  ● 系统所执行的安全性算法可描述如下：（对标上面的第二部分）
  ① 设置两个参数
    <1> 工 作 向 量 W o r k 工作向量Work 工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，它含有 m m m 个元素，在执行安全算法开始时，进行初始化赋值 W o r k = A v a i l a b l e Work=Available Work=Available。
    <2> 标 志 变 量 F i n i s h 标志变量Finish 标志变量Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 F i n i s h [ i ] = f a l s e Finish[i]=false Finish[i]=false；当有足够资源分配给进程时，再令 F i n i s h [ i ] = t u r e Finish[i]=ture Finish[i]=ture。

  ② 从进程集合中找到一个满足下述条件的进程：
    <1> F i n i s h [ i ] = f a l s e Finish[i]=false Finish[i]=false；
    <2> N e e d [ i , j ] < = W o r k [ j ] Need[i,j]<=Work[j] Need[i,j]<=Work[j]；若找得到，执行步骤 ③，否则，执行步骤 ④。

  ③ 当进程 P i P_i Pi​ 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
    <1> W o r k [ j ] = W o r k [ j ] + A l l o c a t i o n [ i , j ] Work[j]=Work[j]+Allocation[i,j] Work[j]=Work[j]+Allocation[i,j]；
    <2> F i n i s h [ i ] = t r u e Finish[i]=true Finish[i]=true；
    <3> G o     t o     s t e p ② Go,,, to,,, step ② Gotostep②；

  ④ 如果所有进程的 F i n i s h [ i ] = t r u e Finish[i]=true Finish[i]=true 都满足，则表示系统处于安全状态；否则，系统处于不安全状态。


  ● 流程图如下：


六、算法样例 —— 代码测试也是用的这个

  ● 题目描述：假定系统中有 5 个进程 { P 0 , P 1 , P 2 , P 3 , P 4 } {P0,P1,P2,P3,P4} {P0,P1,P2,P3,P4} 和 3 类资源 { A , B , C } {A,B,C} {A,B,C} 各类资源的数目分别是10、5、7。已知 T 0 T_0 T0​ 时刻资源分配情况如下，假设 P 1 P_1 P1​ 请求资源 R e q u e s t { 1 , 0 , 2 } Request{1,0,2} Request{1,0,2}，再判断该系统是否是安全的？

解：
① 首先要检测看请求资源是不是比可利用资源、是不是比需要的资源小，如果其中一个或两个条件都不满足，则进程执行等待。

② 如果满足则进行接下来的 *** 作。这里 { 1 , 0 , 2 } {1,0,2} {1,0,2} 是满足这两个条件的。我们进行的 *** 作就是将请求资源加到 A l l o c a t i o n Allocation Allocation 上面，也就是已分配的资源得到扩充。

③ 同样的，因为请求的资源一定是来自可利用资源的，所以可利用资源要减去请求资源的数目。

④ 又因为 N e e d Need Need 和 A l l o c a t i o n Allocation Allocation 的和是一个固定值 M a x Max Max ，所以相应的 A l l o c a t i o n Allocation Allocation 加上一个数值， N e e d Need Need 就要减上一个数值，变化之后的新的资源分配图如下图所示：



● 然后再来找安全序列，判断系统是不是安全的即可。

① 将 A v a i l a b l e Available Available 和 N e e d Need Need 对比， P 0 P_0 P0​ 的 N e e d > A v a i l a b l e Need>Available Need>Available，不满足，往后找。

② P 1 P_1 P1​ 的 A v a i l a b l e Available Available 小于 N e e d Need Need，分配给 P 1 P_1 P1​。 P 1 P_1 P1​ 就能运行完成，最后释放资源 { 2 , 0 , 0 } {2,0,0} {2,0,0} 。所以现在的资源就是 { 2 , 3 , 0 } + { 3 , 0 , 2 } = { 5 , 3 , 2 } {2,3,0}+{3,0,2}={5,3,2} {2,3,0}+{3,0,2}={5,3,2}

③ 然后继续向下找， P 2 P_2 P2​ 不满足条件， P 3 P_3 P3​ 满足条件，将资源分配给 P 3 P_3 P3​，让其运行完成，并释放空间 { 2 , 1 , 1 } {2,1,1} {2,1,1}，所以现在的资源就是 { 5 , 3 , 2 } + { 2 , 1 , 1 } = { 7 , 4 , 3 } {5,3,2}+{2,1,1}={7,4,3} {5,3,2}+{2,1,1}={7,4,3}.

④ 依次类推得到安全序列为 { P 1 , P 3 , P 4 , P 0 , P 2 } {P1,P3,P4,P0,P2} {P1,P3,P4,P0,P2}。过程如下图，其中 F i n i s h Finish Finish 表示进程运行完成。


七、完整代码 —— C++版本

● 算法设计要求：

 

 

● 测试样例：
 

 

 

● C++源代码：【注：“DFS + 回溯” 的算法设计细节没写，因为银行家算法重在的是 “银行家算法的思想”，实现的手段有很多种，“DFS + 回溯” 只是其中一种。但是代码中小编关于 “DFS + 回溯” 这一块，已附加了较为详细的注释】
 

"该代码开源免费,如有疑问欢迎咨询CSDN@一支王同学"
#include 
#include 
#include 
using namespace std;
void Find_Security_Sequence(int, int, int*, int*, bool*, int**, int**);
void Dfs(int, int, int, int*, int*, int*, bool*, int**, int**);
void Print_Brief();
int flag = 0;
int all_Ans[101][101] = { 0 };		// 存储所有答案
int all_i = 0;						// 答案下标, 总共有几种安全序列, all_i 就有多大

int main()
{
	Print_Brief();
	
	int n, m;		// n 个进程, m 类资源
	cout << "请分别输入进程数目和资料种类数 n 和 m 为：";
	cin >> n >> m;

	int* Resource = new int[m];
	string* Res_name = new string[m];
	cout << "请输入这" << m << "种资源分别的名称：";
	for (int i = 0; i < m; i++)
		cin >> Res_name[i];

	cout << "请输入这" << m << "种资源分别的个数：";
	for (int i = 0; i < m; i++)
		cin >> Resource[i];

	int** Max = new int* [n];
	int** Allocation = new int* [n];
	int** Need = new int* [n];
	int* Available = new int[n];
	for (int i = 0; i < n; i++)
	{
		Max[i] = new int[m];
		Allocation[i] = new int[m];
		Need[i] = new int[m];
	}

	cout << "请输入最大需求矩阵 Max(行数：" << n << "，列数：" << m << ")：" << endl;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> Max[i][j];

	cout << "请输入分配矩阵 Allocation(行数：" << n << "，列数：" << m << ")：" << endl;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> Allocation[i][j];

	for (int i = 0; i < n; i++)			// Need 矩阵初始化
		for (int j = 0; j < m; j++)
			Need[i][j] = Max[i][j] - Allocation[i][j];

	for (int j = 0; j < m; j++)			// Available 矩阵初始化
	{
		int tol = 0;
		for (int i = 0; i < n; i++)
		{
			tol += Allocation[i][j];
		}
		Available[j] = Resource[j] - tol;
	}

	int p_num;
	cout << "请输入提出请求的进程号(从 0 开始编号)：";
	cin >> p_num;
	p_num = 1;		// 就是这里.
	int* Request = new int[m];
	cout << "请输入该进程对这" << m << "种资源分别申请的资源数：";
	for (int i = 0; i < m; i++)
		cin >> Request[i];
	

	
	
	cout << "初始化后的资源分配图如下：" << endl;
	cout << "ttMAXttAllocationtNeedttAvailable" << endl;
	cout << "t";
	for (int i = 0; i < 4; i++)
	{
		cout << "t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Res_name[j];
		}
	}
	cout << endl;
	for (int i = 0; i < n; i++)
	{
		cout << "|   进程P" << i << "   |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Max[i][j];
		}
		cout << "    |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Allocation[i][j];
		}
		cout << "    |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Need[i][j];
		}
		cout << "    |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			if (i == 0)
				cout << Available[j];
		}
		if (i != 0)
			cout << "t |";
		else if (i == 0)
			cout << "|";
		cout << endl;
	}
	cout << endl;
	

	
	
	for (int i = 0; i < m; i++)
	{
		if (Request[i] > Need[p_num][i])
		{
			cout << "出错[1]：它所需要的资源数已经超过它所申请的最大值。" << endl;
			exit(1);
		}
	}

	
	for (int i = 0; i < m; i++)
	{
		if (Request[i] > Available[i])
		{
			cout << "出错[2]：尚无足够的资源，进程 P" << p_num << " 需等待。" << endl;
			exit(1);
		}
	}

	
	for (int i = 0; i < m; i++)
	{
		Available[i] = Available[i] - Request[i];
		Allocation[p_num][i] = Allocation[p_num][i] + Request[i];
		Need[p_num][i] = Need[p_num][i] - Request[i];
	}
	


	
	
	cout << "加了新的申请后, 新的资源分配图如下：" << endl;
	cout << "ttMAXttAllocationtNeedttAvailable" << endl;
	cout << "t";
	for (int i = 0; i < 4; i++)
	{
		cout << "t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Res_name[j];
		}
	}
	cout << endl;
	for (int i = 0; i < n; i++)
	{
		cout << "|   进程P" << i << "   |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Max[i][j];
		}
		cout << "    |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Allocation[i][j];
		}
		cout << "    |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Need[i][j];
		}
		cout << "    |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			if (i == 0)
				cout << Available[j];
		}
		if (i != 0)
			cout << "t |";
		else if (i == 0)
			cout << "|";
		cout << endl;
	}
	cout << endl;
	

	
	int* Work = new int[n];
	for (int i = 0; i < m; i++)
		Work[i] = Available[i];

	bool* Finish = new bool[n];

	for (int i = 0; i < n; i++)
		Finish[i] = false;

	int* ans = new int[n];	// 记录序列的编号
	for (int i = 0; i < n; i++)
		ans[i] = -1;

	cout << ">>> 所申请资源未大于其所需资源，亦未大于此时可利用资源，可以预分配并进行安全性检查 <<<" << endl << endl;

	
	Find_Security_Sequence(n, m, ans, Work, Finish, Need, Allocation);		//!!!!!! 全文最核心的函数 !!!!!!!
	
	
	if (flag == 0)
	{
		cout << "分配后系统将进入不安全状态，故分配失败。" << endl;
		exit(1);
	}
	

	
	
	cout << "预分配后系统是安全的，最终实际的资源分配图如下：" << endl;
	cout << "ttMAXttAllocationtNeedttAvailabletFinish" << endl;
	cout << "t";
	for (int i = 0; i < 4; i++)
	{
		cout << "t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Res_name[j];
		}
	}
	cout << endl;
	for (int ind = 0; ind < n; ind++)
	{
		int i = ans[ind];
		cout << "|   进程P" << i << "   |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Max[i][j];
		}
		cout << "    |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Allocation[i][j];
		}
		cout << "    |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			cout << Need[i][j];
		}
		cout << "    |t";
		for (int j = 0; j < m; j++)
		{
			cout.setf(ios::left);
			cout.fill(' ');
			cout.width(3);
			Available[j] += Allocation[i][j];
			cout << Available[j];
		}
		cout << "    |tturet|";
		cout << endl;
	}
	cout << endl;
	cout << "上述资源分配图的安全序列为:";
	for (int i = 0; i < n; i++)
	{
		if (i != n - 1)
			cout << "P" << ans[i] << "-->";
		else
			cout << "P" << ans[i];
	}
	cout << endl << endl;
	cout << "所有的安全序列为：" << endl;
	for (int i = 0; i < all_i; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (j != n - 1)
				cout << "P" << all_Ans[i][j] << "-->";
			else
				cout << "P" << all_Ans[i][j];
		}
		cout << endl;
	}
	

	
	delete[] ans;
	delete[] Finish;
	delete[] Work;
	for (int i = 0; i < n; i++)
	{
		delete[] Max;
		delete[] Allocation;
		delete[] Need;
	}
	delete[n] Max;
	delete[n] Allocation;
	delete[n] Need;
	delete[] Available;
	delete[] Resource;
	delete[] Res_name;
	
	return 0;
}
void Print_Brief()
{
	cout << "+---------------------------------------------------------------------------------------+" << endl;
	cout << "|tt>>> 欢迎使用银行家算法 <<< tttttt|" << endl;
	cout << "|t    这是一个银行家给多个顾客分发贷款的算法，可以类比到操作系统给进程分配资源。t|" << endl;
	cout << "|t这时只要把 银行家 换成 操作系统 ，把 顾客 换成 进程 ，把 资金 换成 资源 ，t|" << endl;
	cout << "|t把银行家决定是否放贷时所用的判断过程（即判断顾客是否有信誉和偿还能力）换成t|" << endl;
	cout << "|t操作系统决定是否分配资源时所用的判断过程（即判断进程是否能及时归还资源）即可。t|" << endl;
	cout << "+---------------------------------------------------------------------------------------+" << endl;
}


void Find_Security_Sequence(int n, int m, int* ans, int* Work, bool* Finish, int** Need, int** Allocation)
{
	int* tmp = new int[n];		// 临时记录答案序列的编号
	for (int i = 0; i < n; i++)
	{
		tmp[i] = -1;
	}
	Dfs(n, m, 0, tmp, ans, Work, Finish, Need, Allocation);
	delete[] tmp;
}


void Dfs(int n, int m, int cnt, int* tmp, int* ans, int* Work, bool* Finish, int** Need, int** Allocation)
{
	for (int i = 0; i < n; i++)
	{
		int step = 3;	// 为什么这里要设为 3, 可回见本文前面写的算法设计步骤
		if (Finish[i] == 0)
		{
			for (int j = 0; j < m; j++)
			{
				if (Need[i][j] > Work[j])
					step = 4;
			}
		}
		else			// 已经分配过了, 就不用考虑该进程, 直接重复循环
			continue;

		if (step != 3)	// step == 4 时将执行 continue
			continue;
		else
		{
			// step == 3 才执行下一步
			for (int j = 0; j < m; j++)
				Work[j] = Work[j] + Allocation[i][j];

			Finish[i] = true;	// 设置为 “分配”
			tmp[cnt] = i;		// 记录临时答案临时
			cnt++;				// 已分配的进程数 + 1
			if (cnt == n)		// 如果资源分配完了(即找到一种分配方案),
			{
				if (flag == 0)
				{
					for (int j = 0; j < n; j++)
					{
						ans[j] = tmp[j];
					}
				}
				for (int j = 0; j < n; j++)
				{
					all_Ans[all_i][j] = tmp[j];
				}
				all_i++;
				flag = 1;
			}
			else // cnt != n
			{
				
				Dfs(n, m, cnt, tmp, ans, Work, Finish, Need, Allocation);
			}
			cnt--;				// 已分配的进程数 - 1
			tmp[cnt] = -999;	// 这句话可要可不要
			Finish[i] = false;	// 重置为 “不分配”
			for (int j = 0; j < m; j++)
			{
				Work[j] = Work[j] - Allocation[i][j];
			}
		}
	}
}


 

 

● 运行结果：
 
 ◆ 对上图的说明：我们写的代码除了能打印(某一种安全列的)最终实际资源分配图，也能实现所有安全序列的输出。可以在右图的 “所以的安全序列中” 发现 “P1–>P3–>P4–>P0–>P2”，即是先前我们手动算的那个样例的正确答案。
 

 

 
八、参考附录 

 
 
无。 (纯手敲，原创，可能存在未知 Bug，烦请指正…)
 

 

 

⭐️ ⭐️
 

2021的最后一篇     
   2021/12/31      
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5692598.html
赞
(0)
打赏
微信扫一扫微信扫一扫
支付宝扫一扫支付宝扫一扫

178插件178插件一级用户组
00
上一篇
2022-12-17

下一篇2022-12-17

发表评论

登录后才能评论

评论列表（0条）
    
	




















    保存