玻尔百科在我们的日常生活和经典计算中，我们习惯于顺序思考——一个步骤接着另一个步骤，形成一条清晰、可预测的线。然而，从多核处理器到繁忙的医院工作流程，现代世界是并行运作的，无数事件同时发生。这种固有的并行性带来了一个重大挑战：我们的顺序直觉不足以设计、管理和推理这些复杂的交互系统。本文旨在通过引导读者了解并发建模的基本概念来弥补这一差距。
第一部分原理与机制，为我们奠定了理论基础。我们将打破单一时间线的幻象，引入如先行发生关系和迹理论等基本思想，以形式化地描述并行执行。接着，我们将探讨佩特里网和状态图等强大的建模工具，它们为设计和分析并发控制流提供了可视化蓝图，并了解抽象概念如何解决像死锁这样的实际问题。
在此基础上，第二部分应用与跨学科联系，展示了这些模型的非凡通用性。我们将穿梭于操作系统和软件的数字世界、分子和气候模拟的物理世界，以及临床工作流程和疾病传播的人类世界。在这些不同领域中，您将发现并发的语言如何为理解和掌握我们所居住的这个复杂的、同步发生的世界提供一个统一的框架。
我们对于事情如何完成的直觉是深度的顺序性的。我们想到的是一份食谱、一张清单、一个有开头、中间和结尾的故事。每一步都紧随上一步，形成一条清晰、可预测的线。这就是经典计算的世界，图灵机优雅地捕捉了这一点：一个勤奋的工人在一条长长的数据带上一次执行一条指令。几十年来，这个模型一直是计算机科学的基石，定义了可计算性的绝对极限。
但我们周围的世界并非单一线程。它是一个熙熙攘攘、混乱的厨房，有许多厨师同时工作。一个在切菜，另一个在烧水；第三个在取香料。他们互相发送消息——“洋葱准备好了！”——有时甚至当场雇佣新的助手。这就是并发的世界。
一个自然而深刻的问题随之而来：这种并行的、交互式的计算方式是否赋予我们新的能力？一群协作的自动机能否解决单个图灵机无法解决的问题？答案，再次强化了原始理论的巨大力量，是否定的。由一群并发进程执行的任何计算，无论它们的交互多么复杂，都可以由一个单一的、有条不紊的图灵机来模拟，它会在其一条长带上细致地记录每一个进程、每一条消息和每一次状态变化。这会极其缓慢，就像一个人试图跑遍各个工位来经营整个餐厅厨房一样，但原则上，它能做到。
因此，并发并没有打破丘奇-图灵论题所阐述的可计算性基本定律。但它的真正魔力在于，它迫使我们发明全新的语言和全新的思维方式，来描述、管理和推理一个事情并非接连发生的世界。其美妙之处不在于改变什么可以被计算，而在于我们为理解并行展开的计算所构建的模型的优雅。
在顺序世界中，时间是一条简单的线。对于任意两个事件A和B，要么A在B之前发生，要么B在A之前发生。但这对于我们厨房里的厨师们来说并非如此。切胡萝卜是在水开始沸腾之前还是之后发生的？如果它们是由不同的厨师同时完成的，这个问题就没有答案。它们仅仅是……并发的。
为了捕捉这一现实，我们必须抛弃单一、普适时间线的概念。取而代之的是，我们用因果关系来思考。Leslie Lamport在先行发生关系中将这一见解形式化，表示为，它通过三个简单的规则构建了一个因果结构：
局部顺序：如果事件和发生在同一个进程中（我们单个厨师的动作序列），并且在前，那么。（你必须先打碎鸡蛋才能炒鸡蛋）。
消息传递：如果事件是发送一条消息，事件是接收同一条消息，那么。（你不能在邮件发送之前阅读它）。
传递性：如果并且，那么。（如果准备食材使得烹饪菜肴成为可能，而烹饪菜肴又使得上菜成为可能，那么准备食材就使得上菜成为可能）。
由此产生的不是一条线，而是一个偏序。它是一块由事件构成的织物，其中一些因果线索是固定的——你必须先倒入咖啡粉才能冲泡咖啡——但其他的则不是。烤面包和冲咖啡可以同时发生，它们的时间线在时间的织物中并行运行，彼此之间没有联系。如果和都不成立，那么两个事件和就是并发的。这是任何并发系统的基本结构。
如果一个并发过程是一个偏序，我们如何将其写下来？我们的语言是建立在词语序列之上的。系统中所有事件的一个单一线性序列被称为交错。它是对并发现实的一种可能的“观察”，就像一个记者逐秒记录厨房的活动。但如果烤面包和冲咖啡是真正独立的，那么一份报告说“开始烤面包，然后开始冲咖啡，然后烤面包结束”和另一份说“开始冲咖啡，然后开始烤面包，然后烤面包结束”的报告，两者描述的是完全相同的底层现实。
这就是迹理论提供优美抽象的地方。我们首先声明一个独立关系，它形式化地说明哪些动作对就像“烤面包”和“冲咖啡”——它们的顺序无关紧要。例如，我们可以声明(toast, brew)是一个独立对。这个关系为我们重写顺序故事提供了一个规则：任何相邻的独立动作对都可以交换位置。
因此，序列(start_toast, start_brew, eat)被认为等同于(start_brew, start_toast, eat)。所有可以通过这些交换相互转换的顺序故事形成一个等价类，这被称为迹。迹本身——这个等价故事的集合——是代表单个并发执行的真正数学对象。它捕捉了底层的偏序，将我们从单一、任意时间线的束缚中解放出来。
为了推理这些复杂的交互，我们需要蓝图。我们需要能够直接绘制因果关系织物的可视化语言。其中最优雅、最强大的工具之一是佩特里网。
想象一个由两种节点组成的简单二分图：称为库所的圆圈（代表条件或状态，如“患者已识别”）和称为变迁的方框（代表事件或动作，如“检查过敏史”）。箭头连接库所到变迁，以及变迁到库所。系统的状态由令牌——驻留在库所中的标记——来显示。当一个变迁的所有输入库所都至少有一个令牌时，它就“可触发”。当它“触发”时，它会从每个输入库所消耗一个令牌，并在其每个输出库所中产生一个令牌。
这个简单的机制表现力惊人。它为并发的基本控制流模式提供了一种自然的语言：
佩特里网为我们提供了分布式系统中控制和资源流动的直接、图形化蓝图，从在医院中为安全的用药工作流程建模，到协调业务流程中的任务。
另一个强大的形式化方法是状态图，它扩展了我们熟悉的有限状态机。一个简单的状态机一次只能处于一个状态，而状态图可以包含正交区域——本质上是在同一组件内并行运行的多个独立状态机。这使得一个系统可以有一个复合状态，例如处于状态(A, X)，其中A是一个子机器的状态，X是另一个子机器的状态。状态图还引入了历史伪状态等概念，它允许一个组件记住它上次被中断时所处的子状态——这是一种在如流程图等更简单的形式化方法中难以建模的记忆形式。
并发是一把双刃剑。当独立的进程必须竞争共享的、有限的资源时，它们可能会陷入一种被称为死锁的致命拥抱。经典的故事涉及餐桌旁的哲学家，他们需要两把叉子才能吃饭，但每对哲学家之间只有一把叉子。每个哲学家都拿起左边的叉子，然后无限期地等待右边的叉子，而右边的叉子正被他的邻居拿着。所有人都饿死了。
这个悲剧性场景在图论中有一个极其简单的表示。我们可以用一个锁序图来为这种情况建模，其中顶点是资源（叉子，或软件系统中的锁），从锁到锁的有向边表示一个进程在已经持有的情况下会请求。
死锁是一种循环等待。你左边的哲学家在等你，你在等右边的哲学家，以此类推，直到这个链条形成一个环。这不过是锁序图中的一个环。在一个复杂的并发程序中检测潜在死锁的抽象问题，简化为在图中寻找有向环这个众所周知的问题。一个简单的深度优先搜索（DFS）可以遍历该图，如果它发现一条“反向边”——一条指向其当前探索路径中已存在顶点的边——它就找到了一个环，因此，也找到了一个潜在的死锁。
我们已经看到，并发建模不是单一的技术，而是一个丰富的思想工具箱。没有一个“最佳”模型；选择合适的形式化方法就像为相机选择合适的镜头——它取决于你想看到什么。“组织的数字孪生”这一现代概念完美地突出了这一点。要为一个复杂的工作流程建立一个全面的模型，你可能需要同时使用几个镜头：
形式正确性的镜头：如果你主要关心的是安全性和可靠性——系统会死锁吗？订单有可能丢失吗？——你需要一种数学上精确的语言。佩特里网在这里是完美的选择，因为它们的形式语义允许对活性（系统不会卡住）和有界性（资源不会无限累积）等属性进行严格的分析和证明。
定量性能的镜头：如果你的问题是关于效率——客户需要等待多长时间？我们的最大吞吐量是多少？——你需要一个统计模型。排队网络将任务的到达和服务建模为随机过程，是理想的工具。它们牺牲了佩特里网的细粒度逻辑细节，以为系统在负载下的性能提供强大的预测。
执行的镜头：如果你只是想构建并运行系统，你需要一种实用的、可执行的表示法。像业务流程模型和标记法（BPMN）这样的标准就是为此设计的。它们提供了一种清晰的可视化语言，可以被工作流引擎直接解释，以协调现实世界中的自动化任务和人工任务。
并发建模的真正力量在于理解如何协同使用这些不同的镜头。你可以用BPMN设计一个流程，将其转换为佩特里网以证明其无死锁，然后将其建模为排队网络以确保它能满足性能目标。这种形式化方法的协同作用使我们能够构建不仅是并发的，而且是正确、高效和健壮的系统。
现在我们已经探索了并发的基本原理，我们可以开始一段旅程，去看看这些思想在哪些领域真正焕发生机。伟大科学原理的一个显著特点是，它们并不局限于其起源领域。就像一粒顽强的种子在意想不到的地方找到了肥沃的土壤，并发的概念——偏序、资源冲突和同步——已经在广阔的人类探究领域中开花结果。从计算机处理器最深处的 recesses 到全球气候的复杂舞蹈，再到人类社会的复杂编排，“事物同时发生”的挑战是普遍存在的。在本节中，我们将看到我们开发的抽象工具如何为那些乍一看似乎相去甚远的领域中的问题提供深刻的见解和实用的解决方案。
并发最自然的家园，当然是计算机科学。现代计算机本质上是并行机器，拥有多个核心、线程和进程，都在争夺内存、磁盘和网络连接等共享资源。如果没有一种形式化的方法来管理这种混乱，我们的数字世界将在混乱的僵局中停滞不前。
这个挑战的一个经典例证是著名的哲学家就餐问题，这是一个关于资源分配的寓言。想象一群哲学家围坐在一张圆桌旁，每人面前都有一盘食物。每对哲学家之间都放着一把叉子。为了吃饭，一个哲学家需要两把叉子——左边的和右边的。那么，一个简单而礼貌的获取叉子的规则是什么呢？如果每个哲学家都决定先拿起左边的叉子，然后等待右边的叉子，我们就会陷入灾难性的死锁。每个哲学家都拿着一把叉子等待另一把，而那把叉子又被他的邻居拿着，邻居又在等待他的邻居，如此循环往复。每个人都在等待，没人能吃饭。这个看似简单的谜题捕捉了操作系统中死锁的本质，即进程持有一个资源，同时无限期地等待另一个资源。
解决方案不在于更复杂的礼仪规则，而在于打破死锁的一个基本条件。一个真正健壮的系统，比如由一个中央“监视器”管理的系统，会强制执行一种“全有或全无”的协议。一个哲学家只有在两把叉子都可用时才能拿起它们。如果不是，他们就在不持有任何叉子的情况下等待。这个简单而强大的策略打破了“持有并等待”的条件，保证了死锁不可能发生。这个原则被构建在现代操作系统的核心之中，确保相互竞争的程序可以共享机器资源而不会使整个系统陷入停顿。
这些思想深深地延伸到软件本身的结构中。在高性能并发编程的世界里，开发者努力创造“无锁”算法，这些算法完全避免了传统的锁机制，而是使用底层的原子硬件指令。考虑实现“惰性求值”的挑战，即一个计算（一个“thunk”）的结果只有在第一次需要时才被计算。如果多个线程同时尝试访问这个结果，你如何确保计算只运行一次？一个极其优雅的解决方案涉及一个状态机和一个原子的“比较并交换”（CAS）操作。第一个到达的线程使用CAS原子地将thunk的状态从“未求值”变为“求值中”，从而赢得了执行计算的权利。任何其他到达的线程会发现状态已经是“求值中”，便只需等待胜利者公布最终结果。这个模式，一个在几纳秒内举行的小型数字选举，是构建快速且可扩展软件的基础。
搞错这些的后果不仅仅是学术性的。在驱动从金融交易到社交媒体等一切的复杂、消息驱动的系统中，并发逻辑中的一个bug就可能产生级联效应。想象一个“actor”——一个独立的计算代理——收到了一个告诉它关闭的“毒丸”消息。如果由于一个bug，它未能正确终止，它就可能变成一个“僵尸进程”，虽然还活着并且系统可以访问到它，但不再正常工作。它可能继续接受工作并分配内存，但从不释放，导致持续的内存泄漏，最终可能使整个应用程序崩溃。设计健壮的关闭协议，例如“排空并停止”程序，即actor首先停止接受新工作，然后优雅地清理其待处理任务，这是并发建模在确保软件系统长期稳定性方面的一个关键应用。
宇宙本身就是一个大规模并发的系统。为了理解它，科学家们在世界上最大的超级计算机上构建庞大的模拟。在这些数字世界中，并发的原则不仅仅是工程效率的问题，而是物理定律的直接反映。
考虑分子动力学模拟的巨大挑战，它通过计算每个原子之间的力来模拟材料的行为。在并行计算机上，数百万个原子分布在数千个处理器上。一个关键步骤是计算附近原子间的相互作用力。如果两个原子A和B相互作用，作用在A上的力等于作用在B上的力的反向力（牛顿第三定律）。在计算这个力时，处理器必须更新两个原子的数据。如果两个不同的计算试图同时更新同一个原子的数据，就会发生竞争条件。例如，当一个处理器正在计算A-B相互作用时，另一个可能正在计算A-C相互作用。两者都需要写入原子A的力累加器。
如何在不使用缓慢、笨重的锁的情况下防止这种冲突？解决方案是来自图论世界的一个天才之举。想象一下，模拟空间被划分为一个三维的单元格网格。并发写入的问题可以映射到一个图上的边着色问题，其中单元格是顶点，边连接相互作用的邻居。所有对应于相同“颜色”的边的相互作用都可以并行计算而没有冲突。对于一个标准的3D网格，其中每个单元格与其26个最近的邻居相互作用，事实证明，你需要至少27种颜色——也就是27个并行阶段——才能在没有任何竞争条件的情况下完成所有计算。这个令人惊讶而美丽的联系使得科学家能够以一种保证正确的方式利用巨大的计算能力。
选择正确分解方式的主题是科学计算的核心。例如，在等离子体物理中，模拟聚变反应堆内部的热、带电气体涉及到跟踪粒子及其产生的电磁场。有两种主要的并行化策略。在区域分解中，每个处理器负责一个固定的空间区域和当前在该区域内的粒子。这很直观，但意味着随着粒子在区域间迁移，处理器必须不断通信。在粒子分解中，每个处理器拥有一个固定的粒子集合，无论它们漫游到哪里。这消除了粒子迁移，但需要大规模的、全对全的通信，因为粒子需要将其电荷“沉积”到一个分布式的场网格上。没有哪种策略是普遍优越的；选择取决于问题的具体物理特性，这个决策由模拟中信息流和依赖关系的建模来指导。
为了衡量这些大规模并行任务的成功，科学家们使用两个关键基准。强扩展问：对于一个固定的问题规模，通过增加更多处理器，我们能快多少？这最终受到阿姆达尔定律的限制——程序中固有的串行部分将永远是一个瓶颈。另一方面，弱扩展问：我们能否通过增加更多处理器，在相同的时间内解决一个成比例增大的问题？这是像气候建模这样的学科的雄心，科学家们希望通过使用更大的机器来提高分辨率（一个更大的问题）。弱扩展的一个有趣例子是同时运行许多独立气候模拟的“系集”，这是一项“易并行”的任务，几乎可以完美扩展，让科学家能够更好地量化他们预测中的不确定性[@problem-id:4051427]。
并发的原则超越了数字和物理领域，延伸到人类活动的结构本身。我们的社会、经济，甚至我们的认知过程，都是由相互作用的并发代理组成的复杂系统。
考虑一下医院这种高风险环境。重症监护室的护士是并发的大师，同时处理多项任务：为一个病人准备药物，为另一个病人响应警报，并为第三个病人记录护理情况。为了理解这种环境下的认知负荷和潜在的错误，医学信息学的研究人员构建了临床工作流程的形式模型。一个简单的流程图是不够的，因为它无法表示重叠的任务、同步点（如给药前强制性的双重检查），以及至关重要的资源争用。
使用像佩特里网这样的形式化方法，我们可以用数学的精确性来为这个工作流程建模。护士的并发任务是网中的并行路径。一个强制性的验证步骤是一个“变迁”，只有当所有先决条件的令牌（例如，“药物已准备”和“患者身份已确认”）都到位时才能触发。一个共享资源，比如一个单一的条形码扫描仪，被建模为一个只有一个令牌的库所。一个任务必须“消耗”这个令牌才能使用扫描仪，使其对其他人不可用，直到令牌被归还。这样的模型揭示了在简单的程序性描述中可能看不见的瓶颈和高负荷决策点。它使我们能够形式化地分析工作结构本身如何产生认知需求，为设计更安全的系统和为临床医生提供更好的支持工具铺平了道路。
这种对资源流和潜在僵局进行建模的思想，在交通模拟中也得到了完美的体现。我们可以将一个城市的道路网络表示为一个图，其中交叉路口是任务，道路是数据通道。一个每个交叉路口都根据其输入更新的朴素模拟，很容易导致死锁，这种情况类似于四辆车同时到达一个四向停车路口，每辆车都在等待其他车先行。一个直接从并行计算中借鉴过来的健壮解决方案是双缓冲。在每个时间步，所有交叉路口都从一个“当前”的道路状态中读取数据，并将其输出写入一个独立的“下一个”状态。只有在所有计算都完成后，系统才会原子地交换缓冲区，使“下一个”状态成为新的“当前”状态。这种在时间上分离读写的简单技巧完全打破了依赖循环并消除了死锁，使得模拟能够以完美的、并行的步调进行。
最后，这些概念可以扩展到整个人群的层面。在流行病学中，传染病的传播是一个由个体间接触驱动的并发过程。通过引入一个并发参数，可以增强简单的模型，该参数代表重叠伴侣关系对疾病传播的影响。例如，在性网络中，更高程度的并发性会比一个拥有相同数量但按序形成的伴侣关系的网络，显著加速性传播感染的传播。通过建立一个包含这些参数的数学模型，公共卫生官员可以进行敏感性分析。他们可以问：哪种干预措施更有效？是减少10%的接触率还是增加10%的避孕套使用率？模型提供了一个定量的答案，表明不同策略的有效性关键取决于人群中并发相互作用的底层结构，从而用严谨的、基于模型的证据来指导政策。
从处理器的逻辑门到公共卫生的逻辑，并发的语言提供了一个统一的框架。它为我们提供了理解、预测和管理我们所居住的这个复杂、互联、同步发生的世界的工具。同步、资源管理和冲突解决的相同基本模式在所有这些领域中回响，揭示了这一基本科学思想的深刻统一性和惊人之美。