尚不存在的记录也要保护
本任务从一个空查询开始，交出三份证据：哪些潜在键受到保护、每次请求为什么能授予或必须等待、被中止的事务怎样重新读取后完成。路线入口是锁的范围、等待与重试，下载有限状态核验器。用普通Python运行；-O会明确拒绝，因为本程序用assert检查不变量。
1. 先重现只锁现存行的错误
逻辑键域为0至31，每键保存一记录或缺失。初态仅存在8与16。业务约束为区间[10,13)内至多一记录。T1计划“若该区间为空则插11”，T2计划“若该区间为空则插12”。两事务都先查询，再执行各自写入，最后提交。
若只对实际返回行加S锁，两次查询都空，因而均不取得读锁。T1锁11、T2锁12后都提交，最终区间为{11,12}。两笔插入没有重复键，不能靠唯一键检查拦住。请列出每个事务依赖的缺失状态，说明为什么任一串行执行都至多插入其中一条：后执行者应在查询阶段看见前者的记录。
2. 保护区间，并复算树上的模式
读谓词与区间锁。两事务在扫描前各取S[10,13)，锁住10、11、12的存在性和值，13在右端之外。列出以下请求是否与它冲突：X[9,10)、X[12,13)、X[13,14)、S[11,15)。答案依次为否、是、否、否；最后一个虽相交，但双方都是S。
再读多粒度锁，把0至31放在固定二叉区间树中。覆盖[10,13)的两个最大完整节点是[10,12)和[12,13)。每个事务分别在这两节点取S，并沿路径取IS。去重后的八个显式节点是：
- [0,32)、[0,16)、[8,16)、[8,12)、[12,16)、[12,14)：IS
- [10,12)、[12,13)：S
写11的路径为[0,32)→[0,16)→[8,16)→[8,12)→[10,12)→[11,12)。前四节点IS可升IX，因为另一方相同节点的IS与IX兼容；到[10,12)时，自身S加IX应升成SIX，却与另一方S冲突，所以停在这里。未批准时自身旧S仍保留，叶X也尚未取得。
另一方清理退出后，重新请求可把[10,12)升SIX并取得X[11,12)。复算为什么SIX不能直接授权写10或11，而叶X确实授权写11。要求同时验证兼容矩阵和实际数据权限，不能把“IX已经取得”当成可以写。
区间锁表和固定树是本任务的两种表示；不要求它们每个内部请求一一对应。前者直接判断范围相交，后者通过祖先模式发现冲突；两者均不得漏掉受保护范围中的潜在插入。
3. 同一业务程序的两种年龄策略
T1年龄10，T2年龄20。先回到直接区间锁表示：两者S[10,13)均已取得，都查询为空。读取年龄定向规则，填下表中的当前阻塞者、结果与仍持有锁。
| 事件 | wait-die的结果 | wound-wait的结果 |
|---|---|---|
| T1请求X[11,12) | 等待T2 | 标记T2为ABORTING，等待其清理 |
| T2想请求X[12,13) | 因T1更老，中止T2 | 已在ABORTING，不能发普通请求 |
| T2清理尚未完成 | 仍持S[10,13) | 仍持S[10,13) |
| T2完成清理并释放 | T1重新检查后可获X | T1重新检查后可获X |
| T1提交插入11 | 发布后释放 | 发布后释放 |
| T2重试 | 原年龄20，重新查到{11}，不插12 | 原年龄20，重新查到{11}，不插12 |
核验器会故意在清理完成前调用底层grant，应因仍有不兼容持有者而拒绝。最终键为{8,11,16}，两个成功执行的串行解释是T1在T2重试之前。中止的第一次T2既没有被算成提交，也没有沿用旧空结果继续写。
本实例使用私有写集，清理先丢弃未提交值，再释放锁。真实原地更新的undo是否完成、日志是否持久，并不由此脚本证明。
4. 迁移：等待图随新持有者变化
先取wait-die：30持S(x)，20请求X(x)而等待，边20→30合法。10随后请求S(x)，它与30相容。但授予10会给旧待请求增加20→10，这条边方向错误。正确管理器在同一事件返回前重查pending，令20进入ABORTING并取消其待请求。
wound-wait反过来：10持S(x)，20等X(x)，30后来请求S(x)。旧等待者20应wound新年轻持有者30。即使30这次S与已授S相容，它也不能在重查尚未完成时继续普通访问；清理前30仍保留刚授的S，20仍不能获X。
再让年龄10与30同时持S(x)，20请求X(x)。wait-die中止20；wound-wait中止30并仍等待10。请说明为什么只检查一名持有者会丢失证明前提，以及为什么清理等待边可不遵循年龄方向，却仍不能形成锁等待环。
5. 迁移：端点、改键与保证范围
将一条记录由9改成11，必须先取得X[9,10)和X[11,12)，再原子发布旧键删除及新键写入。S[10,13)只会与第二把冲突；漏掉新点就会在受保护范围制造幻读。改为从11移到13时，旧点会冲突，新点不冲突，方向换了，不能只固定检查“目标键”。
最后给出三个不同结论：兼容与祖先协议保证授锁安全；年龄方向及有限无锁清理排除所建等待图的环；事务最终是否完成还需要调度与工作量假设。一个永不完成清理的ABORTING事务没有锁等待出边，却可以让别人无限等待，故“图无环”不能填成“保证无饥饿、保证某毫秒内完成”。
6. 核验报告应怎样阅读
检查器枚举四叶树合法模式标记，逐对将兼容粗细锁投影到叶权限；再用整数集合交集检验区间公式，检查每个固定树覆盖恰好等于目标键集合。年龄部分逐事件重建当前等待边，既查方向又查环，保留新持有者重查与清理前错误授锁回归。
这些都是有限模型的正确性证据。全表不变量扫描、重新核待请求、Python集合与字典的费用不属于锁管理器的高性能基准；本任务没有测量真实数据库吞吐，也没有模拟崩溃或分布式消息重排。