银行家算法的安全性算法

‘壹’ 银行家算法安全序列怎么判断

先说一下银行家的算法：
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。
(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转（2)；否则，出错。
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转（3)；否则，等待。
(3)系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];
NEED[cusneed][i]-=REQUEST[cusneed][i];
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
=================================================
题目中的计算过程：
先算出每个进程还需要多少进程才能满足，即Request的值 = Need - Allocation
进程名 Allocation Need Request Available
ABC ABC ABC ABC
P1 4 0 5 4 0 11 0 0 6 2 3 3
P2 4 0 2 5 3 6 1 2 4
P3 2 1 4 4 2 5 2 1 1
P4 2 1 2 5 5 9 3 4 7
P5 3 1 3 4 2 4 1 1 1
第一题A项p3 p1 p4 p2 p5
先分配给P3，其Request(2,1,1) < available(2,2,3) 满足，分配资源等待P3完成，P3进程完成之后，Available = (2,1,4) + (2,3,3) = (4,4,7)
然后分配给p1,其Request(0,0,6) < available(4,4,7)，可以满足资源，分配资源给P1,P1完成任务释放资源Available = (4,0,5) +(4,4,7) = (8,4,12)
接着P4，request(3 4 7) < available(8,4,12),可以满足资源，分配资源给P4,P4完成任务释放资源Available = (2,1,2) +(8,4,12) = (10,5,14)
接着p2，request(1 2 4) < available(10,5,14)可以满足资源，分配资源给P4,P4完成任务释放资源Available = (4,0,2)+ (10,5,14) = (14,5,16)
最后P5,request(1 1 1) < available(14,5,16)可以满足资源，分配资源给P4,P4完成任务,资源全部释放，变为(3 1 3 )+ (14,5,16) = (17,6,19)
所以A是安全序列。
同理分析B p1 p3 p5 p2 p4，先分配给P1的话Request(0,0,6) > available(2,3,3)，C资源不满足，所以该序列不安全。
分析C项p4 p2 p3 p5 p1,先分配给p4, Request(3,4,7) > available(2,3,3)，ABC资源都不满足，该序列不安全。
分析D项p2 p3 p1 p4 p5，先分配给P2，Request(1,2,4) > available(2,3,3)，C资源不满足，所以该序列不安全。

第二题，分析方法跟上面的一样，只是比较费时。如果单选的话，看一下答案，D项，先分配给P4，显然完成P4还需( 3 4 7) ,其大于 available，所D项不安全。

‘贰’ 银行家算法(操作系统）

1、这是安全状态：
P1的需求小于可用资源数，先满足P1的请求，然后回收P1资源：可用资源变为 （3,3,2）＋（2,0,0）＝（5,3,2）；
这时P3可分配，P3结束后回收资源，可用资源为（5,3,2）＋（2,1,1）＝（7,4,3）
这时P0可分配，P0结束后回收资源，可用资源为（7,4,3）＋（0,1,0）＋（7,5,3）
接下来是P2，结束后可用资源为（7,5,3）＋（3,0,2）＝（10,5,5）
最后分配P4，结束后可用资源为（10,5,5）＋（0,0,2）＝（10,5,7）
这样得到一个安全序列：P1－P3－P0－P2－P4，所以T0状态是安全的。

2、T0时刻P1请求（1,1,2）<可用资源数（3,3,2），可以直接满足。

‘叁’ 银行家算法

银行家算法，一种解决资源分配问题的策略，用于避免系统进入不安全状态。其核心思想在于动态检查系统是否满足安全条件。在进行资源分配时，系统会维护一个安全序列，该序列中每一步都确保系统处于安全状态。如果分配请求满足安全序列，系统便可以安全地执行资源分配。否则，请求将被拒绝。通过这种机制，银行家算法确保了系统始终处于安全状态，有效防止了死锁和资源浪费。

银行家算法中，系统维护一个资源分配矩阵，表示系统中各种资源的数量。同时，系统还会维护一个进程资源需求矩阵和一个进程已分配资源矩阵。安全序列的生成需要遵循以下步骤：首先，初始化安全序列为空，然后遍历所有进程，如果当前进程已分配资源加上请求资源不会超过其最大需求，并且不会使系统进入不安全状态，则将该进程加入安全序列。遍历结束后，安全序列中所有进程的资源分配情况即为安全状态。

在实际应用中，银行家算法广泛用于操作系统、数据库管理系统和分布式系统中。特别是在多进程环境下的资源管理，银行家算法通过动态检查安全条件，确保资源分配的合理性和安全性。通过实现银行家算法，系统可以有效避免资源竞争导致的死锁问题，确保系统的稳定运行。

总结，银行家算法通过维护安全序列和动态检查安全条件，确保了资源分配过程的安全性与合理性。在多进程环境中，银行家算法有效地解决了资源分配问题，避免了系统进入不安全状态，为现代操作系统、数据库管理系统和分布式系统提供了坚实的资源管理基础。

‘肆’ 银行家算法

简介
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系银行家算法统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。 要解释银行家算法，必须先解释操作系统安全状态和不安全状态。 安全序列是指一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
安全状态
如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态
不存在一个安全序列。不安全状态不一定导致死锁。
[编辑本段]银行家算法的数据结构
1）可利用资源向量Available 是个含有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还需要Rj类资源K个，方能完成其任务。 Need〔i,j〕=Max〔i,j〕-Allocation〔i,j〕
[编辑本段]银行家算法原理：
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全,银行家规定: (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2) 顾客可以分歧贷款,但贷款的总数不能超过最大需求量; (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款; (4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。 运行平台：Windows XP VS2005 编程语言：C#
[编辑本段]算法的实现
初始化
由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。
银行家算法
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。 银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。 设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。 (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。 (2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则，出错。 (3)系统试探分配资源，修改相关数据： AVAILABLE[i]-=REQUEST[cusneed][i]; ALLOCATION[cusneed][i]+=REQUEST[cusneed][i]; NEED[cusneed][i]-=REQUEST[cusneed][i]; (4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
安全性检查算法
(1)设置两个工作向量Work=AVAILABLE;FINISH (2)从进程集合中找到一个满足下述条件的进程， FINISH==false; NEED<=Work; 如找到，执行(3)；否则，执行(4) (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work+=ALLOCATION; Finish=true; GOTO 2 (4)如所有的进程Finish= true，则表示安全；否则系统不安全。
[编辑本段]算法
/// 资源数 public static int resourceNumber; /// 进程数 public static int processNumber; /// 可用资源数组 public static int[] Available; /// 工作向量 public static int[] work; /// 它表示系统是否有足够的资源分配给进程 public static bool[] Finish; /// 最大需求矩阵 public static int[][] Max; /// 分配矩阵 public static int[][] Allocation; /// 需求矩阵 public static int[][] Need; /// 安全序列 public static int[] SafeSequence; /// 资源请求向量 public static int[] Request; 算法思想： 主要是：递归+深度优先搜寻+回溯 算法源代码如下： /// 深搜+回溯实现银行家算法 /// <param name="n">已完成的进程数</param> public void DFS_searchSafeSequence(int n) { if (n == processNumber) { //找到一个安全序列,可以显示所有安全序列 //显示在richTextBoxshow.Text上 for (int i = 0; i < processNumber; i++) { richTextBoxshow.Text += SafeSequence[i] + " "; } richTextBoxshow.Text += "\n"; return; } for (int i = 0; i < processNumber; i++) { if (Finish[i] == false)//进程尚未完成 { //判断现有资源是否可以满足这个进程 bool isOK = true; for (int j = 0; j < resourceNumber; j++) { if (Need[i][j] > work[j]) { isOK = false; break; } } //可以满足 if (isOK) { //先试探的将资源分配给这个进程 for (int j = 0; j < resourceNumber; j++) { work[j] += Allocation[i][j]; } //已经完成 Finish[i] = true; //加入安全序列 SafeSequence[n] = i; //继续搜索 DFS_searchSafeSequence(n+1); //回溯 Finish[i] = false; SafeSequence[n] = -1; for (int j = 0; j < resourceNumber; j++) { work[j] -= Allocation[i][j];