开幕之夜

原子操作

一条指令看起来可能是一个不可分割的动作，而实际上根本不是。以给内存中的某个值加上 5 为例：

add qword [rel counter], 5

在底层，处理器并不能直接对内存做加法。 它把这一条指令拆成三个更小的步骤，称为微操作：

1. 读取内存中的当前值；
2. 在寄存器中修改这个值，把它加上 5；
3. 把结果写回。

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

这是一种常见的模式，称为读取-修改-写入（RMW）。

注意，读取（加载）和写入（存储）是两个独立的事件，因此它们之间存在一个时间窗口。 我们通常不会注意到这一点，因为在单核上，每条指令都保证在开始下一条之前完整地产生效果。 因此这个窗口是看不见的，add表现得就像一个整体。

然而，现代 CPU 很少是单核的，应用程序常常同时运行在多个核心上，它们之间没有任何先后顺序。 当多个核心在同一瞬间运行时，另一个核心可以在那个窗口内读取或写入counter，也就是在本核心加载之后、存储之前。 两个线程各自加载相同的旧值，各自加上 5，再各自存储自己的结果。 发生了两次加法，但值却只增加了 5。 有一次更新悄无声息地丢失了。

这就是数据竞争，多线程代码中的常见问题。

并不是每个值都会以这种方式被暴露出来。 每个线程都有自己的寄存器和自己的栈，因此保存在寄存器中的值，或者线程栈上的局部变量，都是该线程独有的，不会发生竞争。 只有线程共享的内存，比如上面的counter，才需要保护。

x86-64 提供了一组指令来解决这个问题，方法是让一条指令不可分割。 它不仅对处理它的核心表现为一个整体，对其他所有核心也是如此。 这种始终作为一个整体、其他核心无法拆分的操作，称为原子操作。

原子交换

xchg指令交换两个操作数。 目标操作数会变为源操作数之前的值，而源操作数会变为目标操作数之前的值。 从概念上讲，可以把它看成两条mov指令同时发生。

和往常一样，它既可以用两个寄存器操作数，也可以用一个内存操作数加一个寄存器操作数：

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

当与内存操作数一起使用时，xchg_总是_原子的。

lock 前缀

在 x86-64 中，让一条指令具备原子性最常见的方式，就是加上lock前缀。 它把读取、修改和写入融合成一个不可分割的步骤。 这意味着核心在整个过程中独占该内存，因此其他核心无法在这期间读取或写入那个位置。

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock只在目标是内存时才有效，而且只适用于对该内存执行读取-修改-写入的指令：

1. 算术运算，例如add、sub、inc、dec、neg；
2. 位运算，例如and、or、xor、not；
3. 位操作bts、btr、btc；
4. 其他一些专用指令，例如下面会介绍的xadd和cmpxchg。

交换并相加

普通的lock add会更新内存，但会把旧值丢掉。 很多时候，旧值恰恰是想要的东西，比如给每个线程分配一个不同的号码。

xadd指令（x表示 exchange）在相加的同时返回之前的值。 它把和写入目标，并把目标原来的值留在源寄存器中。

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

加上lock前缀，这就是原子的获取并相加。 当多个线程在同一个计数器上运行时，每次调用都会返回一个不同的旧值。

和lock add一样，计数器最终会正好等于调用的次数。 不过，与lock add不同的是，每一个中间值也都会被返回，分别交给各个调用者。

比较并交换

xadd做加法，xchg做覆盖，但两者都无法让新值依赖于当前值，并且只在底层没有发生变化时才应用它。 cmpxchg（比较并交换）提供的正是这种条件更新，它是这些原语中最通用的一个。

cmpxchg dest, src以rax作为隐式累加器，并将它与dest比较：

• 如果dest == rax，则dest = src，并且ZF = 1。
• 如果dest != rax，则rax = dest，并且ZF = 0。

注意，只有当dest等于之前加载到rax中的预期值时，才会更新dest。 这种相等性确保dest仍然保存着新值所依据的那个值，因此基于过期读取的更新永远不会被应用。 这使得cmpxchg成为原子更新的基础构件，也称为比较并交换（CAS）：

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

这个重试循环是无锁更新的核心。 读取与比较并交换之间的那个窗口，正是另一个线程可能插进来的时机，而cmpxchg通过拒绝存储基于过期读取算出的值来抓住这一点。

内存排序

到目前为止，每个操作都只涉及一个位置。 当线程通过多个位置进行协调时，就出现了一个新问题：一个线程的写入以什么顺序对另一个线程可见。 回答这个问题的规则，就是处理器的内存排序。

无分支代码的概念提到过这样一个想法：现代核心不会一次一条地慢慢执行指令。 它会同时让许多指令处于执行中，并在可能的地方提前运行。 这意味着一次写入变得对其他核心可见的时间，可能比程序所暗示的更晚，而它之后的指令却已经提前执行了。

x86-64 在普通的加载和存储之间保持强内存排序，因此在每个核心上：

1. 加载永远不会被重排到更晚的加载之后；
2. 存储永远不会被重排到更晚的存储之后；
3. 加载永远不会被重排到更晚的存储之后。

唯一可能的重排是：一次存储看起来在针对_不同_地址的后续加载之后才完成。

带lock前缀的指令，或者带内存操作数的xchg，是一道完整的屏障：没有任何东西看起来能跨越它向任一方向移动。 这就是为什么在大多数情况下，它们足以保证完整的顺序。

自旋与pause

这类在设置标志的同时返回它先前状态的指令，称为测试并设置。 它们可以作为自旋锁的基础，确保某个核心对代码的某一部分拥有独占访问权。

下面是用xchg指令配合一个二值标志的完整算法：

1. 标志一开始是0。
2. 为了获取锁，核心把标志中的值与1交换。
3. 如果返回的值是1，说明锁已被另一个核心_持有_。 当前核心于是等待，并再次尝试获取锁。
4. 如果返回的值是0，说明锁是空闲的。 xchg现在已把它设为1，其他核心会一直等到这个核心释放它。
5. 当前核心完成工作后，把标志更新为0就释放了锁。

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

等待循环中的pause指令不会改变代码计算出的结果。 它向处理器提示这是一次自旋等待。 CPU 于是可以降低等待线程的功耗，并让位给共享同一核心的兄弟线程。 没有pause的自旋循环依然是正确的，只是浪费。

线程完成工作后，可以用mov以普通的存储写入0来释放锁。 需要的不过是一条mov而已，因为在 x86-64 上，加载和存储永远不会被重排到更晚的存储之后。 一次存储如果从不越过它之前的访问，就说它具有释放排序；在 x86 上，每条普通存储都具备这一点。