# 无锁编程深入：模式、陷阱与工程实践

> 前置：建议先读 [low-latency-patterns.md](/concepts/latency/low-latency-patterns.md) 的第三节（无锁编程与 RCU 原理）

## 一、无锁编程的概念边界

### 1. 分级定义

- **Wait-Free**：每个操作在有限步骤内完成（最强）
- **Lock-Free**：系统中至少有一个操作在有限步骤内完成（整体进展）
- **Obstruction-Free**：单线程不阻塞即可完成（最弱）

### 2. 无锁 ≠ 不用锁

- 原子指令（CAS、FAA、LL/SC）本身是硬件层面的"微缩锁"
- 真正的开销：缓存一致性协议（MESI 状态迁移）和内存屏障
- "无锁"解决的是调度上的阻塞，不是竞争上的开销

### 3. 何时需要无锁

- 临界区极短（< 100 cycles）→ 无锁更好
- 读多写少 → RCU 更好（见 [rcu-internals.md](/concepts/latency/rcu-internals.md)）
- 中断上下文/信号处理中 → 必须无锁
- 实时系统要求确定性 → 必须 wait-free

## 二、核心原语

### 1. CAS 模式

```cpp
// compare_exchange_weak vs strong
// weak 允许 spurious failure，适合循环
// strong 保证成功才返回，可能有额外开销
```

- CAS 循环的退避策略（指数退避 / 随机退避）
- x86 `LOCK CMPXCHG` vs ARM `LDXR/STXR` 的硬件实现差异
- CAS 的 ABA 问题（见下方）

### 2. FAA（Fetch-And-Add）模式

- 比 CAS 更低竞争的开销
- 适合计数器、索引分配等场景
- 配合位域打包多个变量到一个原子变量

### 3. 内存序选择速查表

| 操作 | 推荐 order | 原因 |
|------|-----------|------|
| 纯计数器 | relaxed | 不需要同步其他数据 |
| 发布数据 | release | 确保之前写入对其他线程可见 |
| 消费数据 | acquire | 确保看到发布者之前的所有写入 |
| 互斥 flag | acq_rel | 需要双向同步 |
| x86 SeqLock | seq_cst | 需要全局顺序 |

## 三、经典无锁数据结构剖析

### 1. Michael-Scott 无锁队列 (FIFO)

- 哨兵节点的作用
- enqueue 的两步 CAS（tail->next 然后更新 tail）
- dequeue 对空/单元素队列的特殊处理
- 内存回收：与队列的耦合

### 2. Treiber Stack (LIFO)

- 单 CAS 的 push/pop——最简单的无锁结构
- 内存泄漏问题：弹出节点何时可以 `free`
- HPEB / RCU 配合解决问题

### 3. Harris 无锁链表

- 逻辑删除标记位（偷 data 的低位 bit）
- 物理删除由后续遍历者完成（helping）
- 查找时的并发修复

### 4. Concurrent Hash Map 思路

- 分桶 + 每桶细粒度锁 / 无锁
- Folly `ConcurrentHashMap` 的 `microshard` 模式
- 无锁跳表作为替代方案

## 四、内存回收：无锁编程的最大挑战

### 1. 为什么不能直接 delete

- 线程 A CAS 拿到指针 → 被抢占 → 线程 B 删除对象 → 线程 A 醒来访问悬空指针

### 2. 四种回收方案

| 方案 | 原理 | 延迟 | 内存 | 复杂度 |
|------|------|------|------|--------|
| Quiescent-State-Based (QSBR) | 所有线程经过静默期后回收 | 最低 | 可能堆积 | 需侵入线程 |
| Epoch-Based (EBR) | 三代 epoch 轮转回收 | 低 | epochs × 对象量 | 中 |
| Hazard Pointers (HP) | 线程声明保护哪些指针 | 中 | 低 | 低 |
| RCU | 内核级宽限期机制 | 低（读）/ 高（收） | 低 | 内核依赖 |

> 详细 RCU 分析见 [rcu-internals.md](/concepts/latency/rcu-internals.md)

### 3. 各方案代码量对比

- HP: ~200 行
- EBR: ~300 行
- QSBR: ~100 行（但需要静态标记静默点）
- RCU: 1 行 `rcu_read_lock()` + 1 行 `synchronize_rcu()`

## 五、ABA 问题与解决方案

### 1. 经典场景

```bash
T1: 读到 head=A;       （被抢占）
T2: pop A, pop B, push A;
T1: CAS 期望 head=A, 实际 head=A → 成功——但链表已变！
```

### 2. 解决手段

- **Tagged Pointer**：指针高位存储版本号，`cmpxchg16b`（128位 CAS）
- **Hazard Pointers**：A 在被"保护"期间不能被复用
- **RCU**：A 在整个宽限期内不释放

## 六、性能量化

### 1. 无锁 vs 有锁 单操作开销

| 操作 | `std::mutex` | `std::atomic` CAS | FAA |
|------|-------------|-------------------|-----|
| 无竞争 | ~25ns | ~10ns (x86) | ~5ns |
| 中度竞争 (4C) | ~150ns | ~60ns | ~30ns |
| 重度竞争 (8C) | ~500ns+ | ~200ns | ~120ns |

### 2. 队列吞吐量 (8 线程)

| 队列类型 | 吞吐量 (M ops/s) | P99 延迟 (ns) |
|----------|-----------------|---------------|
| `std::queue` + `std::mutex` | 2.5 | 1200 |
| `boost::lockfree::queue` | 18 | 800 |
| Michael-Scott + HP | 22 | 600 |
| MPMC bounded array | 35 | 400 |

## 七、工程建议

1. **先用锁，profile 证明是瓶颈再考虑无锁**
2. **优先考虑成熟的库**（`boost::lockfree`、Intel TBB、Folly）
3. **考虑无锁队列替代锁竞争**，而非替换所有锁
4. **内存回收必须从设计阶段就考虑**，不是事后补
5. **测试远比写代码难**：弱内存序的 ARM/POWER 上行为可能迥异

## 八、参考

- [atomic](/concepts/cache/atomic.md) —— 原子操作基础
- [reordering-overview](/concepts/memory-ordering/reordering-overview.md) —— 内存序全景
- [memory-model](/concepts/cache/memory-model.md) —— C/C++ 内存模型
- [rcu-internals.md](/concepts/latency/rcu-internals.md) —— RCU 内核实现