第三章 互斥与锁 (Mutual Exclusion and Locks)

一、导读

1.1 本章学习目标

深入理解互斥（Mutual Exclusion）的概念及其在并发编程中的核心地位

掌握锁（Lock）的基本实现方法，从软件算法到硬件原子指令

理解 Peterson 算法、Lamport 面包店算法等经典互斥算法的原理

掌握 Test-and-Set、Compare-and-Swap 等硬件原子操作的使用方法

学会分析锁的性能指标：争用（Contention）、公平性（Fairness）、复杂度

理解自旋锁（Spin Lock）与阻塞锁（Blocking Lock）的区别与适用场景

掌握锁的常见使用模式和反模式

1.2 为什么本章如此重要

互斥是并发编程中最基本的问题之一。当多个线程需要访问共享资源时，必须确保同一时刻只有一个线程在访问，否则可能导致数据不一致或程序错误。锁是实现互斥的最常用工具，理解锁的原理和实现对于编写正确的并发程序至关重要。

互斥问题的研究有着悠久的历史。从 1965 年 Dijkstra 提出信号量和 P/V 操作开始，到 Peterson 算法（1981）、Lamport 面包店算法（1974），再到基于硬件原子指令的现代锁实现，互斥算法的发展反映了并发编程理论和实践的进步。

本章从最简单的两线程互斥算法开始，逐步引入更复杂的解决方案。每个算法都揭示了并发编程中的一个重要概念：原子性、可见性、公平性、等待条件等。通过理解这些算法的设计思路，读者可以深入理解并发编程的本质挑战。

锁虽然是解决互斥问题的基本工具，但也是并发程序中最常见的性能瓶颈和 bug 来源。死锁、活锁、饥饿、优先级反转等问题都与锁的使用不当有关。因此，理解锁的原理不仅是为了实现互斥，更是为了正确使用锁、避免锁的陷阱。

1.3 核心问题引导

如何在没有硬件支持的情况下实现两线程互斥？Peterson 算法是如何工作的？

如何将互斥算法从两线程推广到 n 线程？Lamport 面包店算法的核心思想是什么？

硬件提供了哪些原子操作来简化互斥的实现？它们各自的优缺点是什么？

自旋锁和阻塞锁有什么区别？在什么场景下应该使用哪种？

如何评估一个锁算法的性能？公平性为什么重要？

锁的常见反模式有哪些？如何避免死锁和优先级反转？

二、核心概念详解

2.1 互斥问题的形式化定义

互斥问题（Mutual Exclusion Problem）是并发编程中的基本问题。其形式化定义如下：有 n 个线程，每个线程反复执行以下代码：

do {
  entry_section();   // 进入区
  critical_section(); // 临界区
  exit_section();     // 退出区
  remainder_section(); // 剩余区
} while (true);

互斥算法需要设计 entry_section() 和 exit_section() 的实现，满足以下三个要求：

互斥（Mutual Exclusion / Safety）：在任何时刻，最多只有一个线程在临界区内。这是安全属性，保证不会出现两个线程同时操作共享资源的情况。

无死锁（Deadlock Freedom / Liveness）：如果两个或多个线程同时试图进入临界区，至少有一个线程能够成功进入。这是活性属性，保证系统不会"卡住"。

无饥饿（Starvation Freedom / Liveness）：每个试图进入临界区的线程最终都能成功进入。这是更强的活性属性，保证不会有线程被永远拒绝。

2.2 Peterson 算法

Peterson 算法是 1981 年由 Gary Peterson 提出的一个优雅的两线程互斥算法。它仅使用共享变量和普通的读写操作（不需要硬件原子指令），就实现了互斥。

算法使用两个共享变量：flag[0] 和 flag[1]（表示线程是否想进入临界区），以及 turn（表示当两个线程都想进入时，谁应该等待）。

线程 i 的进入区代码：

flag[i] = true;       // 表示我想进入
turn = j;             // 让给对方
while (flag[j] && turn == j); // 等待：对方也想进入，且轮到对方

Peterson 算法的正确性可以通过分析所有可能的执行顺序来验证。关键观察是：turn 的赋值是最后一步，它决定了当两个线程都设置 flag 后的优先级。后设置 turn 的线程会"覆盖"先设置的值，从而获得优先权。

Peterson 算法的局限在于：它只适用于两个线程，且依赖于内存操作的顺序性（在弱内存模型的处理器上可能需要额外的内存屏障）。

2.3 Lamport 面包店算法

Lamport 面包店算法（Bakery Algorithm）是 Leslie Lamport 在 1974 年提出的 n 线程互斥算法。它的灵感来自面包店的取号排队系统：每个顾客进入时取一个号码，号码小的先被服务。

算法的核心思想：每个线程在进入临界区之前获取一个"号码"（一个递增的整数），然后等待所有号码更小的线程先进入临界区。如果两个线程的号码相同（可能同时获取），则通过线程 ID 来打破平局。

获取号码的过程需要保证原子性——不能有两个线程获取相同的号码（除非它们确实同时尝试）。Lamport 的解决方案是：先设置一个 choosing[i] 标志为 true，然后取号码，再设置 choosing[i] 为 false。其他线程在读取号码时，如果发现 choosing[j] 为 true，就等待直到 choosing[j] 为 false。

面包店算法满足互斥、无死锁和无饥饿（FIFO 公平性）。但它的时间复杂度较高：获取号码需要 O(n) 时间（读取所有其他线程的号码），等待也可能需要 O(n) 时间。

2.4 硬件原子操作

现代处理器提供了一些硬件原子操作来简化同步的实现。这些操作在硬件层面保证原子性，无法被中断。

Test-and-Set（TAS）：原子地读取一个内存位置的值，并将其设置为 1（或 true）。返回原来的值。如果原来的值为 0，表示成功获取锁；如果为 1，表示锁已被其他线程持有。

Compare-and-Swap（CAS）：原子地比较一个内存位置的值与预期值，如果相等则将其更新为新值。返回原来的值（或布尔值表示是否成功）。CAS 比 TAS 更强大，可以实现无锁数据结构。

Fetch-and-Add（FAA）：原子地读取一个内存位置的值，并将其增加一个增量。返回原来的值。可以用于实现公平的队列锁。

Load-Linked / Store-Conditional（LL/SC）：LL 读取一个内存位置并标记它；SC 写入一个内存位置，但仅当该位置自 LL 以来没有被修改过。LL/SC 可以实现 CAS 的功能，在某些架构（如 ARM、PowerPC）上使用。

2.5 自旋锁与阻塞锁

自旋锁（Spin Lock）：当线程无法获取锁时，它在一个循环中不断重试（"自旋"）。自旋锁适用于锁持有时间很短的场景，因为线程不会放弃 CPU，一旦锁被释放就可以立即获取。但在锁持有时间较长时，自旋会浪费大量的 CPU 时间。

阻塞锁（Blocking Lock）：当线程无法获取锁时，它将自己放入等待队列并让出 CPU（阻塞）。当锁被释放时，操作系统唤醒等待队列中的一个线程。阻塞锁适用于锁持有时间较长的场景，因为它不会浪费 CPU 时间。但在锁持有时间很短时，阻塞和唤醒的开销（涉及操作系统内核调用）可能比自旋更大。

现代操作系统通常提供两种锁的实现：用户态的自旋锁（如 pthread_spinlock）和内核态的互斥锁（如 pthread_mutex）。一些高级的锁实现（如 Linux 的 futex）结合了两者的优点：先自旋一段时间，如果仍然无法获取锁，再切换到阻塞模式。

三、深入分析与讨论

3.1 锁的性能指标

评估锁的性能需要考虑多个维度。吞吐量（Throughput）：单位时间内成功获取和释放锁的次数。在高争用场景下，锁的吞吐量可能成为系统的瓶颈。

公平性（Fairness）：锁是否保证每个等待的线程最终都能获取锁。FIFO 锁保证按请求顺序获取；.ticket 锁是一种典型的 FIFO 锁。非公平锁可能导致某些线程长期饥饿。

可伸缩性（Scalability）：随着线程数增加，锁的性能如何变化。基于 TAS 的简单锁在高争用下可伸缩性很差（所有线程同时竞争同一个缓存行）。队列锁（如 MCS 锁）的可伸缩性更好，因为每个线程只在自己的缓存行上自旋。

延迟（Latency）：从请求获取锁到成功获取的时间。在无争用情况下，理想的锁延迟应该只有几个原子操作的开销。

3.2 锁的优化技术

为了减少锁的争用和开销，研究者提出了多种优化技术。

队列锁（Queue Lock）：如 MCS 锁和 CLH 锁，使用一个隐式或显式的队列来管理等待的线程。每个线程只在队列中自己的节点上自旋，减少了缓存行的争用。MCS 锁的可伸缩性优于 TAS 锁，因为它消除了"缓存行弹跳"。

读写锁（Read-Write Lock）：允许多个读者同时获取锁，但写者需要独占。在读多写少的场景下，读写锁可以显著提高吞吐量。但写者可能饥饿（持续的读者流阻止写者获取锁）。

锁消除（Lock Elimination）：编译器分析发现某个锁只在单线程上下文中使用，可以自动消除该锁。Java 的逃逸分析（Escape Analysis）可以实现锁消除。

锁粗化（Lock Coarsening）：将多个连续的加锁-解锁操作合并为一个大的临界区，减少锁操作的次数。

3.3 死锁与优先级反转

死锁（Deadlock）：两个或多个线程互相等待对方持有的锁，导致所有线程都无法继续。死锁的四个必要条件：互斥、持有并等待、不可抢占、循环等待。打破其中任何一个条件就可以防止死锁。常见的策略包括：锁排序（所有线程按相同顺序获取锁）、超时重试、死锁检测。

优先级反转（Priority Inversion）：高优先级线程等待低优先级线程持有的锁，而中优先级线程又抢占了低优先级线程的执行，导致高优先级线程被间接阻塞。经典的解决方案是优先级继承（Priority Inheritance）：当高优先级线程等待低优先级线程的锁时，临时提升低优先级线程的优先级。

四、实践案例

4.1 基于 TAS 的自旋锁实现

使用 Test-and-Set 指令实现一个简单的自旋锁：

class TASLock {
  private AtomicBoolean locked = new AtomicBoolean(false);
  
  public void lock() {
    while (locked.getAndSet(true)) {
      // 自旋等待
    }
  }
  
  public void unlock() {
    locked.set(false);
  }
}

这个实现的问题是：在解锁时，所有自旋的线程同时尝试获取锁，导致大量的 CAS 失败和缓存行弹跳。改进方案是 Test-and-Test-and-Set（TTAS）：在自旋时先读取（不修改），只有当锁看起来可用时才尝试获取。

4.2 ticket 锁的实现

ticket 锁是一种简单的 FIFO 锁，使用 Fetch-and-Add 实现：

class TicketLock {
  private AtomicInteger next = new AtomicInteger(0);
  private AtomicInteger now = new AtomicInteger(0);
  
  public int lock() {
    int myTurn = next.getAndIncrement();
    while (now.get() != myTurn) {
      // 自旋等待
    }
    return myTurn;
  }
  
  public void unlock(int myTurn) {
    now.set(myTurn + 1);
  }
}

ticket 锁保证了 FIFO 公平性：每个线程获取一个唯一的"号码"，按号码顺序获取锁。但它的可伸缩性有限：解锁时 now 的更新会导致所有自旋线程的缓存行失效。

五、常见误区与注意事项

5.1 在临界区内执行耗时操作

临界区应该尽可能短。在临界区内执行 I/O 操作、网络请求或其他耗时操作会严重降低锁的吞吐量，因为其他线程必须等待。

5.2 忽视锁的粒度

锁的粒度（granularity）直接影响并发度。粗粒度锁（如整个数据结构一把锁）简单但并发度低；细粒度锁（如每个节点一把锁）并发度高但开销大且容易死锁。选择合适的粒度需要根据具体的访问模式来决定。

5.3 忘记释放锁

如果线程在临界区内抛出异常或提前返回，但忘记释放锁，会导致其他线程永远无法获取锁。使用 try-finally 模式或 RAII（Resource Acquisition Is Initialization）模式可以确保锁总是被释放。

5.4 在高争用场景使用简单自旋锁

在大量线程竞争同一把锁时，简单的 TAS 自旋锁会导致严重的性能问题。应该使用可伸缩性更好的锁实现（如队列锁）或考虑无锁算法。

六、本章小结

本章深入探讨了互斥与锁的实现原理。互斥问题要求满足安全性（互斥）和活性（无死锁、无饥饿）。从 Peterson 算法到 Lamport 面包店算法，展示了如何用纯软件方法解决互斥问题。硬件原子操作（TAS、CAS、FAA）大大简化了锁的实现。自旋锁适用于短临界区，阻塞锁适用于长临界区。锁的性能评估需要考虑吞吐量、公平性、可伸缩性和延迟。死锁和优先级反转是锁使用中的常见问题，需要通过锁排序、优先级继承等技术来避免。

七、思考题与练习

实现 Peterson 算法，并通过手动分析所有可能的线程交错来验证其正确性。

实现 Lamport 面包店算法，分析其时间复杂度和空间复杂度。

比较 TAS 锁和 TTAS 锁在不同争用程度下的性能差异。用实验验证你的分析。

实现一个基于 CAS 的自旋锁。它与基于 TAS 的锁有什么区别？

实现 ticket 锁和 MCS 锁，比较它们的公平性和可伸缩性。

设计一个场景来演示优先级反转问题，并实现优先级继承协议来解决它。

分析以下代码是否存在死锁风险，如果有，如何修复？

实现一个读写锁，支持多个读者同时获取锁，但写者独占。分析其在读多写少和写多读少场景下的性能。