【全面讲解】CPU缓存一致性：从理论到实战(下)

扫描关注一起学嵌入式，一起学习，一起成长

• 存储体系结构(上篇)
• 缓存原理(上篇)
• 缓存一致性协议(上篇)
• 内存屏障(上篇)
• x86-TSO(下篇)
• 基准测试(下篇)
• CAS原理(下篇)
• 原子操作(下篇)
• 无锁队列(下篇)
• 参考资料(下篇)

x86-TSO

图10

x86-TSO 有下面几个特点：

• Store Buffer 被实现为 FIFO 队列，CPU 务必优先读取本地 Store Buffer 中的值（如果有的话），否则去缓存或内存里读取；
• 因为 Store Buffer 是 FIFO，所以写写不会重排，也就不需要 StoreStore barrier；
• MFENCE 指令用于清空本地 Store Buffer，并将数据刷到缓存和内存；
• 某 CPU 执行 lock 前缀的指令时，会去争抢全局锁，拿到锁后其他线程的读取操作会被阻塞，在释放锁之前，会清空该线程的本地的 Store Buffer，这里和 MFENCE 执行逻辑类似；
• Store Buffer 被写入变量后，除了被其他线程持有锁以外的情况，在任何时刻均有可能写回内存。
• 因为没有引入 Invalid Queue，所以不需要 LoadLoad barrier；
• LoadStore barrier 仅在乱序(out-of-order)处理器上有效，因为等待写指令可以绕过读指令；而 x86-TSO 相对其他平台缓存一致性是最严格的，读操作不会延后，不会使读写重排；

• 那么最后只有 StoreLoad barrier 是有效的，其他屏障都是no-op。

06

6.1 关于 Store Buffer 的测试

6.1.1 测试核心内是否存在 Store Buffer 

• 解析

• 如果 核心0 和 核心1 各有自己的 Store Buffer，会造成上述情况；
• 核心0 将 x = 1 缓存在自己的 Store Buffer 里，同样 核心1 也将 y = 1 缓存在自己的 Store Buffer 里，核心0 从共享存储中获取 y = 0；
• 同理，核心1 从共享存储中获取 x = 0，无法见到 x = 1；

• 现代 Intel CPU 和 AMD x86 中都有 Store Buffer 结构。

• 解决
• 这个测试中从其他核心角度看当前核心的读操作提前了，就是因为有 Store Buffer 的存在，导致了从其他核心角度看写操作被延后了；
• 所以需要引入 StoreLoad barrier  来防止读操作提前写操作延后；
• 在 x86 中，带 lock 前缀的指令 / XCHG指令 / MFENCE，会清空Store Buffer，使得当前核心之前的写操作立马可以被其他核心看见。
• 下面有两种解决办法示意图：

• 在我的电脑上使用 smp_mb、mb 或 rmb 可以使上述情况不再出现，而使用 barrier 或 wmb 问题还在；

• 除此之外，还可以使用高级语言的原子变量来解决。

6.1.2 测试核心间是否共享 Store Buffer

• 解析

• 如果 核心0 和 核心2 共享一个 Store Buffer，核心1 和 核心3 共享一个 Store Buffer 会出现上述情况；
• 因为读取时会先去 Store Buffer 读取修改，所以 核心0 执行的 x = 1 会被 核心2 读取到，故 EAX = 1 ；
• 因为 核心1 和 核心2 不共享 StoreBuffer，核心1 的 y = 1 操作缓存在自己和 核心3 的共享 Store Buffer 中，所以 EBX = 0 ；

• 核心3 的ECX = 1 和 EDX = 0 与上述同理。

• 总结

• 实际上，上述现象不允许在任何 CPU 上观察到，在我的电脑上没有出现；

• 本例子违反了共享存储一致性，刷到共享存储的数据一定被所有核心可见，并且是一致的。

• 解析

• 如果 核心0 和 核心1 有各自的 Store Buffer；

• 核心0 将 x = 1 缓存在自己的 Store Buffer 中，并且根据 Store Forwarding 原则，核心0 读取 x 到 EAX 的时候会读取自己的 Store Buffer (中 x = 1)，故 EAX = 1；

• 同理，核心1 也会缓存自己的写操作， 即缓存 y = 2 和 x = 2 到自己的  Store Buffer，因此 y = 2 这个操作不会被核心0 观察到，核心0 从共享存储中读到 y = 0 ，故 EBX = 0；

• 总结

• 出现上述情况就说明核心存在 Store Buffer，并且有转发功能；

• 在我的电脑（i7）上可以出现上述现象；

• 其实还有一个更直接的测试用例，如下：

6.2 测试 CPU 是否乱序执行

6.2.1 测试：StoreStore 乱序

• 解析

• 在 x86-TSO 上，从 核心1 的角度看 核心0，x 和 y 的写入顺序不能颠倒；
• 因为写操作会按照 FIFO 的规则进入Store Buffer，并且按照 FIFO 的顺序刷入共享存储，所以写操作无法重排序；
• 所以 x = 1 先入 Store Buffer 队列，接着 y = 1 入；
• 接着 x = 1 先刷入缓存和内存，y = 1 后刷入；

• 所以，如果 EAX 读到 1 的话，那么 EBX 一定不是 0。

• 总结

• 在 x86 上 Store Buffer 是 FIFO 队列，写操作不允许重排序，无论是从自己还是其他核心角度看都不会发生重排序；
• 在乱序（out-of-order）CPU 上，比如 Arm 上可能发生 StoreStore 重排序，所以需要 StoreStore barrier ；

6.2.2 测试：LoadStore 乱序

• 解析

• 在 x86-TSO 上，如果 EAX = 1，那么说明 x = 1 操作已经从 Store Buffer 中刷入到共享存储，并且优先 EAX = x 执行；
• 由于 x86-TSO 的读操纵不能延后，所以 EBX = y 的操作在 x = 1 之前执行；
• 同理，EAX = x 这个读操作也不能延后到 y = 1 之后执行;
• 所以 EBX = y 先于 x = 1 ，x = 1 先于 EAX = x, EAX = x 先于 y = 1 , 所以 EBX 不可能等于 1；

• 总结

• 在 x86 上读操作不能延后，但是可以提前（9.1.1 中就是读提前了）；
• 在乱序（out-of-order）CPU 上，因为等待写指令可以绕过读指令，比如 Arm 上可能发生 LoadStore 重排序，所以需要 LoadStore barrier；

• 解析

• 假如 核心0 和 核心1 都有自己的 Store Buffer；
• 如果 EAX = 2，那么说明 核心1 的 Store Buffer 中 x = 2已经刷到了共享存储， 那么 x = 2 必然在 x = 1 和 EAX = x 之间执行，因为 EAX 会优先读取 Store Buffer 中的 x ，既然 EAX = 2，说明 核心0 的 Store Buffer 中的 x = 1 已经刷到了共享存储，并且在 x = 2 之前执行的；

• EBX 会优先读取 核心1 中的 Store Buffer ，所以 EBX 不可能等于 1 ；

• 总结

• n5 实际上不应该在任何 CPU 上观察到。

6.3.2 测试：n4b

• 解析

• 假如 核心0 和 核心1 都有自己的 Store Buffer；
• 如果 EAX = 2 ，说明 核心1 的 x = 2 操作已经刷到共享存储，并被 核心0 观察到，所以 x = 2 先于 EAX = x 执行；
• 在 x86 上读操作不会延后，即 EX = x 和 x = 2 不会重排，故 EBX = x 先于 EAX = x 执行，更先于 x = 1 执行，所以 EBX 不可能等于 1；

• 总结

• n4b 实际上不应该在任何 CPU 上观察到。

• 解析

• 在 x86-TSO 上，对于 核心1，如果 EAX = 1 ，那么说明 核心1 已经见到了 核心0 的动作；
• 对于 核心2，EBX = 1，说明 核心2 已经见到了 核心1 的动作，又根据之前的 x86-TSO 上读操作不能延后，EAX = x 不能延迟到 y = 1 之后，所以 核心2 必能见到 核心0 的动作，所以 ECX = x 不能为 0。

• 总结

• 在 x86-TSO 上写操作的可见性是传递的；

• 在乱序（out-of-order）CPU 上，写写和读写都是乱序，就不可能保证写的传递性了；

07

CAS原理

比较并交换(compare and swap, CAS)，是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。

下面代码是使用 CAS 的一个例子（无锁队列 Pop 函数）

template bool AtomQueue::Pop(T& v){    uint64_t tail = tail_;    if (tail == head_ || !valid_[tail])        return false;    if (!__sync_bool_compare_and_swap(&tail_, tail, (tail + 1) & mod_))         return false;    v = std::move(data_[tail]);    valid_[tail] = 0;    return true;}

如果这块内存的值在这期间内没被修改过，则旧值 会与内存中的数据相同，这时 CAS 操作将会成功执行，使内存中的数据变为新值。

如果内存中的值在这期间内被修改过，则一般来说旧值 会与内存中的数据不同，这时 CAS 操作将会失败，新值 将不会被写入内存。

7.1 应用

在应用中 CAS 可以用于实现无锁数据结构，常见的有无锁队列（先入先出）以及无锁栈（先入后出）。对于可在任意位置插入数据的链表以及双向链表，实现无锁操作的难度较大。    

7.2 ABA问题

ABA问题是无锁结构实现中常见的一种问题，可基本表述为：

1. 线程 P1 读取了一个数值 A；
2. P1 被挂起(时间片耗尽、中断等)，线程 P2 开始执行；
3. P2 修改数值 A 为数值 B，然后又修改回 A；
4. P1 被唤醒，比较后发现数值 A 没有变化，程序继续执行。

图12

有一个栈(先入后出)中有 top 和 NodeA，NodeA 目前位于栈顶，top指针指向 A。现在有一个线程 P1 想要 pop 一个节点，因此按照如下无锁操作进行

pop(){  do{    ptr = top;            // ptr = top = NodeA    next_ptr = top->next; // next_ptr = NodeX  } while(CAS(top, ptr, next_ptr) != true);  return ptr;   }

图13

线程 P2 首先 pop 出 NodeA，之后又 push 了两个 NodeB 和 C，由于内存管理机制中广泛使用的内存重用机制，导致 NodeC 的地址与之前的 NodeA 一致。

这时 P1 又开始继续运行，在执行 CAS 操作时，由于 top 依旧指向的是 NodeA 的地址(实际上已经变为 NodeC )，因此将 top 的值修改为了 NodeX，这时栈结构如下：

图14

经过 CAS 操作后，top 指针错误地指向了 NodeX 而不是 NodeB。

简单的解决办法是采用 DCAS（双长度 CAS），一个 CAS长度 保存原始有效数据，另一个 CAS长度 保存累计变化的次数，第一个 CAS 可能出现 ABA 问题，但是第二个 CAS 极难出现 ABA 问题。

7.3 实现

CAS 操作基于 CPU 提供的原子操作指令实现。对于 Intel X86 处理器，可通过在汇编指令前增加 lock 前缀来锁定系统总线，使系统总线在汇编指令执行时无法访问相应的内存地址。而各个编译器根据这个特点实现了各自的原子操作函数。

• C语言，C11的头文件。由GNU提供了对应的__sync系列函数完成原子操作。 
• C++11，STL 提供了atomic 系列函数。
• JAVA，sun.misc.Unsafe 提供了compareAndSwap系列函数。
• C#，通过 Interlocked 方法实现。
• Go，通过 import "sync/atomic" 包实现。
• Windows，通过 Windows API 实现了 InterlockedCompareExchangeXYZ 系列函数。

08

原子操作

程序代码最终都会被翻译为 CPU 指令，一条最简单的加减法语句都会被翻译成几条指令执行；为了避免语句在 CPU 这一层级上的指令交叉带来的不可预知行为，在多线程程序设计时必须通过一些方式来进行规范，最常见的做法就是引入互斥锁，但互斥锁是操作系统这一层级的，最终映射到 CPU 上也是一堆指令，是指令就必然会带来额外的开销。

既然 CPU 指令是多线程不可再分的最小单元，那我们如果有办法将代码语句和指令对应起来，不就不需要引入互斥锁从而提高性能了吗? 而这个对应关系就是所谓的原子操作；在 C++11 的 atomic 中有两种做法:

• 常用类型，长度等于 1、2、4 和 8 字节的整形数据，有相应的 CPU 层级的对应，这就是一个标准的 lock-free 类型；
• 大数据类型，结构体等非常用类型数据，采用互斥锁模拟，比如说对于一个 atomic 类型，我们可以给他附带一个 mutex，操作时 lock / unlock 一下，这种在多线程下进行访问，必然会导致线程阻塞；

可以通过 is_lock_free 函数，判断一个 atomic 是否是 lock-free 类型。

原子操作有三类：

• 读：在读取的过程中，读取位置的内容不会发生任何变动。
• 写：在写入的过程中，其他执行线程不会看到部分写入的结果。
• 读‐修改‐写：读取内存、修改数值、然后写回内存，整个操作的过程中间不会有其他写入操作插入，其他执行线程不会看到部分写入的结果。

8.1 自旋锁

使用原子操作模拟互斥锁的行为就是自旋锁，互斥锁状态是由操作系统控制的，自旋锁的状态是程序员自己控制的，常用的自旋锁模型有：

• TAS，Test-and-set，有且只有 atomic_flag 类型与之对应；
• CAS，Compare-and-swap，对应atomic的compare_exchange_strong 和 compare_exchange_weak，这两个版本的区别是：
• weak 版本如果数据符合条件被修改，其也可能返回 false，就好像不符合修改状态一致；

• strong 版本不会有这个问题，但在某些平台上 strong 版本比 Weak 版本慢（在 x86 平台他们之间没有任何性能差距）；绝大多数情况下，优先选择使用 strong 版本；

LOCK 时自旋锁是自己轮询状态，如果不引入中断机制，会有大量计算资源浪费到轮询本身上；常用的做法是使用yield切换到其他线程执行，或直接使用sleep暂停当前线程.

8.2 C++ 内存模型

C++11 原子操作的很多函数都有个 std::memory_order 参数，这个参数就是这里所说的内存模型，对应缓存一致性模型，其作用是对同一时间的读写操作进行排序，一共定义了 6 种类型如下：

• memory_order_relaxed：松散内存序，只用来保证对原子对象的操作是原子的，在不需要保证顺序时使用；
• memory_order_release：释放操作，在写入某原子对象时，当前线程的任何前面的读写操作都不允许重排到这个操作的后面去，并且当前线程的所有内存写入都在对同一个原子对象进行获取的其他线程可见；通常与memory_order_acquire 或 memory_order_consume 配对使用；
• memory_order_acquire：获得操作，在读取某原子对象时，当前线程的任何后面的读写操作都不允许重排到这个操作的前面去，并且其他线程在对同一个原子对象释放之前的所有内存写入都在当前线程可见；
• memory_order_consume：同 memory_order_acquire 类似，区别是它仅对依赖于该原子变量操作涉及的对象，比如这个操作发生在原子变量 a 上，而 s = a + b；那 s 依赖于 a，但 b 不依赖于 a；当然这里也有循环依赖的问题，例如：t = s + 1，因为 s 依赖于 a，那 t 其实也是依赖于 a 的；在大多数平台上，这只会影响编译器的优化；不建议使用；
• memory_order_acq_rel：获得释放操作，一个读‐修改‐写操作同时具有获得语义和释放语义，即它前后的任何读写操作都不允许重排，并且其他线程在对同一个原子对象释放之前的所有内存写入都在当前线程可见，当前线程的所有内存写入都在对同一个原子对象进行获取的其他线程可见；
  
• memory_order_seq_cst：顺序一致性语义，对于读操作相当于获得，对于写操作相当于释放，对于读‐修改‐写操作相当于获得释放，是所有原子操作的默认内存序，并且会对所有使用此模型的原子操作建立一个全局顺序，保证了多个原子变量的操作在所有线程里观察到的操作顺序相同，当然它是最慢的同步模型。

8.3 C++ volatile

这个关键字仅仅保证数据只在内存中读写，直接操作它既不能保证操作是原子的，也不能通用地达到内存同步的效果；

由于 volatile 不能在多处理器的环境下确保多个线程能看到同样顺序的数据变化，在今天的通用应用程序中，不应该再看到 volatile 的出现。

09

无锁队列

本节是 CPU 缓存一致性的实战部分，通过运用前面的理论知识实现一个无锁队列，达到学以致用的目的。

下面是我采用 CAS 实现了一个多生产者多消费者无锁队列，设计参考 Disruptor ，最高可达 660万QPS（单生产者单消费者）和 160万QPS（10个生产者10个消费者）。

9.1 设计思路

1、如图15，使用 2 个环形数组，数组元素均非原子变量，一个存储 T 范型数据（一般为指针），另一个是可用性检查数组（uint8_t）。Head 是所有生产者的竞争标记，Tail 是所有消费者的竞争标记。红色区表示待生产位置，绿色区表示待消费位置。 

图15

2、生产者们通过 CAS 来竞争和移动 Head，抢到 Head 的生产者，先将 Head 加1，再生产原 Head 位置的数据；同样的消费者们通过 CAS 来竞争和移动 Tail，抢到 Tail 的消费者，先将 Tail 加1，再消费原 Tail 位置的数据 。

9.2 实现细节

下面多生产者多消费者无锁队列的代码是在 x86-64（x86-TSO） 平台上编写和测试的。

Talk is cheap. Show me the code.

9.2.1 AtomQueue类模板定义

template class AtomQueue{public:    AtomQueue(uint64_t size);    ~AtomQueue();    bool Push(const T& v);    bool Pop(T& v);    private:    uint64_t    P0[8];  //频繁变化数据, 避免伪共享, 采用Padding    uint64_t    head_;  //生产者标记, 表示生产到这个位置，但还没有生产该位置    uint64_t    P1[8];    uint64_t    tail_;  //消费者标记, 表示消费到这个位置，但还没有消费该位置    uint64_t    P2[8];    uint64_t    size_;  //数组最大容量, 必须满足2^N    int         mod_;   //取模 % -> & 减少2ns    T*          data_;  //环形数据数组    uint8_t*    valid_; //环形可用数组，与数据数组大小一致};

9.2.2 构造函数与析构函数

template  AtomQueue::AtomQueue(uint64_t size) : size_(size << 1), head_(0), tail_(0) {    if ((size_ & (size_ - 1)))     {        printf("AtomQueue::size_ must be 2^N !!!\n");        exit(0);    }    mod_    = size_ - 1;    data_   = new T[size_];    valid_  = new uint8_t[size_];    std::memset(valid_, 0, sizeof(valid_));}
template AtomQueue::~AtomQueue(){    delete[] data_;    delete[] valid_; }

9.2.3 生产者调用的 Push 函数 和 消费者调用的 Pop 函数

template bool AtomQueue::Push(const T& v){    uint64_t head = head_, tail = tail_;    if (tail <= head ? tail + size_ <= head + 1 : tail <= head + 1)        return false;    if (valid_[head])        return false;    if (!__sync_bool_compare_and_swap(&head_, head, (head + 1) & mod_))        return false;    data_[head] = v;    valid_[head] = 1;    return true;}
template bool AtomQueue::Pop(T& v){    uint64_t tail = tail_;    if (tail == head_ || !valid_[tail])        return false;    if (!__sync_bool_compare_and_swap(&tail_, tail, (tail + 1) & mod_))         return false;    v = std::move(data_[tail]);    valid_[tail] = 0;    return true;}

• 当刚初始化的队列，队列还是空的，这时核心0 执行 Push 函数，同时核心1 执行 Pop 函数；
• Push 里的条件（tail <= head ? tail + size_ <= head + 1 : tail <= head + 1）为 true，表示队列已经满了，所以生产失败，其实队列还是空的；
• Pop 里的条件（tail == head_ || !valid_[tail]）为 false，表示队列有数据，并且消费 tail 位置数据，实际上 tail 位置还没数据；
• 导致生产和消费都发生了错误。

解决办法是添加读写屏障（LoadStore barrier），如下表格：

通过执行反汇编命令（objdump -S a.out）得到 Push 中下面代码的汇编代码。

if (!__sync_bool_compare_and_swap(&tail_, tail, (tail + 1) & mod_)) 400a61:  48 8b 45 f8            mov    -0x8(%rbp),%rax400a65:  48 8d 50 01            lea    0x1(%rax),%rdx400a69:  48 8b 45 e8            mov    -0x18(%rbp),%rax400a6d:  8b 80 d8 00 00 00      mov    0xd8(%rax),%eax400a73:  48 98                  cltq   400a75:  48 89 d1               mov    %rdx,%rcx400a78:  48 21 c1               and    %rax,%rcx400a7b:  48 8b 45 e8            mov    -0x18(%rbp),%rax400a7f:  48 8d 90 88 00 00 00   lea    0x88(%rax),%rdx400a86:  48 8b 45 f8            mov    -0x8(%rbp),%rax400a8a:  f0 48 0f b1 0a         lock cmpxchg %rcx,(%rdx)400a8f:  0f 94 c0               sete   %al400a92:  83 f0 01               xor    $0x1,%eax400a95:  84 c0                  test   %al,%al400a97:  74 07                  je     400aa0 <_ZN9AtomQueueIiE3PopERi+0x8c>
return false;400a99:  b8 00 00 00 00         mov    $0x0,%eax400a9e:  eb 40                  jmp    400ae0 <_ZN9AtomQueueIiE3PopERi+0xcc>

发现 __sync_bool_compare_and_swap 函数对应的汇编代码为：

400a8a:  f0 48 0f b1 0a         lock cmpxchg %rcx,(%rdx)

• Alder Lake - 维基百科，自由的百科全书
• CPU Cache：访存速度是如何大幅提升的？
• MESI协议 - 维基百科，自由的百科全书
• MESI协议：多核CPU是如何同步高速缓存的？
• 内存模型：有了MESI为什么还需要内存屏障？
• https://www.scss.tcd.ie/Jeremy.Jones/VivioJS/caches/MESIHelp.htm
• MESIF协议 - 维基百科，自由的百科全书
• MOESI协议 - 维基百科，自由的百科全书

• 为什么在 x86 架构下只有 StoreLoad 屏障是有效指令？

• The JSR-133 Cookbook for Compiler Writers

• The JSR-133 Cookbook for Compiler Writers[译]

• x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors

• 从 Java 内存模型看内部细节

• 比较并交换 - 维基百科，自由的百科全书

• https://en.wikipedia.org/wiki/Compare-and-swap

• C++11原子操作与无锁编程

• 内存模型和atomic：理解并发的复杂性

• x86-TSO : 适用于x86体系架构并发编程的内存模型