第十章 屏障与同步 (Barriers and Synchronization)

一、导读

1.1 本章学习目标

理解屏障（Barrier）的概念及其在并行计算中的核心作用

掌握各种屏障实现方法及其性能特征

深入理解条件同步（Conditional Synchronization）的原理和实现

学会使用信号量、管程（Monitor）和条件变量实现复杂的同步模式

理解经典同步问题（读者-写者、哲学家就餐、吸烟者问题）及其解决方案

掌握同步机制的正确性证明方法

了解同步在实际系统中的应用模式和最佳实践

1.2 为什么本章如此重要

同步是并发编程的基础。在多线程程序中，线程之间经常需要协调执行顺序：一个线程必须等待另一个线程完成某个操作后才能继续；一组线程必须等待所有成员到达某个点后才能一起继续。这些协调需求统称为"同步"。

屏障（Barrier）是一种特殊的同步机制，它要求一组线程都到达屏障点后才能继续执行。屏障在并行计算中有着广泛的应用：迭代算法中每轮迭代结束时的同步、并行归约中各阶段之间的同步、并行搜索中结果汇总前的同步等。

本章系统地介绍了各种同步机制和经典的同步问题。从简单的计数屏障到高效的组合屏障，从基本的信号量到复杂的管程，从理论上的经典问题到实际系统中的同步模式。这些内容构成了并发编程的"同步工具箱"，是编写正确、高效并发程序的基础。

经典同步问题（如哲学家就餐、读者-写者）虽然看似抽象，但它们揭示了同步中的基本挑战：资源竞争、死锁避免、公平性保证。理解这些问题的解决方案，可以帮助程序员在实际系统中识别和解决类似的同步问题。

同步机制的正确性证明是本章的另一个重点。并发程序的正确性不能仅靠测试来验证（因为可能的执行顺序太多），需要通过形式化的推理来保证。不变量（Invariant）、前置条件（Precondition）和后置条件（Postcondition）是证明同步机制正确性的基本工具。

1.3 核心问题引导

什么是屏障？它在并行计算中扮演什么角色？

如何高效地实现一个支持大量线程的屏障？

条件同步与互斥有什么区别？如何实现条件同步？

哲学家就餐问题揭示了什么同步挑战？有哪些解决方案？

读者-写者问题有哪些变体？如何在公平性和性能之间权衡？

如何证明一个同步机制是正确的？

二、核心概念详解

2.1 屏障（Barrier）

屏障是一种同步机制，它要求一组 n 个线程都到达屏障点后才能继续执行。每个线程在执行到屏障点时调用 barrier.await()，该方法会阻塞线程直到所有 n 个线程都调用了 await()。然后所有线程同时被释放，继续执行屏障之后的代码。

屏障在并行计算中有广泛的应用。在迭代算法中（如 Jacobi 迭代、Gauss-Seidel 迭代），每轮迭代结束后所有线程必须同步，确保所有线程都完成了当前轮的计算后才能开始下一轮。在并行归约中，各阶段的计算需要在前一阶段完成后才能开始。在并行搜索中，所有线程完成搜索后需要汇总结果。

屏障的基本实现使用一个计数器和一把锁：

class CounterBarrier {
  private final int n;
  private int count = 0;
  
  public synchronized void await() throws InterruptedException {
    count++;
    if (count == n) {
      notifyAll();  // 最后一个到达的线程唤醒所有等待线程
    } else {
      while (count < n) {
        wait();  // 其他线程等待
      }
    }
  }
}

这个简单实现的问题是所有线程都在同一把锁上竞争，可伸缩性差。

2.2 组合屏障

组合屏障（Combining Barrier）通过树形结构减少锁争用，提高可伸缩性。其思想类似于归约树：将 n 个线程分成若干组，每组使用一个局部屏障；局部屏障完成后，各组的代表线程在全局屏障上同步。

感知器屏障（Sense-Reversing Barrier）是一种高效的屏障实现。它使用一个共享的 count 变量和一个 sense 变量。每个线程维护一个本地的 mySense。线程到达屏障时将 count 减 1；如果 count 变为 0，最后一个线程重置 count 为 n 并翻转 sense；其他线程等待 sense 变为 mySense。

这种实现的优势是：最后一个线程不需要显式唤醒其他线程（通过 sense 变量的变化来通知）；减少了锁争用（可以使用原子操作代替锁）。

2.3 条件同步

条件同步（Conditional Synchronization）是指线程在某些条件满足时才能继续执行。它是比互斥更一般的同步问题。

条件同步的经典例子是有界缓冲区：生产者需要等待"缓冲区不满"的条件，消费者需要等待"缓冲区不空"的条件。这些条件的状态随着其他线程的操作动态变化。

条件同步的实现工具包括：信号量（Semaphore）——通过计数来表示可用资源的数量；条件变量（Condition Variable）——与锁配合使用，支持等待任意布尔条件；管程（Monitor）——封装了锁和条件变量的高级结构。

条件同步的正确性需要保证：安全性（Safety）——线程只在条件满足时继续执行；活性（Liveness）——如果条件最终变为真，等待的线程最终会被唤醒。

2.4 经典同步问题

哲学家就餐问题（Dining Philosophers Problem）：5 个哲学家围坐在圆桌旁，每两个哲学家之间有一根筷子。哲学家交替思考和进餐，进餐时需要同时拿到左右两根筷子。问题是如何安排筷子的获取顺序，使得所有哲学家都能进餐，不会发生死锁。

解决方案包括：资源分级（每个哲学家先拿编号小的筷子，再拿编号大的筷子）——打破循环等待条件；允许最多 4 个哲学家同时拿筷子——打破持有并等待条件；使用服务生（中央协调者）来分配筷子——打破互斥条件。

读者-写者问题（Readers-Writers Problem）：多个线程共享一个数据对象。读者只读取数据，写者修改数据。约束是：多个读者可以同时读取，但写者必须独占访问（不能有读者或其他写者同时访问）。

读者优先版本：读者到来时如果没有写者在写，直接进入；写者到来时必须等待所有读者离开。问题：如果读者持续到来，写者可能饥饿。

写者优先版本：写者到来时，后续的读者必须等待写者完成。问题：如果写者持续到来，读者可能饥饿。

公平版本：按照到达顺序服务，读者和写者公平竞争。

2.5 管程（Monitor）

管程（Monitor）是 Hoare 和 Brinch Hansen 在 1970 年代提出的一种高级同步结构。它将共享数据、操作共享数据的方法和同步机制封装在一起。

管程的基本性质：同一时刻最多只有一个线程在执行管程的任何方法（互斥性）。管程内部可以使用条件变量来实现条件同步。

管程的条件变量与信号量不同：条件变量没有状态（不计数），wait 操作释放锁并阻塞线程，signal 操作唤醒一个等待线程（如果没有等待线程，信号丢失）。

管程的实现方式：Hoare 语义——signal 操作后立即将被唤醒的线程切换为运行状态，当前线程阻塞。Mesa 语义——signal 操作将被唤醒的线程放入就绪队列，当前线程继续运行直到退出管程或等待。Java 的 synchronized 使用 Mesa 语义。

三、深入分析与讨论

3.1 屏障的可伸缩性

屏障的可伸缩性是指随着线程数增加，屏障的性能如何变化。简单的计数屏障使用一把全局锁，所有线程在同一把锁上竞争，可伸缩性差。

树形屏障（Tree Barrier）将线程组织成一棵树，每个内部节点是一个局部屏障。线程到达时从叶子向根逐层同步，释放时从根向叶逐层通知。深度为 O(log n)，每层只有一把锁，总锁争用降低了 log n 倍。

离散屏障（Dissemination Barrier）是一种对数步的屏障实现。它使用 log n 轮同步，每轮中线程按照特定的模式配对。每轮只需要 n/2 把锁，总锁争用为 O(n log n)，但深度只有 O(log n)。

3.2 同步机制的形式化验证

并发程序的正确性不能仅靠测试来验证，因为可能的执行顺序太多。形式化验证使用数学方法来证明程序在所有可能的执行下都是正确的。

不变量方法（Invariant Method）：定义一个关于共享状态的谓词（不变量），证明它在程序的每个可达状态下都为真。例如，互斥的不变量是"最多一个线程在临界区内"。

前置-后置条件方法（Pre-Post Condition Method）：为每个操作定义前置条件（执行前的状态约束）和后置条件（执行后的状态约束）。证明如果前置条件为真，操作执行后后置条件为真。

rely-Guarantee 方法：为每个线程定义它对环境（其他线程）的假设（Rely）和它对环境的保证（Guarantee）。证明在所有线程都满足其保证的情况下，每个线程的假设都成立。

3.3 同步在实际系统中的模式

在实际系统中，有几种常见的同步模式。

双重检查锁定（Double-Checked Locking）：延迟初始化（Lazy Initialization）的优化模式。先检查条件（无锁），如果条件不满足才加锁。需要注意内存可见性问题（在 Java 中需要使用 volatile）。

读写锁模式（Read-Write Lock Pattern）：读操作使用共享锁（多个读者可以并发），写操作使用独占锁。适用于读多写少的场景。

线程本地存储（Thread-Local Storage）：每个线程维护自己的数据副本，避免共享。适用于每个线程需要独立状态的场景（如随机数生成器、数据库连接）。

四、实践案例

4.1 并行迭代算法中的屏障使用

Jacobi 迭代法求解线性方程组：每个线程负责计算一部分变量的新值。每轮迭代结束后，所有线程必须在屏障处同步，确保所有新值都计算完毕后才能开始下一轮。

class JacobiTask implements Runnable {
  private final Barrier barrier;
  
  public void run() {
    for (int iter = 0; iter < MAX_ITER; iter++) {
      computeNewValues();  // 计算新值
      barrier.await();     // 等待所有线程完成
      swapArrays();        // 交换新旧值数组
      barrier.await();     // 确保所有线程完成交换
    }
  }
}

4.2 使用信号量解决哲学家就餐问题

使用资源分级策略：每个哲学家先拿编号小的筷子，再拿编号大的筷子。

class Philosopher implements Runnable {
  private final Semaphore leftChopstick;
  private final Semaphore rightChopstick;
  
  public void run() {
    while (true) {
      think();
      Semaphore first = (id < right.id) ? leftChopstick : rightChopstick;
      Semaphore second = (id < right.id) ? rightChopstick : leftChopstick;
      first.acquire();  // 先拿编号小的
      second.acquire(); // 再拿编号大的
      eat();
      second.release();
      first.release();
    }
  }
}

这种方案打破了循环等待条件，保证了无死锁。

五、常见误区与注意事项

5.1 屏障的重复使用问题

简单的计数屏障在一次使用后不能重置。如果需要重复使用（如迭代算法中的多轮同步），必须使用可重置的屏障实现（如 Java 的 CyclicBarrier 或 Phaser）。

5.2 虚假唤醒问题

使用条件变量时，线程被唤醒后必须重新检查条件（使用 while 循环），因为可能存在虚假唤醒或条件在唤醒后被其他线程修改。

5.3 忽视公平性

某些同步机制可能不公平——某些线程可能被长期饥饿。例如，读者优先的读者-写者问题中，写者可能饥饿。在设计同步机制时，应该考虑是否需要公平性保证。

5.4 过度同步

过多的同步会降低并发度，甚至导致性能比串行程序更差。应该只在确实需要协调的地方使用同步，避免不必要的同步。

六、本章小结

本章系统介绍了屏障与同步机制。屏障是并行计算中用于线程组同步的基本工具，从简单计数屏障到高效的组合屏障和感知器屏障。条件同步是比互斥更一般的同步问题，通过信号量、条件变量和管程来实现。经典同步问题（哲学家就餐、读者-写者）揭示了同步中的基本挑战。管程封装了锁和条件变量，提供了更高层次的同步抽象。同步机制的正确性需要通过形式化方法来验证。在实际系统中，双重检查锁定、读写锁和线程本地存储是常见的同步模式。

七、思考题与练习

实现一个可重置的计数屏障（CyclicBarrier），支持多轮同步。

实现感知器屏障（Sense-Reversing Barrier），分析其性能优势。

使用信号量解决哲学家就餐问题，证明你的方案不会死锁。

实现读者-写者锁的三种版本：读者优先、写者优先、公平版本。比较它们的性能。

使用管程实现一个有界缓冲区，支持多个生产者和多个消费者。

证明：使用信号量可以实现互斥、条件同步和屏障。

实现一个树形屏障，分析其可伸缩性。

讨论：在什么场景下，应该使用屏障而不是锁？给出你的判断标准。