死锁检测算法：银行家算法

可视化演示

展示资源分配图(RAG)中的进程-资源关系，动态检测环路等待条件，可视化死锁形成与解除过程。

死锁初识：窄桥上的僵局

小镇入口的窄桥只容一车通过。两辆卡车从桥两头同时上桥，面对面僵住：谁都不肯倒车，因为倒车意味着低头认输；后方的车又不断鸣笛催促，让倒车变得更加困难。管理员观察了很久，总结出这场僵局的四个特征：桥面同一时刻只能过一辆车（互斥）、每辆车都占着桥面又盯着对面的桥面（占有且等待）、谁也不能强行把其中一辆车拖走（不可剥夺）、两辆车的等待关系构成了一个环形（循环等待）。这四个特征同时出现，僵局就解不开了。

操作系统里的死锁与这座桥如出一辙。进程各自持有资源，又等待其他进程占用的资源，等待关系形成一个环，于是所有进程都无法推进。值得注意的是，这四个条件只是死锁产生的必要条件，而不是充分条件——它们同时成立，只说明死锁“可能”发生，并不保证“一定”发生。例如两辆车虽然对峙，但其中一辆车突然接到倒车的命令，僵局便自行瓦解。所以工程师不会等到死锁真的出现才惊呼，而是希望在资源分配之前就识别出这种风险。

桥上的僵局，四个特征一个不少。要治本，不必同时解决全部四个问题——只要破坏其中任何一个，死锁的链条就会断掉。这也是后面所有策略的出发点：有人拆桥面共享，有人强制拖车，也有人干脆在两车相会之前就安排好通行顺序。

核心思想：银行家的推演盘

小镇上有位王阿姨，开了家银行。今天来了一位做面包坊的企业主，想贷款买新烤箱。王阿姨不着急点头，她翻开推演盘：面包坊老板说，总共需要借 10 万，现在已借 6 万，还差 4 万就能买齐设备开业；开业后每月盈利，能还清贷款。王阿姨又看了看账上现金还剩 8 万，够借。但她还要再想一层：把这 4 万借出去之后，如果面包坊没有如期还款，其他客户的贷款会不会因此断链？于是她把所有客户的借款计划在脑子里排了一遍，发现存在一种顺序：每一位客户都能在某个时刻拿到最后的资金、完工、还款。王阿姨这才盖章放款。

“存在一种顺序让所有客户都能依次还清”——这个顺序在算法里叫安全序列。系统接下来只需按照某个排列，依次满足每个进程的需求，让它运行完毕并归还资源，所有进程就都能走完。只要存在这样一个排列，当前状态就是安全状态。安全状态必然不会死锁，因为系统总是可以沿这条序列运行下去。反之，一个状态如果不是安全的，并不意味着立刻就会死锁，而是存在演变成死锁的可能——好比银行虽然现在没挤兑，但资金链已经脆弱得经不起任何新的贷款违约。

\langle \cdots \rangle \text{ 表示按次序执行 }

数据结构：账本里的四张表

Need_{ij} = Max_{ij} - Allocation_{ij}

安全判定：模拟还贷路径

每个周三下午，王阿姨会做一次“压力测试”。她拿出一张草稿纸，从现金流水账的当前余额开始：第一步，环顾所有客户，找出那个“还差的钱 ≤ 银行现有现金”的人；第二步，在草稿上假设把最后一笔钱借给他，紧接着假设他的项目立刻完工，把全部借款连本带利还回来，于是草稿上的现金数增加了；第三步，重复找下一个还差钱的人。如果某一步突然发现，剩下的每位客户“还差的钱”都大于银行现有现金，草稿就写不下去了——说明按当前资金链，有客户将永远无法完工还款。王阿姨就会冻结新的贷款，直到情况改善。

银行家算法的安全性检查，就是这个压力测试的形式化。设 $Work$ 为系统当前可用资源的模拟值，开始时令 $Work = Available$。每次检查遍历所有未完成的进程，找出满足 $Need \le Work$ 的那个；找到后假装它执行完毕，把它的已分配资源全部归还：$Work = Work + Allocation$，并将它记入安全序列。反复进行，直到所有进程都进入序列，则当前状态安全；若某轮遍历后找不到任何可执行进程，而序列尚未满员，则状态不安全，银行家算法会拒绝触发这次检查的资源请求——宁可让进程等待，也不把系统推向危险。

像王阿姨的压力测试一样，安全检查把未来每一步的还款都提前“排练”了一遍。排练成功，说明系统虽然现在资源吃紧，但总有翻盘的余地；排练失败，就说明资金链已经脆弱到了经不起新贷款的程度。操作系统在每次分配前调用这个检查，就是要确保任何一次分配都不会把系统推进“排练失败”的境地。

策略对比：审批与催债

对待死锁，世上大致有三种态度。第一种人打疫苗：从根上不让死锁条件成立，比如规定一辆车必须等桥完全空了才能上桥，或者一次把桥封死只放单向车流，这叫死锁预防，简单粗暴但代价高。第二种人做体检：像王阿姨那样，分配前先推演，发现风险就拒绝，这叫死锁避免。第三种人请催债公司：平时不管，真出了僵局再派人去拖车、罚款、恢复交通，这叫死锁检测与恢复。三种策略各有取舍，而银行家算法属于第二种——所以在实际请求到达时，它必须先过两道闸门。

当进程 $P_i$ 发出资源请求 $Request_i$ 时，银行家算法先检查：第一，$Request_i \le Need_i$，也就是申请量不能超过自己报备的最大需求——总不能对着银行说“我计划借 10 万”，然后开口要 100 万；第二，$Request_i \le Available$，也就是目前账上确实拿得出这笔钱。两道闸门都通过，系统才做预分配：假设资源已经给了 $P_i$，然后用上一节的安全性检查判断更新后的状态是否仍然安全。安全，则正式分配；不安全，则回滚预分配，让 $P_i$ 继续等待。

体检与追债的最大区别，在于时机与代价。王阿姨的体检方案效果好，但要求客户乖乖报出最大借款计划；催债公司的方案不用预知未来，等死锁真发生了再扫描等待图、回滚页面或杀死进程，代价却可能延误整个系统的吞吐。现代系统因此常做折中：数据库用锁超时与死锁检测程序，操作系统用资源分层与强制剥夺，把“审批”与“催债”结合着用。

算法局限：完美剧本难写

王阿姨的办法有一个隐藏前提：每位客户在开户时，必须准确说出自己这辈子总共要借多少钱，并且这个数字以后不能改。可现实里，面包坊老板可能突然要扩大规模、再借一笔；服装厂可能提前还了款又新开一条产线。客户的计划一变，王阿姨草稿纸上的推演就变得不可靠。更麻烦的是，她假设推演期间银行的资金池不增不减——现实里客户会存款、会取款，资金池随时变动。完美的推演，要求一个不会变动的剧本，可惜现实从不按剧本演出。

银行家算法的局限就藏在“剧本”二字里。通用操作系统中，进程的行为高度动态，一个进程未来到底需要用多少内存、多少文件描述符，连它自己都未必说得清；进程还会随时创建、退出，进程集合本身就不固定；磁盘、网络等资源可能热插拔，资源的种类和数量也在变化。算法要求的“预知最大需求、稳定的进程集合、固定的资源池”，在实验室里很容易满足，在真实系统里却几乎无法凑齐。再加上一次安全性检查的复杂度随进程数平方增长、随资源类型数线性增长，频繁分配时开销也不可忽视：

王阿姨的故事还有另一面。虽然完美的剧本难写，但银行家算法留下的思想——“先想好退路，再往前走”——深刻影响了后世的资源管理设计。数据库在分配行锁前会构建等待图判断是否形成环；云平台在调度容器前会预演资源是否足够；分布式锁普遍引入了租约超时，让不可能完美的“剧本”有了兜底。算法也许退出了通用操作系统的舞台，但它的灵魂留在了每一种与资源打交道的系统里。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-def banker_safety_check(process_count, resource_count, available, maximum, allocation):    need = [[maximum[i][j] - allocation[i][j] for j in range(resource_count)]            for i in range(process_count)]    finish = [False] * process_count    work = available[:]    safe_seq = []    for _ in range(process_count):        found = False        for i in range(process_count):            if not finish[i] and all(need[i][j] <= work[j] for j in range(resource_count)):                for j in range(resource_count):                    work[j] += allocation[i][j]                finish[i] = True                safe_seq.append(i)                found = True                break        if not found:            return False, [], need    return True, safe_seq, need  def main():    process_count = 5    resource_count = 2    available = [3, 3]    maximum = [[7, 5], [3, 2], [9, 0], [2, 2], [4, 3]]    allocation = [[0, 1], [2, 0], [3, 0], [2, 1], [0, 0]]    ok, seq, need = banker_safety_check(process_count, resource_count,                                        available, maximum, allocation)    if ok:        print("safe, seq =", seq)    else:        print("unsafe")    print("need table:")    for i in range(process_count):        print("P%d need = %s" % (i, need[i]))  if __name__ == "__main__":    main()

1. need = [[maximum[i][j] - allocation[i][j] for j in range(resource_count)] for i in range(process_count)]由最大需求矩阵减已分配矩阵，算出每个进程“还差多少”的 Need 表。
2. work = available[:]复制一份可用资源作为推演的工作变量，避免修改真实数据。
3. if not finish[i] and all(need[i][j] <= work[j] for j in range(resource_count)):找“未完成且剩余需求不超过当前可用量”的进程，这是安全推演的核心判断。
4. work[j] += allocation[i][j]模拟该进程执行完毕并归还资源，可用量随之增加。
5. safe_seq.append(i)把找到的进程记入安全序列，记录完整路径。
6. if not found: return False, [], need某轮找不到任何可执行进程，说明推演到此断裂，状态不安全，直接返回失败。
7. for _ in range(process_count):最坏情况下需要执行 n 轮，每轮至多找到一个进程。

常见误区

面试题