面试题：并发与同步：死锁避免算法之银行家算法基础

银行家算法是一种资源分配与死锁预防算法，其原理基于对系统资源状态的持续监控和对进程资源请求的谨慎评估。系统如同银行家，资源类似银行家的资金，进程就像借贷者。银行家需要确保在满足部分借贷者需求后，仍有足够资金满足其他借贷者直至所有借贷者完成任务并归还资金。

资源分配前检查：当一个进程提出资源请求时，银行家算法首先检查系统当前可用资源是否能满足该进程的请求。若不能满足，进程等待。
假设分配后安全性检查：若当前可用资源能满足请求，系统会假设将资源分配给该进程，然后检查此时系统是否仍处于安全状态。如果假设分配后系统能找到一个安全序列（所有进程都能依次运行完成并释放资源），则实际分配资源给该进程；若找不到安全序列，则拒绝此次资源请求，进程等待，以此避免系统进入死锁状态。

假设系统中有3个进程P0、P1、P2，4种资源R0、R1、R2、R3。

定义相关数据结构

[
    [7, 5, 3, 2],  // P0对资源的最大需求
    [3, 2, 2, 1],  // P1对资源的最大需求
    [9, 0, 2, 2]   // P2对资源的最大需求
]

[
    [0, 1, 0, 0],  // P0已分配的资源
    [2, 0, 0, 1],  // P1已分配的资源
    [3, 0, 2, 0]   // P2已分配的资源
]

[
    [7, 4, 3, 2],  // P0还需要的资源
    [1, 2, 2, 0],  // P1还需要的资源
    [6, 0, 0, 2]   // P2还需要的资源
]

寻找安全序列
- 首先从进程中找一个Need <= Available的进程，例如P1，因为P1的Need(1, 2, 2, 0) <= Available(3, 3, 2, 1)。
- 假设将P1需要的资源分配给它，P1运行完成后释放资源，此时Available = Available + Allocation[1] = [3, 3, 2, 1] + [2, 0, 0, 1] = [5, 3, 2, 2]。
- 接着在剩下的进程中继续找满足Need <= Available的进程，比如P0，因为P0的Need(7, 4, 3, 2) <= Available(5, 3, 2, 2)不成立，而P2的Need(6, 0, 0, 2) <= Available(5, 3, 2, 2)不成立，所以先不考虑P0和P2。
- 等P1完成释放资源后，再看P0，此时Available = [5, 3, 2, 2] ，P0的Need(7, 4, 3, 2) <= Available(5, 3, 2, 2)不成立，还是不能分配给P0。
- 再看P2，P2的Need(6, 0, 0, 2) <= Available(5, 3, 2, 2)不成立。
- 继续等待P1完成，P1完成后Available更新，然后重新判断。最终如果能按一定顺序让所有进程都能获取足够资源运行完成，则系统处于安全状态，例如若能找到一个序列如<P1, P0, P2>，则系统是安全的；若找不到这样的序列，系统就处于不安全状态，可能发生死锁。

星途面试题库