互斥锁的实现：从关中断到原子指令与自旋锁

一句话定义

互斥锁（mutex/lock）是保证临界区互斥进入的同步原语；工程实现从单核的关中断，演进到多核时代依赖 test-and-set/CAS 等硬件原子指令，再以"自旋 + 睡眠"混合策略（futex）平衡效率。

为什么重要

锁是并发编程的第一工具，但"会用"与"懂原理"差距巨大：锁放在进程还是线程、该自旋还是睡眠、锁粒度多大，全部取决于其底层机制。理解原子指令，也是进入无锁编程（kp-015）与内核同步原语（自旋锁 vs 信号量）的门票。

前置知识

kp-011（临界区问题与三条件）；kp-006（睡眠与唤醒即上下文切换）。

核心概念

• 关中断方案：进入临界区前关中断——只在单核有效，多核与其他特权场景失效，内核内部偶用但绝不对用户程序开放。
• test-and-set / exchange：硬件保证"读旧值并写新值"一步完成。
• CAS（compare-and-swap）：比较期望值，相等才写入，返回是否成功；x86 为 lock cmpxchg。
• LL/SC：load-linked/store-conditional，另一族原子指令（ARM/RISC-V 采用）。
• 自旋锁（spinlock）：拿不到锁就原地忙等，适合临界区极短、多核场景。
• 互斥锁 + futex：拿不到锁先自旋几次，仍失败则睡眠挂到内核等待队列，避免长忙等。
• 锁的所有者语义：POSIX mutex 谁加锁谁解锁；二值信号量无此约束（kp-013）。

原理与机制

最简自旋锁（test-and-set 版）伪代码：

lock(l):
  while (test_and_set(&l->held) == 1) ;   // 已被持有则忙等
unlock(l):
  l->held = 0;                            // 释放；配合唤醒等待者

test-and-set 之所以是解药，是因为"读-判断-写"三步被硬件压缩为一个不可分割的步骤，两个核同时抢锁必有一先一后，不可能同时看到"锁空闲"。x86 上即带 lock 前缀的指令，会锁缓存行并广播失效（MESI 协议，呼应 kp-002、kp-015）。

但纯自旋有两宗罪：单核上持锁者不运行，等待者空转烧 CPU；临界区越长浪费越大。工程解法是两阶段锁：先自旋一小段（赌持有者马上释放），失败再陷入内核睡眠——Linux 的 futex（fast userspace mutex）正是"无争用时纯用户态、有争用时才进内核"的设计，使无竞争加锁的开销接近一次原子操作。

图示

CAS 抢锁循环:                 双核争用时间线:
lock:                        核A: CAS 成功 -> 进临界区 -> 释放
  old = held                 核B: CAS 失败 -> 缓存行在A处 -> 自旋(等待缓存行迁移)
  if old == free:            核A: unlock -> 缓存行迁回B -> B 的下次 CAS 成功
     held = locked; success
  else retry

直观类比

自旋像在电梯口反复按按钮等电梯（短等划算），睡眠像回工位等叫号（长等省电）。futex 就是先按两下按钮，发现电梯半天不来才回工位登记。

实例或案例

把 kp-011 的竞态计数器加上 pthread_mutex：

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
void* add(void* a){ for(long i=0;i<1000000;i++){ pthread_mutex_lock(&m); counter++; pthread_mutex_unlock(&m); } return NULL; }

结果恒为 2000000。对比实验：临界区改小（去掉循环内加锁、整段加锁一次）性能差异明显，直观感受锁粒度与自旋开销。内核视角可用 perf lock 分析锁争用。

常见误区

• 认为锁是"软件变量"：无硬件原子指令支撑的纯软件锁在多核乱序机器上不成立。
• 在单核/实时场景滥用自旋锁：持锁时间不可控时忙等是纯浪费；内核中自旋锁要求持锁期间不可睡眠。
• 忽略锁的开销来源：无竞争锁几乎免费，真正的开销是争用下的缓存行乒乓与排队（"cache line ping-pong"）。

与其他知识点的关系

原子指令是 kp-015 无锁数据结构的积木；futex 的睡眠唤醒连接 kp-013 信号量的实现；内核态自旋锁不可睡眠的约束与 kp-006 切换成本相关。

延伸阅读

《操作系统导论》并发章节的锁推演（flag/test-and-set/队列锁）；Ulrich Drepper "Futexes Are Tricky"。

自测题

1. 为什么关中断不能解决多核互斥？

答：关中断只阻止本核被抢占，另一个核仍在并行执行并可同时进入临界区；多核互斥必须靠总线/缓存级原子指令。

1. test-and-set 满足原子性的硬件基础是什么？

答：指令在执行期间对相应缓存行持有独占（x86 lock 前缀锁定缓存行并经一致性协议失效其他副本），其他核无法在同一步骤间插入读写。

1. futex 的设计哲学是什么？

答：无竞争时整个加解锁都在用户态用原子指令完成（快路径），只有真正争用需要睡眠/唤醒时才陷入内核，兼顾快与不忙等。