同步原语的底层实现
本文性质声明：本机无 Linux 环境，全部内容未实测，为原理级框架。站内对照实测：conc-mutex（锁的 uncontended 单价 16.65ns、数据竞争丢失 70.7%）、conc-atomics（内存序与 lock-free 判定）、conc-lock-free（无锁栈的 2.07 倍减速）、win-thread-sync（Windows 临界区 13.9ns vs 互斥体 301.5ns）。
一、同步原语都建在同一种指令上
所有锁的尽头都是原子的读-改-写指令：x86 的 lock cmpxchg/lock xadd、ARM 的 ldrex/strex 对。它们的不同只在”抢不到怎么办”：
| 原语 | 原子操作 | 抢不到时 | 适用 |
|---|---|---|---|
| 自旋锁 | test-and-set / CAS | 忙等（继续试） | 临界区极短（纳秒级）、多核、不能睡眠的中断上下文 |
| 互斥锁 | CAS 抢”所有者”位 | 休眠（等唤醒） | 临界区长、可能睡眠、单核也适用 |
| 读写锁 | 原子加减计数器 | 按读者/写者分队列等 | 读远多于写 |
| 顺序锁 | 奇数计数器 | 读者重试 | 写极少、读者要快照 |
自旋 vs 休眠的判据是临界区长度 vs 上下文切换成本：本站 conc-sync 实测过——自旋锁无竞争比 mutex 快 45%，多两个可运行线程就反过来慢 3.6 倍。上下文切换（微秒级）比临界区（纳秒级）贵三个数量级，这是全部取舍的根基。
二、futex：用户态快、内核态等的二相结构
Linux 互斥锁的实现是 futex（fast userspace mutex），思想是”无竞争时完全不进内核”：
加锁：
1. 用户态 CAS 尝试把 0 改 1 ← 快路径：一条指令搞定，无系统调用
2. CAS 失败（有人持锁）→ futex(FUTEX_WAIT) 系统调用
3. 内核把调用者挂到等待队列，睡眠
解锁：
1. 用户态原子把 1 改 0
2. 若原值>1（说明有人在等）→ futex(FUTEX_WAKE) 叫醒一个这个结构解释了两个常见现象：其一，无竞争锁的实测成本就是几次原子操作（本站实测 uncontended mutex 16.65ns 级——futex 快路径从没进内核）；其二，高争用锁的成本是两次系统调用 + 两次上下文切换（睡 + 醒），比临界区本身贵得多——争用场景”合并临界区、减少持锁时间”比”换更快的锁”有效。
条件变量同样建在 futex 上（wait = FUTEX_WAIT + 释放锁的原子组合，signal = FUTEX_WAKE）——conc-condition-variable 实测过的”谓词循环""notify 选择”在语义层，futex 在机制层。
三、死锁：四条件与四个破坏点
死锁的四个必要条件（缺一不死）：
- 互斥：资源排他占用。
- 持有并等待：拿着 A 等 B，不撒手。
- 不可剥夺：别人抢不走你手里的。
- 循环等待：A 等 B、B 等 C、C 等 A。
工程上能动的只有 2/3/4：
| 破坏点 | 做法 | 代价 |
|---|---|---|
| 破”持有并等待” | 一次性申请所有资源（拿不到就全不拿） | 资源利用率低，要知道全集 |
| 破”不可剥夺” | try_lock 抢不到就回滚已持有的重来 | 回滚逻辑复杂 |
| 破”循环等待” | 全局锁顺序（按地址/按 ID 排序加锁） | 要所有人都守规矩，最常用 |
锁顺序的落地方式：给锁编号，代码里永远小编号→大编号；或者按对象地址排序（lock(a<b?a:b) 再 lock(a<b?b:a)）。Linux 内核有 lockdep 静态检查锁顺序违规——用户态没有等价物，只能靠约定 + 评审（本站 engineering-code-review 的观点：能让机器管的别留给人）。
检测：死锁发生了，gdb -p 对所有线程 bt，看栈上”持有一把、等待另一把”的环；超时锁（pthread_mutex_timedlock）把死锁降级为错误。别用”重启就好”糊弄——死锁是确定性 bug，触发条件只是概率问题。
四、RCU 与读多写少
读写锁对”读极多、写极少”仍不够快：读者也要原子地改计数器（写共享缓存行，多核下互相打）。RCU（Read-Copy-Update）的思路是读者完全不写共享状态：
- 读者：读指针 → 读数据 →（宽限期后）确认指针没变。无锁、无原子操作、无缓存竞争。
- 写者：复制一份 → 改副本 → 原子地换指针 → 等宽限期（所有旧读者都走了）→ 释放旧数据。
代价全在写侧和内存回收：宽限期的等待（synchronize_rcu）、以及”读者可能还拿着旧数据”的引用管理。适用面很窄：路由表、配置、/proc 一类”读百万次写几次”的数据。本站 conc-patterns 实测过同思想的用户态版本——COW 快照读段长到 800 次累加才反超 mutex（1.70x），读者不够多时 RCU/COW 是负优化。
五、排障索引
| 症状 | 入口 |
|---|---|
| 多线程全卡住 | 死锁（第三节）；gdb 看锁环 |
| CPU 100% 但吞吐为零 | 自旋锁/忙等失控；或锁公平性极差（等锁的饿死） |
| 加锁后比不加锁还慢 | 临界区太大或争用太高——合并、拆分数据、换无锁结构（先量，conc-lockfree 量过无锁反而慢 2 倍的案例） |
| 偶发数据错乱 | 忘加锁/锁错了对象；TSan 原理见 dbg-sanitizer |
| 优先级反转式卡顿 | 优先级继承（linux-pthread 提过 PTHREAD_PRIO_INHERIT） |
六、未实测清单
- 本文所有原语实现与 futex 行为——无 Linux 环境，未测。
- RCU 的宽限期与吞吐——未测。
- 锁的缓存行争用（伪共享）实测——Windows 侧见 dbg-data-layout 的跨行惩罚测量。
- 死锁的 gdb 现场——未复现。