读者-写者问题

在现代计算世界中，无数进程和线程常常需要同时访问相同的共享数据。这种并发访问是一把双刃剑：它释放了巨大的性能，但也引入了协调方面的深远挑战。这种复杂性的核心在于一个简单的区别：观察数据（读取）与修改数据（写入）。读者-写者问题是一个经典挑战，即设计一个系统，允许任意数量的读者并发访问资源，同时确保写者拥有独占访问权。如果没有一个鲁棒的策略，这种微妙的平衡可能会崩溃，导致数据损坏、系统冻结和隐蔽的错误。本文将深入探讨这个基本问题。

接下来的章节将引导您从理论走向实践。在“原理与机制”中，我们将剖析核心的交互规则，探讨如竞争条件等不受控制的访问所带来的危险，并分析在偏向读者的策略与偏向写者的策略之间的公平性权衡。我们还将揭示工程解决方案，从简单的锁到优雅的排队机制，以防止饥饿和死锁。然后，在“应用与跨学科联系”中，我们将看到这个抽象问题如何在现实世界中体现。我们将穿梭于数据库并发控制、操作系统内部、硬件设计，甚至揭示在调控生命本身的表观遗传机制中一个惊人的相似之处。

并发编程世界的核心围绕着一个简单而根本的区别：观察与改变之间的差异。我们称这些动作为​​读取​​和​​写入​​。一次“读”是无害的行为；一个线程窥视一块共享数据但保持其原封不动。然而，一次“写”是一种变革性行为；它修改数据，创造一个新的状态。读者-写者问题就是协调一个由读者和写者组成的线程社会的挑战，它们都试图访问同一个共享资源——无论它是一个数据库、一个文件，还是内存中的一个简单变量。

乍一看，交互规则似乎显而易见：

1. 任意数量的读者可以同时访问资源。毕竟，如果它们只是在看，它们不会互相妨碍。
2. 写者必须拥有独占访问权。当写者正在改变数据时，任何其他人——无论是另一个写者，还是一个读者——都不能在场。否则，就可能导致读者看到一个未完成的、无意义的状态，或者两个写者互相扰乱对方的工作。

但究竟什么才构成“写”？这个区别可能比表面上看起来更微妙。想象一下相关的​​生产者-消费者问题​​，其中生产者线程向共享缓冲区添加项目，而消费者线程则移除它们。生产者显然是一个写者；它改变缓冲区的内容及其占用计数。但消费者呢？它从缓冲区“读取”一个项目，但这样做时，它也修改了共享状态——它减少了项目计数并更新了指向下一个可用项目的指针。从整个缓冲区系统的角度来看，消费者也是一个​​写者​​。这一洞见是关键：“写”是任何以任何方式改变共享状态的操作。读者-写者问题处理的是我们拥有纯粹观察者——真正的读者——的特殊情况，他们绝对不会改变状态。

如果我们没有规则会怎样？想象两个读者线程，$R_1$和$R_2$，需要更新一个共享计数器rw_count来宣告它们的存在。一个看似简单的增量操作 rw_count = rw_count + 1，其实是一个陷阱。在计算机上，这不是一个瞬时动作，而是一个序列：首先，将值从内存加载到临时寄存器；其次，给寄存器加一；第三，将新值存回内存。

现在，设想一下这种灾难性的交错执行：

1. $R_1$ 将 rw_count 的值（假设为 $0$）加载到其寄存器中。
2. 系统调度器突然抢占 $R_1$，让 $R_2$ 运行。
3. $R_2$ 将 rw_count 的值（仍然是 $0$）加载到它的寄存器中。
4. $R_2$ 将其寄存器的值加一（现在是 $1$），并将此值存回 rw_count。内存现在保存的值是 $1$。
5. $R_1$ 最终被重新调度。它记得它的寄存器里是 $0$。它加一，得到 $1$，并将这个值存回 rw_count。

内存中的最终值是 $1$。但有两个读者进入。正确的值应该是 $2$。我们丢失了一次更新。这是一个经典的​​竞争条件​​。为防止这种情况，整个读-改-写序列必须是​​原子的​​——一个不可分割、不能被中断的操作。这通常通过使用​​互斥锁​​（或​​mutex​​）来实现，它确保在任何时候只有一个线程可以执行那段临界区代码，或者通过使用硬件提供的特殊原子指令。

一旦我们同意访问必须被控制，一个新的、更深层次的问题就出现了：控制它的最公平的方式是什么？正是在这里，读者和写者的简单规则演变成了一项关于策略及其后果的迷人研究。

两种经典的哲学是​​读者优先​​和​​写者优先​​。

​​读者优先​​策略是读者的天堂。只要至少有一个读者在活跃地读取，大门就对任何其他碰巧到达的读者保持敞开。他们可以源源不断地进来加入。在这个世界里，写者是二等公民。写者必须耐心等待，直到最后一个读者离开。这个策略最大化了读者的并发性，但它有一个阴暗面：​​写者饥饿​​。如果读者以连续、重叠的流方式到达，一个等待中的写者可能被无限期推迟，这违反了​​有限等待​​这一关键属性，该属性规定了其他线程插队的数量必须有一个限制。

​​写者优先​​策略则反转了剧本。一旦一个写者到达并声明其写入意图，门上就会挂起一个“新读者禁止入内”的牌子。系统会宽容地等待当前读者完成，但不允许任何新的读者进入。等待的写者获得下一个执行机会。这优雅地解决了写者饥饿问题。其机制可以惊人地简单：一个读者在进入之前，不仅检查是否有写者在活动，还要检查是否有写者在等待。如果 writersWaiting 计数大于零，即使资源当前正被其他读者使用，该读者也必须等待。当然，这引入了​​读者饥饿​​的可能性，即源源不断的写者流可能会永久地阻挡一群等待中的读者。

两种偏好策略似乎都并非真正公平。我们需要一个既服务于读者又服务于写者而不会使任何一方饥饿的系统。解决方案是一个优雅的同步工程设计，通常被称为​​旋转门​​或​​闸门​​[@problem_D:3687709]。

想象在我们的共享资源入口处有一个单人旋转门。每个线程，无论是读者还是写者，都必须一个接一个地通过这扇门。这个旋转门为请求访问强制执行了一个先进先出的队列。

现在，让我们看看这是如何防止写者饥饿的。一个写者 $W$ 到达。它通过旋转门，然后等待当前活动的读者完成。关键的技巧是：$W$ 在等待时“持有”旋转门。因为一次只能有一个线程在旋转门内，所以没有新的读者能够接近主入口。源源不断的插队者从源头上被切断了。活动的读者最终完成，最后一个读者发出信号表示资源已空闲，$W$ 便继续执行。当 $W$ 完成后，它释放旋转门，允许队列中的下一个线程（可能是读者或另一个写者）进入。这个简单的机制漂亮地为每个人恢复了有限等待，创建了一个公正有序的系统。

有一个出色的高层计划是一回事；正确地实现它是另一回事。通往一个可用的读者-写者锁的道路上布满了可能导致灾难性失败的微妙陷阱。

摧毁一切的异常

考虑一个读者线程，它正确地获取了锁，增加了 rw_count，并开始工作。突然，它的代码遇到了一个错误——也许是来自一个有故障的网络连接——并且一个异常被抛出。该线程突然终止，跳过了它整个退出流程。它从未能减少 rw_count。计数器现在被永久性地夸大了。对于锁来说，看起来好像一个读者仍然在里面，永远如此。再也不会有写者被授予访问权限，导致永久的写者饥饿。解决方案在于鲁棒的编程模式，如​​try-finally代码块​​。关键的清理代码（减少计数器，释放锁）被放置在finally块中，系统保证无论try块如何退出——无论是正常退出还是通过异常——finally块都会被执行。

过早庆祝的危险

操作的顺序至关重要。想象一个有错误的写者实现。写者完成了它的任务，并在兴奋之中，它向等待的读者发出信号，告诉它们可以进入。只有在这样做之后，它才去释放自己的独占写锁。会发生什么？一个抢占式调度器可能会立即切换到一个新唤醒的读者。这个读者相信它有权限，开始读取。但写者技术上仍然持有写锁！有一瞬间，一个读者和一个写者同时在临界区内，这是对互斥的公然违反。教训简单但至关重要：你必须在邀请他人轮到他们之前，完全放弃你自己的特权。

野心导致的死锁

如果一个线程在读取时意识到它需要修改数据怎么办？它持有一个读锁，但想要​​升级​​它为一个写锁。一个天真的方法可能是：“我会等到所有其他读者都离开，然后我将成为写者。”现在想象两个线程，$T_1$ 和 $T_2$，都持有读锁，同时有了这个相同的想法。$T_1$ 等待 $T_2$ 离开。但是 $T_2$ 正在等待 $T_1$ 离开。两者都无法继续。这是一个经典的​​死锁​​，一个循环依赖，其中每个人都在等待圈中的其他人先行动。解决这个问题需要一个更复杂的机制，比如一个唯一的“升级令牌”，以确保在任何时候只有一个线程可以尝试升级，从而打破循环等待。

同步问题很少孤立存在。它们是更大系统中的组件，它们的相互作用可以导致美丽，有时甚至是可怕的涌现行为。

考虑一个系统，其中一个读者-写者锁保护一个数据库，但还有一个用于传递更新的有界消息队列（一个缓冲区）。写者产生更新并将其放入队列；读者从队列中获取更新，然后用它们来读取数据库。

让我们分析一个看似合乎逻辑但致命有缺陷的设计：一个读者首先获取数据库的读锁，然后尝试从队列中获取消息。

现在，观察灾难的发生。消息队列变空了。一大批读者到来。它们各自成功地获取了读锁。然后，它们都试图从空队列中获取消息并阻塞等待。此时，我们有一群读者都持有读锁，并且都卡住了。一个写者到达，准备产生一个可以解锁它们的消息。为了产生消息，它必须首先获取写锁。但它不能！写锁被等待的读者们阻塞了。

我们造成了整个系统的冻结。读者们持有写者需要的锁。写者持有读者们需要的消息。这是一个完美的、系统级的死锁，源于两个被充分理解的同步模式的无辜交互。

解决方案，就像问题一样，在其简单性中蕴含着深刻的道理：颠倒操作的顺序。读者应该首先从队列中获取消息，然后才获取读锁来使用它。通过在等待另一个资源时不持有锁，依赖循环被打破了。这个单一的例子阐明了并发设计最深刻的原则之一：你获取资源的顺序至关重要，而未能看到整个交响乐的全貌可能会让整个演出戛然而止。

在经历了定义读者-写者问题的原理和机制的旅程之后，人们可能会倾向于将其归档为一个聪明但抽象的计算机科学家谜题。这样做将是一个巨大的错误。这就像学会了国际象棋的规则，却从未见证过特级大师对弈的惊人美感。读者-写者问题不仅仅是一个教科书练习；它是一种冲突与合作的基本模式，在工程、技术，以及最令人惊讶的是，生命本身中回响。一旦你学会识别它的特征——众多需要观察者与少数需要改变者之间的紧张关系——你就会开始在各处看到它。

也许读者-写者逻辑最直观和广泛的应用是在数据管理的世界里。想象一个巨大的、共享的数字图书馆，比如一个数据库或一个键值存储。无数的用户（读者）在不断地查找信息，而少数管理员（写者）则在更新记录、添加新条目或纠正错误。

你如何防止用户在更新过程中读取到一条记录，从而得到一条无意义的、残缺的信息？一个简单的解决方案是使用一个数字“图书管理员”——一个读者-写者锁。当管理员需要写入时，他们向图书管理员请求独占访问。图书管理员等待所有当前读者完成，锁上门，让管理员进行更改，然后再次开门。这确保了正确性，但如果读者不断涌入呢？管理员可能会永远等待下去。

这种紧张关系将我们带到数据库并发的核心，读者-写者问题直接映射到SELECT（读）和UPDATE（写）操作之间的冲突。不同的锁定策略提供不同的保证。“读者优先”锁优先考虑读者，冒着写者饥饿的风险。“写者优先”或“公平”锁通过让新读者等待来确保写者有机会，但这会降低读取吞吐量。这些选择对应于数据库理论中的不同​​隔离级别​​，例如READ COMMITTED，在这种级别下，读者保证不会看到垃圾数据，但如果它在同一事务内两次读取同一记录，可能会看到不同的值。

然而，现代系统通常采用一种更优雅的解决方案，尤其是在读取远多于写入（$\lambda_r \gg \lambda_w$）的情况下。这就是​​多版本并发控制（MVCC）​​的领域。MVCC不像让读者和写者争夺一个单一的、实时的数据版本，而是像一台神奇的印刷机一样工作。当写者更新一条记录时，它不会擦除旧的记录，而是创建一个新的、带有时间戳的版本。当读者开始一个事务时，它会得到一个“快照”——它保证能看到数据库在那个时间点存在的一个一致性版本。读者可以从容地进行操作，完全不知道可能有写者正在并发地创建更新的版本。读者从不阻塞写者，写者也从不阻塞读者。这就是SNAPSHOT隔离级别背后的魔力，也是对读者-写者问题的一个漂亮解决方案，它用一点存储空间（来保存旧版本）换取了并发性的巨大提升。

这个“快照”思想出现在许多高性能系统中。在延迟至关重要的分布式云缓存中，一种称为​​序列锁（seqlock）​​的技术提供了一个轻量级的变体。写者增加一个版本号，写入数据，然后再次增加版本号。读者乐观地读取数据，但在读取前后会检查版本号。如果数字是奇数（表示正在进行写入）或者在他们读取期间发生了变化，他们就知道他们的数据可能已损坏，只需重试即可。这是一个荣誉系统，速度极快，因为读者根本不需要获取锁。

如果说数据库是图书馆，那么操作系统（OS）就是管理整个演出的无形编舞者。操作系统内核本身就是一个巨大的并发系统，其中读者-写者模式无处不在。

考虑打开一个文件这样一个简单的行为，比如 /home/user/document.txt。内核必须遍历这个路径，在其目录项缓存（dentry cache）中查找home，然后是user，然后是document.txt。这是一个读操作。现在，想象在一个多核服务器上，成千上万的进程和线程同时在做这件事。与此同时，一个用户可能正在重命名一个目录或删除一个文件——这是一个写操作。如果我们对dentry cache使用一个简单的全局锁，那么每当一个文件被重命名时，整个文件系统都会陷入停顿。性能将是灾难性的。

Linux内核对此的解决方案是一个读者-写者工程的杰作，称为​​读取-复制-更新（RCU）​​。RCU是一种在不锁定读者的情况下实现更新的方法。当写者需要修改一个数据结构（比如断开一个dentry的链接）时，它不是在原地修改。相反，它复制相关部分，修改副本，然后原子地切换一个指针以使新版本生效。那旧数据怎么办？它会原地保留一个“宽限期”。系统会等待，直到能保证在变更之前活跃的读者都不再持有对旧数据的引用，然后才会释放旧数据。读者可以飞速地遍历数据结构，无需任何锁、开销或等待，并确信脚下的地面不会消失。

操作系统还有其他锦囊妙计。创建新进程的[fork()](/sciencepedia/feynman/keyword/fork()|lang=zh-CN|style=Feynman)系统调用利用内存管理硬件通过​​写时复制（CoW）​​来解决读者-写者问题。当一个进程fork时，父进程和子进程最初共享所有相同的物理内存页，但它们被标记为只读。子进程可以作为父进程在fork瞬间状态的读者。如果父进程（写者）随后尝试修改一个页面，硬件会触发一个故障。操作系统会介入，为父进程制作该页面的私有副本，然后让写入继续进行。子进程不受影响；它们继续看到原始的、未改变的快照。这是另一种形式的快照隔离，但是在系统内存的架构层面实现的。

当然，即使使用显式锁，程序员也必须小心。例如，当使用像[epoll](/sciencepedia/feynman/keyword/epoll)这样的I/O通知机制来唤醒等待的读者线程时，必须记住，唤醒信号本身并不保证内存同步。被写者信号唤醒的读者仍然必须正确获取读锁，以确保它能看到写者的更改，从而建立一个“happens-before”关系。忘记这一点会导致一些微妙而令人抓狂的错误，即读者基于过时的数据进行操作。

读者-写者模式是如此基础，以至于它甚至出现在处理器和物理机器的设计中。

现代CPU有时包含一个称为​​硬件事务内存（HTM）​​的功能。这允许一个线程推测性地执行一个代码块——一个事务。硬件会跟踪所有被读取和写入的内存位置。如果事务在完成时没有任何其他核心写入它读取的位置，或读取/写入它写入的位置，那么这些更改就会被原子地提交。如果检测到冲突，硬件会自动中止事务并回滚其所有更改。这可以用来实现一个速度极快的读者-写者锁。读者在事务中运行。如果一个写者出现并修改了数据，所有读者的事务都会被硬件自动中止。这种“事务锁消除”可以提供巨大的性能，但它需要一个鲁棒的、传统的、公平的软件锁作为后备，以应对事务可能反复中止的高争用情况。

当我们从硅转向钢时，这个问题的后果变得更加具体。想象一群自主机器人在构建它们环境的地图。数十个传感器线程（读者）在不断地采样环境并查阅共享地图以进行导航。一个单一的规划器线程（写者）负责整合新的传感器数据并对地图进行全局更新。在这里，读者-写者冲突不是关于软件慢；而是关于一个机器人因为读取了过时的地图版本而撞到墙上。

在这样的实时系统中，我们必须平衡两个相互对立的需求。规划器必须周期性地获得独占访问权，以防止地图变得过于陈旧。但这些独占的“写者窗口”会导致传感器线程阻塞，从而在其采样率中引入“抖动”。设计这样的系统需要仔细计算这些窗口的周期和持续时间，以同时满足控制系统的最大陈旧度容忍度和传感器的最大抖动容忍度。抽象的读者-写者问题体现为机器物理性能上的具体权衡。

这种协调模式是如此普遍，以至于似乎进化在数十亿年前就发现了它。读者-写者问题最深刻、最美丽的应用不是在计算机中，而是在你每一个细胞的细胞核中。

把你的DNA看作是终极的共享数据结构，而基因表达的模式——哪些基因是开启或关闭的——则是写在上面的数据。这些数据不是存储在DNA序列本身，而是存储在包装DNA的组蛋白上的一层化学修饰中。这些被称为表观遗传标记。

在这个生物学背景下，“写者”是一种在组蛋白上添加特定标记的酶。例如，PRC2复合物会写入一个抑制性标记（H3K27me3），告诉一个基因“保持沉默”。“读者”是一个物理上识别并结合到该特定标记的蛋白质结构域。

魔术就发生在这里，与我们的计算系统形成了惊人的平行。这些复合物中的许多都表现出​​读者-写者反馈循环​​。例如，PRC2复合物不仅包含EZH2“写者”亚基，还包含一个EED“读者”亚基。当EED读者结合到一个已有的H3K27me3标记时，它会变构激活EZH2写者，刺激它在相邻的核小体上沉积相同的标记。

这是一个正反馈循环。一个被写入的标记被读取，而读取的行为会招募或激活写者，将该标记传播给它的邻居。因此，一个单一位置的初始“写入”可以像波浪一样传播，将整个基因域从活跃状态翻转到沉默状态。另一个著名的系统，涉及写者Suv39和读者HP1，对H3K9me3标记做同样的事情，以建立沉默的异染色质。这种传播是一个动态过程，是读者-写者反馈（$k_f$）和移除标记的擦除酶（$k_e$）之间持续的斗争。要使一个沉默基因的区域扩张，反馈驱动的写入速率必须超过擦除的速率。

这是一个令人谦卑的认识。工程师们用锁、快照和事务内存解决的同一个抽象问题——协调并发观察与独占修改——也被自然选择解决了。进化使用酶作为写者，蛋白质结构域作为读者，并利用变构反馈作为机制，来编排复杂的基因调控交响曲，使得一个单一的基因组能够产生你体内所有不同种类的细胞。读者-写者问题，最终，不仅仅是关于代码。它是在数字世界和生命世界中一个深刻而统一的组织原则。