第一章 并发编程基础 (Foundations of Concurrent Programming)
一、导读
1.1 本章学习目标
理解并发编程的基本概念，区分并发（Concurrency）与并行（Parallelism）
掌握进程（Process）与线程（Thread）的区别与联系
理解线程的生命周期及其状态转换
掌握共享内存模型下的并发编程基本模型
学会分析并发程序中的竞态条件（Race Condition）和数据竞争（Data Race）
理解并发程序的正确性标准：安全属性（Safety）与活性属性（Liveness）
了解并发编程的历史发展与多处理器体系结构的演进
1.2 为什么本章如此重要
并发编程是现代软件开发的必备技能。随着多核处理器的普及，几乎所有的现代系统——从移动设备到数据中心服务器——都在使用多核架构。编写能够正确、高效利用多核的计算程序，已经成为每个程序员必须掌握的能力。
然而，并发编程也是最具挑战性的编程领域之一。并发程序的行为是非确定性的：相同的输入在不同的执行顺序下可能产生不同的输出。这种非确定性使得并发程序的调试和验证极其困难。一个在测试中运行了 1000 次都正确的并发程序，可能在第 1001 次运行时因为微妙的时序问题而产生错误的结果。
Herlihy 和 Shavit 在本书开篇就建立了并发编程的理论基础。他们从进程和线程的基本概念出发，逐步引入共享内存模型、并发程序的正确性标准等核心概念。这些概念不仅是理解后续章节的基础，也是与并发程序"对话"的语言——没有这些概念，就无法精确地描述和讨论并发程序的行为。
本章还传达了一个重要的观点：并发编程的困难不是偶然的，而是本质的。并发程序需要处理的问题——竞态条件、死锁、活锁——是共享状态和并行执行的自然后果。理解这些问题的根源，比简单地学习避免它们的技术更加重要。
1.3 核心问题引导
并发和并行有什么本质区别？一个程序可以并发但不并行吗？
为什么线程比进程更"轻量"？它们在资源共享方面有什么不同？
什么是竞态条件？它为什么如此难以检测和复现？
并发程序的正确性如何定义和验证？"正确"在并发语境下意味着什么？
什么是安全属性和活性属性？它们分别对应什么样的错误？
多处理器体系结构的演进如何影响了并发编程模型？
二、核心概念详解
2.1 进程与线程
进程（Process）是操作系统进行资源分配和调度的基本单位。每个进程拥有独立的地址空间、文件描述符、信号处理等系统资源。进程之间的内存空间是隔离的，一个进程不能直接访问另一个进程的内存。进程间通信（IPC）需要通过操作系统提供的机制（如管道、消息队列、共享内存、信号量等）来实现。
线程（Thread）是进程内的执行单元，是 CPU 调度的基本单位。同一个进程内的多个线程共享该进程的地址空间和资源（如打开的文件、内存映射等），但每个线程有自己的栈空间和寄存器状态。线程之间的通信可以通过直接读写共享内存来实现，这使得线程间通信比进程间通信更高效，但也更容易出错。
线程的"轻量"体现在：创建和销毁线程的开销远小于进程（不需要复制地址空间）；线程间切换的开销小于进程间切换（不需要切换地址空间，缓存更友好）；线程间通信不需要内核介入（直接读写共享内存）。
2.2 并发模型
并发编程有多种模型，本书聚焦于共享内存模型（Shared Memory Model）。在这个模型中，多个线程通过读写共享的内存位置来进行通信和协调。
共享内存模型的核心抽象是：存在一组线程，每个线程执行一个顺序的程序；这些线程可以访问一组共享的寄存器（或内存位置）；线程通过读写这些共享寄存器来进行通信。
共享内存模型的优势在于编程模型简单直观：线程可以直接通过读写变量来交换信息。但其挑战在于：多个线程同时读写同一个位置时，结果取决于具体的执行顺序（时序依赖性），这使得程序的行为难以预测和验证。
另一种并发模型是消息传递模型（Message Passing Model），线程之间不共享内存，而是通过发送和接收消息来通信。这种模型避免了共享内存的许多问题（如数据竞争），但引入了新的复杂性（如消息丢失、消息顺序）。MPI（Message Passing Interface）和 Actor 模型是消息传递模型的代表。
2.3 竞态条件与数据竞争
竞态条件（Race Condition）是指程序的正确性依赖于多个线程的执行顺序。当多个线程并发执行时，如果不同的交错顺序（Interleaving）导致不同的结果，且某些结果是不正确的，就存在竞态条件。
数据竞争（Data Race）是竞态条件的一种特殊形式：当两个或多个线程同时访问同一个内存位置，且至少有一个是写操作，且这些访问之间没有适当的同步，就发生了数据竞争。数据竞争在 C/C++ 和 Java 中是未定义行为（Undefined Behavior），可能导致任何不可预测的结果。
一个经典的竞态条件例子是"检查后执行"（Check-then-Act）模式：线程 A 检查某个条件为真，然后执行相应操作；但在 A 检查和执行之间，线程 B 可能修改了条件，导致 A 的操作基于过时的信息。例如，两个线程同时检查银行账户余额是否足够，然后同时执行转账操作，可能导致透支。
消除竞态条件的基本方法是使用同步机制（如锁、原子操作）来确保关键操作的原子性。
2.4 安全属性与活性属性
并发程序的正确性可以用两类属性来描述：安全属性（Safety）和活性属性（Liveness）。
安全属性表示"坏事永远不会发生"：程序不会进入非法状态。典型的安全属性包括：互斥（Mutual Exclusion，两个线程不会同时进入临界区）、不变量保持（Invariant Preservation，共享数据始终满足某些约束）。安全属性的违反意味着程序产生了错误的结果。
活性属性表示"好事最终会发生"：程序最终会取得进展。典型的活性属性包括：无死锁（Freedom from Deadlock，线程最终能获取所需的锁）、无饥饿（Freedom from Starvation，每个试图获取资源的线程最终都能成功）。活性属性的违反意味着程序"卡住"了，虽然没有产生错误的结果，但也没有取得任何进展。
区分安全属性和活性属性有助于系统性地分析并发程序的问题。安全错误通常更容易发现（通过检查结果是否正确），而活性错误更难发现（程序可能只是在某些情况下永远不终止）。
2.5 多处理器体系结构
理解多处理器体系结构的演进对于理解并发编程至关重要。从单核到多核的演进，从根本上改变了性能提升的方式：过去通过提高时钟频率来提升性能，现在通过增加核心数量来提升性能。
共享总线架构（Shared Bus）：所有处理器通过一条共享总线访问内存。简单但扩展性差，因为总线带宽是所有处理器共享的瓶颈。
缓存一致性协议（Cache Coherence Protocol）：每个处理器有自己的缓存，缓存一致性协议确保所有处理器看到的内存值是一致的。常见的协议有 MESI（Modified-Exclusive-Shared-Invalid）和 MOESI。
NUMA 架构（Non-Uniform Memory Access）：每个处理器有自己的本地内存，访问本地内存快，访问远程内存慢。NUMA 架构对并发程序的性能有重要影响：数据的放置位置会影响访问延迟。
内存一致性模型（Memory Consistency Model）定义了多线程程序中内存操作的可见性顺序。顺序一致性（Sequential Consistency）是最直观的模型：所有处理器的操作以某种全局顺序交错执行。但为了实现更高的性能，现代处理器采用了更弱的内存模型（如 x86 的 TSO、ARM 的弱排序），允许某些内存操作的重新排序。
三、深入分析与讨论
3.1 并发编程的本质困难
并发编程的困难不是技术细节的复杂性，而是思维方式的根本转变。在顺序编程中，程序员可以假设代码按照书写顺序执行；但在并发编程中，多个线程的执行顺序是不确定的，程序员必须考虑所有可能的交错。
对于一个有 n 个线程、每个线程有 m 条指令的程序，可能的交错数量为 (nm)! / (m!)^n。即使 n 和 m 都很小，这个数字也大到无法穷举测试。这就是为什么并发程序的 bug 如此难以发现——测试只能覆盖所有可能执行的一小部分。
这种本质困难意味着：并发程序的正确性不能仅靠测试来保证，还需要通过形式化的推理（如不变量、前置/后置条件）来论证。这也是为什么本书在介绍并发编程时，首先建立正确性的形式化定义。
3.2 确定性并行与不确定性并行
确定性并行（Deterministic Parallelism）是指程序的输出不依赖于线程的执行顺序。如果程序是确定性并行的，那么无论线程如何交错，结果都是相同的。这种程序最容易推理和调试。
不确定性并行（Nondeterministic Parallelism）是指程序的输出可能依赖于线程的执行顺序。大多数并发程序都是不确定性的——即使程序没有 bug，不同的执行顺序也可能导致不同的（但都正确的）结果。例如，一个并行搜索算法可能在不同的运行中找到不同的最优解（如果有多个等价的最优解）。
区分确定性和不确定性并行有助于选择合适的验证策略：确定性程序可以通过比较输出来验证；不确定性程序需要更复杂的验证方法（如检查输出是否满足某些属性）。
3.3 并发编程的抽象层次
并发编程可以在不同的抽象层次上进行：硬件层面（指令级并行、流水线）、操作系统层面（进程、线程、同步原语）、语言层面（并发库、并发语言特性）、应用层面（设计模式、架构风格）。
每个抽象层次都有其适用的场景和局限性。底层的抽象（如原子指令）提供了最大的灵活性和性能，但使用复杂且容易出错。高层的抽象（如并发容器、Actor 模型）使用简单，但可能限制性能或表达能力。
本书采用自底向上的方法：从硬件提供的原子操作出发，逐步构建更高层次的同步抽象（锁、信号量、 monitors、并发数据结构）。这种方法帮助读者理解每个抽象层次的实现原理和代价。
四、实践案例
4.1 简单的线程创建与管理
以 Java 为例，展示线程的基本创建和管理。通过 Thread 类和 Runnable 接口创建线程，使用 start() 启动线程，使用 join() 等待线程结束。
一个典型的场景是并行计算：将一个大的计算任务分成若干子任务，每个子任务在一个独立的线程中执行，最后汇总结果。例如，并行计算大数组的元素之和：将数组分成 N 段，每段在一个线程中求和，最后将 N 个部分和相加。
这个案例展示了并发编程的基本模式：分治（Divide and Conquer）+ 并行执行 + 结果合并。同时也引出了需要同步考虑的问题：如何确保所有线程都完成了计算？如何处理线程异常？
4.2 一个简单的竞态条件
展示一个经典的竞态条件案例：多个线程同时对一个共享计数器执行递增操作。count++ 看似是原子操作，但实际上包含三个步骤：读取 count 的值、加 1、写回 count。如果两个线程同时执行这三个步骤，可能导致丢失更新。
通过不同的线程交错来演示这个问题：线程 A 读取 count = 0，线程 B 也读取 count = 0，线程 A 写回 count = 1，线程 B 写回 count = 1。结果是 count = 1 而不是预期的 2。
解决方案包括：使用 synchronized 关键字、使用 AtomicInteger、使用显式锁等。每种方案都有不同的性能特征和适用场景。
五、常见误区与注意事项
5.1 混淆并发与并行
并发是关于程序的结构（多个独立的任务在重叠的时间段内执行），并行是关于程序的执行（多个任务在同一时刻同时执行）。一个并发程序可以在单核上通过时间片轮转来执行（并发但不并行），也可以在多核上同时执行（并发且并行）。
5.2 忽视内存可见性问题
在一个线程中对共享变量的修改，不一定立即对其他线程可见。现代处理器和编译器可能重新排序内存操作，缓存可能导致不同处理器看到不同的值。理解内存模型和使用适当的同步机制（如 volatile、内存屏障）是确保可见性的关键。
5.3 过度使用同步
同步是解决数据竞争的手段，但过度使用同步会严重降低并发程序的性能。每个同步操作都有开销（获取锁、释放锁、内存屏障等），过多的同步可能导致线程频繁阻塞和唤醒，甚至使并发程序比串行程序更慢。
5.4 假设测试能发现所有并发 bug
并发 bug 通常是间歇性的（Heisenbug），只在特定的线程交错下出现。测试只能覆盖所有可能执行的一小部分，因此不能保证发现所有并发 bug。并发程序的正确性需要通过形式化的推理和设计来保证。
六、本章小结
本章建立了并发编程的基础概念框架。进程和线程是并发的基本执行单元，共享内存模型是并发通信的基本方式。竞态条件和数据竞争是并发程序中最常见的错误来源。安全属性和活性属性是描述并发程序正确性的两个维度。多处理器体系结构的演进决定了并发编程的硬件基础。理解这些基础概念是学习高级并发编程技术的前提。并发编程的困难是本质的——多线程程序的执行顺序不确定，使得程序的行为难以预测和验证。
七、思考题与练习
编写一个多线程程序，演示竞态条件导致的错误结果。分析不同的线程交错如何导致不同的错误。
比较进程和线程在创建时间、内存占用、通信开销等方面的差异。用实验数据支持你的分析。
解释以下场景分别属于安全属性违反还是活性属性违反：（a）两个线程同时修改同一个账户导致余额错误；（b）一个线程永远等待一个永远不会被释放的锁。
在一个 4 核处理器上，一个程序有 4 个线程，每个线程执行 3 条指令。计算可能的交错总数。
解释为什么 count++ 不是原子操作。在 x86 架构上，如何使其成为原子操作？
分析以下场景中的安全属性和活性属性：一个生产者-消费者队列，生产者向队列添加元素，消费者从队列取出元素。
研究 MESI 缓存一致性协议的工作原理。解释它如何保证多处理器环境下的缓存一致性。
讨论：为什么现代处理器采用比顺序一致性更弱的内存模型？这种权衡的利弊是什么？