这个任务的产物是一份逐消息状态账:每一步都能指出谁仍可读、谁可写、最新值在哪个缓存或消息里,以及 home 为什么暂时不能处理下一请求。状态名之外,还要交付等待集合和消息数。
一、先准备两个共享副本
使用目录一致性协议的单块模型。缓存编号 A=0、B=1、C=2,home 初值0,三个缓存均 I。依次让 A、B 读,并等待各自 Installed 回到 home。两个读都返回0,A/B=S(0),C=I,内存0;共6条消息。
现在 C 申请写10,使它的 GetM 先到 home。A 随后申请写20,让它的 GetM 进入等待队列。不要给 A 特权:它正等待升级,仍须处理为 C 发来的撤销。
二、停在最后一份确认之前
先交付 Inv(A)、InvAck(A)。检查以下四项同时成立:
- A=I,写20的 pending 仍存在
- B=S(0),可以完成一次本地读并得到0
- C=I,写10尚未完成
- home 的待确认集合恰为
{B},没有发出 GrantM
若参考器此时已经让 C 写10,即使最终所有缓存能收敛,也已失败:B 仍有读权限,读写独占条件在当前观察点被破坏。
接着交付 Inv(B)。B 变 I 后发出一个读请求,使其 GetS 排在 A 后;然后才让 B 的 InvAck 回到 home。至此 home 才能向 C 发 GrantM(0)。
三、安装不等于 home 已收到确认
C 收到 GrantM,安装 M 并完成写10,发 Installed。在该确认到达 home 之前,C 再本地写11。这一步没有消息,C=M(11),内存仍0;home 还在等 C 的 Installed,不能提前开始 A 的请求。
交付 C 的 Installed 后,home 才发送 FwdM 到 C。C 处理它,把11装入 Data 并变 I。现在请把“所有缓存 I、内存0”抄进账本,同时写下 Data(11) 的来源与去向。这里最新值没有消失,它位于在途消息,目录正处于等 Data 阶段。
随后交付 Data、GrantM 给 A。A 先接到11,再获得 M 并写20,发 Installed。此时内存为11,最新值是 A 的20。不能把给 A 的授权数据直接填成0,然后因为 A 最终写20而认为测试通过;数据交接步骤本身也必须正确。
四、结束最后一次读并核对23条消息
A 的 Installed 回来后,home 处理 B 的 GetS。FwdS 使 A 以20回应并降为 S;Data 把 home 更新为20;GrantS 让 B 安装 S 并读到20。最后交付 B 的 Installed,home 空闲。
最终 A/B=S(20),C=I,内存20。完成写的值依次为10、11、20;B 的预先本地读是0,最后的远程读是20,两者都满足各自执行时的权限与最新值条件。
消息账分为四部分:
| 部分 | 消息构成 | 条数 |
|---|---|---|
| A/B 预热读 | 各 GetS、GrantS、Installed | 6 |
| C 取独占权 | GetM、两份 Inv、两份 InvAck、GrantM、Installed | 7 |
| A 从脏 C 取独占权 | GetM、FwdM、Data、GrantM、Installed | 5 |
| B 从脏 A 读取 | GetS、FwdS、Data、GrantS、Installed | 5 |
| 合计 | 两次本地命中不额外计消息 | 23 |
home 在队列里持有请求也不额外创造一条网络消息。重复把 GetM 的发送、入队和取出都算成“消息”,会把这个账本算大。
五、交付失败证书与真正改变执行的迁移
先构造三个失败证书,每个只删除一项关键保障:未收齐 B 的撤销确认就授权,会出现 M(10) 与 S(0);丢弃旧 owner 的11而返回内存0,会出现不同值的 S;不等 Installed 就转发下一请求,乱序可让 FwdS 到达尚为 I 的预定 owner。写出第一个不合法状态,不能只写“可能有竞态”。
然后恢复正确协议,改变请求到达次序:让 A 的写20先到 home,C 的写10排在后面。等这两个事务完整结束,再让 B 读。B 应读10。这次迁移改变了真实完成顺序,因此与原轨迹末值20不同;不要把原表的最终值当成所有网络调度的常数。
最后考虑 N=1:无其他共享者的升级等待集合为空,但 GetM、GrantM、Installed 仍有三条。解释为何“零个撤销目标”和“已经获得写权”是两个不同条件。
下载完整标准库参考器。直接运行或加 -O 都会执行显式检查,输出相同 JSON。endpoint 给出关键快照,boundaries 故意破坏三个步骤并确认被拒绝;random/exhaustive 是有限作者自查,不是对任意规模网络的自动认证。全部处理规则和进展假设仍以正文为准。