《操作系统导论》第28章：锁 - 深度知识架构

1. 核心矛盾 (The Crucial Problem)

在单处理器中断或多处理器并发的复杂环境下，如何以低成本构建一种互斥（Mutual Exclusion）机制，同时兼顾线程获取资源的公平性与极高的执行性能？ 本质上，这是在探讨如何通过软硬件的巧妙协作，让原本混乱并发的代码序列重新获得“原子性（Atomicity）”的控制权。

2. 核心概念 (Core Concepts)

• 锁 (Lock) / 互斥量 (Mutex)：
  • 定义：一种像变量一样存在的同步结构。放在临界区（Critical Section）周围，保证临界区能够像单条原子指令一样执行。在可移植操作系统接口 (Portable Operating System Interface, POSIX) 库中被称为互斥量。
  • 角色：并发世界的“秩序维护者”。它把原本由操作系统 (Operating System, OS) 调度的混乱状态变得更为可控，确保同一时刻只有一个线程活跃在临界区中。
• 自旋锁 (Spin Lock)：
  • 定义：一种最基础的锁实现。当线程尝试获取一个已被持有的锁时，它不会放弃中央处理器 (Central Processing Unit, CPU)，而是在一个 while 循环中不断“自旋”检查锁的状态。
  • 角色：短时间等待场景下的“性能利器”，但在单 CPU 或长时间等待场景下则是“算力黑洞”。
• 排号锁 (Ticket Lock)：
  • 定义：利用两个计数器（ticket 和 turn）构建的锁。每个尝试获取锁的线程抽取一个号码（ticket），当该号码等于当前服务号码（turn）时，线程进入临界区。
  • 角色：并发系统中的“公平法官”。它彻底解决了传统自旋锁无法保证线程公平性、极易导致线程饿死（Starve）的问题。
• 两阶段锁 (Two-Phase Lock)：
  • 定义：第一阶段先自旋等待一段时间，如果未能获取锁，则进入第二阶段（休眠等待）。
  • 角色：一种实用主义的“混合器 (Hybrid)”。它完美结合了自旋锁的低延迟与休眠锁的低消耗优势。

3. 逻辑演进 (Logical Evolution)

为了造出一把好锁，计算机先驱们进行了一场跌宕起伏的演进：

• 最初的尝试（纯软件/OS级）：关闭中断 (Disable Interrupts)。
  • 机制：在进入临界区前调用特权指令关闭硬件中断，防止上下文切换。
  • 遇到的问题：这是一种极其危险的做法，它要求给普通用户程序赋予特权；同时它根本无法在多处理器系统上工作（关闭一个 CPU 的中断阻止不了另一个 CPU 上的线程进入临界区）；且关闭中断会使得系统可能丢失重要的物理事件。
• 演进 1：单纯依靠硬件的原子指令（测试并设置 / Test-and-Set）。
  • 机制：既然纯软件不行，那就要求硬件提供一条不可被中断的“超级指令”。硬件工程师提供了测试并设置 (Test-and-Set) 指令（或称原子交换），能原子地读取旧值并赋新值。基于它，我们造出了经典的自旋锁。
  • 遇到的问题 1（公平性）：这把锁会导致饿死现象，某些线程可能永远抢不到锁。于是，人们发明了获取并增加 (Fetch-and-Add) 指令，造出了保证绝对公平的 排号锁 (Ticket Lock)。
  • 遇到的致命问题 2（性能）：自旋实在太浪费 CPU 了！如果有 N 个线程竞争，就会浪费 N−1 个时间片只是在盲目循环检查一个不会改变的值。
• 演进 2：硬件与操作系统的协作（让出 CPU / Yield）。
  • 机制：当线程发现锁被占用时，调用 OS 提供的 yield() 接口主动放弃 CPU，从运行态转为就绪态。
  • 遇到的问题：虽然避免了毫无意义的 99% 时间片的自旋，但 100 个线程不断“运行-让出”导致的上下文切换成本依然是极其高昂的。
• 最终的成熟方案：利用队列和休眠机制替代自旋。
  • 机制：我们必须施加严格的控制。利用 OS 提供的休眠与唤醒支持（如 Solaris 的 park()/unpark() 或 Linux 的 futex），配合一个等待队列。如果锁被占用，线程就把自己加入队列并休眠。当持有锁的线程释放锁时，主动从队列中唤醒下一个等待者。
  • 结果：彻底终结了自旋带来的算力浪费，将控制权精确地交还给操作系统和锁的维护结构。

4. 机制与策略 (Mechanisms vs. Policies)

• 底层的“实现手段”（机制 - Mechanisms）：
  • 硬件机制：提供了强大的原子指令作为基石。不仅有测试并设置 (Test-and-Set)，还有更复杂的比较并交换 (Compare-and-Swap, CAS)、无锁编程常备的链接的加载和条件式存储 (Load-Linked/Store-Conditional, LL/SC)，以及获取并增加 (Fetch-and-Add)。
  • OS 机制：提供了底层的线程状态管理能力，如 yield() 让出 CPU，以及控制线程睡眠和唤醒的底层系统调用（如 park、unpark、futex）。
• 上层的“决策逻辑”（策略 - Policies）：
  • 在两阶段锁 (Two-Phase Lock) 的实现中体现了纯粹的策略决策：系统策略决定了一个线程在发现锁被占有时，究竟应该自旋多久才放弃自旋并转入休眠。

5. 设计折衷 (Design Trade-offs)

• “自旋浪费”与“上下文切换开销”的折中：自旋锁（Spin Lock）牺牲了获取不到锁时的 CPU 周期（空转），换取了极低的唤醒延迟（一旦锁释放立刻就能拿到），它适用于临界区极短的场景。休眠锁牺牲了上下文切换的高昂时间成本，换取了 CPU 资源的释放，它适用于临界区长、竞争激烈的场景。现代的“两阶段锁”正是对这一折中的完美调和。

6. 关键洞察 (Key Insights)

• 硬件与操作系统的精妙交响：并发不能只靠程序员（写个while循环会自旋死），不能只靠硬件（硬件不懂队列和调度），也不能只靠操作系统（关闭中断代价太大）。一把真正高能且可用的锁，其实是“基于硬件原子指令构建状态防线，基于操作系统原语执行等待与唤醒”的巅峰协同之作。
• 代码越少越好（劳尔定律 Lauer's Law）：在系统级编程中，复杂不仅意味着慢，更意味着海量的并发 Bug。Hugh Lauer 指出，简洁的代码更易懂，缺陷更少。当我们看到 Linux 的 futex 或者条件式存储（LL/SC）的简短实现时，不得不惊叹于以极少的代码完成极复杂同步逻辑的工程之美。
• 一切皆可杂合（Hybrid）：当遇到两个看似完全相反的概念（如自旋与休眠）时，计算机科学家的智慧往往是不要做单选题。两阶段锁告诉我们，先自旋一会儿，再休眠，结合两种好想法往往能得到一个在绝大多数真实工作负载下表现更优的机制。

导师的下一步建议： 现在我们手里不仅握有底层机制（硬件原子指令），还学会了如何利用操作系统支持手工打造一把兼具高性能与公平性的工业级锁。 那么，有了这些强大的工具，我们如何在诸如并发链表、并发散列表等实际的数据结构中使用它们，使得这些结构不仅线程安全，而且能支持成千上万的并发访问呢？

MOC · 下一章：Ch28补充理解 临界区和锁