银行家算法

银行家算法

一、死锁的条件和处理方法

产生死锁的必要条件

• 互斥条件
• 请求和保持条件
• 不可抢占条件
• 循环等待条件

处理死锁的方法

• 预防死锁
• 避免死锁
• 检测死锁
• 解除死锁

银行家算法

银行家算法是利用避免死锁的方式来处理死锁的算法。

1、银行家算法中的数据结构

​ (1) 可利用资源向量 Available。这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j] = K，则表示系统中现Rj类资源K个。

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

(3)分配矩阵 Allocation。这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,jl = K，则表示进程i当前己分得Rj类资源的数目为K。

(4)需求矩阵Need.这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K，则表示进程i还需要Rj类资源K个方能完成其任务。
上述三个矩阵间存在下述关系:
　　　　　　　　　　Need[i,j] = Max[i,j] - allocation[i, j]

2.银行家算法

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

(1) 如果 Requesti[j] ≤ Need[i,j]便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

(2) 如果 Requesti[j] ≤ Available[j]，便转向步骤(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];

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

3.安全性算法

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

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

银行家算法之例

假定系统中有五个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各种资源的数量分别为10，5，7，在T0时刻的资源分配情况如图：

1. T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析，可知，T0时刻存在着一个安全序列{P1，P3，P4，P2，P0}，故系统是安全的。

2. P1请求资源：P1发出请求向量Request1（1，0，2），系统按银行家算法进行检查：
   
   
   

银行家算法

银行家算法

一、死锁的条件和处理方法

产生死锁的必要条件

• 互斥条件
• 请求和保持条件
• 不可抢占条件
• 循环等待条件

处理死锁的方法

• 预防死锁
• 避免死锁
• 检测死锁
• 解除死锁

银行家算法

银行家算法是利用避免死锁的方式来处理死锁的算法。

1、银行家算法中的数据结构

​ (1) 可利用资源向量 Available。这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j] = K，则表示系统中现Rj类资源K个。

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

(3)分配矩阵 Allocation。这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,jl = K，则表示进程i当前己分得Rj类资源的数目为K。

(4)需求矩阵Need.这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K，则表示进程i还需要Rj类资源K个方能完成其任务。
上述三个矩阵间存在下述关系:
　　　　　　　　　　Need[i,j] = Max[i,j] - allocation[i, j]

2.银行家算法

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

(1) 如果 Requesti[j] ≤ Need[i,j]便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

(2) 如果 Requesti[j] ≤ Available[j]，便转向步骤(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];

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

3.安全性算法

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

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

银行家算法之例

假定系统中有五个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各种资源的数量分别为10，5，7，在T0时刻的资源分配情况如图：

1. T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析，可知，T0时刻存在着一个安全序列{P1，P3，P4，P2，P0}，故系统是安全的。

2. P1请求资源：P1发出请求向量Request1（1，0，2），系统按银行家算法进行检查：