原子操作 属于

关于 原子操作

一条指令看起来可能是一个不可分割的动作，实际上却完全不是。以给内存中的某个值加上 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）。

注意，读取（load）和写入（store）是两个独立的事件，所以它们之间存在一个时间窗口。在单核上我们通常察觉不到这一点，因为每条指令都保证在下一條指令之前完整地产生效果。因此这个窗口是不可见的，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前缀用于其他指令的机制相同。

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。

用在其他任何指令上，比如普通的mov，这个前缀都是无效的，处理器会抛出无效操作码异常。单独的加载或单独的写回不需要前缀：自然对齐的访问本身就是原子的。

原子位操作

在可加锁的指令当中，位测试指令与本文末尾的自旋锁天然搭调。bts、btr和btc各自都会把一个指定的位复制到进位标志中，然后对它置位、清零或翻转。加上lock前缀后，这就变成了一次一位的读-改-写：该位被原子地改变，而CF报告它原来的值。

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

一次置位如果发现该位已被置位，就说明另一个线程抢先占有了它。这相当于xchg对整个字所做的那种标志抢占，只是缩小到了单个位。

交换并相加

普通的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不同，每个中间值也都会被返回，一次一个，交给各自的调用者。

源操作数可以是任何通用寄存器，操作数宽度从 1 个字节到 1 个四字不等。加上一个负值，同一条指令就变成了取回并相减。

比较并交换

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

cmpxchg dest, src把rax当作隐式的累加器，并将它与dest比较：

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

累加器随操作数大小而变：字节用al，更宽的用ax、eax和rax。

注意，只有当dest等于先前加载到rax中的预期值时，它才会被更新。这种相等保证了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通过拒绝写入基于过期读取计算出的值来抓住这种情况。

有一个细节值得了解。cmpxchg检查的是值是否等于读取到的值，而不是该位置从未被碰过。如果另一个线程在这个窗口内把值从A改成B再改回A，交换_仍然会成功_，哪怕底下的世界已经变过了。

对普通的计数器来说，这无害，因为计数相同就同样好用。但对无锁链表头部的内存地址来说就不是了，因为同一个地址现在可能指向别处。这就是 ABA 问题。

解决这个问题的常见做法，是给值配上一个“戳记”，比如一个只会不断增长的计数器。由于戳记只会前进，戳记匹配就能证明该位置在此期间没有被碰过，而不只是看起来没变。

不过，要在多线程环境中做到这一点，内存地址和它的戳记必须一起更新。而在 x86-64 中，一个内存地址就是一个完整的四字，所以光靠cmpxchg不足以同时更新它和另一个值。

有一条双倍宽度的指令叫 cmpxchg16b，它在语义上与cmpxchg相同，但一次处理 16 个字节，可以用在这种场合。它没有源操作数，而是用rcx:rbx作为替换值。它唯一的操作数是一个按 16 字节对齐的内存位置。这条指令还使用rdx:rax作为累加器，而不只是rax。

内存顺序

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

branchless-code 这个概念介绍过这样的想法：现代核心不会一条一条地慢慢执行指令。它会让许多指令同时处于执行中，并在能超前的地方超前执行。这意味着一次写入对其他核心可见的时间，可能比程序所暗示的更晚，而它之后的指令却已经抢先执行了。

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

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

唯一可能的重排，是一个存储看起来在对_不同_地址的更晚加载之后才完成。

带lock前缀的指令，或者带内存操作数的xchg，是一个完整的屏障：任何东西都不会看起来跨过它移动，无论朝哪个方向。这就是为什么在大多数情况下，它们足以保证完整的顺序。

唯一幸存的那次重排，背后的机制是存储缓冲区。为了持续超前执行，核心会把每次存储都暂存到缓冲区里，让后面的指令先执行，而这次存储还没到达其他核心能看到的内存。因此，一次写入之后紧跟一次对不同位置的读取，就可能看起来乱了顺序：写入可能还待在缓冲区里，而后面的读取已经先走了。这种模型，除了那个“先写后读”的缺口之外一切都保持有序，被称为全存储顺序。

仅这一个缺口，就足以破坏一次“先存储再检查”的握手。如果两个线程各自写入自己的标志，然后读取对方的标志，两次读取都可能返回未置位，因为两次存储都还没有离开各自的存储缓冲区。mfence指令通过排空存储缓冲区来补上这个缺口：在它之前的每次写入，都会在它之后的任何读取之前可见。

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

还有两个更窄的屏障：

• sfence负责安排写入之间的顺序，主要用在流式的非临时存储上；
• lfence负责安排读取之间的顺序。

对于上面那些普通的原子模式，带lock前缀的指令本身就带有完整的顺序保证，所以只有像上面那样用普通存储和加载搭起来的握手，才需要显式的屏障。

这些保证的名字并不局限于 x86。当一个操作之后的任何访问都不会看起来移到它前面时，这个操作就具有获取顺序；当一个操作之前的任何访问都不会看起来移到它后面时，就具有释放顺序。在 x86 上，每次加载都是一个获取，每次存储都是一个释放，而带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的自旋循环仍然是正确的，只是浪费。

注意，在测试并设置中，像xchg这样的指令总是会把标志设置上，即使它已经被设置过。这意味着它每次自旋都会取得对内存的独占访问，哪怕锁很可能仍被持有。

这个算法有一个变体，称为测试并测试再设置，它会先测试（读取）标志，检查它是否已经被设置。只有当锁看起来空闲时，它才会尝试测试并设置（这里是xchg）：

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

线程完成工作后，可以用mov做一个普通的0存储来释放锁。只需要一条mov就够了，因为在 x86-64 上，加载和存储永远不会被重排到更晚的存储之后。一个永远不会越过它之前的访问的存储，就称为具有释放顺序，而在 x86 上，每次普通存储都带有它。