第5章 进程同步（协调并发）
一、导读
1.1 本章学习目标
理解竞态条件（Race Condition）的概念及其产生的原因
掌握临界区（Critical Section）问题和解决临界区问题的三个条件
了解硬件同步指令（TestAndSet、CompareAndSwap）的工作原理
掌握信号量（Semaphore）的概念、操作和使用方法
理解管程（Monitor）的设计思想和使用方法
掌握经典同步问题（生产者-消费者、读者-写者、哲学家进餐）的解决方案
理解条件变量（Condition Variable）的作用和使用方式
了解现代编程语言提供的同步机制和最佳实践
1.2 为什么本章如此重要
进程同步是并发编程的核心挑战，也是操作系统设计中最复杂的问题之一。当多个进程或线程并发执行并共享资源时，如果没有适当的同步机制，程序的执行结果将变得不可预测——这就是竞态条件。竞态条件导致的bug极其难以发现和修复，因为它们只在特定的执行时序下出现，在测试时可能永远不会暴露，但在生产环境中偶尔发生，造成数据损坏、系统崩溃甚至安全事故。
从理论角度看，进程同步问题涉及计算理论的核心概念。Dijkstra提出的信号量概念开创了并发编程的形式化方法。临界区问题的研究推动了形式化验证和模型检测的发展。经典同步问题（如哲学家进餐问题）成为并发理论的标准案例，被用于验证新的同步机制和算法。
从实践角度看，几乎所有现代软件都需要处理并发问题。数据库系统需要保证事务的隔离性，操作系统需要协调多个进程对共享资源的访问，分布式系统需要实现跨节点的一致性。理解同步机制的原理和使用方法，是编写正确并发程序的前提。
1.3 核心问题引导
什么是竞态条件？为什么它如此难以调试和复现？
解决临界区问题需要满足哪三个条件？为什么三个条件缺一不可？
信号量的wait和signal操作为什么必须是原子的？如何用硬件指令实现？
管程相比信号量有什么优势？为什么说管程更安全？
哲学家进餐问题为什么不能简单地用互斥锁解决？如何避免死锁？
读者-写者问题中，为什么需要区分读者优先和写者优先？
条件变量与信号量有什么区别？各自适用于什么场景？
二、核心概念详解
2.1 临界区问题与竞态条件
竞态条件（Race Condition）是指多个进程并发访问共享数据，最终结果取决于执行时序的情况。例如，两个进程同时对共享变量执行i++操作，如果两个进程同时读取i的值，各自加1后写回，结果只增加了1而不是预期的2。这种bug在大多数情况下可能正确执行，只在特定时序下出错，极难调试。
临界区（Critical Section）是进程中访问共享资源的代码段。如果保证同一时刻最多只有一个进程在临界区内执行，就能避免竞态条件。临界区问题就是设计一个协议，让进程能够安全地访问共享资源。
解决临界区问题必须满足三个条件。互斥（Mutual Exclusion）：如果进程P在临界区内执行，则其他进程不能进入临界区。前进（Progress）：如果没有进程在临界区内，且有进程希望进入临界区，则应在有限时间内选择一个进程进入，不能无限拖延。有限等待（Bounded Waiting）：进程请求进入临界区后，应在有限时间内获得许可，不能无限等待（防止饥饿）。
软件解决方案包括Peterson算法，它通过两个变量（flag和turn）实现两个进程的互斥访问。Peterson算法满足三个条件，但仅适用于两个进程，且依赖于"存储和读取在同一位置"的假设——在某些硬件架构（如弱内存模型）上可能失效。
2.2 硬件同步支持
现代处理器提供了特殊的原子指令来支持同步操作。测试并设置（TestAndSet, TAS）指令原子地读取一个内存位置的值并将其设置为1，返回原始值。如果原始值为0，表示成功获取锁；如果为1，表示锁已被占用。TAS指令在单个总线周期内完成，不可被中断。
比较并交换（CompareAndSwap, CAS）指令原子地比较内存位置的值与预期值，如果相等则将其更新为新值，返回原始值。CAS比TAS更灵活，可以实现无锁数据结构。CAS是Java并发包（java.util.concurrent.atomic）的底层基础。
基于这些原子指令，可以实现自旋锁（Spinlock）：进程循环执行TAS指令直到成功获取锁。自旋锁适用于锁持有时间短的场景，因为等待进程不释放CPU而是忙等待（busy waiting），浪费CPU周期。对于长时间持有的锁，应使用阻塞锁（blocking lock），让等待进程进入睡眠状态。
2.3 信号量
信号量（Semaphore）由Dijkstra于1965年提出，是一种用于进程同步的整数变量，只能通过两个原子操作wait(S)（也称P操作或down操作）和signal(S)（也称V操作或up操作）来访问。
wait(S)操作：while S <= 0 do no-op; S = S - 1;（实际实现中使用原子操作）。signal(S)操作：S = S + 1;。
信号量分为两种类型。计数信号量（Counting Semaphore）的值域为任意非负整数，用于控制对多个资源实例的并发访问。互斥锁/二进制信号量（Mutex/Binary Semaphore）的值只能是0或1，用于实现互斥访问。
信号量的正确使用方式：互斥访问时，进程在进入临界区前执行wait(mutex)，离开后执行signal(mutex)。同步时，进程P1执行signal(S)通知P2某事件已发生，P2执行wait(S)等待该事件。信号量的值表示可用资源的数量或已发生事件的次数。
信号量的主要缺点是使用不当可能导致死锁或饥饿。如果两个进程分别wait两个信号量但顺序相反，可能发生死锁。信号量没有强制的获取顺序，可能导致某些进程长期等待（饥饿）。
2.4 管程
管程（Monitor）是一种高级同步构造，将共享数据和操作封装在一起，自动处理互斥。管程由共享变量、操作过程和初始化代码组成。同一时刻最多只有一个进程在管程内执行，管程自动保证互斥，程序员不需要显式使用锁。
管程使用条件变量（Condition Variable）实现等待/通知机制。条件变量提供三个操作：wait()——调用进程释放管程的互斥锁并进入等待队列；signal()——唤醒等待队列中的一个进程；broadcast()——唤醒等待队列中的所有进程。条件变量与信号量不同：条件变量本身不存储状态，signal()在没有等待进程时不产生效果。
管程的优势在于将同步逻辑封装在模块内部，减少了程序员出错的可能。Java的synchronized方法和wait()/notify()方法就是管程的实现。C++的std::mutex配合std::condition_variable也提供了类似功能。Hoare管程和Mesa管程在signal()的语义上有区别：Hoare管程中signal()立即将CPU控制权转移给被唤醒进程，Mesa管程中被唤醒进程需要重新竞争管程的所有权。
三、深入分析与讨论
3.1 经典同步问题详解
生产者-消费者问题（Producer-Consumer Problem）描述了一组生产者进程和一组消费者进程共享有限缓冲区的情景。生产者向缓冲区放入数据，消费者从缓冲区取出数据。需要保证：缓冲区满时生产者等待，缓冲区空时消费者等待，缓冲区的访问互斥。使用三个信号量解决：mutex（互斥锁，初始值1）保护缓冲区访问，empty（空位数，初始值n）控制生产者，full（满位数，初始值0）控制消费者。
读者-写者问题（Readers-Writers Problem）描述了多个读者和写者共享数据的情景。读者只读不写，可以并发执行；写者修改数据，必须独占访问。读者优先方案中，只要有读者在读，新来的读者可以直接进入，写者必须等待所有读者完成。写者优先方案中，一旦写者请求写，新来的读者必须等待，避免写者饥饿。
哲学家进餐问题（Dining Philosophers Problem）由Dijkstra提出，五个哲学家围坐圆桌，每人左右各有一支筷子，思考与进餐交替。进餐需要同时持有两支筷子。最简单的方案是每支筷子一个信号量，哲学家先拿左再拿右，但这会导致死锁（所有人同时拿起左筷子）。解决方案包括：限制最多四个哲学家同时拿筷子、奇数哲学家先左后右偶数先右后左、使用管程确保拿筷子是原子操作。
3.2 内存模型与同步的关系
现代处理器的内存模型影响同步的正确性。强内存模型（如x86的TSO）保证写入对其他核心的可见顺序与程序顺序一致，同步相对简单。弱内存模型（如ARM、RISC-V）允许处理器和编译器重排内存操作以提高性能，可能导致在x86上正确的同步代码在ARM上出错。
内存屏障（Memory Barrier/Fence）指令强制处理器按照指定顺序执行内存操作。获取-释放语义（Acquire-Release Semantics）是C++和Java内存模型的核心：获取操作（如加锁）之前的读写不会被重排到获取之后，释放操作（如解锁）之后的读写不会被重排到释放之前。理解内存模型对于编写跨平台的正确并发程序至关重要。
四、实践案例
4.1 Linux内核中的同步机制
Linux内核提供了丰富的同步原语。自旋锁（spinlock）用于短时间持锁，持有者忙等待。互斥锁（mutex）用于长时间持锁，等待者睡眠。读写锁（rwlock）允许多个读者并发但写者独占。RCU（Read-Copy-Update）是一种无读锁的同步机制，读者不需要获取任何锁，写者复制数据并等待所有读者离开旧数据后释放。RCU适用于读多写少的场景，在Linux内核的路由表、进程列表等数据结构中广泛使用。
原子操作（atomic_t）提供对整数的原子读写和算术操作，底层使用硬件原子指令。位操作（如set_bit、clear_bit）提供对单个位的原子操作，用于标志位管理。per-cpu变量为每个CPU核心提供独立副本，无需同步即可访问，适用于统计计数器等场景。
4.2 Java并发包的设计哲学
Java的java.util.concurrent包提供了比synchronized更灵活的同步工具。ReentrantLock支持可中断等待、超时等待和公平锁。ReadWriteLock区分读写锁，提高读多写少场景的性能。StampedLock（Java 8）引入了乐观读模式，读者不获取锁而是检查版本号，如果没有写者修改则成功。ConcurrentHashMap使用分段锁（Java 7）或CAS操作（Java 8+）实现高并发。CountDownLatch和CyclicBarrier提供进程级别的同步点。CompletableFuture支持异步编程和函数式组合。
五、常见误区与注意事项
信号量的初始值很重要：互斥信号量初始值为1，计数信号量初始值为可用资源数量，同步信号量初始值为0。错误的初始值会导致同步失败。
wait和signal的顺序不能随意交换：在生产者-消费者问题中，必须先wait(empty/full)再wait(mutex)，否则可能导致死锁。两个进程都持有mutex等待对方释放empty/full信号量。
管程中的signal()不等于信号量的signal()：管程的signal()是通知等待者，如果没有等待者则不产生效果。信号量的signal()总是增加计数值，即使没有进程在等待。
无锁不等于没有同步：无锁数据结构使用原子指令（如CAS）代替锁，但仍然需要同步机制来保证正确性。无锁编程极其复杂，除非有充分理由，否则应优先使用锁。
volatile不等于线程安全：volatile保证可见性（一个线程的修改对其他线程立即可见），但不保证原子性。i++操作即使是volatile的也不是线程安全的。
六、本章小结
本章全面讲解了进程同步的核心概念和机制。竞态条件是并发编程的根本挑战，临界区问题要求互斥、前进和有限等待三个条件同时满足。硬件原子指令为同步提供了基础支持。信号量作为经典的同步原语，可以解决互斥和同步问题，但使用不当可能导致死锁。管程提供了更高层次的抽象，自动处理互斥并减少出错可能。经典同步问题展示了实际应用中的常见挑战，其解决方案为并发编程提供了重要的参考模式。现代编程语言和框架提供了丰富的同步工具，但底层原理仍然相同。
七、思考题与练习
给出一个竞态条件的具体例子，说明其产生的原因和可能的后果。
用Peterson算法实现两个进程的互斥访问，验证其满足三个条件。
使用信号量解决生产者-消费者问题，分析wait和signal顺序的重要性。
解释哲学家进餐问题中死锁的产生条件，给出至少两种避免死锁的方案。
比较管程和信号量的优缺点，说明为什么管程更安全。
分析读者-写者问题中读者优先和写者优先的实现差异。
讨论自旋锁和阻塞锁的适用场景，分析各自的性能特征。
研究RCU（Read-Copy-Update）的原理，分析它为什么适合读多写少的场景。