面试题：并发与同步之银行家算法资源分配判断

Question

假设有5个进程P0 - P4，3种资源类型A、B、C，资源总量分别为(10, 5, 7)。当前各进程已分配资源情况为：P0(0, 1, 0)，P1(2, 0, 0)，P2(3, 0, 2)，P3(2, 1, 1)，P4(0, 0, 2)；各进程最大需求为：P0(7, 5, 3)，P1(3, 2, 2)，P2(9, 0, 2)，P3(2, 2, 2)，P4(4, 3, 3)。此时P1发出请求(1, 0, 2)，请用银行家算法判断该请求能否被满足，并简述判断过程。

Answer 1

1. 计算当前可用资源：
   • 已知资源总量为((10, 5, 7))。
   • 已分配资源为((0 + 2+3 + 2+0, 1+0 + 0+1 + 0, 0+0 + 2+1 + 2)=(7, 2, 5))。
   • 所以当前可用资源(Available=(10 - 7, 5 - 2, 7 - 5)=(3, 3, 2))。
2. 判断P1的请求是否满足：
   • P1请求资源((1, 0, 2))。
   • 首先判断(Request_{P1}(1, 0, 2)\leq Available(3, 3, 2))，此条件满足，说明当前可用资源能满足P1的请求。
   • 假设将资源分配给P1，此时：
     • (Available = Available - Request_{P1}=(3 - 1, 3 - 0, 2 - 2)=(2, 3, 0))。
     • (Allocation_{P1}=Allocation_{P1}+Request_{P1}=(2 + 1, 0+0, 0 + 2)=(3, 0, 2))。
     • (Need_{P1}=Max_{P1}-Allocation_{P1}=(3 - 3, 2 - 0, 2 - 2)=(0, 2, 0))。
3. 用安全性算法检查系统是否处于安全状态：
   • 此时系统状态如下：

     进程	Allocation	Need	Available
     P0	(0, 1, 0)	(7, 5, 3)	(2, 3, 0)
     P1	(3, 0, 2)	(0, 2, 0)
     P2	(3, 0, 2)	(9, 0, 2)
     P3	(2, 1, 1)	(2, 2, 2)
     P4	(0, 0, 2)	(4, 3, 3)

   • 找一个(Need_{i}\leq Available)的进程，P1满足(Need_{P1}(0, 2, 0)\leq Available(2, 3, 0))。
   • 假设P1完成，释放资源，(Available = Available+Allocation_{P1}=(2 + 3, 3+0, 0 + 2)=(5, 3, 2))。
   • 此时：

     进程	Allocation	Need	Available
     P0	(0, 1, 0)	(7, 5, 3)	(5, 3, 2)
     P2	(3, 0, 2)	(9, 0, 2)
     P3	(2, 1, 1)	(2, 2, 2)
     P4	(0, 0, 2)	(4, 3, 3)

   • 接着找，P3满足(Need_{P3}(2, 2, 2)\leq Available(5, 3, 2))。
   • 假设P3完成，释放资源，(Available = Available+Allocation_{P3}=(5 + 2, 3+1, 2 + 1)=(7, 4, 3))。
   • 此时：

     进程	Allocation	Need	Available
     P0	(0, 1, 0)	(7, 5, 3)	(7, 4, 3)
     P2	(3, 0, 2)	(9, 0, 2)
     P4	(0, 0, 2)	(4, 3, 3)

   • 接着找，P4满足(Need_{P4}(4, 3, 3)\leq Available(7, 4, 3))。
   • 假设P4完成，释放资源，(Available = Available+Allocation_{P4}=(7 + 0, 4+0, 3 + 2)=(7, 4, 5))。
   • 此时：

     进程	Allocation	Need	Available
     P0	(0, 1, 0)	(7, 5, 3)	(7, 4, 5)
     P2	(3, 0, 2)	(9, 0, 2)

   • 接着找，P0满足(Need_{P0}(7, 5, 3)\leq Available(7, 4, 5))。
   • 假设P0完成，释放资源，(Available = Available+Allocation_{P0}=(7 + 0, 4+1, 5 + 0)=(7, 5, 5))。
   • 此时：

     进程	Allocation	Need	Available
     P2	(3, 0, 2)	(9, 0, 2)	(7, 5, 5)

   • 最后P2满足(Need_{P2}(9, 0, 2)\leq Available(7, 5, 5))。
   • 存在一个安全序列({P1, P3, P4, P0, P2})，所以系统处于安全状态。

所以P1发出的请求((1, 0, 2))能被满足。