银行家算法详解：从死锁避免到系统架构实践

做系统架构这行死锁是个绕不开的话题。我印象最深的一次线上事故是数据库里两条业务链路互相持有对方的行锁两边都在等对方释放最后直接拖垮了整个核心链路。当时DBA kill进程都kill了两轮第一次kill错了新请求又把锁堵上了整个排查过程持续到凌晨。后来翻操作系统书的时候看到银行家算法我脑子里第一反应是如果资源分配之前能像这样“先算一笔账”很多死锁问题本来就不该发生。银行家算法Bankers Algorithm是经典的死锁避免机制它解决的问题非常具体当多个进程同时向系统申请有限资源时系统如何判断这次分配会不会把全局拖入死锁。它不是“死锁发生了怎么恢复”而是“在分配之前就预判这条路走不走得通”。这篇内容适合系统架构设计师、后端开发、中间件开发以及所有需要跟并发、资源池、锁打交道的人。我会从算法原理讲到手工推演再给一套能直接改改就用的代码骨架最后聊聊它在真实架构里的落地边界和选型思路。1. 死锁问题为什么在系统架构中如此棘手1.1 一次线上事故死锁不是理论问题先说我遇到的那次事故。两个微服务A和BA服务的某个任务先更新订单表、再更新库存表B服务的另一个任务恰好反过来先更新库存表、再更新订单表。当两个任务同时跑且命中同一批数据时A握着订单锁等库存锁B握着库存锁等订单锁谁也不退让。这种场景在高并发下不是小概率事件。数据库里两条update语句互相等待MySQL默认的锁等待时间一过事务回滚业务层重试流量一上来就会放大成雪崩。更麻烦的是死锁现场很难复现因为它是多个请求在时间轴上恰好交错的结果日志里只能看到“Deadlock found when trying to get lock; try restarting transaction”看不到完整的资源申请轨迹。死锁真正让人头疼的地方在于它不是单点故障而是多个节点之间的资源循环依赖。系统架构越微服务化锁的粒度越小、嵌套越深死锁出现的可能反而越大。处理死锁不能靠运气必须在设计阶段就有一套机制去规避或者缓解。1.2 死锁的四要件与架构中的真实场景教科书里把死锁产生的条件归纳为四个我在实际排查时发现这四个条件在分布式系统里几乎处处成立互斥条件资源同一时刻只能被一个进程占用。数据库的行锁、分布式锁、连接池里的连接都是典型互斥资源。持有并等待进程占用了部分资源又在等待别的资源。比如事务A更新了订单表还没提交又去更新库存表这时候它手里的订单锁就是“持有”对库存锁就是“等待”。不可剥夺进程占用的资源不能被系统强行抢走。除非事务回滚否则数据库不会把你已经拿到的行锁释放给别人。循环等待多个进程形成一条闭环等待链。A等B、B等C、C等A闭环一旦形成谁也跑不掉。四个条件只需同时满足死锁就成立。架构设计里最难破的是“持有并等待”和“循环等待”因为这两个往往是业务逻辑天然带来的——代码写出来就是先做一件事再做另一件事你很难为了规避死锁去重排所有业务操作的顺序。1.3 为什么“事后处理”总让人头疼死锁发生之后最常见的处理方式是超时和回滚。数据库本身会检测锁等待图发现环就选一个牺牲者回滚应用层则设置lock wait timeout超时后整个事务重来。这套“事后处理”的思路有几个绕不开的痛点。第一回滚成本可能很高。长事务里可能已经执行了几十条SQL一旦回滚前面所有的CPU、I/O、网络开销全部白费而且回滚期间它持有的锁还在反而拖慢后面的所有请求。第二重试可能引发“惊群”。事务回滚后客户端立刻重试多个事务在同一时间点重新发起一模一样的申请顺序死锁会再次出现甚至每次都命中同一批资源形成锁死循环。第三超时时间很难定。设短了正常的锁等待也被误伤设长了死锁期间业务延迟会无限放大。我在项目里见过把innodb_lock_wait_timeout调到50秒的死锁一来整个接口的P99直接奔着分钟级去了。所以核心思路应该转变不去等死锁发生再处理而是在每次分配资源之前先判断“这次给了之后系统还能不能找到一个办法让所有进程都走完”如果找不到宁可让这个请求等一等也不要冒险发资源。这就是银行家算法的出发点。2. 银行家算法的设计思想与核心数据结构2.1 银行家为什么不破产一个贷款类比理解银行家算法最好的方式是把它当成银行在审核贷款申请。银行手里有一笔钱多个企业家来借钱每个企业家知道自己最多需要借多少钱最大需求会分期来借已分配未来还要继续借剩余需求。银行放贷的原则很简单借出去这笔钱之后银行手里剩下的钱加上未来所有企业家还回来的钱必须能把每个企业家最终需要的钱都给齐否则就存在有人中途资金链断裂、钱收不回来的风险。放到操作系统里资源就是钱进程就是企业家银行家就是资源分配器。每次收到一个资源请求系统不是先给再说而是先做一次“纸上演算”假装把资源分出去然后检查系统里是否存在某个执行顺序让每个进程都能依次拿到自己还需要的资源并最终运行结束。如果存在这次分配就是安全的如果不存在系统就拒绝这次分配让进程先等着资源留给真正能走通的路径。这个“拒绝”的瞬间其实就是架构里的熔断思想与其让一个请求把系统拖进泥潭不如现在让它等一等。2.2 四张表Available、Max、Allocation、Need银行家算法用几组数据结构来描述整个系统假设系统里有n个进程、m类资源。Available可用资源向量长度为m表示当前系统中各类资源还剩多少可用。注意是“还能自由分配的”不包含已经被进程占用的部分。Max最大需求矩阵n行m列表示每个进程在整个生命周期内最多需要多少资源。这个值是进程启动时声明的相当于企业家的商业计划书里写的资金上限。Allocation已分配矩阵n行m列表示每个进程当前已经占用的各类资源数。Need剩余需求矩阵n行m列表示每个进程还差多少资源才能达到它的最大需求。计算公式是 Need[i][j] Max[i][j] - Allocation[i][j]这是个恒等式任何时候都成立。系统还要保证两个全局约束对每一类资源所有进程最大需求的总和不能超过资源总数否则从一开始这系统就不可能让所有人都跑完算法直接进入“不可调度”状态同时每个进程的已分配资源数不能超过它的最大需求。这几张表之间的关系我在推演案例时会反复用到。实际写代码的时候我习惯把矩阵存成二维数组向量存成一维数组初始化和更新都按行列访问避免踩到行列颠倒的坑。2.3 安全状态和安全序列的定义银行家算法引入了两个容易混淆的概念安全状态和安全序列。安全序列是指存在一个进程执行顺序比如 P1、P3、P0、P2、P4按这个顺序每个进程在当前可用资源下都能满足剩余需求运行完再释放自己的资源让下一个进程接着跑。只要存在这样的顺序系统当前就处于安全状态。安全状态的反面是不安全状态指的是无论如何都找不到一个执行顺序能让所有进程都走完。注意不安全状态不一定马上死锁因为进程并不一定会同时申请资源可能运气好大家交错着完成了但从数学期望上讲只要进入不安全状态后续任何一次请求都可能触发死锁风险已经不可控。这里我想强调一个很多初学者会忽略的点银行家算法防止的是“当前系统进入不安全状态”而不是直接杜绝死锁。它的哲学是“我不做那个把牌局搞僵的人”每次分配决策都保证牌局还存在一条让所有人出完牌的通路。至于后续进程到底按不按那条路走算法不关心因为只要路径存在系统早晚能收敛到安全状态去。理解了这四个条件、四张表和安全状态的概念就可以开始推演一个真实案例了。3. 手工推演一个完整的资源分配案例3.1 初始状态5个进程、3类资源我直接用操作系统教材里最经典的例子来推演这个例子也在系统架构设计师考试的案例分析里出现过。系统有5个进程P0到P43类资源A、B、C总数分别是10、5、7。T0时刻的分配情况如下。进程Max (A,B,C)Allocation (A,B,C)Need (A,B,C)P0(7,5,3)(0,1,0)(7,4,3)P1(3,2,2)(2,0,0)(1,2,2)P2(9,0,2)(3,0,2)(6,0,0)P3(2,2,2)(2,1,1)(0,1,1)P4(4,3,3)(0,0,2)(4,3,1)Available (3,3,2)算法校验一下所有进程已分配的资源总和是 (7,2,5)用总量 (10,5,7) 减掉正好得到 (3,3,2)表是正确的。先验证当前状态是否安全。用Work表示当前可用资源的动态集合初始为Available(3,3,2)。P0的Need (7,4,3)大于Work不满足P1的Need (1,2,2)完全小于等于Work可以执行。让P1运行完它释放手里的(2,0,0)Work变成(5,3,2)。P3的Need (0,1,1)满足执行后释放(2,1,1)Work变成(7,4,3)。P4的Need (4,3,1)满足执行后释放(0,0,2)Work变成(7,4,5)。P0的Need (7,4,3)满足执行后释放(0,1,0)Work变成(7,5,5)。最后P2的Need (6,0,0)满足执行完整个系统回到(10,5,7)。所以初始状态存在安全序列P1、P3、P4、P0、P2系统当前处于安全状态。3.2 第一次请求P1申请(1,0,2)成功现在P1发出一个资源请求 Request(1,0,2)。按照算法流程先做三道检查。第一Request必须在P1的最大需求范围内即 Request Need[P1] (1,2,2)满足。第二Request必须小于等于系统当前可用资源即 (1,0,2) (3,3,2)满足。第三假设把资源分给P1预分配之后系统是否还能处于安全状态。预分配后的全新状态是Available变成(2,3,0)P1的Allocation从(2,0,0)变成(3,0,2)P1的Need从(1,2,2)变成(0,2,0)其他进程的表项不变。对这组新状态重新做安全性检查。Work(2,3,0)。P0的Need(7,4,3)不满足P1的Need(0,2,0)满足运行完释放(3,0,2)Work变成(5,3,2)。接着P3的Need(0,1,1)满足释放(2,1,1)Work变成(7,4,3)。P4的Need(4,3,1)满足释放(0,0,2)Work变成(7,4,5)。P0的Need(7,4,3)满足释放(0,1,0)Work变成(7,5,5)。P2的Need(6,0,0)满足释放(3,0,2)Work变成(10,5,7)。安全序列存在P1、P3、P4、P0、P2。这次分配可以批准系统把资源(1,0,2)正式分配给P1同时更新全局状态。3.3 第二次请求P0申请(0,2,0)必须拒绝P1拿到资源后P0紧接着发出请求 Request(0,2,0)。检查第一项Request(0,2,0) Need[P0](7,4,3)满足。检查第二项Request(0,2,0) Available(2,3,0)也满足。注意这时候Available的B类还有3个P0只要2个从表面的资源数量上看是够的。但第三步的预分配演算马上会暴露问题。假设先把(0,2,0)分给P0系统的状态会变成Available(2,1,0)P0的Allocation从(0,1,0)变成(0,3,0)P0的Need从(7,4,3)变成(7,2,3)。对这份新状态执行安全性检查。Work(2,1,0)。P0Need(7,2,3)A类7大于2B类2大于1不满足。P1Need(0,2,0)B类2大于1不满足。P2Need(6,0,0)A类6大于2不满足。P3Need(0,1,1)C类1大于0不满足。P4Need(4,3,1)都不满足。扫描完一整轮找不到一个可以安全执行的进程更凑不出安全序列。系统一旦真的把资源给了P0就进入不安全状态后续任何一次常规请求都可能引爆死锁。所以算法给出结论拒绝P0的这次请求所有预分配的表项全部回滚P0继续等待。这个例子展示了银行家算法最有价值的一点从表面看资源是够的但分配之后整个系统失去了“可收敛性”。普通直觉在这里会犯错算法不会。3.4 整个判定流程的伪代码视角把上面两次请求的处理流程抽出来就得到一套完整的判定逻辑。1. 收到进程Pi的资源请求向量Request 2. 如果 Request[j] Need[i][j]说明进程申请量超过了它声明的最大需求 属于非法请求直接报错 3. 如果 Request[j] Available[j]说明当前资源不够进程必须等待 4. 进入预分配 Available Available - Request Allocation[i] Allocation[i] Request Need[i] Need[i] - Request 5. 调用安全性检查算法 Work Available Finish [False, False, ...] 循环扫描所有进程 如果能找到一个未完成、且Need[i] Work的进程 假设它执行完毕释放资源Work Work Allocation[i] 标记Finish[i] True 重新从头扫描 如果一整轮扫描找不到任何可执行进程跳出循环 如果所有Finish都为True存在安全序列预分配生效 否则系统进入不安全状态回滚预分配拒绝请求安全性检查本身是个两层循环外层最多扫描n轮每轮要遍历n个进程、比较m类资源最坏复杂度是O(n²m)n和m不大的时候很快但是资源类型变多、进程数上千之后这个开销不能忽略后面讲落地时会提到。4. 可运行代码骨架安全检查和请求处理4.1 安全性检查函数的实现先写安全性检查函数它是银行家算法的核心。我给出一份可以直接跑的Python实现便于理解也便于改写成其他语言。def is_safe(available, allocation, need): 判断当前系统是否存在安全序列 :param available: 一维列表当前可用资源 :param allocation: 二维列表各进程已分配资源 :param need: 二维列表各进程剩余需求 :return: (是否安全, 安全序列) n len(allocation) # 进程数 m len(available) # 资源类型数 work available[:] # 工作向量动态变化 finish [False] * n # 标记进程是否已执行完 sequence [] # 收集安全序列 while len(sequence) n: found False for i in range(n): if not finish[i] and all(need[i][j] work[j] for j in range(m)): # 模拟进程i运行完成释放其占用的全部资源 for j in range(m): work[j] allocation[i][j] finish[i] True sequence.append(i) found True break if not found: # 一整轮扫描找不到可执行的进程系统不安全 return False, [] return True, sequence函数里有个细节值得注意每轮扫描找到第一个可执行进程后要 break 出来重新从头扫。因为前面进程释放资源后后面的进程可能就能满足了必须在新的一轮里重新检查所有未完成的进程而不是继续往后扫。这个写错的话安全序列判断会出错。4.2 资源请求判定与回滚逻辑在安全性检查之上资源请求逻辑就顺理成章了。def request_resources(pid, request, available, allocation, need): 处理进程pid的资源请求 :param pid: 请求资源的进程编号 :param request: 一维列表本次申请的各类资源数 :return: 字符串提示granted/wait/error/denied n len(allocation) m len(available) # 第一步检查是否超过最大需求 for j in range(m): if request[j] need[pid][j]: return error: request exceeds declared max need # 第二步检查当前可用资源是否足够 for j in range(m): if request[j] available[j]: return wait: system has insufficient resources, try again later # 第三步预分配 for j in range(m): available[j] - request[j] allocation[pid][j] request[j] need[pid][j] - request[j] # 第四步安全性检查 safe, seq is_safe(available, allocation, need) if safe: return fgranted: safe sequence {seq} # 第五步不安全则回滚预分配 for j in range(m): available[j] request[j] allocation[pid][j] - request[j] need[pid][j] request[j] return denied: would lead to unsafe state, request postponed这个函数的顺序绝对不能乱。先判最大需求再判可用资源最后预分配和回滚。回滚时要把三张表available、allocation、need全部还原缺一个都会让系统状态错乱。我还建议把安全序列打印出来方便做测试验证。经典的推演数据可以直接喂进函数里跑看输出是不是我们刚才推演的结果。4.3 实现时容易踩的坑第一处是副本和引用的混淆。is_safe函数里我用了 work available[:]这是复制出一份新的列表避免修改原始available。Python里如果直接写 work available函数内部对work的任何修改都会污染原始数据。其他语言同理传引用前先想清楚。第二处是整数溢出和负数。预分配之后出现负数说明某处逻辑漏了判断比如Request比Available还大就混进了预分配。我在代码里把返回类型设计成字符串而不是布尔值就是为了把wait、error、denied区分开排查问题的时候一眼能看出来走到哪一步。第三处是性能退化。is_safe的时间复杂度是O(n²m)进程数几千、资源类型几十时一次请求就要做几百万次比较。如果系统里请求频率很高这个算法本身就会变成瓶颈。后面章节会说怎么在架构上规避这个问题。5. 银行家算法在真实系统架构中的实践边界5.1 数据库系统为什么没有直接用它很多人会问数据库锁管理器为什么不用银行家算法这是个好问题答案在于“最大需求不可知”。银行家算法要求每个进程在开始前就声明自己的Max但SQL事务里一个事务到底要更新多少行、持有哪些锁只有执行到那一刻才知道不可能预先声明。PostgreSQL、MySQL这类数据库的死锁处理普遍走的是“锁等待图检测超时回滚”路线就是在死锁已经发生或即将发生时把它打破。但这不代表银行家算法对数据库设计没有启发。数据库连接池、线程池这类资源池恰恰是“最大需求”可以量化的场景——每个任务在提交时知道自己要占用多少连接、多少线程资源池管理者可以在发放资源前做准入控制。5.2 分布式架构下的天然限制把银行家算法直接搬到分布式系统里会遇到几个硬约束。最大需求难以预知。微服务之间的调用链跨节点、跨数据库一个请求最终会触碰哪些资源连发起方都不完全清楚。让每个服务预先声明“我可能用到多少CPU、多少内存、多少连接”这在业务层面几乎不可能。资源模型不是一维向量。银行家算法把资源抽象成若干类别每类独立计数但真实系统的CPU配额、内存、带宽、磁盘I/O、数据库连接是相互纠缠的内存不够可能换页导致CPU飙升连接池打满可能拖垮数据库多类资源之间不是简单的“各自满足”关系而是存在复杂的转换和联动效应。分布式系统里还有协调开销。算法要求所有资源分配决策集中在一个中心节点上所有进程的请求和释放都要同步过来这个中心节点本身就变成单点和性能瓶颈。即便用分布式锁或共识协议来协调通信延迟也会让算法的信息同步远远跟不上真实系统状态的变化速度。所以现实中银行家算法在分布式领域很难整体落地但它的核心思想——资源分配前做一次安全预判——可以局部化、单机化地应用在各类资源池组件里。5.3 最像银行家算法的现代系统连接池与任务调度我实际在工程里用过类似思路的地方是数据库连接池的准入控制。曾经有个服务突发流量线程池被打满所有线程都在等待数据库连接而连接池的连接又被超时未清理的事务占着整个服务进入假死。后来我给连接池管理加了一层“最小可用连接保护”连接分配前判断如果本次分配后剩余空闲连接是否还能覆盖当前所有已挂起任务的已知需求如果不能就让新的请求排队。这其实就是银行家算法里“分配前检查安全状态”的变体只是把进程换成了请求把资源换成了连接。任务调度器里也能看到类似设计。一个调度器收到一批任务每个任务声明自己需要多少内存、多少临时磁盘调度器批处理时不是来一个分一个而是先做一次全量校验——这批任务并行之后系统里有没有哪个任务会因为资源不足而永久挂起如果存在这种任务调度器就把它延后先跑更有把握的任务组合。Kubernetes里的requests和limits设计也有点这个味道。Pod申报资源请求调度器根据节点剩余可分配量判断能否调度并且要求节点上所有Pod的资源请求总和不能超过节点容量。这保证了节点上的Pod都有一个“名义上的可满足上限”虽然它不能完全避免资源竞争但从架构理念上说和银行家算法的“预占式资源检查”是一脉相承的。6. 死锁避免、预防、检测的选型建议6.1 三种主流策略的对比死锁处理策略整体上可以分三类预防、避免、检测与恢复。我习惯把它们的核心手段、成本和适用场景放到一张表里对比。策略核心手段优点缺点典型场景死锁预防破坏死锁四个必要条件之一比如资源按序分配、一次性分配所有资源简单直接实现成本低不需要运行时判断资源利用率低限制进程行为业务改造成本高单机嵌入式系统、强约束的批处理任务死锁避免分配前检查是否存在安全序列银行家算法资源利用率高能在一定程度上容忍动态请求需要提前知道最大需求运行时计算有开销操作系统内存管理、单节点资源池、有限状态的调度器死锁检测与恢复允许死锁发生用等待图或超时发现再回滚或杀死进程通用性强不需要预知最大需求死锁期间有性能损耗回滚成本不可控数据库锁管理、分布式锁、微服务调用链没有哪个策略是绝对最优的关键在于系统的资源特征。如果业务操作顺序可以强制统一资源排序的预防策略最省心如果系统规模小、资源类型少、最大需求明确银行家算法的避免策略最优雅如果是动态性很强的复杂调用链那就老老实实做检测加超时兜底。6.2 我在工程中的组合拳打法我在系统架构里很少单独依赖某一种策略常规组合是“预防为主、检测兜底、关键节点避免”。对业务代码里那些可以标准化的资源申请顺序比如必须先查用户后写订单我会在架构规范层面强制排序这是成本最低的预防。对数据库这类无法预知最大需求的场景依赖事务锁等待超时和死锁重试机制这是检测与恢复。而对连接池、线程池、任务队列这类“资源类型少、最大需求可声明”的组件我会用类似银行家算法的准入判断做避免宁可让请求在前台排队也不让它进入资源池后相互卡死。这套组合的本质是根据不同资源的特点选择不同策略而不是试图用一套算法通吃。6.3 最后的个人体会我自己折腾银行家算法最大的收获并不是学会了那套矩阵演算而是养成了一个分配资源的习惯给资源之前先想想如果现在把东西给出去了有没有办法收场。连接池、线程池、限流器、调度器凡是涉及“把稀缺资源交给多个竞争方”的系统都可以先问一句——当前这批请求全部进场之后有没有可能谁也走不完如果有可能就得在入场的源头设一道闸。系统架构里的很多问题都是这样真正值钱的不是某个算法本身而是它逼你养成的那个思考框架。银行家算法就是这样一把扳手它未必每个场景都能直接拧螺丝但会让你在面对资源分配时多一个从“能不能给”到“给了之后还能不能收场”的判断维度。