Foundations of Concurrency and Parallelism

并发与并行基础

在现代计算系统的设计与实现中，并发与并行已经成为两个不可或缺的核心概念。从多核处理器到分布式微服务架构，从实时数据流处理到大规模Web请求响应，我们几乎找不到任何一个不涉及并发机制的复杂软件系统。然而，正是这种广泛的应用使得正确理解并发与并行的本质变得尤为重要——不是因为它们难以理解，而是因为对它们的误解往往会导致系统设计中难以发现且代价高昂的错误。

理解并发与并行的本质

并发的定义与特征

Concurrency, as first formally studied byEdsger Dijkstra in his 1965 paper on cooperating sequential processes, refers to the ability of a system to handle multiple tasks by interleaving their execution over time. The key insight here is that concurrency does not necessarily imply that multiple tasks are executing simultaneously; rather, it describes a design property of a system where multiple tasks can make progress by overlapping their execution periods. This distinction is fundamental because it captures the essence of what makes concurrent systems different from purely sequential ones.

并发性是一种系统属性，描述的是系统管理多个任务、使其能够交错执行从而取得进展的能力。这种能力在单核处理器时代就已经存在——操作系统通过快速切换CPU使用权，使得用户可以一边听音乐一边编辑文档，尽管CPU在任意时刻只能执行一条指令。进程的切换创造了时间上的重叠，使得多个任务看似同时进行。从软件设计的角度来看，并发性关注的是如何组织代码结构以处理多个同时进行的工作流，而非硬件是否真正支持同时执行。

理解并发性的一个关键是从组合性（composability）的角度出发。并发系统的一个重要特征是其组件应该能够被安全地组合使用，而不会因为组合而产生新的问题。Leslie Lamport在1990年代的研究中深刻指出：“并发不是关于时间的——它是关于对象之间的独立性。”这意味着当我们讨论并发时，我们实际上是在讨论系统中哪些部分可以相对独立地运行，而不必关心它们在时间维度上的精确对齐。

并发性的另一个核心概念是不确定性（nondeterminism）。并发程序的执行结果通常依赖于运行时的事件顺序，而这个顺序可能因多种因素而不同——包括操作系统的调度决策、硬件中断的时机、网络延迟的变化等。这种内在的不确定性使得并发程序的测试和调试变得尤为困难，也正是为什么我们需要各种并发控制机制来管理这种不确定性。

并行的定义与特征

Parallelism, in contrast to concurrency, specifically refers to the simultaneous execution of multiple computations. This fundamentally requires hardware support—either multiple processing units within a single chip (as in multi-core processors), multiple chips in a single machine, or multiple machines in a distributed system. The primary motivation for parallelism is performance: when we execute tasks in parallel, we aim to reduce the total time required to complete a set of work by leveraging the hardware's ability to perform multiple operations at the same physical moment.

并行性是一种执行属性，它关注的是同时执行这一物理事实。在现代计算机架构中，多核处理器是最常见的并行执行平台。一个8核处理器理论上可以在同一个时钟周期内执行8条指令的不同部分，前提是这些指令之间没有依赖关系。GPU（图形处理单元）则代表了另一种并行架构，其设计初衷是同时处理数千个简单的并行任务，这使得它在图形渲染、深度学习、科学计算等领域表现出色。

并行性与性能的关系可以用一个简单的比喻来理解：如果你需要挖一条沟渠，一个人挖需要10小时，那么两个人同时挖理论上只需要5小时——但前提是这条沟渠足够宽，能容纳两个人同时工作，且工作之间不会相互干扰。在计算世界中，这个比喻对应着任务划分（task decomposition）和数据划分（data decomposition）两种主要的并行化策略。任务划分将工作分成多个独立的子任务并行执行，而数据划分则将数据分成多个块并行处理。

并发与并行的关系

The relationship between concurrency and parallelism is often misunderstood, leading to conflating these two distinct concepts. E.J.H. Chalin captured this distinction elegantly: “Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once.” This aphorism highlights that concurrency is primarily a structural and organizational concept, while parallelism is an execution concept.

并发与并行之间的关系可以总结为：并行性是并发性的一种实现方式，但并发性并不需要并行性。这是一个微妙但重要的区分。在单核处理器上，我们可以通过时间片轮转实现并发控制——操作系统快速切换执行的任务，创造出多个任务同时进行的假象。这种并发不涉及真正的并行执行，但仍然是有价值的，因为它允许系统在等待I/O操作完成时处理其他工作，提高了整体的吞吐量和响应性。

然而，在多核处理器上，我们可以同时拥有并发性和并行性。想象一个Web服务器同时处理多个客户端请求：从结构上看，这些请求的处理逻辑是并发的（多个请求同时存在）；从执行上看，如果系统有多个CPU核心，操作系统可以将这些请求分配到不同的核心上同时处理，实现真正的并行执行。这种双重属性使得现代多核系统能够同时获得并发带来的结构优势和并行带来的性能提升。

Go语言的创造者Rob Pike有一句经典表述：“并发是关于结构的，并行是关于执行的。”这句话精炼地概括了两者的核心区别。当你设计一个处理并发请求的系统时，你关心的是如何组织代码以优雅地处理多个同时发生的事件；当你优化一个并行算法时，你关心的是如何最大化硬件利用率以减少执行时间。理解这一点对于系统设计至关重要——错误地混淆这两个概念可能导致过度设计或性能瓶颈。

共享状态系统的根本挑战

共享状态的本质

Shared state lies at the heart of most concurrent and parallel systems, and understanding its challenges is essential for building correct high-performance software. When multiple execution contexts—threads, processes, or coroutines—access and modify the same data, we enter the realm of shared-state concurrency, which introduces a class of subtle and often difficult-to-reproduce bugs.

共享状态指的是多个执行单元可以访问的同一份数据。在单线程程序中，所有的数据访问都是顺序的，没有任何歧义——当你读取一个变量时，你得到的就是上一次写入的值。然而，当多个线程共享同一份数据时，情况变得复杂起来。考虑一个简单的计数器场景：两个线程同时读取当前值为0，然后各自加1，最后各自写回结果。由于执行顺序的不同，最终的计数值可能是1或2，而不是预期的3。这种看似简单的情况却揭示了共享状态系统中最根本的挑战。

共享状态问题的根源在于操作的原子性（atomicity）假设被打破。在单线程环境中，一个表达式如`counter = counter + 1`看起来是一个不可分割的操作。但在多线程环境中，CPU执行这条语句实际上涉及多个微操作：读取counter的值到寄存器、将寄存器值加1、将结果写回counter。这三个步骤在执行过程中可能被其他线程插入，导致数据竞争和状态不一致。

现代硬件和编程语言进一步增加了共享状态问题的复杂性。现代CPU采用乱序执行（out-of-order execution）技术来提高指令级并行度，这意味着指令的执行顺序可能与程序员编写的代码顺序不同。编译器优化也可能重排代码以提高性能。缓存系统引入的内存可见性问题使得一个线程对数据的修改可能对另一个线程不可见，直到缓存一致性协议将修改传播到所有CPU核心。这些硬件特性虽然提高了单线程性能，却给并发编程带来了额外的负担。

数据竞争与竞态条件

A data race occurs when two or more threads access the same memory location concurrently, at least one of the accesses is a write, and the threads are not using any exclusive access mechanism to coordinate. Under the C++ memory model and the Java Memory Model, data races have well-defined semantics: they result in undefined behavior in C++, and in Java they introduce happens-before guarantees that can lead to inconsistent reads and corrupted data structures.

数据竞争（Data Race）是共享状态系统中最常见的并发问题之一。它发生在两个或多个线程并发访问同一内存位置，且至少有一个访问是写入操作，而线程之间没有使用任何同步机制来协调访问的情况。数据竞争之所以危险，是因为它的行为是未定义的——程序可能运行数千次都没有问题，然后在一次特定的操作顺序下崩溃或产生错误的结果，这使得调试变得极为困难。

与数据竞争密切相关的是竞态条件（Race Condition）。竞态条件描述的是程序的正确性依赖于线程执行顺序的情况。数据竞争是竞态条件的一种形式，但竞态条件可以更加微妙。考虑一个银行转账系统：账户A向账户B转账100元，同时账户B向账户A转账50元。如果这两个操作交错执行，可能导致两个账户的总余额不变，但中间状态却可能出现问题。虽然每个单独的转账操作都是原子的，但组合操作之间存在竞态条件。

一个经典的竞态条件例子是检查后执行（Check-Then-Act）模式。考虑以下代码：

```python

不安全的双重检查锁定实现

class Singleton: _instance = None

@classmethod def get_instance(cls): if cls._instance is None: # 第一次检查 cls._instance = cls() # 可能被多个线程同时执行 return cls._instance ```

这段代码的问题在于多个线程可能同时通过第一次检查，然后各自创建实例，破坏了单例模式的语义。正确的实现需要在外层加锁，或者使用其他机制确保实例只被创建一次。竞态条件往往隐藏在看似正确的代码逻辑中，只有在特定的事件序列发生时才会暴露问题。

缓存一致性与内存可见性

Modern multi-core processors use cache hierarchies to improve performance, but these caches introduce subtle semantics regarding when writes by one core become visible to other cores. The CPU cache coherence protocols, such as MESI (Modified, Exclusive, Shared, Invalid) and its variants, ensure that eventually all cores observe consistent values, but the timing of this consistency is not guaranteed by default.

缓存一致性（Cache Coherence）是现代多核处理器面临的核心挑战之一。在典型的多核CPU中，每个核心拥有自己的L1和L2缓存，共享L3缓存。考虑这样一个场景：核心0读取内存位置X的值并将其缓存在自己的L1缓存中，同时核心1也读取同一位置并缓存。然后核心0修改了X的值，这个修改可能只写入核心0的L1缓存，而不是立即写回主内存。此时，核心1的缓存中仍然持有X的旧值，导致两个核心看到的数据不一致。

缓存一致性协议（如MESI协议）通过在缓存行级别跟踪数据状态来解决这个问题。协议定义了四种状态：Modified（M）表示数据被当前核心修改且未同步到其他核心；Exclusive（E）表示当前核心独占数据且与主内存一致；Shared（S）表示数据可能被多个核心共享且与主内存一致；Invalid（I）表示缓存行无效。MESI协议通过核心间的总线嗅探确保在任何时刻只有一个核心能持有修改状态，从而维护数据一致性。

然而，缓存一致性并不意味着程序员不需要关心内存可见性问题。在没有适当同步的情况下，一个线程对共享变量的修改可能不会立即对其他线程可见。这是因为处理器可能将写入操作暂存在store buffer中，等待合适的时机才写入缓存。更复杂的是，编译器优化和CPU指令重排可能进一步改变操作的执行顺序。这些优化对于单线程程序是正确的，因为它们保持了程序的串行语义；但对于多线程程序，它们可能破坏程序逻辑。

```c // 内存可见性问题示例 // 线程1 void producer() { ready = true; // 可能先执行 data = 42; // 可能后执行 }

// 线程2 void consumer() { if (ready) { // 可能看到ready为true printf("%d", data); // 但data可能还是旧值0 } } ```

这个例子展示了内存可见性问题。编译器或CPU可能重排线程1中的两条语句的执行顺序，导致消费者看到ready为true时，data还没有被赋值。这种问题不能通过简单地声明变量来解决，而需要使用适当的内存屏障（memory barrier）或同步原语来确保操作顺序。

Amdahl定律与Little定律

Amdahl定律：并行化的理论极限

Gene Amdahl在1967年提出的定律为并行计算的性能极限提供了精确的数学描述。这一定律的核心洞察是：程序中无法并行化的部分将成为性能瓶颈，无论我们拥有多少个处理器核心。Amdahl定律的形式化表述为：

$$S(n) = \frac{1}{(1-P) + \frac{P}{n}}$$

其中$S(n)$是使用$n$个处理器核心时获得的加速比，$P$是程序中可并行化部分所占的比例。$(1-P)$表示程序中必须串行执行的部分。

考虑一个具体例子：假设一个程序中75%的计算可以并行化，25%必须串行执行。在单核上执行需要100秒。使用8个核心并行化后，执行时间变为：

$$T(n) = T_{serial} \times \left( (1-P) + \frac{P}{n} \right) = 100 \times \left( 0.25 + \frac{0.75}{8} \right) = 34.375 \text{秒}$$

加速比仅为$100 / 34.375 \approx 2.91$，远小于理想的8倍加速。随着核心数增加到无穷大，加速比趋近于$1 / (1-P)$。对于P=0.75的示例，最大加速比约为4倍。这意味着即使拥有无限多的处理器核心，由于存在25%的串行部分，程序最多只能快4倍。

Amdahl定律揭示的结论对系统设计有深远影响。首先，它强调了优化串行部分的重要性——即使串行部分只占10%，它也会将最大加速比限制在10倍以内。其次，它表明在某个点上，增加更多的处理器核心带来的收益会急剧减少。对于P=0.9的程序，使用10个核心可达到9.17倍加速，但使用100个核心只能达到9.91倍加速，最后10%的潜在加速需要增加90个核心。

Amdahl定律的另一个重要含义是关于强扩展（strong scaling）与弱扩展（weak scaling）的区别。强扩展指的是在固定问题规模下，增加核心数能带来多大的加速；弱扩展指的是在问题规模随核心数增加而增加的情况下，效率如