非阻塞缓存与未决缺失合并

可以把 MSHR 看成一张“货还在路上”的登记单。上面除了货物编号，还写着谁在等、各自要哪一部分，以及货到以后放在哪个位置。新的顾客若要同一批货，只加入登记单；要已经在架上的货，则当场取走。

这里有两个常被混淆的容量。MSHR 数量限制正在等待多少个不同块；每条目标列表长度限制多少次读取可以等同一块。还有第三个约束：一个组的路都被占作填充位置时，即使全局仍有空闲 MSHR，也不能再接收映射到该组的新块。

正确性可以逐事件归纳。初始没有未决事务，所有行无效。假定事件前满足四条不变量：

• 每个未决块只有一条事务，每个被保留的路只有一个事务所有者
• 有效行不被保留，且数据逐字等于它所标记的内存块
• 每个尚未返回的已接收请求，恰在一条对应块的目标列表中
• 已返回请求不再留在任何目标列表中

HIT 只读正确的有效行，生成新身份并立即返回，不加入等待集合。MERGE 只往已找到的唯一同块列表添加新身份。MISS 在检查资源后才分配，选择的路没有所有者，因此不会破坏另一个事务的归属；旧驻留值失效后不可再被命中。complete 找到原身份的唯一记录，将可信整行安装到它仍拥有的位置，把整张目标列表移出等待集合并返回。释放记录以后，旧身份再也找不到，故不能重复响应。失败与重试不改状态，也保持不变量。

这份证明没有要求先来的事务先返回。内存不变，所以两个不同块的返回次序不会改变任何读取值。它也没有证明处理器能够越过任意数据依赖，更没有给寄存器提交、异常或多核可见性作保证；这里的调用者只是能够持有多个独立读取的事件驱动器。

取 $K=4,S=2,W=2,M=2,T=2$，令 $A[i]=17i+11$。字节地址 $0,16,32,48$ 分别是块 $0,1,2,3$ 的首字。

先读取地址 0 并完成填充。随后读 16，建立块 1 的事务；读 0 立即 HIT；读 20 合并进块 1 的目标列表。再读 24 时目标已满，返回 target-full，不能悄悄丢掉此前等待者，也不能为块 1 再建一条事务。

接着读 32，建立第二条事务。现在再读新块首址 48 得到 mshr-full，但重读驻留地址 0 仍然可以命中。先完成块 2，再完成块 1，返回地址及值依次是

返回次序不同于接收次序，请求身份却不会混淆。包括预热在内，真正发往下层的事务只有三条，而不是每次未命中读取都发一条。

单独把配置改成 $S=1,W=2,M=3$：先接收两个不同块的缺失，二者占满该组两路。第三个新块失败的原因是 ways-reserved，不是 MSHR 不够。若错误地把保留路当成普通 LRU 牺牲品，两条事务会指向同一个物理位置；较晚的一次填充可能覆盖较早但尚未正确消费的数据，所有权归纳从这里断开。

$M=1$ 仍允许等待期间的驻留命中与同块合并，只是不允许第二个不同块同时在途。$T=1$ 则使第二个同块等待者暂时重试。重复读取同一地址也占不同的目标身份，因为调用者仍在等待两次响应。

本页没有写缓冲、脏行、取消、总线错误、地址转换、失效消息或缓存一致性。若内存会变化，仅凭不可变 $A$ 的证明已不足够；若需要取消，还要定义目标何时退出、迟到结果如何识别，以及存储位置何时可重用。Kroft 原始 lockup-free 设计处理了更多情况，包含逐字转发、写入和过时记录管理；这里特意采用更容易审计的整次填充保留一路教学策略，不宣称复现原设计或 gem5。

完整参考程序中的 WholeLineCache 实现上述合同，六项任务要求分别交出接收、合并、重试和完成记录。返回批次交给调用者，缓存内部不保存随运行增长的完成日志。请求上的 origin 只区分 demand 与 prefetch 标签，不改变取值语义。

令 $r\le M$ 是当前未决数，$t\le T$ 是本次响应数。参考实现线性扫描组路和未决列表，命中查找为 $O(W)$，合并查找为 $O(W+M)$；目标列表追加是摊还常数，若要求一次调用的最坏 Python 列表扩容成本，应再加 $O(T)$。新缺失还初始化 $K$ 个接收标记，故为 $O(W+M+K)$。整行完成包括寻找与删除列表记录、复制 $K$ 个字以及构造 $t$ 个结果，为 $O(M+K+t)$。这些是软件事件成本，不能当成硬件组合电路的周期数。

数据数组占 $SWK$ 个字，路元数据占 $O(SW)$。共享参考框架还给每条未决事务保留 $K$ 个接收标记，即使整行模式暂不使用其中的部分有效状态；因此内部辅助空间为 $O(M(K+T+1))$，不是只算 MSHR 头部的 $O(M)$。下层不可变内存的复制占 $O(N)$，构造总成本为 $O(N+SWK)$。返回批次、调用者保存的旧身份和诊断快照另计；snapshot() 与 check() 遍历数据和目标，未参与每次正常转移。

以上按可容纳地址和计数器的字操作计费。参考程序的序号与时间戳单调增长，运行 $E$ 个事件后需要 $O(\log (E+1))$ 位，任意精度整数运算不能在无界运行中永久按常数位成本计算。程序明确限制几何与输入数组规模，并拒绝布尔值冒充地址或容量；这些有限校验边界不是硬件容量标准。

非阻塞允许重叠等待，能否转化为更短程序时间还取决于独立请求、下层服务能力、资源冲突和真正的关键依赖。增加 MSHR 只能扩大可同时接收的集合，不能从安全不变量推出吞吐翻倍。