第5章笔记：死锁、活锁与资源分配

本章问题

从等待图与不变量区分预防、避免、检测和恢复。 本章不是七个术语的并列清单，而是一条从可观察现象到内部状态、从内部状态到工程证据的因果链。学习时始终标出对象身份、队列或表项、触发事件、权限边界和不可破坏的不变量。

七节机制连接

• 四个必要条件与等待环：互斥、占有并等待、不可抢占、循环等待同时成立才可能死锁；实验入口为让T1持A等B、T2持B等A，分别画资源分配图与单实例等待图；反查边界是必要条件不是充分判据；多实例资源图有环不一定已经死锁。
• 锁顺序与死锁预防：给资源建立全序并要求按升序获取，可破坏循环等待，但要处理动态资源集合；实验入口为给账户ID排序后执行双账户转账，比较未排序的AB/BA获取与统一顺序；反查边界是try-lock超时只是检测/退避策略，不自动保证业务操作幂等或无活锁。
• 银行家算法与安全状态：安全状态存在一个让所有进程依次完成的序列；当前不能立即满足不等于永远死锁；实验入口为由Available、Allocation、Max计算Need，逐轮寻找Need≤Work的进程并释放资源；反查边界是安全不等于高利用率；最大需求声明不可信时算法结论也不可信。
• 死锁检测与恢复：单实例可检测等待图环，多实例需按可完成进程迭代；恢复可终止、回滚或抢占资源；实验入口为对四事务等待图运行DFS找环，再按损失成本选择牺牲者并重新验证；反查边界是恢复选择必须考虑事务副作用、回滚能力和饥饿，不能只选资源占用最少者。
• 活锁、饥饿与优先级反转：活锁中参与者持续动作却无进展，饥饿是特定任务长期得不到资源，优先级反转由依赖链造成；实验入口为模拟两个线程同时礼让后退的活锁，再加入随机退避；用优先级继承修复持锁反转；反查边界是随机退避降低同步碰撞但不给绝对时限保证；公平锁也可能牺牲吞吐。
• 实验：等待图环检测：有向图DFS用白灰黑颜色区分未访问、当前路径和已完成节点，灰边意味着环；实验入口为输入事务与等待边，输出DEADLOCK及一个环，或SAFE；反查边界是自环也是死锁候选；图随系统变化，快照检测结果需要结合资源释放语义。
• 实验：银行家安全序列：工作向量从Available开始，完成进程释放Allocation，直到全部完成或无可推进者；实验入口为实现多资源银行家检测，输出字典序最小安全序列或UNSAFE；反查边界是请求试分配后还要重新做安全性检查；Need或Available出现负数应视为非法输入。

请给七节画依赖箭头：前一节留下的状态或接口怎样成为下一节输入？每条箭头补单位、事件或保护条件。若任何一节可以随意搬走且不影响上下文，说明你还没有建立章内联系。

章内实验

选择本章至少一个代码实验，从空环境运行全部内联测试，再新增一个资源耗尽、非法迁移、同刻事件或崩溃输入。保存输入、输出、参考模型、首个偏差和修复后的回归证据。不可复现的睡眠竞态或人工截图不算实验结果。

错题闭环

把错误编码为对象混淆、状态跳步、单位错误、队列顺序、竞态遗漏、权限越界或恢复假设。不要只写粗心。一周后更换数字和事件顺序重做阶段卷；能在新输入下重建机制而非记住答案，才算迁移成功。