操作系统 - 《银行家算法》

（一）安全序列

安全序列：

（二）银行家理论入门

概念：

        银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
　　在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在操作系统中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
　　银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
  

进一步阐述：

        当进程申请资源时，银行家算法通过模拟分配资源给该进程，然后判断这种模拟分配后的系统是否安全。若不安全，则撤销模拟分配，并让该进程继续等待。

要确定系统是否安全，我们需要参考以下组件：

以下组件：

进程Pi

  MAX：进程Pi的最大需求资源数量。
  Allocation：已经分配给该进程的资源数量。
  Need：进程还需要的资源数量，即`Need = MAX - Allocation`。

Available：当前的空闲资源数量。系统中的总资源量等于资源池的剩余资源量加上已经分配给所有进程的资源。

        当资源P1申请资源时，银行家算法首先模拟分配资源给它。只有当申请的资源数量小于或等于Available时，这种模拟分配才会进行。然后，算法会检查分配给P1后的剩余资源是否能够满足至少一个进程的需求。如果没有一个进程可以完成并释放资源，那么系统将处于不安全状态，因为随着时间的推移，所有的进程都可能被阻塞，导致死锁。

        但是，如果有一个或多个进程可以使用剩余的资源完成，我们可以模拟地回收这些进程的资源并继续检查其他进程。这种模拟过程的目的是找到一个可能的进程执行序列，这些进程可以依次完成并释放它们的资源，使得其他进程也能够完成。

        通过上述模拟分配和回收过程，我们可以生成一个安全的进程序列，例如{P0, P3, P2, P1}。这表示我们首先满足P0的需求，然后从P0回收资源，接着满足P3的需求，依此类推。这样的序列表明我们可以安全地分配资源而不会导致死锁。

 

总结： 

        银行家算法以及如何使用该算法判断系统是否处于安全状态，从而避免死锁。简要地说，当进程请求资源时，银行家算法会尝试为该进程分配资源。但在正式分配之前，算法会先判断，如果现在为该进程分配资源，系统是否仍然处于一个“安全”的状态。

        "安全"的状态意味着即使为某个进程分配了资源，也仍有足够的资源满足其他进程的最大需求，这样就不会因为某个进程霸占资源而导致其他进程无法完成。如果所有进程都能够完成，并且按照某种顺序释放它们的资源，这样其他等待的进程就能继续完成，那么系统就被认为是“安全”的。反之，如果存在任何一个进程不能完成，那么系统就可能进入死锁状态。

        为了确定系统是否处于安全状态，银行家算法使用了一个简单的测试。算法首先检查是否有一个进程其所需的资源小于等于可用资源。如果有，算法就会假定资源被该进程请求，并将该进程标记为完成。然后，假设该进程在完成后释放了它所有的资源。这个过程将继续，直到所有进程都被标记为完成，或者没有进程可以被标记为完成。

        如果所有进程都被标记为完成，那么系统就处于安全状态。否则，系统就可能会死锁。

        总之，银行家算法的关键思想是，通过模拟进程请求和释放资源的情况来预测是否可能发生死锁。如果模拟过程中发现可能会有死锁，那么算法就不会为请求的进程分配资源。

（三）银行家算法经典习题（***）

解答：

（1）计算Need矩阵，对应相减：Max-Allocation

（2）根据题意，计算出对应的Available

（3）找安全序列，一个就行了

（4）其他（可不写）

2.

答：

（1）

肯定是安全的，安全序列：P0 ，3 ,4,1,2

或者  0   ，3    ，1 ，   2，   4

或者0   ，3    ，1 ，   2，   4