Theory · OS · Synchronization & Mutual Exclusion
竞态 → 原子指令 → 锁的分层实现：自旋 / 睡眠 / futex —— 从硬件 CAS 到 Go sync.Mutex 的完整栈
i++ 是三条指令——共享 + 交错 = 丢失更新；原子性、可见性、有序性是并发三原罪
硬件原子指令打底 → 自旋锁忙等 → futex 快慢两路 → 互斥锁/条件变量/信号量的语义封装
sync.Mutex 的 normal/starvation 双模式、RWMutex 写优先——教科书原则在 runtime 里的真实落地
Race Condition · i++ Anatomy
Atomic Primitives in Hardware
单核时代"进临界区前关中断"确实可行；多核下另一核照常访问共享内存——关中断只挡调度，不挡并发访存。而且用户态根本无权关中断。于是需要"读改写一条完成"的指令：CPU 用缓存一致性协议（如对 cache line 加锁 / 总线锁）保证其原子性。
原子地"读旧值 + 写新值"。用它把"检查锁 + 上锁"合成一步，锁就不会在检查与上锁之间被抢——自旋锁的最小实现。
原子地"比较等于期望值才写入"：x86 的 lock cmpxchg、ARM 的 LL/SC 对（ldxr/stxr）。CAS 是现代无锁数据结构与所有互斥锁快路径的通用积木——Go 的 atomic 包全部映射到它。
// 用 TAS 实现自旋锁（教科书版） func Lock(l *int32) { for atomic.Swap(l, 1) == 1 { // 换到 1 说明别人持锁 → 忙等 // (改进：先读后写，减少总线风暴) } } func Unlock(l *int32) { atomic.Store(l, 0) } // CAS 语义（Go atomic 包） swapped := atomic.CompareAndSwapInt32( &v, old, new) // v==old 时才写 new
Spinlock vs Blocking Mutex
| 维度 | 自旋锁 spinlock | 互斥锁 mutex（睡眠） |
|---|---|---|
| 等待方式 | 原地循环重试（忙等） | 挂起线程，让出 CPU |
| 开销来源 | 占着 CPU 空转 | 两次上下文切换 + 唤醒延迟 |
| 适用临界区 | 极短（几条指令）、持锁者马上放 | 较长、可能睡眠（I/O） |
| 能否在内核使用 | 能（中断上下文唯一选择） | 中断上下文不能睡 |
| 单核陷阱 | 持锁者被抢 → 等待者空转烧完时间片 | 无此问题 |
临界区 < 一次上下文切换成本（μs 级）→ 自旋划算；临界区长或持锁睡眠 → 自旋是纯浪费（烧 CPU 还拖慢持锁者）。自适应自旋就是 runtime 用历史信息在线做这道题。
Linux 内核里 spinlock 是硬约束选择——中断处理、调度器自身不能睡眠；mutex 才能睡。用户态则相反：pthread_mutex 几乎总是首选，自旋锁只在极热的短临界区（内核池、无锁队列旁路）才值得。
读多写少场景把"互斥"放宽为"读共享、写独占"——但写者公平性与 cache 一致性开销是新的坑，Go RWMutex 甚至有"递归读锁可能死锁"的陷阱。
Fast Userspace Mutex
Condition Variable
互斥锁只能保证"一次只有一个"，但线程常常要等"某个谓词成立"（缓冲区非空、队列有位）才能干活。自旋检查谓词浪费 CPU；条件变量提供"睡眠等通知"。
"检查谓词 + 睡眠"必须是原子的，否则"检查完不成立 → 刚要睡 → 生产者恰好放入并 signal → 再睡"——唤醒丢失。所以 wait 前必须持锁，内核在 wait 内部原子地"放锁 + 睡眠 + 醒后重新拿锁"。
被唤醒后谓词可能又变了：① 虚假唤醒（实现允许无故唤醒）；② 其他线程抢先消费，条件再次不成立。规范写法：while (!条件) wait(c, m);——醒来重查。
// 消费者线程（标准姿势） pthread_mutex_lock(&m); while (queue.empty()) { // while! 不是 if pthread_cond_wait(&cv, &m); // 内部：原子地 解锁+睡眠 // 醒来后：重新加锁再返回 } item = queue.pop(); pthread_mutex_unlock(&m); // 生产者线程 pthread_mutex_lock(&m); queue.push(item); pthread_cond_signal(&cv); // 唤一个 // broadcast: 唤醒全部（如状态翻转） pthread_mutex_unlock(&m);
Semaphore · RWLock
内核/runtime 维护的原子计数器 + 等待队列：P（减一，不足则睡）与 V（加一，唤醒等待者）。与互斥锁的本质区别：无所有权——A 加的锁必须 A 还；信号量 B 的 V 可以合法唤醒 C 的 P。于是它能表达"资源池有 N 份"。
初值 1 的信号量看似互斥锁，但没有所有权约束：可以在 A 线程 P、B 线程 V 当"信号传递"用——这是能力也是事故源（误用导致解别人锁）。需要互斥语义时用 mutex，需要资源计数时用 semaphore。
读多写少场景：允许多读者并行，写者独占。两个设计争议：① 写者饥饿（读者川流不息）→ 现实实现普遍让挂起写者挡住新读者；② 读者间 cache line 争抢使高并发读性能反而不佳 → 这引出了 RCU：读完全零锁、写者复制后改指针（内核热路径的终极答案，一句话了解即可）。
| 原语 | 语义 | 典型场景 |
|---|---|---|
| mutex | 独占 + 所有权 | 保护临界区 |
| cond | 等谓词成立 | 队列空/满等待 |
| semaphore | 计数许可，无所有权 | 连接池 N 个名额 |
| rwlock | 读共享写独占 | 读多写少的配置/缓存 |
| barrier | 集合点：等全员到齐 | 分阶段并行计算 |
Producer-Consumer · Dining Philosophers
要素：互斥锁护缓冲；信号量 empty（初值 N，缓冲空位）与 full（初值 0，现有数据）。生产者 P(empty) → P(mutex) → 放 → V(mutex) → V(full)；消费者对称。
陷阱：P 的顺序不能反——先 P(mutex) 再 P(empty)，缓冲满时持着 mutex 睡，生产者全堵死（自己锁死自己）。
五人五叉，每人先拿左再拿右 → 可能循环等待（死锁雏形，下一篇主角）。三种标准解法：① 资源有序：奇数号先左、偶数号先右，打破循环等待条件；② 一次拿全：用信号量/互斥锁保证"两叉同时拿"；③ 限制人数：最多 4 人同时上桌（破坏"占有并等待"的密度）。
所有同步问题都是三步：① 找不变式（缓冲 ≤ N、叉子不共用）；② 选原语（数量→信号量、资格→互斥、时序→条件变量）；③ 检查获取顺序（谁先谁后决定会不会锁死自己）。
// Go 版生产者-消费者（channel 一行顶三件套） ch := make(chan int, N) // 有界缓冲 // 生产者 go func() { for i := 0; i < 100; i++ { ch <- i // 满则阻塞 = P(empty) } close(ch) }() // 消费者 for v := range ch { _ = v // 空则阻塞 = P(full) } // runtime 内部：hchan 的 lock(互斥) // + sendq/recvq(等待队列) 全套齐活
Go sync × OS
normal 模式：CAS 快路径 + 短暂自旋，失败入 FIFO 等待队列但允许新来的抢（吞吐优先）；等待者被唤醒后还要和新来者赛跑。 starvation 模式：等待超过 1ms 触发，改为严格 FIFO 直接交接（公平优先），持锁者释放时直接把锁递给队头。1.9 引入，专治长尾延迟。
挂起的写者会阻塞后续读者，防写者饿死。代价：递归读锁（读锁内再拿读锁）遇到中间夹写者时可能死锁——文档明示的陷阱。读多写少极端场景用原子操作或分片（shard）替代。
竞争激烈时走 futex（Linux）让 goroutine 挂起？不——Go 先在 runtime 层把 G 挂到 mutex 的等待队列（semaRoot 的 treap），必要时才动用 futex 睡 M：runtime 复刻了一遍 futex 的快慢两阶段，只是快路径是用户态的 G 队列。
// 两模式的行为差异（伪代码） func (m *Mutex) Lock() { if atomic.CompareAndSwapInt32(&m.state, 0, 1) { return // 快路径：一次 CAS 搞定 } m.lockSlow() // 自旋 → 排队 → 竞争升级 } // normal: 新来者可与被唤醒者抢锁（吞吐） // starving: 释放时直接交接队头（公平） // 触发: 等待 > 1ms 切入 starving // 解除: 队列清空 或 拿到锁的等待者很少
Interview QA · Part 1
结果取决于执行交错顺序的缺陷。最小例子：两线程并发 i++——load/add/store 三步交错后两次自增只加 1（丢失更新）。根源 = 共享 + 交错；解法 = 消除交错（原子）或串行化（锁）。
CAS 原子地"等于期望才写入"。ABA：值从 A→B→A，CAS 误以为没变（指针场景可能拿到已释放的旧对象）。解法：带版本号/标签指针（CAS 双字），或用能检测 ABA 的原语（LL/SC）。x86 的 cmpxchg8b/16b 支持带标签比较。
临界区接近或小于一次上下文切换成本（μs 级）且持锁者不睡眠 → 自旋；反之睡眠锁。现实是混合：先自适应自旋几轮再睡。内核中断上下文只能自旋（不能睡眠）是硬约束。
无竞争时锁的获取/释放只是用户态一次 CAS，零系统调用、零切换；只有真正竞争时才陷入内核睡眠/唤醒。把"乐观情形留在用户态"是它的设计哲学，pthread_mutex 与 Go mutex 都建立在其上。
配锁：让"查谓词 + 睡眠"原子，否则检查与入睡之间对方 signal 就丢了唤醒。while：醒来后条件可能已变（他人抢先消费/虚假唤醒），必须重查谓词再继续。
互斥锁有所有权（谁加谁解、递归语义），信号量是计数许可（无所有权，V 可来自任意线程）。互斥锁表达临界区，信号量表达资源池；二值信号量当互斥锁用会引入"解别人的锁"类事故。
Interview QA · Part 2
三件套（mutex + empty + full）之外，灵魂是 P 的顺序：必须先 P(empty/full) 再 P(mutex)——反了会在缓冲满/空时持锁睡眠，锁死对方。Go 里一个带缓冲 channel 等价实现，正确性内建。
normal 允许新来者与被唤醒者抢锁（缓存热、吞吐高），但持续竞争会饿死队头；等待超 1ms 切入 starvation 严格 FIFO 交接，压平长尾。等待队列空了自动回 normal。典型"两难权衡用状态机调和"。
读者也要原子更新 readerCount——高并发读时所有读者抢同一个 cache line，性能可能不如普通锁甚至原子操作。读多写少且读者极多时：分片锁、副本更新（copy-on-read）、或 RCU 式发布。
写者优先：写者阻塞时新读者排队。于是"读锁内再拿读锁"遇上中间到达的写者——外层读锁等内层，内层读锁等写者，写者等外层释放 → 死锁。规避：读锁内绝不递归拿读锁；或换成一次性读快照。
按优先级：① 不共享（每 goroutine 私有数据，channel 传值）；② 原子操作（计数器、标志位，atomic 包）；③ Copy-on-Write（读用不可变快照，写时整体替换，如 COW map）；④ 真无锁结构（CAS 循环，谨慎）。锁是最后手段，不是默认。
Go：runtime.SetMutexProfileFraction 开锁画像，pprof 看 contention 排名与持锁调用栈；CPU 上不去但延迟高 → 大概率锁串行化。手段：缩临界区（出锁再做 I/O）、分片、无共享化。内核侧 perf lock / 火焰图看 futex 站队。
Interview QA · Part 3
几乎没有：单核上持锁者与等待者轮流上 CPU，等待者自旋只会烧完时间片拖慢持锁者。唯一例外：抢占被关闭的内核临界区（关中断 + 自旋），这时"自旋"其实是在等中断上下文退出，时序可控。
资源有序（奇偶分组拿叉）破坏"循环等待"；一次拿全（原子取两叉）破坏"逐步占有"；限 4 人上桌破坏"占有并等待"的成立密度。与死锁预防一一对应——下一篇的伏笔。
C 的 volatile 只禁止编译器优化掉读写，不提供原子性与内存序，多核下照样丢更新。Java volatile 有 happens-before 语义（可见性+有序性）但仍无原子性（i++ 依然不安全）。Go 没有 volatile，用 atomic 包或锁。三语言的差异本身就是高频考点。
无关变量共享一把锁 → 假性竞争（false contention）：访问 A 的线程被访问 B 的线程拖住。拆锁提升并行度，但引入锁序问题（持 A 锁申请 B 锁必须全局有序，否则死锁——下一篇）。粒度 vs 正确性是永恒权衡。
持锁线程被切走，临界区被"拉长"到它回来为止，等待者空转或睡眠——这就是自旋锁单核陷阱的通用版。Go 的缓解：syscall 前 P 解绑（不让慢 syscall 拖住 P 上的其他 G）；持锁 goroutine 被抢占则整个 P 的队列排队。
atomic.AddInt64 一行搞定（底层 lock xadd）。上限：极高并发时所有核抢同一 cache line（伪共享），吞吐反而不如分片——如 runtime 的 per-P 计数再聚合（Go GC 的 stats 就是这么干的）。无锁 ≠ 无成本。
Related & References
sync 并发原语底层 →（本 deck 的 Go 源码版）
Channel 底层原理 →（"通信即同步"的实现）
InnoDB 锁体系 →（同一套思想在数据库的化身）
参考来源（本 deck 结论可溯源至下列一手材料）
| OSTEP ch.28–31（锁 / 条件变量 / 信号量 / 常见并发问题） | TAS→TTAS→排队锁演化、条件变量规范、哲学家三解法 |
| man 2 futex / man 7 pthreads | futex 两阶段语义、等待队列与重校验规则 |
| CSAPP ch.12（并发编程） | 基于信号量的生产者-消费者、读者-写者模型 |
| Go src/sync/mutex.go（1.9+ 双模式） | normal/starvation 状态机、1ms 阈值、队列交接 |
| xiaolincoding.com《图解系统》multithread_sync / pessim_and_optimi_lock | 互斥/同步中文叙述、悲观乐观锁对照 |
| MCS Lock 论文（Mellor-Crummey & Scott, 1991） | 排队自旋锁原型，Go runtime osq 的思想源头 |