面试题：并发与同步之死锁：银行家算法应对死锁

Question

假设系统中有5个进程P1 - P5，3类资源R1、R2、R3，当前资源分配情况如下：进程P1已占有1个R1，还需要1个R2和1个R3；进程P2已占有1个R2，还需要2个R1；进程P3已占有1个R3，还需要1个R1和1个R2；进程P4已占有2个R1，还需要1个R3；进程P5已占有1个R2，还需要1个R1。系统当前可用资源为R1:1、R2:1、R3:1。请运用银行家算法判断系统是否处于安全状态，如果是，给出安全序列；如果不是，说明原因，并阐述银行家算法是如何预防死锁的。

Answer 1

1. 分析当前资源状况
   • 已分配资源：
     • (R1)已分配：(1 + 0+0 + 2+1=4)
     • (R2)已分配：(0 + 1+0 + 0+1=2)
     • (R3)已分配：(0 + 0+1 + 0+0=1)
   • 最大需求：
     • (P1)：(R1:1 + 1=2)，(R2:0 + 1=1)，(R3:0 + 1=1)
     • (P2)：(R1:0 + 2=2)，(R2:1 + 0=1)，(R3:0 + 0=0)
     • (P3)：(R1:0 + 1=1)，(R2:0 + 1=1)，(R3:1 + 0=1)
     • (P4)：(R1:2 + 0=2)，(R2:0 + 0=0)，(R3:0 + 1=1)
     • (P5)：(R1:1 + 0=1)，(R2:1 + 0=1)，(R3:0 + 0=0)
   • 需求资源：
     • (P1)：(R1:0)，(R2:1)，(R3:1)
     • (P2)：(R1:2)，(R2:0)，(R3:0)
     • (P3)：(R1:1)，(R2:1)，(R3:0)
     • (P4)：(R1:0)，(R2:0)，(R3:1)
     • (P5)：(R1:0)，(R2:0)，(R3:0)
   • 可用资源：(R1:1)，(R2:1)，(R3:1)
2. 寻找安全序列
   • 初始可用资源为((1,1,1))。
   • 进程(P5)需求为((0,0,0))，可以满足，执行(P5)，释放资源后可用资源变为((1 + 1,1 + 1,1+0)=(2,2,1))。
   • 进程(P1)需求为((0,1,1))，可以满足，执行(P1)，释放资源后可用资源变为((2+1,2 + 1,1+1)=(3,3,2))。
   • 进程(P2)需求为((2,0,0))，可以满足，执行(P2)，释放资源后可用资源变为((3+2,3 + 1,2+0)=(5,4,2))。
   • 进程(P3)需求为((1,1,0))，可以满足，执行(P3)，释放资源后可用资源变为((5+1,4 + 1,2+1)=(6,5,3))。
   • 进程(P4)需求为((0,0,1))，可以满足，执行(P4)，释放资源后可用资源变为((6+2,5 + 0,3+1)=(8,5,4))。
   • 所以存在安全序列(<P5,P1,P2,P3,P4>)，系统处于安全状态。
3. 银行家算法预防死锁原理
   • 银行家算法通过检查系统是否处于安全状态来预防死锁。
   • 当一个进程请求资源时，银行家算法先假设把资源分配给该进程，然后检查系统是否仍然处于安全状态（即是否能找到一个安全序列）。
   • 如果分配后系统仍然安全，则进行实际分配；如果分配后系统不安全，则拒绝分配该资源。这样就避免了系统进入死锁状态，因为死锁发生时系统必然处于不安全状态，通过始终保持系统处于安全状态，从而预防了死锁的发生。