并发原语与内存序深度剖析：从 Mutex 到 Atomic 到 Lock-Free 数据结构

本文系统梳理 Linux/x86_64 环境下各种并发同步机制的实现原理、硬件行为和性能开销，并完整讲解 C++ 内存模型与六种内存序的语义、典型误用与调试方法，为 HFT 场景下的并发设计提供决策依据。本文是本站内存序主题的权威出处，其他文章涉及内存序时均链接至此。

一、硬件基础：理解开销的根源 #

在讨论任何同步原语之前，必须先理解 CPU 缓存一致性协议，因为所有同步开销的本质都是 cache line 在核间的传输。

1.1 MESI 协议 #

现代多核 CPU 通过 MESI 协议（Modified, Exclusive, Shared, Invalid）维护缓存一致性：

        Core 0                Core 1
     ┌──────────┐          ┌──────────┐
     │ L1 Cache │          │ L1 Cache │
     │  Line X: │          │  Line X: │
     │ Modified │          │ Invalid  │
     └────┬─────┘          └────┬─────┘
          │                     │
          └──────┬──────────────┘
                 │
          ┌──────┴──────┐
          │   L3 Cache  │  (或 Directory)
          │   / Ring Bus│
          └─────────────┘

四种状态：

关键性能数据：

状态转换                              开销
─────────────────────────────────────────
L1 命中 (M/E/S)                      ~1 ns  (4 cycles)
L2 命中                               ~3 ns  (12 cycles)
L3 命中                               ~12 ns (40 cycles)
S → M (本 socket 内, 需 invalidate)   ~20 ns (70 cycles)
I → S/E (从其他核的 L1/L2 获取)       ~30 ns (100 cycles)
I → S (从 DRAM)                       ~60 ns (200 cycles)
跨 NUMA socket (QPI/UPI)              ~80 ns (250 cycles)

这就是为什么 alignas(64) 如此重要——如果两个无关的 atomic 变量在同一条 64 字节 cache line 上（false sharing），一个核写变量 A 会导致另一个核的变量 B 的 cache line 被 invalidate，即使 B 没有被修改。

1.2 x86 的 TSO 内存模型 #

x86 使用 Total Store Order (TSO) 内存模型，这是一种相对强的内存序：

允许的重排序:
  Store → Load  (可以)  ← 唯一允许的重排序，因为 store buffer
  Load  → Load  (不可以)
  Store → Store (不可以)
  Load  → Store (不可以)

实际效果:
  - atomic load(acquire)  = 普通 MOV 指令 (编译器屏障即可)
  - atomic store(release) = 普通 MOV 指令 (编译器屏障即可)
  - atomic store(seq_cst) = MFENCE 或 LOCK XCHG (需要刷 store buffer)

这意味着在 x86 上，memory_order_acquire 和 memory_order_release 几乎是"免费"的——编译器只需要确保不做指令重排，CPU 的 TSO 保证了硬件层面的顺序。

ARM 则不同，它是弱内存序模型，acquire/release 需要真正的屏障指令 (ldar/stlr)。

二、std::mutex 的实现剖析 #

2.1 三层结构 #

std::mutex 在 Linux/glibc 下最终基于 futex 实现，分为三层：

用户态:
  std::mutex::lock()
      │
      ▼
  pthread_mutex_lock()
      │
      ├─ Fast Path: atomic CAS (不进内核)
      │
      └─ Slow Path: futex(FUTEX_WAIT) → 进入内核态
                         │
内核态:                  ▼
                    futex_wait()
                         │
                    将线程挂到 wait queue
                         │
                    schedule() → 上下文切换

2.2 三态模型 #

Linux 的 mutex 实现使用一个 int 值表示三种状态：

值 = 0: UNLOCKED (未锁定)
值 = 1: LOCKED   (已锁定，无等待者)
值 = 2: CONTENDED (已锁定，有等待者)

lock() 的完整流程 #

void mutex_lock(int* state) {
    // Fast Path: 尝试 0 → 1
    if (atomic_compare_exchange(state, 0, 1) == SUCCESS)
        return;  // 拿到锁，无需进内核。耗时 ~20ns

    // Slow Path: 锁被占用
    // 先自旋几次 (PTHREAD_MUTEX_ADAPTIVE_NP 才会)
    for (int i = 0; i < SPIN_COUNT; i++) {
        if (*state == 0 && atomic_compare_exchange(state, 0, 2) == SUCCESS)
            return;
        _mm_pause();
    }

    // 自旋失败，标记为 CONTENDED 并进入内核等待
    while (atomic_exchange(state, 2) != 0) {
        futex(state, FUTEX_WAIT, 2, NULL);
        // 线程被挂起，等待 unlock 唤醒
        // 被唤醒后重新尝试 exchange
    }
}

unlock() 的完整流程 #

void mutex_unlock(int* state) {
    int prev = atomic_exchange(state, 0);  // 解锁

    if (prev == 2) {
        // 有等待者，需要唤醒
        futex(state, FUTEX_WAKE, 1, NULL);  // 唤醒一个等待线程
        // 这是一个系统调用，即使唤醒操作本身很快
    }
    // prev == 1: 没有等待者，不需要进内核，直接返回
}

2.3 为什么竞争时延迟不可控 #

时间轴 (纳秒):

0ns        线程B: CAS 失败，锁被线程A持有
           │
50ns       线程B: 自旋几次 (ADAPTIVE 模式)
           │
200ns      线程B: 放弃自旋，调用 futex(FUTEX_WAIT)
           │
           │  ← 进入内核态
           │
500ns      线程B: 被放入等待队列，调度器 deschedule
           │
           │  ← 线程B不再执行，CPU 时间片给其他线程
           │
           │  ... (等待线程A释放锁) ...
           │
5000ns     线程A: unlock() → futex(FUTEX_WAKE)
           │
           │  ← 线程B被放入可运行队列
           │
5500ns     调度器: 选择下一个运行的线程
           │
           │  ← 如果有更高优先级任务，线程B可能要继续等
           │
7000ns     线程B: 被调度回 CPU
           │
           │  ← 恢复执行上下文 (寄存器、栈指针)
           │
           │  ← L1/L2 cache 已被其他线程污染
           │     需要重新加载工作数据 (数百纳秒)
           │
8000ns     线程B: 重新尝试 exchange → 拿到锁

总延迟: ~8µs，其中绝大部分是操作系统调度开销。而且这个延迟不确定——取决于当时系统上有多少线程在竞争 CPU 时间。

2.4 pthread_mutex 的四种类型 #

三、Spinlock 的演进 #

Spinlock 的核心思想：不进内核，在用户态忙等。适用于临界区极短（<100ns）的场景。

3.1 Test-and-Set (TAS) — 最简单但最差 #

class TASLock {
    std::atomic_flag flag_ = ATOMIC_FLAG_INIT;
public:
    void lock() {
        while (flag_.test_and_set(std::memory_order_acquire)) {
            // 忙等
        }
    }
    void unlock() {
        flag_.clear(std::memory_order_release);
    }
};

问题：每次 test_and_set 都是一个原子写操作。即使 CAS 失败，也会在总线上发出写意图（MESI 协议需要获取 Exclusive 状态），导致 cache line 在所有核之间不断 bounce：

Core 0: test_and_set → 请求 Exclusive → invalidate 其他核
Core 1: test_and_set → 请求 Exclusive → invalidate 其他核
Core 2: test_and_set → 请求 Exclusive → invalidate 其他核
... (每次迭代都产生总线流量)

3.2 Test-and-Test-and-Set (TTAS) — 关键优化 #

class TTASLock {
    std::atomic_flag flag_ = ATOMIC_FLAG_INIT;
public:
    void lock() {
        while (true) {
            // 先 test (只读，可在 Shared 状态的本地 cache 满足)
            while (flag_.test(std::memory_order_relaxed)) {
                _mm_pause();  // 提示 CPU 这是自旋等待
            }
            // 看到锁释放了，再尝试 test_and_set (写操作)
            if (!flag_.test_and_set(std::memory_order_acquire))
                return;  // 成功拿到锁
        }
    }
    void unlock() {
        flag_.clear(std::memory_order_release);
    }
};

为什么 TTAS 好得多：

锁被持有时:
  Core 0 (持有者): cache line 状态 = Modified
  Core 1 (等待者): flag_.test() → 需要从 Core 0 获取 → 状态变为 Shared
  Core 1 (等待者): flag_.test() → 本地 cache 命中 (Shared) → ~1ns
  Core 1 (等待者): flag_.test() → 本地 cache 命中 (Shared) → ~1ns
  ... (读操作可以在本地 Shared 副本上满足，不产生总线流量)

锁释放时:
  Core 0: flag_.clear() → cache line 从 Shared → Modified → invalidate Core 1
  Core 1: flag_.test() → cache miss → 从 Core 0 获取 → 看到锁释放
  Core 1: flag_.test_and_set() → 请求 Exclusive → 拿到锁

TTAS 的读自旋不产生总线流量（在本地 Shared cache 上完成），只有在锁释放那一刻才需要跨核通信。

3.3 Ticket Lock — 公平但有 scalability 问题 #

class TicketLock {
    alignas(64) std::atomic<uint32_t> next_ticket_{0};
    alignas(64) std::atomic<uint32_t> now_serving_{0};

public:
    void lock() {
        // 原子取号 — 保证 FIFO 顺序
        uint32_t my_ticket = next_ticket_.fetch_add(1, std::memory_order_relaxed);
        // 等待轮到自己
        while (now_serving_.load(std::memory_order_acquire) != my_ticket) {
            _mm_pause();
        }
    }
    void unlock() {
        // 叫下一个号
        now_serving_.fetch_add(1, std::memory_order_release);
    }
};

优点：严格 FIFO 公平，不会饿死任何线程。

缺点：所有等待者都在 now_serving_ 上自旋。unlock 时 now_serving_++ 会 invalidate 所有 N 个等待者核心上的 cache line，导致 O(N) 次 cache line 传输（“thundering herd”）。

3.4 MCS Lock — 每个等待者自旋在自己的变量上 #

struct MCSNode {
    std::atomic<MCSNode*> next{nullptr};
    std::atomic<bool> locked{true};
};

class MCSLock {
    std::atomic<MCSNode*> tail_{nullptr};

public:
    void lock(MCSNode* me) {
        me->next.store(nullptr, std::memory_order_relaxed);
        me->locked.store(true, std::memory_order_relaxed);

        // 原子地将自己加入队列尾部
        MCSNode* prev = tail_.exchange(me, std::memory_order_acq_rel);
        if (prev != nullptr) {
            // 队列非空，把自己链到前驱后面
            prev->next.store(me, std::memory_order_release);
            // 在自己的 node 上自旋 (local spin)
            while (me->locked.load(std::memory_order_acquire))
                _mm_pause();
        }
    }

    void unlock(MCSNode* me) {
        MCSNode* next = me->next.load(std::memory_order_acquire);
        if (next == nullptr) {
            // 可能是最后一个节点
            MCSNode* expected = me;
            if (tail_.compare_exchange_strong(expected, nullptr,
                                              std::memory_order_release))
                return;  // 确实是最后一个，队列清空
            // CAS 失败: 有新节点正在 link，等它完成
            while ((next = me->next.load(std::memory_order_acquire)) == nullptr)
                _mm_pause();
        }
        // 唤醒下一个等待者（只 invalidate 一条 cache line）
        next->locked.store(false, std::memory_order_release);
    }
};

核心优势：每个线程等待时只自旋在自己的 MCSNode.locked 上（local spin）。unlock 时只需要写一个节点的 locked 字段，只 invalidate 一条 cache line，无论有多少个等待者。

对比:
  Ticket Lock unlock: invalidate N 条 cache line (all waiters spin on now_serving_)
  MCS Lock unlock:    invalidate 1 条 cache line (只影响 next 节点)

Linux 内核从 4.2 开始使用 qspinlock，其核心就是 MCS 的变体。

3.5 _mm_pause() 的作用 #

_mm_pause();  // 汇编: rep nop (或 pause)

作用：

1. 降低功耗：提示 CPU 当前处于自旋等待，可以降低执行速率
2. 避免流水线清空：自旋循环中反复读同一个内存地址，CPU 会推测执行。当值终于变了，之前的推测都要清空。pause 减少推测深度，避免代价高昂的 pipeline flush
3. 释放执行资源：在超线程 (HT) 的核上，pause 让出执行端口给同核的另一个硬件线程

注意：Skylake 之后 pause 的延迟从 ~10 cycles 增加到 ~140 cycles，这会影响 spinlock 在短竞争下的性能表现。

3.6 Spinlock 对比总结 #

四、std::atomic 与内存序 #

4.1 内存模型基础：三个问题与三个重排序来源 #

C++ 内存模型回答三个问题：

1. 原子性 (Atomicity)：操作能否被视为不可分割的整体——其他线程不会看到"写了一半"的中间状态
2. 可见性 (Visibility)：一个线程的写入何时对其他线程可见
3. 顺序性 (Ordering)：多个内存操作之间的顺序约束——其他线程观察到的顺序是否与程序顺序一致

之所以需要显式约束，是因为重排序来自三个层面：

1. 编译器重排序：优化器在"单线程结果不变"的前提下调整指令顺序、把变量缓存进寄存器
2. CPU 重排序：乱序执行与 store buffer 延迟写入（x86 TSO 下唯一的重排来源，见 1.2 节）
3. 缓存层面：多核各自的 cache 使写入的传播存在时间窗口（由 MESI 保证最终一致，见 1.1 节）

happens-before 是内存模型的核心概念：如果操作 A happens-before 操作 B，则 A 的结果（以及 A 之前的所有写入）对 B 可见。同一线程内按程序顺序自动成立；跨线程的 happens-before 必须通过同步操作显式建立——这正是内存序参数存在的意义。下面的六种内存序，本质就是六种"建立（或不建立）happens-before 边"的方式。

4.2 六种内存序 #

C++11 定义了六种内存序，从弱到强：

                    弱 (快) ─────────────────────────────► 强 (慢)

                    relaxed    consume    acquire    release    acq_rel    seq_cst
读操作可用:           ✓          ✓         ✓                                ✓
写操作可用:           ✓                               ✓                    ✓
RMW 可用:            ✓          ✓         ✓          ✓         ✓          ✓

memory_order_relaxed #

counter.fetch_add(1, std::memory_order_relaxed);

• 只保证操作本身是原子的
• 不提供任何跨线程的顺序保证
• 在 x86 上，RMW 操作（如 fetch_add）编译为 LOCK XADD，开销与 seq_cst 相同（因为 LOCK 前缀天然提供 full fence）；但 relaxed store 编译为普通 MOV，远比 seq_cst store（XCHG 或 MOV + MFENCE）便宜，relaxed load 同理也是普通 MOV
• 在 ARM 上，RMW 编译为 ldxr/stxr 循环（不带 acquire/release），比 seq_cst 更便宜；relaxed store/load 分别编译为普通 str/ldr

典型用途：计数器、统计信息、标志位（不需要与其他变量建立 happens-before 关系的场景）

memory_order_acquire / release #

// 生产者:
data = 42;
ready.store(true, std::memory_order_release);
// release 保证: data = 42 在 ready = true 之前对其他线程可见

// 消费者:
while (!ready.load(std::memory_order_acquire)) {}
// acquire 保证: 看到 ready == true 之后，也一定能看到 data == 42
assert(data == 42);  // 保证成立

在 x86 上的编译结果：

; store(release) — 只需要编译器屏障，CPU 天然保证 store-store 顺序
mov [ready], 1      ; 普通 MOV 指令

; load(acquire) — 只需要编译器屏障，CPU 天然保证 load-load 顺序
mov eax, [ready]    ; 普通 MOV 指令

x86 上 acquire/release 是零开销的！ 因为 TSO 已经保证了所需的顺序。

在 ARM 上则不同：

; store(release)
stlr w0, [x1]       ; store-release 指令，包含屏障

; load(acquire)
ldar w0, [x1]       ; load-acquire 指令，包含屏障

memory_order_seq_cst #

x.store(1, std::memory_order_seq_cst);

• 最强语义：所有线程看到的 seq_cst 操作顺序是一致的（全局全序）
• 在 x86 上：store 需要额外的 MFENCE 或使用 XCHG（因为 TSO 允许 store-load 重排）

; store(seq_cst) 在 x86 上:
mov [x], 1
mfence          ; 或者直接用 xchg [x], 1 (lock前缀隐含 mfence)

; store(release) 在 x86 上:
mov [x], 1      ; 就这一条指令，不需要 mfence

MFENCE 大约耗时 20-40ns，这就是 seq_cst 比 release 慢的原因。

memory_order_acq_rel #

用于 RMW（read-modify-write）操作：读取部分具有 acquire 语义，写入部分具有 release 语义。典型场景是"接管旧状态、发布新状态"的 exchange / compare_exchange——如 3.4 节 MCS Lock 中的 tail_.exchange(me, std::memory_order_acq_rel)：acquire 保证看到前驱节点的完整初始化，release 保证自己节点的初始化对后继可见。

4.3 内存栅栏：不绑定变量的同步原语 #

除了在原子操作上标注内存序，还可以使用独立的栅栏：

std::atomic_thread_fence(std::memory_order_acquire);  // 获取栅栏
std::atomic_thread_fence(std::memory_order_release);  // 释放栅栏
std::atomic_thread_fence(std::memory_order_seq_cst);  // 完整栅栏

栅栏与原子操作上的内存序有一个关键区别：原子操作的序只约束围绕这一个变量的重排，栅栏则约束它前后的所有内存操作。典型用法是"批量读 + 一次校验"：先做一批普通读，放一条 acquire fence，之后的校验 load 就不会被重排到批量读之前。6.2 节 Seqlock 的 read_validate 正是这个模式：

bool read_validate(uint32_t s) {
    std::atomic_thread_fence(std::memory_order_acquire);  // 数据拷贝不得越过此线
    return seq_.load(std::memory_order_relaxed) == s;
}

在 x86 上 acquire/release fence 只是编译器屏障（0 开销），seq_cst fence 才会生成 mfence（~20ns），见 4.5 节对照表。

4.4 原子 RMW 操作 #

fetch_add #

std::atomic<int64_t> counter{0};
int64_t old = counter.fetch_add(1, std::memory_order_relaxed);

x86 编译结果：

lock xadd [counter], 1    ; 原子加，返回旧值
; lock 前缀: 锁定该 cache line，保证原子性
; 开销: ~15-30 cycles (无竞争), ~40-100 cycles (有竞争)

compare_exchange_weak vs compare_exchange_strong #

int expected = 0;
// weak: 可能虚假失败 (spurious failure)，即使 *this == expected 也可能返回 false
bool ok = val.compare_exchange_weak(expected, 1, std::memory_order_acq_rel);

// strong: 不会虚假失败
bool ok = val.compare_exchange_strong(expected, 1, std::memory_order_acq_rel);

在 x86 上两者编译结果完全相同（都是 lock cmpxchg），因为 x86 的 CAS 本身不会虚假失败。

在 ARM 上有区别：

• weak 编译为一次 ldxr/stxr，stxr 可能虚假失败（LL/SC 架构特性），但单次操作更快
• strong 编译为一个循环包装，直到 stxr 成功或值确实不匹配

在循环中永远用 weak（因为循环本身会重试），单次判断用 strong。

4.5 x86 vs ARM 指令对照表 #

4.6 三种典型误用 #

误用一：该同步时用了 relaxed

std::atomic<bool> ready{false};
int data = 0;

// 线程1
data = 42;
ready.store(true, std::memory_order_relaxed);  // ✗ 应为 release

// 线程2
if (ready.load(std::memory_order_relaxed)) {   // ✗ 应为 acquire
    assert(data == 42);  // 可能失败：没有 happens-before，data 的可见性无保证
}

relaxed 只保证 ready 本身原子，不为周围的普通读写建立任何顺序。x86 上这段代码往往"碰巧正确"（TSO + 编译器恰好没重排），移植到 ARM 才真实失败——这是最危险的一类 bug：测试全绿，换平台就炸。

误用二：同步链断裂

// 线程1
flag1.store(1, std::memory_order_release);

// 线程2
if (flag1.load(std::memory_order_acquire)) {
    flag2.store(1, std::memory_order_relaxed);  // ✗ 链条在这里断了，应为 release
}

// 线程3
if (flag2.load(std::memory_order_relaxed)) {   // ✗ 应为 acquire
    // 无法保证看到线程1的写入
}

happens-before 可以传递，但每一跳都必须是 release/acquire 配对；中间任何一环用了 relaxed，传递链即断。

误用三：无脑 seq_cst

counter.fetch_add(1);                             // 默认 seq_cst
counter.fetch_add(1, std::memory_order_relaxed);  // 计数器场景的正确选择

反方向的错误：不需要全局全序的场景用了默认的 seq_cst。对 store 而言 x86 上要多付一条 mfence（~20ns），高频路径上代价可观。

4.7 调试与审查方法 #

• 工具：ThreadSanitizer（-fsanitize=thread）能捕获绝大多数数据竞争，包括误用一这类"缺 happens-before"的问题；Helgrind、Intel Inspector 作为补充。注意 TSan 有 5-15 倍减速，放在单独的 CI job 里跑
• 压力测试：在弱内存序平台（ARM）上跑并发测试暴露 x86 上被 TSO 掩盖的问题；x86 上通过随机延迟、扰动线程数来放大竞争窗口
• 审查模式：新代码先全部用 seq_cst 保证正确，profile 确认热点后再逐个降级为 acquire/release/relaxed，每次降级写明理由（“此变量不发布任何数据”／“此处与 X 的 acquire 配对”）。反着做——先写 relaxed 再补序——几乎必然出错

五、Lock-Free 数据结构 #

5.1 SPSC Queue — 最简单也最快的 lock-free 结构 #

Single Producer Single Consumer 队列是 HFT 中最常用的跨线程通信手段：

template <typename T, size_t N>  // N 必须是 2 的幂
class SPSCQueue {
    static_assert((N & (N - 1)) == 0, "N must be power of 2");

    // 关键: head 和 tail 在不同的 cache line 上
    alignas(64) std::atomic<size_t> head_{0};  // consumer 写
    alignas(64) std::atomic<size_t> tail_{0};  // producer 写
    alignas(64) T ring_[N];

public:
    bool push(const T& val) {
        const size_t tail = tail_.load(std::memory_order_relaxed);  // 只有 producer 写 tail
        const size_t next = (tail + 1) & (N - 1);  // 位运算代替取模
        if (next == head_.load(std::memory_order_acquire))  // 读 head 需要 acquire
            return false;  // 满
        ring_[tail] = val;
        tail_.store(next, std::memory_order_release);  // release: 保证 ring_[tail] 的写对 consumer 可见
        return true;
    }

    bool pop(T& val) {
        const size_t head = head_.load(std::memory_order_relaxed);  // 只有 consumer 写 head
        if (head == tail_.load(std::memory_order_acquire))  // 读 tail 需要 acquire
            return false;  // 空
        val = ring_[head];
        head_.store((head + 1) & (N - 1), std::memory_order_release);
        return true;
    }
};

为什么不需要 CAS？

因为 SPSC 的约束保证了 head 和 tail 各只有一个线程写：

• Producer 用 relaxed load 读自己的 tail_（只有自己写，一定是最新的）
• Producer 用 acquire load 读 head_（需要看到 consumer 最新的消费进度）
• Producer 用 release store 写 tail_（publish 新数据给 consumer）
• Consumer 完全对称

没有任何 CAS、没有任何自旋等待、没有任何锁。每次 push/pop 只需要 1 个 relaxed load + 1 个 acquire load + 1 个 release store。在 x86 上这三条操作都是普通 MOV 指令（加编译器屏障），总开销 ~5ns。

5.2 MPSC Queue — Vyukov 有界队列 #

当多个线程需要向同一个消费者发送数据时（如多个 IO 线程 → 处理线程），使用 MPSC 队列：

struct alignas(64) Slot {
    T                    data;
    std::atomic<size_t>  seq;  // 三态标记
};

class MPSCBoundedQueue {
    static constexpr size_t kCap = 512;  // 必须是 2 的幂

    Slot ring_[kCap];
    alignas(64) std::atomic<size_t> tail_{0};  // 多个 producer 竞争
    alignas(64) size_t              head_{0};  // 单个 consumer，不需要 atomic

public:
    MPSCBoundedQueue() {
        for (size_t i = 0; i < kCap; i++)
            ring_[i].seq.store(i, std::memory_order_relaxed);
    }

    // 多线程安全的 push
    bool push(T&& val) {
        size_t pos;
        Slot* slot;
        while (true) {
            pos = tail_.load(std::memory_order_relaxed);
            slot = &ring_[pos & (kCap - 1)];
            size_t seq = slot->seq.load(std::memory_order_acquire);
            intptr_t diff = (intptr_t)seq - (intptr_t)pos;

            if (diff == 0) {
                // 这个 slot 可用，尝试抢占
                if (tail_.compare_exchange_weak(pos, pos + 1,
                                                std::memory_order_relaxed))
                    break;  // 成功抢到位置
            } else if (diff < 0) {
                return false;  // 队列满
            }
            // diff > 0: 有其他 producer 正在写这个 slot，retry
        }
        slot->data = std::move(val);
        slot->seq.store(pos + 1, std::memory_order_release);  // 标记为已写入
        return true;
    }

    // 单线程消费
    bool pop(T& val) {
        Slot* slot = &ring_[head_ & (kCap - 1)];
        size_t seq = slot->seq.load(std::memory_order_acquire);
        intptr_t diff = (intptr_t)seq - (intptr_t)(head_ + 1);

        if (diff < 0)
            return false;  // 队列空

        val = std::move(slot->data);
        slot->seq.store(head_ + kCap, std::memory_order_release);  // 标记为可复用
        head_++;
        return true;
    }
};

Slot 的 seq 字段是精髓。它承载了三个含义：

• seq == pos: slot 空闲，等待 producer 写入
• seq == pos + 1: slot 已被 producer 写入，等待 consumer 消费
• seq == pos + kCap: slot 被 consumer 消费后回收

5.3 SPMC 与 MPMC：序列号模式的推广 #

5.2 的序列号机制可以推广到其余两种线程拓扑，核心规则是：哪一端有多个线程，哪一端的游标就要用 CAS 竞争。

SPMC（单生产者→多消费者）：生产端与 SPSC 一样用普通 store 推进 tail；消费端多个线程共享一个 atomic<size_t> head，通过 CAS 竞争消费权：

// 多消费者 pop 的核心：CAS 抢占 head，抢到者独占该 slot
std::optional<T> pop() {
    size_t pos = head.load(std::memory_order_relaxed);
    while (true) {
        Element& e = buffer[pos % Capacity];
        if (e.sequence.load(std::memory_order_acquire) != pos + 1)
            return std::nullopt;                       // 数据未就绪（队列空）
        if (head.compare_exchange_weak(pos, pos + 1,
                std::memory_order_relaxed, std::memory_order_relaxed)) {
            T result = std::move(e.data);              // CAS 成功，独占消费此 slot
            e.sequence.store(pos + Capacity, std::memory_order_release);  // 归还 slot
            return result;
        }
        // CAS 失败时 pos 已被自动更新为最新 head，直接重试
    }
}

注意消费权必须通过共享的 atomic head + CAS 来分配；如果每个消费者线程各自维护一份 head（例如 thread_local），所有消费者会从同一位置独立递增，同一元素被重复消费。

MPMC（多对多）：两端都用"CAS 游标 + slot 序列号"的完整模式——enqueue_pos 与 dequeue_pos 各一个 atomic，slot 序列号三态与 5.2 完全相同。

量级参考：SPSC ~5-10ns；MPSC/SPMC 无竞争 ~10-20ns，有竞争随线程数上升（CAS 重试 + cache line bounce）；MPMC 高竞争下可达数百 ns。竞争端每多一个，延迟分布的尾部就厚一分——这是 7.3 节"能用 SPSC 就不用 MPSC"的定量依据。

5.4 alignas(64) 与 false sharing #

❌ 错误设计:
struct Queue {
    std::atomic<size_t> head;  // 偏移 0
    std::atomic<size_t> tail;  // 偏移 8
    // 两者在同一条 64 字节 cache line 上!
};

当 producer 写 tail 时:
  1. 请求 tail 所在 cache line 的 Exclusive 权限
  2. 这条 line 同时包含 head
  3. consumer 核上的 head 副本被 invalidate
  4. consumer 下次读 head 时 cache miss → ~30ns 延迟
  5. consumer 写 head 时也要请求 Exclusive → invalidate producer 的 tail 副本
  6. producer 下次读 tail 时 cache miss → ~30ns 延迟

结果: 每次 push 和 pop 都多 ~30-60ns 的 false sharing 开销

✅ 正确设计:
struct Queue {
    alignas(64) std::atomic<size_t> head;  // cache line 0
    alignas(64) std::atomic<size_t> tail;  // cache line 1
};

producer 写 tail: 只影响 cache line 1, head 所在的 cache line 0 不受影响
consumer 写 head: 只影响 cache line 0, tail 所在的 cache line 1 不受影响
两者完全独立，cache 行为就像在两台不同的机器上操作一样

六、读写锁进阶 #

6.1 std::shared_mutex #

std::shared_mutex mtx;

// 多个读者并发:
{
    std::shared_lock lock(mtx);  // 共享锁
    // 读取数据
}

// 独占写者:
{
    std::unique_lock lock(mtx);  // 独占锁
    // 修改数据
}

内部实现 (Linux)：通常基于一个 atomic<int32_t> + 两个 futex：

• 正值: 当前读者数量
• -1: 被写者独占
• 0: 空闲

问题：

• 读者都在同一个 atomic 上做 fetch_add/fetch_sub，高并发读时 cache line 仍然 bounce
• 写者可能被持续到来的读者饿死（除非用 writer-prefer 策略）

6.2 Seqlock — 读者零阻塞 #

class SeqLock {
    std::atomic<uint32_t> seq_{0};
    // seq_ 为奇数 = 正在写入; 偶数 = 数据一致

public:
    // 写者 (必须互斥，多写者需要外部锁)
    void write_begin() {
        seq_.fetch_add(1, std::memory_order_release);  // 变奇数
    }
    void write_end() {
        seq_.fetch_add(1, std::memory_order_release);  // 变偶数
    }

    // 读者 (乐观读，完全无阻塞)
    uint32_t read_begin() {
        uint32_t s;
        while ((s = seq_.load(std::memory_order_acquire)) & 1) {
            _mm_pause();  // 写入进行中，等一下
        }
        return s;
    }
    bool read_validate(uint32_t s) {
        std::atomic_thread_fence(std::memory_order_acquire);
        return seq_.load(std::memory_order_relaxed) == s;
    }
};

// 使用模式:
struct Data { double price; int64_t qty; int64_t ts; };
Data shared_data;

// 读者:
Data local;
uint32_t seq;
do {
    seq = seqlock.read_begin();
    local = shared_data;       // 可能读到不一致的数据（torn read）
} while (!seqlock.read_validate(seq));
// 到这里 local 一定是一致的

// 写者:
seqlock.write_begin();
shared_data = new_data;
seqlock.write_end();

优势：

• 读者永远不会阻塞写者（写者直接写，读者自己重试）
• 无竞争时读者开销极低（两个 load + 一条 fence）
• 非常适合"一写多读"的行情数据场景

限制：

• 读者可能读到"撕裂"的数据（部分旧值部分新值），所以只适用于 POD 类型
• 不能用于含指针的数据结构（撕裂的指针 = use-after-free）

6.3 RCU (Read-Copy-Update) #

RCU 是 Linux 内核中最重要的并发原语之一：

// 核心思想: 读者完全不加锁，写者创建新副本

// 共享数据 (通过指针间接访问)
std::atomic<Config*> g_config;

// 读者 (零开销):
void reader() {
    rcu_read_lock();  // 在用户态: 实际上只是禁止抢占，开销约0-1ns
    Config* cfg = rcu_dereference(g_config);  // atomic load + acquire
    use(cfg);  // 安全读取，不需要任何锁
    rcu_read_unlock();
}

// 写者:
void writer(Config new_cfg) {
    Config* new_ptr = new Config(new_cfg);   // 创建新副本
    Config* old_ptr = g_config.exchange(new_ptr);  // 原子替换指针
    synchronize_rcu();  // 等待所有读者退出 rcu_read_lock 区域
    delete old_ptr;     // 安全释放旧数据
}

时间线:
                读者1         写者          读者2
                  │            │              │
                  │ read old ──│──────────    │
                  │            │ swap ptr ─── │ read new
                  │ ──────── exit rcu        │
                  │            │              │
                  │            │ synchronize  │
                  │            │ ... wait ... │
                  │            │ readers done │
                  │            │ delete old   │

读的开销 = 0（在 x86 上，rcu_read_lock 只是一个编译器屏障）。这使得 RCU 是读密集型场景的终极方案。

七、全景开销对比 #

7.1 单次操作延迟 #

操作                                           大约耗时
──────────────────────────────────────────────────────────
L1 cache 命中 (普通读写)                         1 ns
atomic load/store (relaxed, x86)                 1 ns      ← 与普通读写相同
atomic load (acquire, x86)                       1 ns      ← TSO 保证，零额外开销
atomic store (release, x86)                      1 ns      ← TSO 保证，零额外开销
atomic store (seq_cst, x86)                      8 ns      ← 需要 MFENCE
atomic fetch_add (无竞争)                        5-8 ns    ← LOCK XADD
atomic CAS (无竞争)                              5-12 ns   ← LOCK CMPXCHG
SPSC queue push/pop                              5-10 ns   ← 几条 atomic load/store
_mm_pause()                                      3-40 ns   ← Skylake 后大幅增加
Spinlock lock/unlock (无竞争)                    5-8 ns    ← 一次 TAS
std::mutex lock/unlock (无竞争)                  15-25 ns  ← CAS + 函数调用开销
shared_mutex shared lock (无竞争)                20-30 ns  ← fetch_add + fetch_sub
MPSC queue push (无竞争)                         10-20 ns  ← CAS loop
──────────────────────────────────────────────────────────
Cache line 从同 socket 其他核获取                 20-30 ns
Cache line 从跨 socket (NUMA) 获取               60-100 ns
Spinlock (有竞争, 短临界区)                      50-200 ns  ← 自旋等待
系统调用 (最小开销, 如 getpid)                   50-100 ns
──────────────────────────────────────────────────────────
std::mutex (有竞争)                              1-10 µs   ← futex + 上下文切换
上下文切换                                       1-5 µs
RAND_bytes(4 bytes)                              1-3 µs    ← 密码学安全随机数
printf (短字符串)                                1-5 µs    ← stdout 锁 + write 系统调用
malloc/free (小对象)                             0.05-0.5 µs
std::string 构造 (短字符串 SSO)                  5-10 ns
std::string 构造 (>22 字节, 需 malloc)           50-200 ns

7.2 决策矩阵 #

落到常见系统上：日志系统（多业务线程→单落盘线程）是标准的 MPSC 场景；GUI／事件循环（多源产生事件→主线程分发）同样是 MPSC；行情快照一写多读用 Seqlock；工作窃取调度器（每线程一个队列、互相偷任务）才真正需要 MPMC。

7.3 HFT 中的黄金法则 #

1. 能用 SPSC 就不用 MPSC：减少竞争是减少延迟抖动的根本
2. 能用 atomic 就不用锁：锁的延迟分布有长尾（竞争时进内核）
3. 能用 relaxed 就不用 seq_cst：在 x86 上差 ~7ns，在 ARM 上差更多
4. 能用 weak 就不用 strong：在循环中 weak CAS 更适合 ARM
5. 能预分配就不 malloc：malloc 本身有内部锁（glibc 的 arena lock）
6. 永远 alignas(64)：false sharing 的开销远比你想象的大
7. _mm_pause() 放在每个自旋循环中：保护超线程伙伴，避免流水线冲刷

八、总结 #

从 mutex 到 atomic 到 lock-free 数据结构，本质上是在 通用性 和 性能 之间做取舍：

                        通用                                      专用
                         │                                         │
    std::mutex ────► spinlock ────► atomic CAS ────► SPSC queue ──►│
                         │                                         │
    任何场景             短临界区         无锁算法            最快但限制最多
    最慢但最简单          中等            需要仔细设计         只能一对一
    延迟不可控           延迟可控         延迟可控            延迟最低

没有"最好"的同步原语，只有最适合特定场景的选择。在 HFT 中，我们追求的是延迟的确定性——宁可平均延迟稍高，也不要有百万分之一概率出现的 10µs 长尾。这就是为什么 lock-free 设计在 HFT 中如此重要：不是因为它平均更快（有时甚至稍慢），而是因为它的延迟分布更窄、更可预测。