速度快的存储硬件成本高、容量小，速度慢的成本低、容量大。为了权衡成本和速度，计算机存储分了很多层次，扬长避短，有寄存器、L1 cache、L2 cache、L3 cache、主存（内存）和硬盘等。图1 展示了现代存储体系结构。
根据程序的空间局部性和时间局部性原理，缓存命中率可以达到 70～90% 。因此，增加缓存可以让整个存储系统的性能接近寄存器，并且每字节的成本都接近内存，甚至是磁盘。
所以缓存是存储体系结构的灵魂。
cache line（缓存行）是缓存进行管理的最小存储单元，也叫缓存块，每个 cache line 包含 Flag、Tag 和 Data ，通常 Data 大小是 64 字节，但不同型号 CPU 的 Flag 和 Tag 可能不相同。从内存向缓存加载数据是按整个缓存行加载的，一个缓存行和一个相同大小的内存块对应。
图2
图2中，缓存是按照矩阵方式排列(M × N)，横向是组(Set)，纵向是路(Way)。每一个元素是缓存行(cache line)。
那么给定一个虚拟地址 addr 如何在缓存中定位它呢？首先把它所在的组号找到，即：
//左移6位是因为 Block Offset 占 addr 的低 6 位，Data 为 64 字节
Set Index = (addr >> 6) % M;然后遍历该组所有的路，找到 cache line 中的 Tag 与 addr 中 Tag 相等为止，所有路都没有匹配成功，那么缓存未命中。
整个缓存容量 = 组数 × 路数 × 缓存行大小我电脑的CPU信息：
我电脑的缓存信息：
通过缓存行大小和路数可以倒推出缓存的组数，即：
缓存组数 = 整个缓存容量 ÷ 路数 ÷ 缓存行大小目前最常用的缓存替换策略是最近最少使用算法（Least Recently Used ，LRU）或者是类似 LRU 的算法。
LRU 算法比较简单，如图3，缓存有 4 路，并且访问的地址都哈希到了同一组，访问顺序是 D1、D2、D3、D4 和 D5，那么 D1 会被 D5 替换掉。算法的实现方式有很多种，最简单的实现方式是位矩阵。
首先，定义一个行、列都与缓存路数相同的矩阵。当访问某个路对应的缓存行时，先将该路对应的所有行置为 1，然后再将该路对应的所有列置为 0。
最近最少使用的缓存行所对应的矩阵行中 1 的个数最少，最先被替换出去。
图3
缓存缺失就是缓存未命中，需要把内存中数据加载到缓存，所以运行速度会变慢。
就拿我的电脑来测试，L1d 的缓存大小是 32KB（32768B），8路，缓存行大小 64B，那么
缓存组数 = 32 × 1024 ÷ 8 ÷ 64 = 64运行下面的代码
char *a = new char(64 * 64 * 8); //32768B
for(int i = 0; i < 20000000; i++)
for(int j = 0; j < 32768; j += 4096)
a[j]++;结果：循环 160000000 次，耗时 301 ms。除了第一次未命中缓存，后面每次读写数据都能命中缓存。
调整上面的代码，并运行
char *a = new char(64 * 64 * 8 * 2); //65536B
for(int i = 0; i < 10000000; i++)
for(int j = 0; j < 65536; j += 4096)
a[j]++;结果：循环 160000000 次，耗时 959 ms。每一次读写数据都没有命中缓存，所以耗时增加了 2 倍。
程序局部性就是读写内存数据时读写连续的内存空间，目的是让缓存可以命中，减少缓存缺失导致替换的开销。
我电脑上运行下面代码
int M = 10000, N = 10000;
char (*a)[N] = (char(*)[N])calloc(M * N, sizeof(char));
for(int i = 0; i < M; i++)
for(int j = 0; j < N; j++)
a[i][j]++;结果：循环 100000000 次，耗时 314 ms。利用了程序局部性原理，缓存命中率高。
修改上面的代码如下，并运行
int M = 10000, N = 10000;
char (*a)[N] = (char(*)[N])calloc(M * N, sizeof(char));
for(int j = 0; j < N; j++)
for(int i = 0; i < M; i++)
a[i][j]++;结果：循环 100000000 次，耗时 1187 ms。没有利用程序局部性原理，缓存命中率低，所以耗时增加了 2 倍。
当两个线程同时各自修改两个相邻的变量，由于缓存是按缓存行来整体组织的，当一个线程对缓存行中数据执行写操作时，必须通知其他线程该缓存行失效，导致另一个线程从缓存中读取其想修改的数据失败，必须从内存重新加载，导致性能下降。
我电脑运行下面代码
struct S {
long long a;
long long b;
} s;
std::thread t1([&]() {
for(int i = 0; i < 100000000; i++)
s.a++;
});
std::thread t2([&]() {
for(int i = 0; i < 100000000; i++)
s.b++;
});结果：耗时 512 ms，原因上面提到了，就是两个线程互相影响，使对方的缓存行失效，导致直接从内存读取数据。
解决办法是对上面代码做如下修改：
struct S {
long long a;
long long noop[8];
long long b;
} s;结果：耗时 181 ms，原因是通过 long long noop[8] 把两个数据（a 和 b）划分到两个不同的缓存行中，不再互相使对方的缓存失效，所以速度变快了。
本小节的测试代码都没有开启编译器优化，即编译选项为-O0 。
在单核时代，增加缓存可以大大提高读写速度，但是到了多核时代，却引入了缓存一致性问题，如果有一个核心修改了缓存行中的某个值，那么必须有一种机制保证其他核心能够观察到这个修改。
从缓存和内存的更新关系来看，分为：
从写缓存时 CPU 之间的更新策略来看，分为：
写更新（Write Update）每次缓存写入新的值，该核心必须发起一次总线请求，通知其他核心更新他们缓存中对应的值。
坏处：写更新会占用很多总线带宽；
好处：其他核心能立刻获得最新的值。
写无效（Write Invalidate）每次缓存写入新的值，都将其他核心缓存中对应的缓存行置为无效。
坏处：当其他核心再次访问该缓存时，发现缓存行已经失效，必须从内存中重新载入最新的数据；
好处：多次写操作只需发一次总线事件，第一次写已经将其他核心缓存行置为无效，之后的写不必再更新状态，这样可以有效地节省核心间总线带宽。
从写缓存时数据是否被加载来看，分为：
MESI协议是⼀个基于失效的缓存⼀致性协议，是⽀持写回（write-back）缓存的最常⽤协议。也称作伊利诺伊协议 (Illinois protocol，因为是在伊利诺伊⼤学厄巴纳-⾹槟分校被发明的)。
为了解决多个核心之间的数据传播问题，提出了总线嗅探（Bus Snooping）策略。本质上就是把所有的读写请求都通过总线（Bus）广播给所有的核心，然后让各个核心去嗅探这些请求，再根据本地的状态进行响应。
这些状态信息实际上存储在缓存行（cache line）的 Flag 里。
处理器对缓存的请求:
PrRd：核心请求从缓存块中读出数据；
PrWr：核心请求向缓存块写入数据。
总线对缓存的请求:
BusRd：总线嗅探器收到来自其他核心的读出缓存请求；
BusRdX：总线嗅探器收到另一核心写⼀个其不拥有的缓存块的请求；
BusUpgr：总线嗅探器收到另一核心写⼀个其拥有的缓存块的请求；
Flush：总线嗅探器收到另一核心把一个缓存块写回到主存的请求；
FlushOpt：总线嗅探器收到一个缓存块被放置在总线以提供给另一核心的请求，和 Flush 类似，但只不过是从缓存到缓存的传输请求。
图4
表1是对状态机图4 的详解讲解（选读）
| 当前状态 | 事件 | 响应 |
| PrRd |
| |
| PrWr |
| |
| BusRd |
| |
| BusRdX |
| |
E | PrRd |
|
| PrWr |
| |
BusRd |
| |
BusRdX |
| |
| S | PrRd |
|
PrWr |
| |
| BusRd |
| |
BusRdX |
| |
| I | PrRd |
|
PrWr |
| |
BusRd |
| |
BusRdX/BusUpgr |
|
表1
图5
各家 CPU 厂商没有都完全按照 MESI 实现缓存一致性协议，导致 MESI 有很多变种，例如：Intel 采用的 MESIF 和 AMD 采用的 MOESI，ARM 大部分采用的是 MESI，少部分使用的是 MOESI 。
MOESI 是一个完整的缓存一致性协议，它包含了其他协议中常用的所有可能状态。除了四种常见的 MESI 协议状态之外，还有第五种 Owned 状态，表示修改和共享的数据。
这就避免了在共享数据之前将修改过的数据写回主存的需要。虽然数据最终仍然必须写回，但写回可能是延迟的。
MESIF 是一个缓存一致性和记忆连贯协议，该协议由五个状态组成：已修改**（M），互斥（E），共享（S），无效（I）和转发（F）**。
M，E，S 和 I 状态与 MESI 协议一致。F 状态是 S 状态的一种特殊形式，当系统中有多个 S 时，必须选取一个转换为 F，只有 F 状态的负责应答。通常是最后持有该副本的转换为 F，注意 F 是干净的数据。
该协议与 MOESI 协议有较大的不同，也远比 MOESI 协议复杂。该协议由 Intel 的 快速通道互联 QPI（QuickPath Interconnect）技术引入，其主要目的是解决“基于点到点互联的非一致性内存访问（Non-uniform memory access，NUMA**）处理器系统”的缓存一致性问题，而不是“基于共享总线的一致性内存访问（Uniform Memory Access， UMA**）处理器系统”的缓存一致性问题。
编译器和处理器都必须遵守重排序规则。在单处理器的情况下，不需要任何额外的操作便能保持正确的顺序。但是对于多处理器来说，保证一致性通常需要增加内存屏障指令。即使编译器可以优化掉字段的访问（例如因为未使用加载到的值），编译器仍然需要生成内存屏障，就好像字段访问仍然存在一样（可以单独将内存屏障优化掉）。
内存屏障只与内存模型中的高级概念（例如 acquire 和 release）间接相关。内存屏障指令只直接控制 CPU 与其缓存的交互，以及它的写缓冲区（持有等待刷新到内存的数据的存储）和它的用于等待加载或推测执行指令的缓冲。这些影响可能导致缓存、主内存和其他处理器之间的进一步交互。
几乎所有的处理器都至少支持一个粗粒度的屏障指令（通常称为 Fence，也叫全屏障），它保证了严格的有序性：在 Fence 之前的所有读操作（load）和写操作（store）先于在 Fence 之后的所有读操作（load）和写操作（store）执行完。对于任何的处理器来说，这通常都是最耗时的指令之一（它的开销通常接近甚至超过原子操作指令）。大多数处理器还支持更细粒度的屏障指令。
LoadLoad Barrier（读读屏障）
指令 Load1; LoadLoad; Load2 保证了 Load1 先于 Load2 和后续所有的 load 指令加载数据。通常情况下，在执行预测读（speculative loads）或乱序处理（out-of-order processing）的处理器上需要显式的 LoadLoad Barrier。在始终保证读顺序（load ordering）的处理器上，这些屏障相当于无操作（no-ops）。
StoreStore Barrier（写写屏障）
指令 Store1; StoreStore; Store2 保证了 Store1 的数据先于 Store2 及后续 store 指令的数据对其他处理器可见（刷新到内存）。通常情况下，在不保证严格按照顺序从写缓冲区（store buffers）或者 缓存（caches）刷新到其他处理器或内存的处理器上，需要使用 StoreStore Barrier。
LoadStore Barrier（读写屏障）
指令 Load1; LoadStore; Store2 保证了 Load1 的加载数据先于 Store2 及后续 store 指令刷新数据到主内存。只有在乱序（out-of-order）处理器上，等待写指令（waiting store instructions）可以绕过读指令（loads）的情况下，才会需要使用 LoadStore 屏障。
StoreLoad Barrier（写读屏障）刷新写缓冲区，最耗时
指令 Store1; StoreLoad; Load2 保证了 Store1 的数据对其他处理器可见（刷新数据到内存）先于 Load2 及后续的 load 指令加载数据。StoreLoad 屏障可以防止后续的读操作错误地使用了 Store1 写的数据，而不是使用来自另一个处理器的更近的对同一位置的写。因此只有需要将对同一个位置的写操作（stores）和随后的读操作（loads）分开时，才严格需要 StoreLoad 屏障。StoreLoad 屏障通常是开销最大的屏障，几乎所有的现代处理器都需要该屏障。之所以开销大，部分原因是它需要禁用绕过缓存（cache）从写缓冲区（Store Buffer）读取数据的机制。这可以通过让缓冲区完全刷新，外加暂停其他操作来实现，这就是 Fence 的效果。一般用 Fence 代替 StoreLoad Barrier ，所以事实上，执行 StoreLoad 指令同时也获得了其他三个屏障的效果，但是通过组合其他屏障通常不能获得与 StoreLoad Barrier 相同的效果。
表2：各处理器支持的内存屏障和原子操作
严格按照MESI协议，核心0 在修改本地缓存之前，需要向其他核心发送 Invalid 消息，其他核心收到消息后，使他们本地对应的缓存行失效，并返回 Invalid acknowledgement 消息，核心0 收到后修改缓存行。这里核心0 等待其他核心返回确认消息的时间对核心来说是漫长的。
图6
为了解决这个问题，引入了 Store Buffer ，当核心想修改缓存时，直接写入 Store uffer ，无需等待，继续处理其他事情，由 Store Buffer 完成后续工作。
图7
这样一来写的速度加快了，但是引来了新问题，下面代码的 bar 函数中的断言可能会失败。
int a = 0, b = 0;
// CPU0
void foo() {
a = 1;
b = 1;
}
// CPU1
void bar() {
while (b == 0) continue;
assert(a == 1);
}第一种情况：CPU 为了提升运行效率和提高缓存命中率，采用了乱序执行；
第二种情况：Store Buffer 在写入时，b 所对应的缓存行是 E 状态，a 所对应的缓存行是 S 状态，因为对 b 的修改不需要核心间同步，但是修改 a 则需要，也就是 b 会先写入缓存。与之对应 CPU1 中 a 是 S 状态，b 是 I 状态，由于 b 所对应的缓存区域是 I 状态，它就会向总线发出 BusRd 请求，那么 CPU1 就会先把 b 的最新值读到本地，完成变量 b 值的更新，但是从缓存直接读取 a 值是 0 。
举一个更极端的例子
// CPU0
void foo() {
a = 1;
b = a;
}第一种情况不会发生了，原因是代码有依赖，不会乱序执行。但由于 Store Buffer 的存在，第二种情况仍然可能发生，原因同上。这会让人感到更加匪夷所思。
为了解决上面问题，引入了内存屏障，屏障的作用是前边的读写操作未完成的情况下，后面的读写操作不能发生。这就是 Arm 上 dmb 指令的由来，它是数据内存屏障（Data Memory Barrier）的缩写。
int a = 0, b = 0;
// CPU0
void foo() {
a = 1;
smp_mb(); //内存屏障，各CPU平台实现不一样
b = 1;
}
// CPU1
void bar() {
while (b == 0) continue;
assert(a == 1);
}加上内存屏障后，保证了 a 和 b 的写入缓存顺序。
总的来说，Store Buffer 提升了写性能，但放弃了缓存的顺序一致性，这种现象称为**弱缓存一致性**。通常情况下，多个 CPU 一起操作同一个变量的情况是比较少的，所以 Store Buffer 可以大幅提升程序的性能。但在需要核间同步的情况下，还是需要通过手动添加内存屏障来保证缓存一致性。
上面解决了核间同步的写问题，但是核间同步还有一个瓶颈，那就是读。
前面引入 Store Buffer 提升了写入速度，那么 invalid 消息确认速度相比起来就慢了，带来了速度不匹配，很容易导致 Store Buffer 的内容还没及时写到缓存里，自己就满了，从而失去了加速的作用。
为了解决这个问题，又引入了 Invalid Queue。收到 Invalid 消息的核心立刻返回 Invalid acknowledgement 消息，然后把 Invalid 消息加入 Invalid Queue ，等到空闲的时候再去处理 Invalid 消息。
图8
运行上面增加内存屏障的代码，第 11 行的断言又可能失败了。
核心0 中 a 所对应的缓存行是 S 状态，b 所对应的缓存行是 E 状态；核心1中 a 所对应的缓存行是 S 状态，b 所对应的缓存行是 I 状态；
引入 Invalid Queue 后，对核心1 来说看到的 a 和 b 的写入又出现乱序了。
解决办法是继续加内存屏障，核心1 想越过屏障必须清空 Invalid Queue，及时处理了对 a 的无效，然后读取到新的 a 值，如下代码：
int a = 0, b = 0;
// CPU0
void foo() {
a = 1;
smp_mb();
b = 1;
}
// CPU1
void bar() {
while (b == 0) continue;
smp_mb(); //继续加内存屏障
assert(a == 1);
}这里使用的内存屏障是全屏障，包括读写屏障，过于严格了，会导致性能下降，所以有了细粒度的读屏障和写屏障。
分离的写屏障和读屏障的出现，是为了更加精细地控制 Store Buffer 和 Invalid Queue 的顺序。
优化前面的代码如下
int a = 0, b = 0;
// CPU0
void foo() {
a = 1;
smp_wmb(); //写屏障
b = 1;
}
// CPU1
void bar() {
while (b == 0) continue;
smp_rmb(); //读屏障
assert(a == 1);
}这种修改只有在区分读写屏障的体系结构里才会有作用，比如 alpha 结构。在 x86 和 Arm 中是没有作用的，因为 x86 采用了 TSO 模型，后面会详细介绍，而 Arm 采用了单向屏障。
单向屏障 (half-way barrier) 也是一种内存屏障，但它不是以读写来区分的，而是像单行道一样，只允许单向通行，例如 ARM 中的 stlr 和 ldar 指令就是这样。
图9 ARM Figure 13.2. One-way barriers
理论普及的差不多了，接下单独来说说服务端同学工作中最常用的 x86 内存模型，填一下 4.3 中留下的坑。
x86-TSO（ Total Store Order）采用的是图10 模型。
图10
x86-TSO 有下面几个特点：
下面的代码是 Linux 在 x86 下的内存屏障定义
解析
如果 核心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，使得当前核心之前的写操作立马可以被其他核心看见。
下面有两种解决办法示意图：
解析
如果 核心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）上可以出现上述现象；
其实还有一个更直接的测试用例，如下：
解析
在 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 重排序，所以需要 **Store****Store barrier** ；
解析
在 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 重排序，所以需要 **Load**Store 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 上观察到。
解析
假如 核心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 上，写写和读写都是乱序，就不可能保证写的传递性了；
比较并交换(compare and swap, CAS)，是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。
下面代码是使用 CAS 的一个例子（无锁队列 Pop 函数）
template <typename T>
bool AtomQueue<T>::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 操作将会成功执行，使内存中的数据变为新值。
如果内存中的值在这期间内被修改过，则一般来说旧值 会与内存中的数据不同，这时 CAS 操作将会失败，新值 将不会被写入内存。
在应用中 CAS 可以用于实现无锁数据结构，常见的有无锁队列（先入先出）以及无锁栈（先入后出）。对于可在任意位置插入数据的链表以及双向链表，实现无锁操作的难度较大。
ABA问题是无锁结构实现中常见的一种问题，可基本表述为：
对于 P1 来说，数值 A 未发生过改变，但实际上 A 已经被变化过了，继续使用可能会出现问题。在CAS操作中，由于比较的多是指针，这个问题将会变得更加严重。试想如下情况：
图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;
}而线程 P2 在 P1 执行 CAS 操作之前把它打断了，并对栈进行了一系列的 pop 和 push 操作，使栈变为如下结构：
图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 问题。
CAS 操作基于 CPU 提供的原子操作指令实现。对于 Intel X86 处理器，可通过在汇编指令前增加 lock 前缀**来锁定系统总线，使系统总线在汇编指令执行时无法访问相应的内存地址。而各个编译器根据这个特点实现了各自的原子操作函数。**
程序代码最终都会被翻译为 CPU 指令，一条最简单的加减法语句都会被翻译成几条指令执行；为了避免语句在 CPU 这一层级上的指令交叉带来的不可预知行为，在多线程程序设计时必须通过一些方式来进行规范，最常见的做法就是引入互斥锁，但互斥锁是操作系统这一层级的，最终映射到 CPU 上也是一堆指令，是指令就必然会带来额外的开销。
既然 CPU 指令是多线程不可再分的最小单元，那我们如果有办法将代码语句和指令对应起来，不就不需要引入互斥锁从而提高性能了吗? 而这个对应关系就是所谓的原子操作；在 C++11 的 atomic 中有两种做法:
可以通过 is_lock_free 函数，判断一个 atomic 是否是 lock-free 类型。
原子操作有三类：
使用原子操作模拟互斥锁的行为就是自旋锁，互斥锁状态是由操作系统控制的，自旋锁的状态是程序员自己控制的，常用的自旋锁模型有：
LOCK 时自旋锁是自己轮询状态，如果不引入中断机制，会有大量计算资源浪费到轮询本身上；常用的做法是使用yield切换到其他线程执行，或直接使用sleep暂停当前线程.
C++11 原子操作的很多函数都有个 std::memory_order 参数，这个参数就是这里所说的内存模型，对应缓存一致性模型，其作用是对同一时间的读写操作进行排序，一共定义了 6 种类型如下：
在不同的 CPU 架构上，这些模型的具体实现方式可能不同，但是 C++11 帮你屏蔽了内部细节，不用考虑内存屏障，只要符合上面的使用规则，就能得到想要的效果。可能有时使用的模型粒度比较大，会损耗性能，当然还是使用各平台底层的内存屏障粒度更准确，效率也会更高，对程序员的功底要求也高。
这个关键字仅仅保证数据只在内存中读写，直接操作它既不能保证操作是原子的，也不能通用地达到内存同步的效果；
由于 volatile 不能在多处理器的环境下确保多个线程能看到同样顺序的数据变化，在今天的通用应用程序中，不应该再看到 volatile 的出现。
本节是 CPU 缓存一致性的实战部分，通过运用前面的理论知识实现一个无锁队列，达到学以致用的目的。
下面是我采用 CAS 实现了一个多生产者多消费者无锁队列，设计参考 Disruptor ，最高可达 660万QPS（单生产者单消费者）和 160万QPS（10个生产者10个消费者）。
1、如图15，使用 2 个环形数组，数组元素均非原子变量，一个存储 T 范型数据（一般为指针），另一个是可用性检查数组（uint8_t）。Head 是所有生产者的竞争标记，Tail 是所有消费者的竞争标记。红色区表示待生产位置，绿色区表示待消费位置。
图15
2、生产者们通过 CAS 来竞争和移动 Head，抢到 Head 的生产者，先将 Head 加1，再生产原 Head 位置的数据；同样的消费者们通过 CAS 来竞争和移动 Tail，抢到 Tail 的消费者，先将 Tail 加1，再消费原 Tail 位置的数据 。
下面多生产者多消费者无锁队列的代码是在 x86-64（x86-TSO） 平台上编写和测试的。
Talk is cheap. Show me the code.
template <typename T>
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_; //环形可用数组，与数据数组大小一致
};细心的你会看到 head_ 和 tail_ 还有后面的变量中加添加了无意义的字段 P0、P1 和 P2 ，因为 head_ 和 tail_ 频繁变化，目的是防止出现前面讲过的伪共享导致性能下降问题。
template <typename T>
AtomQueue<T>::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 <typename T>
AtomQueue<T>::~AtomQueue()
{
delete[] data_;
delete[] valid_;
}构造函数中强制传入的队列大小（size）必须为 2 的幂数，目的是想用 & 而不是 % 取模，因为 & 比 % 快 2ns，最求极致性能。
template <typename T>
bool AtomQueue<T>::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 <typename T>
bool AtomQueue<T>::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;
}分析一下上述 Push 和 Pop 函数中读写操作是否需要增加内存屏障，读写操作可以抽象描述如下表格：
在读写操作乱序的 CPU 上可以出现上述情况，会导出线 Bug，解释一下：
解决办法是添加读写屏障（LoadStore barrier），如下表格：
在 Arm 等乱序执行的平台上可以解决问题；幸好 x86-TSO 平台上读操作不能延后，也就不需要读写屏障，手动加了也是空操作（no-op）。
通过执行反汇编命令（objdump -S a.out）得到 Push 中下面代码的汇编代码。
if (!__sync_bool_compare_and_swap(&tail_, tail, (tail + 1) & mod_))
400a61: 48 8b 45 f8 mov -0x8(%rbp),%rax
400a65: 48 8d 50 01 lea 0x1(%rax),%rdx
400a69: 48 8b 45 e8 mov -0x18(%rbp),%rax
400a6d: 8b 80 d8 00 00 00 mov 0xd8(%rax),%eax
400a73: 48 98 cltq
400a75: 48 89 d1 mov %rdx,%rcx
400a78: 48 21 c1 and %rax,%rcx
400a7b: 48 8b 45 e8 mov -0x18(%rbp),%rax
400a7f: 48 8d 90 88 00 00 00 lea 0x88(%rax),%rdx
400a86: 48 8b 45 f8 mov -0x8(%rbp),%rax
400a8a: f0 48 0f b1 0a lock cmpxchg %rcx,(%rdx)
400a8f: 0f 94 c0 sete %al
400a92: 83 f0 01 xor $0x1,%eax
400a95: 84 c0 test %al,%al
400a97: 74 07 je 400aa0 <_ZN9AtomQueueIiE3PopERi+0x8c>
return false;
400a99: b8 00 00 00 00 mov $0x0,%eax
400a9e: eb 40 jmp 400ae0 <_ZN9AtomQueueIiE3PopERi+0xcc>发现 __sync_bool_compare_and_swap 函数对应的汇编代码为：
400a8a: f0 48 0f b1 0a lock cmpxchg %rcx,(%rdx)是带 lock 前缀的命令，前面讲过，在 x86-TSO 上，带有 lock 前缀的命令具有刷新 Store Buffer 的功能，也就是 head_ 和 tail_ 的修改都能及时被其他核心观察到，可以做到及时生产和消费。
OMG，竟然写了这么多，头一次！终于把 CPU缓存、内存屏障、原子操作以及无锁队列一口气梳理完了。期间查阅大量资料，这里特地感谢一下参考资料中的作者，让我学到了很多知识；期间也写了很多测试代码来验证理论，避免误人子弟，尽量做到有理有据。由于作者水平有限，本文错漏缺点在所难免，希望读者批评指正。
本文由哈喽比特于1年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/kJF_ezR2TdPnYlfPCjwdKQ
京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而，京东官方通过微博发言人发布的消息澄清了这些传言，称这些言论纯属虚假信息和蓄意捏造。
日前，据博主“@超能数码君老周”爆料，国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。
据报道，荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦（ASML）CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。
今年早些时候，抖音悄然上线了一款名为“青桃”的 App，Slogan 为“看见你的热爱”，根据应用介绍可知，“青桃”是一个属于年轻人的兴趣知识视频平台，由抖音官方出品的中长视频关联版本，整体风格有些类似B站。
日前，威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”，同时，他发文表示：中国汽车普及率低于非洲国家尼日利亚，每百户家庭仅17户有车。意大利世界排名第一，每十户中九户有车。
近日，一项新的研究发现，维生素 C 和 E 等抗氧化剂会激活一种机制，刺激癌症肿瘤中新血管的生长，帮助它们生长和扩散。
据媒体援引消息人士报道，苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后，3D系统一度大涨超10%，不过截至周三收盘，该股涨幅回落至2%以内。
9月2日，坐拥千万粉丝的网红主播“秀才”账号被封禁，在社交媒体平台上引发热议。平台相关负责人表示，“秀才”账号违反平台相关规定，已封禁。据知情人士透露，秀才近期被举报存在违法行为，这可能是他被封禁的部分原因。据悉，“秀才”年龄39岁，是安徽省亳州市蒙城县人，抖音网红，粉丝数量超1200万。他曾被称为“中老年...
9月3日消息，亚马逊的一些股东，包括持有该公司股票的一家养老基金，日前对亚马逊、其创始人贝索斯和其董事会提起诉讼，指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。
据消息，为推广自家应用，苹果现推出了一个名为“Apps by Apple”的网站，展示了苹果为旗下产品（如 iPhone、iPad、Apple Watch、Mac 和 Apple TV）开发的各种应用程序。
特斯拉本周在美国大幅下调Model S和X售价，引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金（Future Fund）管理合伙人加里·布莱克发帖称，降价是一种“短期麻醉剂”，会让潜在客户等待进一步降价。
据外媒9月2日报道，荷兰半导体设备制造商阿斯麦称，尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效，但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。
近日，根据美国证券交易委员会的文件显示，苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元（约 4.65 亿元人民币）。用于在 2023-2025 年期间，发射卫星，进一步扩展苹果 iPhone 系列的 SOS 卫星服务。
据报道，马斯克旗下社交平台𝕏（推特）日前调整了隐私政策，允许 𝕏 使用用户发布的信息来训练其人工智能（AI）模型。新的隐私政策将于 9 月 29 日生效。新政策规定，𝕏可能会使用所收集到的平台信息和公开可用的信息，来帮助训练 𝕏 的机器学习或人工智能模型。
9月2日，荣耀CEO赵明在采访中谈及华为手机回归时表示，替老同事们高兴，觉得手机行业，由于华为的回归，让竞争充满了更多的可能性和更多的魅力，对行业来说也是件好事。
《自然》30日发表的一篇论文报道了一个名为Swift的人工智能（AI）系统，该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。
近日，非营利组织纽约真菌学会（NYMS）发出警告，表示亚马逊为代表的电商平台上，充斥着各种AI生成的蘑菇觅食科普书籍，其中存在诸多错误。
社交媒体平台𝕏（原推特）新隐私政策提到：“在您同意的情况下，我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”
2023年德国柏林消费电子展上，各大企业都带来了最新的理念和产品，而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。
罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品，具体内容为：“以我对我‘子公司’的了解，我认为 iPhone 15 跟 iPhone 14 不会有什么区别的，除了序（列）号变了，这个‘不要脸’的东西，这个‘臭厨子’。
