内存依赖推测与后缀重放

错误会顺着数据继续走 ​

I1从槽4暂读3，I2算出 2*3+1=7，I3又从I2转发7。此时只改I1为17是不够的：I2的数据还是7，I3的结果也还是7。一个暂定值可以污染地址、数据和更多load，恢复边界必须覆盖所有这些年轻工作。

完整后缀清除虽然会顺带丢掉一些无关计算，但证明简单：所有消费者都比生产者年轻，所以取消j及其后缀不会留下依赖j的活跃值。选择性重放可以更省，却要额外追踪所有传递消费者及状态，不能只保留看起来“与这次load无关”的指令。

同一四条程序，先得到7，再正式得到35 ​

初值M[4]=3、M[8]=0，使用前页I0写17、I1读4、I2写 2*v1+1 到8、I3读8的程序。I0地址释放延迟6，其他字段延迟1。盲猜模式的完整关键过程如下：

第一次I3即使已DONE，也不能越过I0提前退休。重放后的I1从M读取17，所以来源再次是−1；−1不是“最早那次错误写”的永久标签，而表示这一次读来自当前已提交内存。

最后两次load各执行了两遍，共4次load执行，1次重放取消3项。保守模式只执行2次load。两种模式在这个驱动下都到第10轮完成，因为老store本来就压住退休前缀；减少违例不保证这个例子的总轮数下降。

地址也要清除，不只是数据 ​

把I2改成 store [v1] := 2*v1+1，I3改成 load [v1]，初始额外设M[3]=M[17]=0。第一次I1暂读3，年轻项已经把地址算成3、数据算成7。

正确恢复后，I2与I3的旧地址也变成未知，重新用17得到槽17。最终M[3]仍为0，M[4]=17，M[17]=35。若保留旧地址，只重新算store数据，可能把35写到槽3；若只修I1而完全保留消费者，甚至会留下槽3的7。终点要求直接查看取消前后字段，不以“最后load看起来修好了”代替检查。

同址并不总要重放 ​

另取I0晚揭晓写槽4=17，I1早已知道写槽4=23，I2从I1读到23。I0地址后来也成为4时，I2的来源年龄1大于I0的年龄0，不满足 $s_{\ell }<s$，因此无需重放。

原因是I1在程序序中遮住I0。即使I0先写17，随后I1仍写23，I2应读23。若所有年轻同址load一律重放，安全性通常仍可保持，却会白白丢掉这里已经正确的工作。

相反，把唯一老store的值设成当前内存已有的3，load先读3、老地址后到，仍满足来源−1<0。参考器会重放一次，即使数值碰巧相等。本文没有实现按值消除违例，更没有由“一次相等”推导未来地址或副作用都无关。

三个真的会失败的简化 ​

• 删除违例检测：主例提交的load为3、7，最终M[8]=7
• 只重置I1：I1后来正确提交17，I2与I3仍提交7，最终M[8]=7
• 恢复后仍接受旧代次：旧完成动作可能落入重新使用的位置，破坏新一次执行的字段与时序

前两个是下载程序实际运行的外部子类变体；第三个由保存旧token、触发恢复、再次调用的拒绝检查覆盖。三者分别针对发现、传播清除与身份生命周期，不能用同一个最终数值测试互相代替。

为什么错误读不可能通过退休边界 ​

对已退休前缀归纳。它之前的所有store都已按序写进M，所有已提交load都正确。考虑下一个准备退休的load $\ell$。它的地址表达式只读更老load，因而在这次仍有效的执行中地址正确；若更老load后来被取消，后缀规则也会取消 $\ell$，旧地址不可能继续保留。

设顺序语义中最后一个同址老store为s。若load执行时s已经退休，M已经含s的写，且年轻store未退休，读M或后续更近的合法转发会得到正确最近写。若s尚未退休但地址已知，查询必选最近同址项；数据未到就等，不能越过它读更老值。

剩下的情况是load执行时s地址未知。它所记录的来源只能比s更老，否则会存在一个位于s和load之间的同址store，与s是最后写者矛盾。当s地址揭晓， $\ell \in V_s$ ，于是最老违例j≤ℓ，整段取消包含ℓ。s又必须在ℓ之前退休，所以检测一定早于ℓ可能提交的时刻。该错误实例不可能成为退休load。

store退休时，它的地址和数据也只依赖更老load；同样的后缀生命周期保证它们是正确版本。因此每次退休都扩展一个正确顺序前缀。推测结果可以错，承诺结果不能错；证明靠检测与恢复，而不是靠猜测命中率。

进展、代价与边界 ​

有限程序、有限字段释放延迟、纯总整数计算，且驱动持续调度队首时，最老未退休项不会被重放取消：能取消它的store必须更老而尚未退休，这与它处于队首矛盾。其数据依赖来自已退休load，最终可以形成所需字段并完成、退休。依次推进，有限程序终止。任意外部调用者一直只尝试某个等待中的年轻项，则没有这种公平性保证。

设窗口n项。一次store地址揭晓扫描年轻load需 O(n)，恢复清除后缀需 O(n)；若结合下一页预测器，另加集合更新成本。普通字段计算、来源年龄比较和单项退休按字操作计为常数，但load来源查询有前页列明的扫描、校验与排序费用。驱动一轮可能尝试多条等待load，保守最坏界为 $O(n(m+n\log (n+1)+1))$，再加当轮重放与训练；乘实际轮数T才是整次软件运行费用。

窗口及结果记录 O(n)，显式内存 O(m)。事件日志、完整状态打印与顺序oracle保存每个前缀都另外计费；默认前缀快照可达 $O(n(m+n))$ 空间。任意精度整数的运算和表示位数也不免费。轮数预算耗尽会抛异常，不返回“已验证完成”的半份结果。

这只是单核架构值保持。缓存访问痕迹、瞬态执行泄漏、多核load重排序与语言内存模型均未建模；准确恢复软件可见前缀，不能自动证明这些其他性质。