面试题：并发与同步：死锁避免算法原理及应用

Question

请阐述银行家算法是如何避免死锁的，并举例说明在一个简单的资源分配场景（如具有3种资源，5个进程）中，银行家算法是怎样工作的，以及如何判断系统是否处于安全状态。

Answer 1

银行家算法避免死锁的原理

银行家算法通过模拟系统资源的分配过程，在每次分配资源前，检查此次分配是否会导致系统进入不安全状态。只有在分配后系统仍处于安全状态时，才真正进行资源分配，以此避免死锁。它维护了关于系统资源的几种数据结构，包括可用资源向量（Available）、最大需求矩阵（Max）、已分配资源矩阵（Allocation）和需求矩阵（Need）。通过对这些数据结构的动态检查和更新，确保系统始终处于一种可以通过合理分配资源，使所有进程都能运行完成的安全状态。

简单资源分配场景下银行家算法的工作过程及安全状态判断

假设系统有3种资源，分别记为R1、R2、R3，数量分别为3、3、2 ，有5个进程P0、P1、P2、P3、P4 。

1. 初始状态数据结构

   • 可用资源向量Available：Available = [3, 3, 2]
   • 最大需求矩阵Max： |进程| R1 | R2 | R3 | | ---- | ---- | ---- | ---- | |P0 | 7 | 5 | 3 | |P1 | 3 | 2 | 2 | |P2 | 9 | 0 | 2 | |P3 | 2 | 2 | 2 | |P4 | 4 | 3 | 3 |
   • 已分配资源矩阵Allocation： |进程| R1 | R2 | R3 | | ---- | ---- | ---- | ---- | |P0 | 0 | 1 | 0 | |P1 | 2 | 0 | 0 | |P2 | 3 | 0 | 2 | |P3 | 2 | 1 | 1 | |P4 | 0 | 0 | 2 |
   • 需求矩阵Need：Need = Max - Allocation |进程| R1 | R2 | R3 | | ---- | ---- | ---- | ---- | |P0 | 7 | 4 | 3 | |P1 | 1 | 2 | 2 | |P2 | 6 | 0 | 0 | |P3 | 0 | 1 | 1 | |P4 | 4 | 3 | 1 |

2. 寻找安全序列

   • 首先检查进程P3，其需求Need[3] = [0, 1, 1] ，Available = [3, 3, 2] ，Available 大于等于Need[3] ，可以满足P3运行。P3运行完后释放资源，Available = Available + Allocation[3] = [3 + 2, 3 + 1, 2 + 1] = [5, 4, 3] 。

   • 接着看P1，Need[1] = [1, 2, 2] ，Available = [5, 4, 3] ，可以满足P1运行。P1运行完释放资源，Available = [5 + 2, 4 + 0, 3 + 0] = [7, 4, 3] 。

   • 再看P4，Need[4] = [4, 3, 1] ，Available = [7, 4, 3] ，可以满足P4运行。P4运行完释放资源，Available = [7 + 0, 4 + 0, 3 + 2] = [7, 4, 5] 。

   • 然后看P2，Need[2] = [6, 0, 0] ，Available = [7, 4, 5] ，可以满足P2运行。P2运行完释放资源，Available = [7 + 3, 4 + 0, 5 + 2] = [10, 4, 7] 。

   • 最后看P0，Need[0] = [7, 4, 3] ，Available = [10, 4, 7] ，可以满足P0运行。

   • 得到一个安全序列：<P3, P1, P4, P2, P0> ，说明系统处于安全状态。

3. 判断系统是否安全 如果能够找到一个安全序列，使得每个进程都能在有限时间内获得所需资源并运行完成，则系统处于安全状态；若找不到这样的安全序列，则系统处于不安全状态。在上述例子中，由于找到了安全序列<P3, P1, P4, P2, P0> ，所以系统处于安全状态。