浅谈 CPU 的 Invalidate Queue

在浅谈x86的TSO memory ordering中，介绍了Store Buffer：CPU 可以先把写操作暂存起来，而不是一直等待写入完成。

本文换到接收请求的一侧，浅谈 Invalidate Queue（失效队列）。

为便于理解，下面采用 Paul E. McKenney 书中的简化模型：失效请求可以先入队并应答，随后再处理。 这不是所有 CPU 的统一实现；本文也不把这一模型直接套用到 x86。示例是硬件层伪代码，不是可以直接照写的普通 C/C++ 并发代码。

What

先把最容易混淆的一点说清楚：

1
2
3

CPU 已经应答了缓存失效请求
        ≠
对应的 Cache Line 已经完成失效

Invalidate Queue 是用于暂存缓存失效请求的队列。

当其他 CPU 要修改某条被共享的 Cache Line 时，本 CPU 可能收到一个请求，要求将自己的缓存副本置为无效。

队列中记录的是：

1	“让包含 x 的 Cache Line 失效”

而不是：

1	“把 x 更新为 1”

所以：

Invalidate Queue 暂存的是“让旧副本失效的请求”，不是其他 CPU 写入的新数据。

Why

处理缓存失效请求，也需要时间。

例如，本地 Cache 正忙于处理 Load/Store，或者短时间内收到大量失效请求，都可能导致失效处理不能立即完成。

如果必须等到缓存行真正失效后才能返回应答，那么发起写入的 CPU 就需要等待更久。

Store Buffer 可以让 CPU 暂时继续执行，但缓冲区写满后，CPU 仍需要停下来等待。

因此，可以把两个动作分开：

1
2
3

先接收请求并返回应答
        ↓
随后完成缓存失效

Invalidate Queue 的目的可以概括为：

减少写入方等待失效应答的时间，而不是省略缓存失效本身。

基础 Example

假设初始状态为：

1 2	CPU 0 的 Cache：x = 0，共享状态 CPU 1 的 Cache：x = 0，共享状态

现在 CPU 0 要执行：

1	Store x = 1

为获得写权限，CPU 0 需要让 CPU 1 的对应缓存副本失效。

先失效，再应答

先看一个不提前应答的处理过程：

CPU 0                              CPU 1

发送失效请求 ---------------------> 收到请求
等待                                Cache 正忙，暂时无法处理
等待                                将 x 所在缓存行置为无效
收到 ACK <------------------------- 返回应答

获得写权限，更新 x = 1

这里，CPU 0 等待的时间包含了 CPU 1 实际处理缓存失效的时间。

先应答，再失效

使用 Invalidate Queue 后，在队列能够接收请求且满足协议条件时，可以变成：

CPU 0                              CPU 1

发送失效请求 ---------------------> 请求进入 Invalidate Queue
收到 ACK <------------------------- 先返回应答

获得写权限，更新 x = 1               ……
                                    随后处理队列中的请求
                                    将 x 所在缓存行置为无效

两种方式都需要完成缓存失效。

区别在于：

第二种方式不再要求“缓存失效处理完成”，才能向写入方返回应答。

How

关键是把“接收请求”和“处理请求”解耦，但提前应答并不是随意答应。

在本文采用的模型中，请求进入队列，相当于 CPU 作出一个承诺：

在针对同一条 Cache Line 发出后续一致性协议消息之前，先处理已经排队的失效请求。

这样，失效工作可以延后，但不能绕过相关协议约束。

因此，Invalidate Queue 不是“缓存一致性可以不管了”，而是“在遵守协议的前提下，把一部分工作延后处理”。

记忆图

把它与 Store Buffer 放在一起，可以这样记：

本 CPU 发起的写入：

    Store → Store Buffer → 满足条件后更新缓存


其他 CPU 引起的失效请求：

    失效请求 → Invalidate Queue → 稍后使本地旧副本失效
                     │
                     └── 可以先返回 ACK

两者暂存的东西不同：

Store Buffer：
    暂存“我准备写入的内容”

Invalidate Queue：
    暂存“别人要求我作废哪些缓存副本”

一句话概括：

先把失效请求记下来并应答，让写入方少等一会儿；真正的失效操作，随后按协议完成。

参考资料：

文章目录

What

Why

基础 Example

先失效，再应答

先应答，再失效

How

记忆图