计算机系统工程-07：并发原子性

并发服务

银行程序接到一笔转账后，需要读取余额、计算新值、保存结果，再回复用户。用户通过 RPC 向服务器发请求；若服务器一次只处理一笔，其他请求就要等待。请求越来越多时，增加线程或机器可以分担工作，也会让多笔业务同时访问账户数据。

本节先解释吞吐量怎样影响用户等待，再分析并发访问中的竞态条件，最后介绍锁、可串行化和死锁。主要问题是：多个业务同时运行时，怎样让每笔业务的读取和结果都符合一笔接一笔执行的规则。

前一节讨论故障发生后，一笔业务的修改能否完整恢复。本节先假设运行期间没有故障，数据放在内存中，重点检查不同线程的操作怎样交错。需要同时处理故障与并发时，还要把这里的锁和事务规则与日志恢复结合起来。

请求排队

吞吐量表示单位时间完成多少个请求，例如每秒完成 1000 笔存款。延迟表示一个请求从发起到取得结果需要多久，例如一次存款需要 10 ms。两者都由具体负载和实现决定。

设服务器忙于处理一个请求的平均时间为 $S$ 。单线程连续工作、每次只处理一个请求时，最大处理能力近似为：

$\mu=\frac{1}{S}$

$\mu$ 读作 mu，单位通常为请求/秒；后文也用它表示最大吞吐量。若平均每笔需要 1 ms，也就是 0.001 s，则 $\mu=1000$ 请求/秒。实际平均完成量还取决于是否有足够请求，以及 I/O、网络和其他共享资源是否限制了处理。

B 请求到达后，先等待 A，再由服务器处理

图中三条横线分别是用户 A、银行服务器和用户 B，时间向右增加。A 的请求先进入服务器；B 的请求随后到达，但服务器仍在处理 A，所以 B 先等待。A 完成后，服务器才处理 B。

在这个简化模型中，一次请求在服务器中的时间为：

$W=W_q+S$

$W_q$ 是排队时间， $S$ 是实际处理时间。真实的端到端延迟还可能包含请求传输、客户端调度和回复传输。下面先把这些额外时间放在一旁，观察排队造成的影响。

思考题：单线程银行服务平均用 2 ms 处理一笔请求，最大吞吐量约是多少？用户只关心延迟，为什么仍需要提高吞吐量？

解答：

2 ms 为 0.002 s，因此最大吞吐量约为 $1/0.002=500$ 请求/秒。若请求平均每秒到达 600 个，每秒就会多积压约 100 个，后来的用户要等前面的请求完成。

提高吞吐量能让服务器更快处理积压。在到达负载给定时，处理能力会影响排队时间，因此也影响用户感受到的延迟。

批量请求

增加处理能力还可以减少排队。假设六个请求同时到来，每个实际处理时间为 100 ms，一台工作线程依次处理时，它们分别在 100、200、300、400、500、600 ms 完成。后来的请求虽然同样只计算了 100 ms，却在前面等待。

两个互不争用资源的工作线程同时处理时，每轮完成两个请求，完成时间成为 100、100、200、200、300、300 ms。请求内部的计算量保持不变，等待时间缩短，所以平均响应时间从 350 ms 降为 200 ms。

练习：三个工作线程共同处理这六个请求，忽略额外开销，全部请求多久完成？平均响应时间是多少？

解答：

每轮处理三个请求，共两轮，全部完成需要 200 ms。三个请求在 100 ms 完成，另外三个在 200 ms 完成，平均为 $(3\times100+3\times200)/6=150$ ms。

过载积压

到达率 $\lambda$ 表示单位时间平均到达多少个请求，读作 lambda。假设到达率和处理能力都不变，服务器一直有请求可处理，观察经过的时间为 $t$ ，队列从空开始，则积压量可粗略写为：

$Q(t)\approx(\lambda-\mu)t\qquad(\lambda>\mu)$

这里的 $t$ 是观察持续时间。例如 $\lambda=1200$ 请求/秒、 $\mu=1000$ 请求/秒，10 秒后约积压 2000 个请求。若随后停止接收新请求，处理这批积压仍需约 2 秒。

只要超出处理能力的负载持续到达，积压就继续增长。无限容量的理想队列会越来越长；真实队列通常有容量限制，满后会拒绝请求、触发超时或丢弃任务。容量限制能控制资源占用，应用仍需要定义过载时怎样响应。

$\lambda<\mu$ 是形成稳定队列的基本条件之一。它表示长期平均处理能力足以应付到达量，短时间内仍可能排队。在随机到达模型中，稳定意味着长期统计分布可以保持稳定；偶尔出现很长的队列仍然有可能。

思考题：到达率长期高于最大吞吐量时，把队列容量扩大十倍能解决延迟问题吗？

解答：

扩大队列可以延后队列满的时刻，也会允许更多请求等待。每秒到达量仍超过每秒完成量，积压继续增长。需要增加处理能力、减少每次请求的工作量，或通过限流和拒绝控制实际接收量。

突发到达

平均到达率较低，也可能出现几笔请求同时到达。例如每秒只到达三个请求，但它们集中在同一个毫秒内；单线程服务器要依次处理，后面的请求仍会排队。

前三个请求集中到达，第四个请求在服务器空闲时到达

图中 Req 1、Req 2、Req 3 接连到达。Req 1 先处理，Req 2、Req 3 等待；处理完这三笔后，服务器暂时空闲。Req 4 较晚到达，能够立即进入处理。忙碌与空闲交替发生，不能仅凭一段时间的平均到达量推断每次请求都无需等待。

思考题：最大吞吐量高于平均到达率，队列是否总为空？

解答：

请求可能集中到达。当短时间的到达量超过这段时间内能够完成的数量，剩余请求就进入队列。即使之后服务器有空闲，前面那批请求已经经历了等待。

泊松到达

许多用户各自偶尔发出请求，彼此没有统一安排到达时刻。这种负载常用泊松过程近似。模型假设平均到达率固定，不相交时间段内的到达量独立；它适用于某些随机负载，实际服务还可能有定时任务、共同热点等相关到达。

独立用户的请求汇集后，每个时间窗口中的到达量不同

图中上方每条线对应一个用户，短竖线表示一次请求；下方 Bank 线把所有用户的请求汇集起来。每个等长窗口的平均到达量为 $\lambda t=2$ ，实际数量依次出现 2、0、3、1、5、2、3、0、2。平均数为 2，并没有规定每个窗口恰好到达两个请求。

长度为 $t$ 的窗口内，到达 $k$ 个请求的概率为：

$P(N(t)=k)=\frac{(\lambda t)^k e^{-\lambda t}}{k!}$

$N(t)$ 是这段时间里的请求数； $k$ 可以为 0、1、2 等非负整数； $k!$ 是阶乘，例如 $3!=3\times2\times1=6$ 。 $e$ 是自然对数的底。公式把某个具体到达数量与它出现的概率联系起来。

当 $\lambda t=2$ 时，没有请求的概率为 $e^{-2}\approx0.1353$ ，到达五个请求的概率为 $2^5e^{-2}/5!\approx0.0361$ 。因此，同样的平均负载会同时产生空闲窗口和积压窗口。

练习：某窗口平均到达两个请求。窗口内可能一次到达五个吗？这种情况怎样影响后面的请求？

解答：

在泊松模型中可以发生，其概率约为 3.61%。如果服务器在该窗口内处理不了五个请求，就会留下积压。后面的请求到达时，需要等待相应积压先完成；出现平均处理能力有余量的窗口后，队列才可能逐渐缩短。

平均延迟

利用率 $U$ 表示服务器的忙碌程度。在稳定的单服务者模型中，平均服务时间为 $S=1/\mu$ ，可以写为：

$U=\lambda S=\frac{\lambda}{\mu}$

例如每秒到达 800 个请求，最大吞吐量为每秒 1000 个，则 $U=0.8$ 。这表示长期平均约 80% 的时间用于服务请求。

Little 定律联系平均人数与平均停留时间：

$L=\lambda W$

这里 $L$ 是系统里的平均请求数，包含正在处理的请求和排队中的请求； $W$ 是请求在这个系统里的平均停留时间。若只计算队列，也要对应使用 $L_q=\lambda W_q$ 。例如每秒接收 100 个请求，平均每笔停留 0.1 s，则系统里平均有 10 个请求。

可以用固定学制核对 Little 定律的含义：假设某校每年招 100 人，每人在校 5 年，招生和毕业已稳定进行，也没有其他流入流出，则在校人数为 100 人/年×5 年=500 人。单位相乘得到人数，对应 $L=\lambda W$ ；排队系统中的 W 也应使用同一统计范围内的总停留时间。

一个直观近似是：新请求到来时，前面平均有 $L$ 个请求，还需要完成自己这一次处理，于是：

$W\approx(L+1)S$

将 $L=\lambda W$ 代入：

$W\approx\lambda WS+S=UW+S$

移项得到：

$W\approx\frac{S}{1-U}=\frac{1/\mu}{1-U}$

这个推导用来解释利用率接近 1 时等待增长的趋势。公式的精确适用范围需要说明：在泊松到达、服务时间服从指数分布的单服务者 M/M/1 模型中，稳定状态下有精确结果：

$W=\frac{1}{\mu-\lambda}=\frac{S}{1-U},\qquad\lambda<\mu$

其中第一个 M 表示到达间隔服从指数分布，第二个 M 表示服务时间服从指数分布，1 表示只有一个服务者。这个 $W$ 已包含服务时间；平均排队时间为 $W_q=W-S$ 。MIT 的 M/M/1 讲义

若每次服务时间严格固定为 $S$ ，则属于 M/D/1 模型。在相应稳定条件下， $W=S+\frac{US}{2(1-U)}$ 。两种模型都体现高利用率带来的排队增长，但具体数值取决于服务时间的分布。MIT 排队模型讲义

负载余量

平均延迟随利用率提高而增长，接近满载时增长明显

横轴为利用率 $U$ ，纵轴为平均延迟相对平均服务时间的倍数。按 $W=S/(1-U)$ 计算：

利用率	平均延迟	平均服务时间为 1 ms 时
0	$S$	1 ms
0.5	$2S$	2 ms
0.8	$5S$	5 ms
0.9	$10S$	10 ms
0.99	$100S$	100 ms

当 $U$ 趋近 1，分母趋近 0，稳定模型中的平均等待不断增长。实际服务常保留一部分处理余量，吸收突发和处理时间的波动。80% 可以作为本例中的说明数值，具体目标应由延迟要求、负载分布和资源成本决定。

练习：平均服务时间为 1 ms，到达率为每秒 900 个请求。按 M/M/1 模型，平均总延迟和排队时间各是多少？若处理能力提高到每秒 2000 个，到达率保持不变，平均总延迟是多少？

解答：

原来的 $\mu=1000$ ， $U=0.9$ ，所以 $W=1/(1000-900)=0.01$ s，即 10 ms。服务时间为 1 ms，平均排队时间为 9 ms。

提高处理能力后， $W=1/(2000-900)\approx0.000909$ s，即约 0.909 ms。新的平均服务时间为 0.5 ms，因此平均排队时间约为 0.409 ms。这些数值使用了题目给定的随机模型。

并行扩展

提高处理能力可以从减少单次工作量和增加执行资源入手。过去处理器频率增长曾使许多串行程序直接受益；约 2004 年前后，持续依靠频率提升获得性能增长的路线受到功耗等条件限制，多核逐渐成为主要扩展方式之一。单线程程序仍可能从缓存、指令执行等改进中受益，充分使用更多核则需要安排并行工作。

单机使用更多执行资源，以及使用多台机器扩展

scale-up 可以在一台机器上使用多个线程与多个 CPU 核；scale-out 把计算安排到多台机器。线程是程序的执行序列，同一进程中的线程通常共享地址空间，因此可以直接访问同一份银行数据。多台机器共享数据时，则需要存储服务和通信协议。

并发表示多个任务的执行过程可以相互交错；并行表示它们在某个时刻实际由不同执行资源同时执行。单核切换线程也能形成并发。接下来的错误只需要操作发生交错，在单核与多核环境中都可能出现。

增加执行资源后，吞吐量能提高多少还取决于共享数据、锁、I/O 和其他资源。多线程银行服务首先要保证，多笔存款访问同一个账户时仍能保留每笔存款的效果。

购票冲突

有些依赖在执行前就已确定，例如后续矩阵层需要前层输出。购票请求则可能在运行中才选出票号，因此也在运行中才知道两次请求是否访问同一记录。

余票为一时，两笔事务交错导致两个订单

图中只有一张余票。两笔事务都读到 left=1，各自把库存写为 0，并分别建立 Alice、Bob 的订单，造成一张票对应两个成功订单。需要共同协调查询、判断、扣票与建单。

思考题：两个用户都请求“购买任意一张票”，为什么请求开始时很难知道二者是否冲突？如果它们都读到余票为 1，怎样协调扣票和建订单？

解答：

请求开始时尚未选定票号，两次请求后来可能选中同一张票，冲突因此在执行中才出现。要把查库存、判断、扣票和建订单作为受协调的一组操作：用锁依次处理时，后一事务读到 0 就停止；用乐观控制时，第一笔提交后，第二笔发现旧读取已失效，重新读取后停止购买。

下面先用存款说明共享读改写，再介绍锁；按版本验证的 OCC 过程见事务机制。

存款交错

设 Alice 的余额最初为 0。T0、T1 各执行一次存款 10 元，预期余额应为 20。T0、T1 在这里表示两个执行线程，每个线程运行一笔存款动作。

下面用伪代码表示业务；bank[acct] 表示读取或修改账户余额，amt 表示存入金额。代码先展示未经并发保护的操作：

1
2
3

def deposit(bank, acct, amt):
    """读取现有余额并加款，暂未提供并发保护。"""
    bank[acct] += amt

源代码只有一条加法，实际可能包含三个步骤：把共享余额读入当前线程使用的寄存器或局部变量，在本地加 10，再把新余额写回共享数据。两个线程有各自的临时计算值。

# 示意性的读、计算、写步骤；实际指令随语言和编译器变化。
tmp = read(alice)
tmp = tmp + 10
write(alice, tmp)

两个线程都先读到 0，最后各写入 10

沿图中从左到右的顺序：

步骤	执行内容	共享余额	线程临时值
①	T0 读取余额	0	T0 保存 0
②	T1 读取余额	0	T1 保存 0
③	T0 加 10	0	T0 保存 10
④	T1 加 10	0	T1 保存 10
⑤	T0 写回	10	T0 已完成
⑥	T1 写回	10	T1 已完成

两次写回都把余额设为 10。T1 的计算基于它先前读到的 0，写回时没有把 T0 已存入的 10 再加进去。这种并发更新未能保留全部修改的情况称为丢失更新（lost update）。

普通读写的原子保证取决于数据宽度、对齐、语言和硬件接口。即使每次读取和写入各自完整发生，整个“读取、加法、写回”仍需要额外保证。有些接口提供原子的加法操作，复杂的多账户事务则需要保护更大范围的操作。

思考题：两个线程各存入 10 元，Alice 期待多少余额？两个线程都执行完成后，为什么可能只剩 10 元？

解答：

期待 20 元。两者都从旧余额 0 计算并写回 10，就只保留一次增加；上表列出了这个丢失更新的完整交错。若两个线程各自自增一万次，同类覆盖也可能使总数少于两万。

竞态条件

同样两笔存款，交错执行得到 10，依次执行得到 20

图中上半部分是前面的交错顺序。下半部分让 T0 完整做完，再让 T1 读取余额：T0 把 0 改为 10，T1 读到 10 后加 10，最终为 20。

竞态条件（race condition）表示结果受到多个执行过程相对时序的影响，某些允许的时序会破坏程序要求。分析共享数据时，常见线索是多个线程访问同一对象，其中至少一个会写入，而相关业务步骤缺少足够协调。

程序设计还会使用 data race 这一术语，它通常由具体语言的内存模型定义。例如没有适当同步的冲突内存访问，在 C/C++ 中可能产生未定义行为。本节的图按抽象的读写步骤分析业务交错，实际代码还应满足语言的同步要求。

锁可以避免某些交错，也需要覆盖完整的业务依赖。每次内存访问都有锁，多个访问之间仍可能出现业务上的竞态，转账与审计的例子会进一步展示这一点。

复现困难

一次测试按安全顺序运行成功，后一次可能按其他顺序运行失败。系统调度、网络延迟和线程暂停都能改变相对时序，错误于是可能间歇出现。

假设两个线程各有三个步骤，并且只要求保留各线程内部顺序，可能的交错共有：

$\binom{6}{3}=20$

这个组合数表示从六个位置中选三个放 T0 的步骤，剩余位置放 T1。步骤和线程更多时，可能的交错数量迅速增长。程序需要保证协议允许的每一种执行都满足要求。

加一条打印语句、连接调试器，可能改变调度或增加同步，让原来的错误暂时消失。这类受到观察方式影响、难以重复出现的错误常称为 Heisenbug。

确定性多线程执行（DMT）尝试让同样输入产生同样的执行安排。记录与回放（record and replay）则保存一次运行中必要的事件顺序，再重现该运行。两者都需要处理线程、系统调用、外部输入等来源，也会增加记录、执行或调度成本。它们可以帮助调试，应用仍需要定义正确的并发协议。

界面乱序

评论页面中的编号顺序与显示的发布时间顺序存在差异

这张评论截图标出第 1、2、3 条，显示时间分别为约 4 小时前、2 小时前、1 小时前。在第 1、2 条之间，还插着一条约 1 小时前的评论，整个显示顺序为“4 小时前、1 小时前、2 小时前、1 小时前”。页面组织、后台更新和评论到达可能各自按不同过程推进，用户看到的排列因此可能暂时不同。

仅凭截图无法确定应用内部的具体线程交错。它用来说明，用户能观察到由多个更新过程形成的不一致界面。若应用允许之后重新排列，影响可以较轻；涉及余额、奖项或其他业务约束时，则要检查这种临时结果是否会参与进一步操作。

“影响较轻”需要依据应用的要求判断。显示暂时乱序可以按产品规则处理，底层实现仍应遵守语言和接口规定的同步条件。

设备配置

Therac-25 的事故调查说明，并发问题也可能影响设备控制。下面使用一个简化模型，只检查模式、功率设置和部件位置之间的关系；实际事故涉及更多软件、硬件和系统设计因素。Leveson 与 Turner 的原始调查

示例包含两种模式：

模式	功率设置	图中的金属部件
X-ray，记为 X	较高，示意为电子模式的约 100 倍	位于束流路径中
Electron，记为 E	较低	移出束流路径

需要保持模式与配置配套。高功率配上移出的部件，会形成危险组合。这里的比例和位置用于解释程序依赖，完整的物理装置需结合原始调查理解。

键盘代码写 mode，配置代码和部件控制代码分别读取它

mode 是共享的模式变量。键盘代码根据操作员输入修改它；setup code 读取它，设置束流参数与磁铁，图中这一过程约需 8 秒；plate code 也读取它，控制部件放入或移出。

思考题：模式变量由谁写入、由谁读取？若修改被部件控制代码看见，配置代码却继续使用旧值，会怎样？

解答：

键盘代码写 mode，配置代码和部件代码分别读取。两者采用不同版本时，可能组合出高功率与部件移出的危险状态；需要在启用前确认整组配置相符。

X 模式开始配置后，用户改为 E，两个执行过程使用了不同版本

图中的过程为：

键盘写入 X，部件控制读到 X，将部件放入。
配置代码也读到 X，选择高功率，开始约 8 秒的设置过程。
设置尚未结束时，键盘把模式改为 E。
部件控制再次读取，取得 E，把部件移出。
配置代码未处理这次修改，仍按 X 完成。
启用束流时，设备保留高功率，部件已经移出。

每次读取都可能准确返回当时的 mode，配置整体仍可能不配套。这里要保护的是“接受一个版本的模式、完成全部相关配置、确认后启用”这一组过程。实际安全设计还需检查真实部件状态和其他保护条件。

DNS 更新

DNS 将域名解析为连接所需的地址。应用访问 dynamodb.us-east-1.amazonaws.com 时，需要取得对应 IP；解析与连接可以使用缓存，新的地址查询失败会使需要建立连接的应用受到影响。

服务器仍存在，但域名的地址记录为空，应用无法取得连接地址

图右边的服务节点仍有 IP 1、IP 2、IP 3，DNS 记录却为空。数据服务的进程和存储可以继续存在，应用仍因取得不到地址而无法建立新连接。AWS 对 2025 年 10 月 19—20 日 us-east-1 故障的报告记录了这种情况。AWS 官方事件总结

DNS Planner 周期性产生地址规划，包含应使用的节点和权重等信息；DNS Enactor 将规划应用到 Route 53。多个执行器分别运行在三个可用区，提高组件失效时继续更新的能力。

一个 Planner 产生版本规划，多个 Enactor 修改共享 DNS 记录

这形成了多个写入者共享一份逻辑记录的场景。图中用 #7、#8、#12 表示递增版本，后面的版本代表较新的规划。一次执行包含检查当前版本、应用规划、清理旧规划等步骤，步骤之间会发生等待。

旧版写入延迟到新版之后完成，随后清理删除了正在使用的旧规划

按图中的简化版本编号逐步分析：

步骤	执行器 1	执行器 2	当前记录
①	读取 #7，判断自己的 #8 更新	尚未修改	#7
②	应用 #8 的操作出现较长延迟	读取 #7，判断 #12 更新	#7
③	仍在等待	应用 #12	#12
④	延迟的 #8 应用完成	开始相关清理过程	#8
⑤	已完成旧规划应用	清理显著早于 #12 的规划，包括 #8	地址为空

第一次检查时，#8 确实比 #7 新。操作等待期间，#12 已经被应用，这次检查就过期了。#8 随后覆盖 #12，而较新执行器的清理又删掉了已经重新成为当前版本的 #8。官方报告还说明，当前规划被删除后，自动更新进入无法自行修复的状态，需要人工介入。

思考题：多个执行器交错时，为什么“开始前检查自己的版本更新”仍可能让旧规划覆盖新规划？清理过程又怎样使结果进一步恶化？

解答：

检查后的等待使旧判断过期，延迟的 #8 因而覆盖 #12；清理再删除当前 #8，导致地址为空。应用和回收都需验证自己的并发前提，不能只依赖开始时的一次检查。

单次记录替换使用事务，也需要配合整个“检查、应用、清理”的依赖。系统可以设计带条件的更新、共同协调或明确的版本回收规则，具体方案需覆盖这组步骤发生的所有交错。

这个案例中的客户数据保持完整，DNS 故障仍使依赖该入口的访问失败。图中“约 2.5 小时”概括主要 DNS 修复过程。官方报告给出的 DynamoDB API 错误率升高区间为美国太平洋夏令时间 10 月 19 日 23:48 至 10 月 20 日 02:40，后续其他服务的恢复继续进行了更长时间。作为该次事件的处置，AWS 停用了相关自动化，并宣布在重新启用前修复竞态和增加错误规划保护。这些是事件报告中的处置记录。

事务隔离

应用容易根据一份逻辑数据、一次完整业务来推理。例如每笔存款增加指定金额，每笔转账一边加钱、一边扣钱；若这些业务能够按某个共同顺序解释，就可以依次检查每笔操作的结果。

事务（transaction，简称 TX）把需要共同处理的一组读写联系起来。存款包含读取余额、计算和写回；转账包含两个账户的修改；审计包含读取多个账户并计算总额。事务边界由业务要求决定。

线性一致性可以规定一次读取或写入怎样生效。将两次读取、一次计算和一次写入组合起来时，仍需规定这一整组步骤与其他事务的关系。前面的存款交错中，每次读取和写入都可能单独符合寄存器接口的规则，整个存款却丢失了一笔更新。

多个动作各包含一组读写，整体行为需要对应某个串行顺序

图上方是三组并发动作，每个 Action 框包含读和写。下方给出一个共同顺序：先完成蓝色动作，再完成黑色动作，最后完成绿色动作。并发实现要让调用方得到的读取和结果能按这样的完整动作顺序解释。

先后原子性（before-or-after atomicity）要求从调用者观察到的行为看，并发动作之间能够体现完整的先后关系。它联系到事务隔离（isolation）：系统协调一组读写，使其他动作的交错不会破坏这组动作需要保持的关系。

在本节的无故障读写模型中，可串行化用于精确检查这种“能够解释为依次执行”的要求。实际事务隔离有多种级别，需要确认接口承诺哪一种。若还要求已完成事务排在后来发起的事务之前，就需要加入实时约束，形成严格可串行化；本节的普通可串行化主要检查等价的串行解释。

要求	检查的问题
单次操作的线性一致性	一次读写能否在调用区间内生效，并保留实时先后
事务的可串行化	整组读写的结果能否等价于某个串行事务顺序
故障下的全有或全无	中途失败后，整组修改能否完整保留或撤销

一笔真实转账通常需要结合这些保证：读取遵守接口规则，多笔转账之间正确协调，失败后能够恢复，已经确认的结果可靠保留。

思考题：所有 read 和 write 各自都满足线性一致性，能否直接保证两笔存款正确？

解答：

仍可能发生 R0(余额)=0、R1(余额)=0、W0(余额)=10、W1(余额)=10。每个单次访问可按这个合法顺序解释，但两笔完整存款的结果应为 20。需要为整组读改写提供并发保护，例如在同一把锁内完成存款，或使用满足所需语义的原子加法接口。

互斥锁

锁是一份用于协调访问的共享状态。互斥锁在某一时刻只允许一个持有者进入受保护范围；其他执行者要等持有者释放后再取得它。持锁的代码范围称为临界区（critical section）。

基本操作为：

acquire(lock)：申请取得锁，成功后继续执行。
release(lock)：释放已经持有的锁，使其他执行者可以取得它。

等待的实现可以让线程反复检查，也可以由操作系统把它暂时挂起；互斥不要求 CPU 始终忙等。pthread_mutex 是常用接口之一，具体的等待、调度和内存可见性规则由接口提供。OSTEP 锁章节

锁要由所有相关访问者共同遵守。一个线程持有账户锁，另一个线程直接绕过锁读取或修改余额，保护条件就不完整。同一笔业务也要明确从哪一步加锁、到哪一步释放。

本节伪代码中的 with lock: 表示进入时取得锁、离开时释放锁。它说明同步范围，真实实现需要处理异常、取消和锁接口错误。释放锁的机制与业务修改的回滚机制分别安排；已经执行一半的事务发生失败时，还要使用恢复规则。

全局加锁

全局锁用同一把锁保护整个银行动作。只要访问银行数据的所有动作都遵守它，同一时刻就只有一笔动作执行受保护的读写。

def deposit_with_global_lock(bank, bank_lock, acct, amt):
    """用一把共享锁保护完整的存款读改写。"""
    with bank_lock:
        bank[acct] += amt

T1 等待 T0 释放全局锁后，读到 10，再写入 20

图中 L 表示 lock，取得锁；U 表示 unlock，释放锁。按图的顺序：

T0 取得锁，读取 Alice 的余额 0。
T1 申请同一把锁，被阻塞。
T0 加 10、写回 10，然后释放锁。
T1 取得锁，读取余额 10，再加 10、写回 20。
T1 释放锁，两笔存款完成。

T1 在持锁后才读取余额，因此使用的是 T0 完成后的值。也可能由 T1 先取得锁，最终仍能按两个完整存款的某个顺序解释。谁先申请并不能单凭这段伪代码保证谁先取得，锁的公平性要看具体接口。

全局开销

Alice 与 Bob 的存款互不修改同一账户，全局锁仍让两者等待

图上方两笔存款分别修改 Alice、Bob，可以各自从 10 改为 20。加上全局锁后，T1 等 T0 完成，即使二者访问的是不同账户，也会按同一把锁依次执行。

若业务的大部分时间都在这个临界区里，增加线程后，受保护工作仍一次只做一笔。加锁、唤醒和线程切换还可能增加开销，吞吐量甚至低于原来的单线程实现。临界区外的独立工作仍有并行机会，需要看实际工作分布。

优化通常检查两个方面：

减少需要共同等待的范围，例如按数据对象分工，或把不依赖共享状态的解析与准备放到临界区外。
降低加锁与解锁的实现开销，例如减少争用和不必要的唤醒。

更快的锁操作可以减少管理成本。临界区占据主要处理时间时，同一把锁所要求的互斥执行仍会限制吞吐量。

思考题：怎样选择应该保护的代码范围？把锁移到写回前，能否安全完成存款？

解答：

要保护计算依赖的共享读取和对应写入。存款的新值依赖旧余额，读取旧余额后到写回之间，其他存款可能改变余额。

若只在写回前加锁，两个线程仍可能先各自读到 0，再依次写回 10。因此需要在读取前取得相应锁，完成读、计算、写回后再释放；可独立完成的参数解析等工作可以放在这个范围外。

Linux 曾逐步将 Big Kernel Lock 替换为更细的同步机制，最后的 BKL 机制在 2.6.39 中移除。这类迁移需要重新检查共享状态和临界区，体现锁范围设计的工程成本。2011 年内核报告

按账户锁

细粒度锁（fine-grained locking）将保护范围划分到更小的数据对象，例如每个账户一把锁。locks[acct] 是指定账户的锁，bank[acct] 是其余额；锁与数据的对应关系由系统维护。

def deposit_with_record_lock(bank, locks, acct, amt):
    """只占用目标账户的锁，保护该账户的完整存款。"""
    with locks[acct]:
        bank[acct] += amt

Alice 与 Bob 各有一把锁，两笔存款可以交错执行

T0 取得 lock[alice]，T1 取得 lock[bob]。它们读取、计算和写回各自余额，没有申请同一把锁，所以可以同时进行。两笔存款都针对 Alice 时，仍通过 Alice 的锁协调。

锁粒度表示一把锁覆盖多少数据。全局锁覆盖整个银行，账户锁覆盖单条记录。粒度越小，独立访问越容易并行；锁数量、身份管理和多对象业务的协调也会增加。

思考题：每个账户都有一把锁，是否足以让所有银行动作都正确？

解答：

对本例中单账户的存款，保护整个读改写即可。转账涉及两个账户，审计涉及多个账户，还需要规定这些锁在整笔动作里何时取得、何时释放。仅保护每一次独立访问，仍可能让另一动作读到部分完成的转账。

转账审计

初始 a=10,b=10。Transfer 从 a 向 b 转 10，示例先给 b 加钱、再从 a 扣钱；完整结果为 a=0,b=20。Audit 读取各账户并计算总额，不应改变余额。

这里先展示一种每次访问结束就释放账户锁的方案：

def transfer_with_short_locks(bank, locks, a, b, amt):
    """分别保护两个账户的访问，两个锁的范围尚未覆盖整笔转账。"""
    with locks[b]:
        bank[b] += amt

    with locks[a]:
        bank[a] -= amt


def audit_with_short_locks(bank, locks, accounts):
    """逐个读取并立即释放锁，可能组合到不同阶段的余额。"""
    total = 0
    for acct in accounts:
        with locks[acct]:
            total += bank[acct]
    return total

accounts 是审计要访问的账户列表。下面的动画令审计先读 b、再读 a；这个顺序用于展示一种具体的允许交错。

转账先把 b 改为 20 并解锁，审计读到 b=20、a=10

逐步追踪：

步骤	动作	a	b	审计临时总额
①	Transfer 锁住 b	10	10	0
②	Transfer 把 b 改为 20，并释放 b 锁	10	20	0
③	Audit 取得 b 锁，读到 20，再释放	10	20	20
④	Audit 取得 a 锁，读到 10，再释放	10	20	30
⑤	Transfer 取得 a 锁，把 a 改为 0，再释放	0	20	30

Transfer 在释放 b 锁后，尚未完成 a 的扣款。Audit 就在这个间隔里取得两个余额，组合成 30。两笔动作全部完成后，银行余额仍是正确的 0,20，审计已经产生了错误结果。

思考题：图中的最终账户状态是否正确？Audit 得到的 30 是否正确？如果审计完全在转账之前或之后执行，各得到多少？

解答：

最终 a=0、b=20 正确；Audit 的 30 错误。完整转账前后总额都是 20，30 来自把新 b 与旧 a 拼在一起，因此没有合法串行解释。

读者也需要参与并发控制。Audit 虽然只读取银行数据，它读取的是一个需要共同解释的账户集合。只看最终写入状态，会漏掉这类已经返回给用户或用于下一步处理的错误读取。

静态加锁

静态加锁（static locking）先确定动作需要访问哪些对象，在首次数据访问之前取得全部相关锁，动作结束后再释放。锁仍可以细到单个账户；改变的是取得与释放的时机。

def transfer_with_static_locks(bank, lock_manager, a, b, amt):
    """预先锁住两个账户，完整转账后统一释放。"""
    accounts = sorted({a, b})
    with lock_manager.acquire_all(accounts):
        bank[b] += amt
        bank[a] -= amt

acquire_all 是锁管理器的抽象接口，表示已安全取得这些锁后才进入代码块，离开后统一释放。实现可以按统一的账户顺序申请；也可以采用全部可用才授予的管理方式。这个名字本身不提供原子取得多把锁的能力。

转账持有 a、b 的锁直到完整结束，审计随后读取 0 和 20

Transfer 开始前锁住 a、b。它给 b 加钱时，a 的锁也已经持有；Audit 申请相关锁，暂时等待。Transfer 完成 a 的扣款后释放锁，Audit 才读取 b=20,a=0，得到 20。Audit 自己也需要让整组读取遵守相应协议。

若 Audit 先取得全部相关锁，Transfer 就在 Audit 完成后继续，审计读到的为 10,10。两种执行都符合一个完整业务在另一个之前。

静态加锁需要提前知道读写集合，也就是动作会访问哪些对象。固定的两个账户转账很容易列出集合；查询或遍历中的后续目标可能依赖读出的数据，提前列出全部对象会更困难。审计一个动态银行还要保护账户集合，避免读取期间新增或删除账户改变范围，可以使用共同的集合锁或更完整的事务机制。

持锁范围

a 和 b 的锁都持有六个时间单位，合计十二个锁时间单位

图中横轴为执行步骤，纵轴分别是 lock[a] 与 lock[b]。两条记录都从步骤 0 锁到步骤 6，每把锁占六个时间单位，合计 12。

a 到后半段才实际使用，却从开始一直被占用。这段等待可以挡住另一笔只访问 a 的存款。静态加锁的完整范围便于推理，也可能占用尚未使用的对象更长时间。

“锁数乘持有时间”的面积可以概括本例的占用量。它用于比较同一时间划分中的锁持有范围，实际吞吐量还取决于其他动作访问哪些账户、持锁线程是否被调度以及真正发生多少争用。

两阶段锁

两阶段锁（two-phase locking，简称 2PL）允许动作在运行中逐步申请锁，并遵守两条规则：

访问一个共享对象前，必须先取得对应且与访问方式匹配的锁。
释放了任意一把锁以后，这个事务不能再申请新的锁。

本节先用互斥锁简化所有访问；读锁、写锁等更细的模式需要遵守相应兼容规则。事务中的锁操作分为：

增长阶段：可以取得新锁，保留已取得的锁。
收缩阶段：可以释放锁，后续不再取得新锁。

增长阶段仍可以执行读写。取得最后一把锁的时刻称为锁点（lock point），之后保有的锁可以依规则逐步释放。

对于先修改 b、后修改 a 的转账，可以使用：

# 无故障模型中的基本 2PL 顺序。
acquire(lock[b])
read(b)
write(b, new_b)

# 必须先取得最后需要的锁，才能开始释放。
acquire(lock[a])
release(lock[b])
read(a)
write(a, new_a)
release(lock[a])

new_b、new_a 表示根据本事务相应读取计算出的余额。这段顺序中，释放 b 前已经取得 a，后面只需要 a，因此不再申请其他锁。

练习：判断下面两组锁操作是否满足基本 2PL，并解释原因。

A. L(b)、读写b、U(b)、L(a)、读写a、U(a)。

B. L(b)、读写b、L(a)、U(b)、读写a、U(a)。

解答：

A 在释放 b 后又取得 a，违反“开始释放后不再取得新锁”的规则。它就是前面转账可能暴露半笔结果的方式。

B 在首次释放前取得全部需要的锁，之后只使用已持有的 a 锁并释放它，满足基本 2PL。所有相关动作还要共同遵守锁协议。

并发机会

静态加锁先占用 a，2PL 则让只访问 a 的存款先完成

图中 Transfer 从 a 转到 b，Deposit 给 a 存入 10。初始 a=b=10。

上半部分使用静态加锁：Transfer 一开始取得 a、b 两把锁，Deposit 一直等待 a。Transfer 得到 a=0,b=20 后释放，Deposit 将 a 改为 10，最终 a=10,b=20。

下半部分使用基本 2PL：

Transfer 先锁 b，开始把 b 从 10 改为 20。
此时 a 未被它占用，Deposit 锁 a，把 a 从 10 改为 20，然后释放。
Transfer 取得 a 锁，再释放 b 锁。
Transfer 读到 a=20，减去 10，写回 a=10，最后释放 a。

这次实际交错的最终结果可以按“Deposit 完整执行，再执行 Transfer”解释。Transfer 在 b 上较早工作，两者仍有共同的串行业务解释。

静态方案的占用面积为十二，示例 2PL 的占用面积为七

按图的时间单位，静态方案两把锁各持有 6，总占用为 12。2PL 中 b 持有 4、a 持有 3，总占用为 7；锁数量依次为 1,1,1,2,1,1,0。步骤 3 取得 a 后形成锁点，随后进入收缩阶段。

该例展示按需取锁、适时释放如何减少占用。2PL 的实际优势需要结合业务冲突情况判断；提前释放写锁还会影响失败时的恢复条件，后面会补充这一范围。

思考题：2PL 减少了图中的持锁时间，是否要求每笔业务实际完整执行后，下一笔才开始？

解答：

两笔业务可以交错，甚至一笔尚未完成时，另一笔已处理某个独立账户。要求检查整个交错的读取和写入，是否能够对应某个合法串行顺序。图中可以对应 Deposit 在 Transfer 前的结果。

执行调度

调度（schedule）记录多个事务的操作实际按什么顺序发生。它保留每个事务内部的操作顺序，同时写出不同事务之间的交错。这里的调度重点是数据库读写历史，与操作系统选择哪个线程运行的调度相联系。

使用以下两个事务，初始 x=0,y=0：

# T1 读取 x，再基于读取到的 y 计算新 y。
T1:
    begin
    read(x)
    tmp = read(y)
    write(y, tmp + 10)
    commit

# T2 将两个对象设置为给定值。
T2:
    begin
    write(x, 20)
    write(y, 30)
    commit

begin、commit 标记事务边界。T1 读 x 的值虽然没有参与 y 的计算，仍是需要检查的观察结果；它可能返回给调用者，也可能参与其他判断。tmp 是 T1 的私有临时变量，T2 改变 y 后，这份先前读出的临时值不会自动更新。

后文用 $R_i(x)$ 表示事务 $T_i$ 读取 x， $W_i(x,v)$ 表示它把 x 写为 v。例如 $R_1(y)=30$ 表示 T1 的读取返回 30。分析时同时记录操作次序、读取来源和最终写入。

串行结果

串行调度（serial schedule）先运行一笔完整事务，再运行下一笔；不同事务的步骤没有交错。两个事务只有 T1→T2 和 T2→T1 两种串行顺序。

两个串行顺序分别得到 y=30 和 y=40

先 T1、后 T2：

T1 读到 x=0,y=0，把 y 改为 10。
T2 把 x 改为 20、y 改为 30。
最终为 x=20,y=30。

先 T2、后 T1：

T2 把 x、y 改为 20、30。
T1 读到 x=20,y=30，计算 30+10=40。
最终为 x=20,y=40。

串行顺序	T1 读 x	T1 读 y	最终 x	最终 y
T1 → T2	0	0	20	30
T2 → T1	20	30	20	40

这两行提供了判断后面交错执行的依据：检查读到什么、读自哪个版本，以及最终修改能否与某一行相符。

交错判断

调度 A 的读取和结果与串行 T2→T1 相符，调度 B 得到另一结果

调度 A 的操作为：

# 每行代表一次按顺序发生的共享访问。
W2(x, 20)
R1(x) = 20
W2(y, 30)
R1(y) = 30
W1(y, 40)

T1 在 T2 两次写入之间读 x，但等 T2 写 y 后才读 y。T1 的两次读取都来自 T2，最终为 20,40，可以按 T2→T1 的串行顺序解释。

调度 B 的操作为：

# T1 的 y 计算仍使用它读取时保存的 0。
R1(x) = 0
W2(x, 20)
R1(y) = 0
W2(y, 30)
W1(y, 10)

T1 先取得 y 的旧值 0，再由 T2 把共享 y 改为 30。T1 根据自己的临时值计算 10，写回时覆盖了 30。最终为 x=20,y=10，与两个串行顺序都不相符。

思考题：并发调度 A 能否按某个串行顺序解释？调度 B 的问题出现在哪一步？

解答：

A 对应 T2→T1。B 使用旧 y=0 算出 10，并在 T2 写 30 后覆盖它；两个串行顺序只能得到 y=30 或 40，因此 B 无合法解释。

读取结果

调度 C 最终得到 20、40，但 T1 同时读取到旧 x 和新 y

调度 C 为：

# T1 的两个读取落在 T2 修改的两侧。
R1(x) = 0
W2(x, 20)
W2(y, 30)
R1(y) = 30
W1(y, 40)

最终 x、y 为 20、40，与串行 T2→T1 的最终状态相同。但 T1 读到的组合为 x=0,y=30：

若 T1 完整在 T2 前，两个读取应都得到初始值 0。
若 T1 完整在 T2 后，应得到 20、30。

两个串行顺序都无法产生 0,30 这个读取组合。T1 可以依据这个组合做判断、生成结果或执行后续操作，因此读取历史也要纳入正确性检查。

思考题：调度 C 的最终状态与某个串行顺序相同，能否据此判定可串行化？

解答：

还要检查读取来源。T1 的 0、30 混合了 T2 前后的状态；串行 T1→T2 时应读 0、0，T2→T1 时应读 20、30，均与 C 不符。

视图等价

视图等价（view equivalence）检查两个调度是否给事务相同的读取来源和最终写入责任。通常用三个条件表示：

若某个事务在一个调度中读取对象的初始值，在另一个调度中也读取初始值。
若某个读取在一个调度中取得另一事务写入的版本，在另一个调度中也从同样的写入来源取得版本。
对每个对象，两个调度中完成最后写入的事务相同。

这里的“来源”有具体含义。例如 T1 读 y=30，需要确定它读自 T2 的写入；另一个事务恰好也写过 30，单凭数值相同无法确定版本关系。具体模型在同一事务多次访问同一对象时，还需对应相应读写操作。

视图可串行化（view serializability）表示一个并发调度与某个串行调度视图等价。给定相同初始状态和确定的事务计算，保持读取来源与最终写入关系，就能用那个串行调度解释观察到的结果。

对前面的例子：

调度	T1 对 x 的读取来源	T1 对 y 的读取来源	最终写 x、y 的事务	判断
A	T2	T2	T2、T1	对应 T2 → T1
B	初始状态	初始状态	T2、T1	无对应串行顺序
C	初始状态	T2	T2、T1	无对应串行顺序

若 B 想对应 T1→T2，最后写 y 的应为 T2，实际却是 T1。C 则同时要求 T1 位于 T2 修改 x 前、修改 y 后，无法把整笔 T1 放在 T2 的同一侧。

判断成本

一种直接检查方法是枚举事务的串行排列，再对比是否视图等价。n 笔事务有 $n!$ 种排列，10 笔就有 3,628,800 种，事务更多时搜索量迅速增加。

枚举说明了直接方法的成本。一般视图可串行化判定属于 NP 完全问题；它可以判定，但目前没有已知的通用多项式时间算法。小规模或受限制的调度可以专门处理，系统需要选择能高效检查和生成的并发规则。Papadimitriou 的原论文

思考题：视图可串行化是否可以检查？为什么系统常采用更容易验证的条件？

解答：

有限历史可以枚举串行顺序并检查视图等价，一般判定问题为 NP 完全。冲突判据把检查转成找环，并可由 2PL 等协议直接维护，所以更便于系统使用。

读写冲突

两个操作构成冲突，需要同时满足：

属于不同事务。
访问同一个数据对象。
至少一个是写入。

不同事务都只读 x，交换先后通常不改变它们读取的版本；一个读取与另一个写入 x，交换顺序就可能改变读取来源；两个写入 x，交换顺序可能改变最终保留的版本。

操作对	是否冲突	原因
$R_1(x),R_2(x)$	否	两个操作只读
$R_1(x),W_2(x)$	是	同对象、不同事务，包含写入
$W_1(x),R_2(x)$	是	同对象、不同事务，包含写入
$W_1(x),W_2(x)$	是	两个写入同对象
$W_1(x),W_2(y)$ ，x 与 y 独立	否	访问不同对象
$R_1(x),W_1(x)$	不计为跨事务冲突	同一事务的程序顺序本来就要保留

本节把对象按独立记录建模。数据结构还可能有跨记录约束、范围查询和新记录插入，真实协议应把这些访问依赖也纳入保护范围。

冲突等价

两个调度包含相同事务和读写操作，并且每一对冲突操作的先后都相同，就称为冲突等价（conflict equivalent）。非冲突步骤可以以其他方式交错，事务内的程序顺序仍要保留。

若一个调度与某个串行调度冲突等价，它就具有冲突可串行化（conflict serializability）。这里把判断重点放到必须保留的依赖顺序上。

一个理解方法是交换相邻的非冲突操作。它们访问不同对象，或都只读取同一对象，交换后不会改变相关的读写依赖。若通过这些交换能够整理出串行调度，就找到了对应的串行解释。

冲突列表

调度 A 只有三对跨事务冲突，分别发生在 x 和 y 上

图中的 T1.1、T1.2、T1.3 表示 T1 的第 1、2、3 个数据操作；T2.1、T2.2 表示 T2 的两个写入。小数点后的编号只标识操作次序。

调度 A 的三对冲突为：

对象	先发生的操作	后发生的操作	对事务顺序的约束
x	$W_2(x,20)$	$R_1(x)$	T2 在 T1 前
y	$W_2(y,30)$	$R_1(y)$	T2 在 T1 前
y	$W_2(y,30)$	$W_1(y,40)$	T2 在 T1 前

三对冲突都要求 T2 在 T1 前，因此可以统一满足。T1 读取 x 与 T2 写 y 访问不同对象，没有额外的冲突约束；这也是图中允许部分交错的原因。

冲突图

冲突图（conflict graph，也称优先图）把事务画为节点，把冲突要求画为有向边。若某对冲突中 T1 的操作先发生、T2 的操作后发生，就画 $T1\to T2$ 。

同一事务对之间发生多次同方向冲突，只需保留一条边，并记录它们共同提供的约束。图的作用是判断，是否能找到满足全部约束的事务顺序。

调度 A 的三对冲突合为一条 T2 指向 T1 的边

调度 A 的图中只有 T2→T1。先安排 T2，再安排 T1，就满足全部边的方向，因此它冲突可串行化。

一个调度冲突可串行化，当且仅当冲突图没有有向环：

$\text{冲突图无环}\quad\Longleftrightarrow\quad \text{冲突可串行化}$

无环图可以进行拓扑排序：先选一个没有未满足前驱的节点，安排它执行，再继续安排后面的节点。由边所限制的事务在前，依赖它的事务在后；若存在多个可选节点，就可能有多个合法串行顺序。

环形依赖

调度 C 在 x 上要求 T1 在前，在 y 上要求 T2 在前，形成环

调度 C 中：

$R_1(x)$ 先于 $W_2(x,20)$ ，产生 $T1\to T2$ 。
$W_2(y,30)$ 先于 $R_1(y)$ 和 $W_1(y,40)$ ，产生 $T2\to T1$ 。

图中形成 T1→T2→T1。安排 T1 在前无法满足第二条边，安排 T2 在前无法满足第一条边。因此没有满足全部冲突方向的串行顺序，C 不具备冲突可串行化。

构图与找环可以分别执行。若共有 m 个数据操作，直接枚举操作对最坏需要 $O(m^2)$ 次检查；构图后，用深度优先搜索或拓扑排序检查环，成本为 $O(V+E)$ ，其中 V 为事务节点数、E 为边数。实际系统也可以在访问时增量记录依赖。

练习：为调度 B 构图。它的操作为 R1(x)、W2(x)、R1(y)、W2(y)、W1(y)，忽略数值只看先后。

解答：

x 上的读取先于 T2 写入，产生 T1→T2。y 上的 T1 读取也先于 T2 写入，继续产生同方向边。随后 T2 写 y 先于 T1 写 y，产生 T2→T1。

两个方向形成环，因此 B 不具备冲突可串行化。它的最终 y=10 也已经在前面的串行结果检查中暴露出问题。

盲写示例

冲突可串行化对所有冲突方向提出要求，视图可串行化允许某些被后续写入覆盖、又没有被任何读取观察到的写入以不同方式排列。下面的例子具体展示二者的范围。

盲写（blind write）表示事务直接写某个对象，写入之前没有先读取该对象来计算结果。它可能覆盖较早写入，而某些被覆盖的版本没有进入任何读取。

T1 与 T2 的写入顺序形成冲突环，最后的 T3 写入覆盖前面的结果

三个事务在 x 上的调度为：

# 用来源关系分析，图中的写入没有标出具体数值。
R1(x)        # 读取初始值
W2(x)
W1(x)
W3(x)        # 最后写入

T1 的读取先于 T2 的写入，要求 T1→T2；T2 的写入又先于 T1 的写入，要求 T2→T1，所以存在冲突环。T3 最后写入，还得到 T1→T3 和 T2→T3 等关系。

检查视图等价时，可以尝试串行顺序 T1→T2→T3：

T1 仍在其他事务写入前读取 x，来源为初始值。
T2、T3 没有读取 x，因此没有新的读取来源需要对应。
T3 仍执行最终写入，覆盖 T1、T2 的版本。

这与原调度的视图条件相同，因此该调度视图可串行化，同时不具备冲突可串行化。

思考题：为什么系统可能限制这个已经视图可串行化的调度？它在语义上是否必然错误？

解答：

在本题给定的读写模型中，它可以按 T1→T2→T3 的视图解释，满足这个判据。采用冲突可串行化的系统会限制它，因为 T1、T2 形成冲突环。

这种限制换来了较容易检查的条件，以及 2PL 等直接维护合法调度的协议。系统接受的范围可以比所有视图可串行化调度更小，需要依据所提供的保证判断。

可串行化

两种判据的关系为：

$\text{冲突可串行化}\quad\Longrightarrow\quad \text{视图可串行化}$

保持全部冲突方向，就会保持读取来源和最终写入关系，因此冲突可串行化的调度也视图可串行化。前面的盲写例子说明，视图条件还允许额外的调度。

判据	保留的关系	一般检查方式
视图可串行化	初始读取、读取来源、最终写入责任	搜索一个视图等价的串行顺序，一般问题为 NP 完全
冲突可串行化	每对冲突操作的先后	构建冲突图，检查是否有环

冲突判据便于验证，也便于通过加锁等协议在运行中维护。系统使用它时，会限制部分仍能找到视图串行解释的执行，换取可操作的检查与控制方法。

两阶段证明

在本节所有相关访问都使用互斥锁的模型中，2PL 保证冲突可串行化。关键是两类顺序能够联系起来：

互斥保证一笔事务释放对象锁后，另一笔才可以取得它并执行冲突访问。
2PL 保证同一事务的全部成功取锁，先于它的任何释放锁。

假设冲突环存在，会推出一次释放锁发生在自身之前

用反证法分析。假设一个完成的调度存在环：

$T_1\to T_2\to\cdots\to T_k\to T_1$

把每条边所对应的冲突对象记为 $x_1,x_2,\ldots,x_k$ 。箭头 $T_1\to T_2$ 表示在 $x_1$ 上，T1 的冲突访问先于 T2。互斥要求：

$U_1(x_1)<L_2(x_1)$

L 表示成功取得锁，U 表示释放， $<$ 表示时间上先发生。T2 还需要释放 $x_2$ 给 T3。根据 T2 的 2PL 规则：

$L_2(x_1)<U_2(x_2)$

T2 可以先取得 $x_2$ ，再等待 $x_1$ ；只要仍满足 2PL，取得 $x_1$ 必须发生在任何释放之前，因此这个关系仍成立。

沿环依次连接，得到：

$U_1(x_1)<L_2(x_1)<U_2(x_2) <\cdots<U_k(x_k)<L_1(x_k)$

最后根据 T1 的 2PL 规则，取得 $x_k$ 也必须早于释放 $x_1$ ：

$L_1(x_k)<U_1(x_1)$

合起来会要求 $U_1(x_1)<U_1(x_1)$ ，也就是同一次释放先于自身，矛盾。因此冲突环无法存在，调度冲突可串行化。

还可以用锁点理解：若 $T_i\to T_j$ ，Tj 成功取得引起这项冲突的锁时，Ti 已开始释放；Ti 的锁点因此更早，Tj 的锁点更晚。沿每条边锁点都向后推进，便无法绕回同一个锁点。按锁点排列能提供一个符合冲突约束的串行顺序。

思考题：某事务先取得 x2 的锁，再等待 x1 的锁，会破坏上面的证明吗？

解答：

不会；证明只要求所有成功取锁先于首次释放。先取 x2、再取 x1 合法；释放 x2 后再申请 x1 就违反 2PL。

业务正确性

可串行化把并发执行归约到某个串行顺序，业务动作本身也要正确。例如初始 a、b 各有 10，转 10 元：

def transfer_correct(bank, a, b, amt):
    """示意正确转账的两项余额变化，外层负责事务控制。"""
    bank[b] += amt
    bank[a] -= amt


def transfer_buggy(bank, a, b, amt):
    """错误示例：收款增加了两倍金额，破坏余额总额。"""
    bank[b] += amt * 2
    bank[a] -= amt

第一段完整执行后得到 a=0,b=20，总额仍为 20。第二段得到 a=0,b=30，总额变为 30；即使只有一个线程，也会产生业务错误。

串行正确性可以用状态推理。设符合业务规则的初始状态为 $S_0$ ，每个事务在满足前置条件的状态中执行，都产生符合规则的新状态。那么按某个串行顺序执行：

$S_0\xrightarrow{T_1}S_1\xrightarrow{T_2}S_2 \xrightarrow{\cdots}S_n$

每一步都维持相应业务条件，最终状态也符合条件。可串行化允许并发历史按这类串行过程解释，从而减少需要单独分析的交错。

余额总额、余额下限、权限和每个请求只执行一次等条件，由业务逻辑与系统协议共同维护。例如转账必须检查付款账户余额是否足够，读取余额、判断和扣款也要放在相应事务范围中。系统能维护规定的约束，应用仍要告诉它什么条件算正确。

思考题：将错误的 transfer_buggy 放进完整的全局锁中，会恢复余额总额不变吗？

解答：

不会。该函数串行执行也使收款加 20、付款减 10，总额增加 10。锁不能修正业务计算，需要先保证单笔逻辑正确。

回滚范围

前面基本 2PL 的证明针对读写调度及其冲突顺序。若允许事务失败或主动撤销，提前释放写锁还需要考虑未提交结果被后续事务使用的情况。

例如 T1 改了 b，并取得它以后需要的 a 锁，然后释放 b；T2 取得 b 锁，基于 T1 的新值计算。T1 随后撤销时，要恢复 b 的旧值，T2 已经依赖那个被撤销版本，它的结果也需要处理。这可能产生级联回滚。

实际事务系统常将写锁保留到提交或完成回滚，配合日志决定何时允许其他事务使用新结果。通常所称的严格 2PL（strict 2PL）要求写锁保留到事务结束；若所有读写锁都保留到结束，也常称为强严格 2PL 或 rigorous 2PL。不同教材的命名范围会有所差别，使用时应核对锁的具体释放规则。CMU 并发控制讲义

严格方案仍可以逐步取得锁，增长阶段也可以与其他无冲突事务交错。释放时机与提交决定、故障恢复结合起来，避免后续事务依据尚未确定的结果继续工作。

本节的 2PL 图用于分析无故障、无撤销的调度；保存到磁盘、提交失败和恢复的具体方法，可以继续结合故障原子性中的日志过程理解。

锁的等待

2PL 属于悲观并发控制：访问前先进行协调，遇到冲突就等待对应锁。这种方式不需要先执行完整业务再发现读写冲突，也可能让等待持续较长时间。

审计先申请 b 的锁，被转账挡住，随后读取完整新余额

图中仍为 a=b=10，Transfer 先锁 b，再锁 a；Audit 也先申请 b：

Transfer 取得 b 锁，把 b 改为 20。
Audit 申请 b，被阻塞，此时它还没有占有 a。
Transfer 取得 a，把 a 改为 0。
Transfer 完整修改后释放锁。
Audit 取得 b，读取 20，再取得 a，读取 0，总额为 20。

等待只影响完成时间，并没有让 Audit 提前返回半笔转账的结果。Transfer 后续需要的 a 此时可取得，所以它能够继续执行并最终让 Audit 前进。

死锁过程

死锁（deadlock）表示一组执行者各自等待其他执行者持有的资源，形成无法自行继续的等待关系。它需要结合持有的资源、申请的资源和释放条件来判断。

Transfer 持有 b 等 a，Audit 持有 a 等 b

本例按以下顺序：

步骤	Transfer	Audit
①	取得 b 锁	取得 a 锁
②	读取 b	读取 a
③	申请 a，等待 Audit	仍持有 a
④	仍持有 b	申请 b，等待 Transfer

Transfer 需要 a 才能继续；Audit 需要 b 才能继续。两者在等待时都保留已有锁，在没有外部中止、超时等机制的情况下，无法执行到释放步骤。

这段取锁行为可以符合 2PL：两个事务都在增长阶段，还没有释放锁。2PL 保证完成调度的冲突可串行化，执行是否一定能够推进还需要额外的活性安排。

思考题：图中 Transfer 或 Audit 能否靠正常执行完成？2PL 为什么没有自动解决等待？

解答：

不能。两者各等对方持有的锁，又都无法执行到释放步骤。2PL 允许增长阶段持锁等待，仍需统一取锁、死锁检测或中止规则来保证推进。

统一取锁

一种预防办法是给所有锁规定共同顺序，例如所有账户按 ID 从小到大申请。Transfer、Audit 和其他访问者都遵守相同顺序，避免一边先 a 后 b、另一边先 b 后 a。

若 a 排在 b 前，Transfer 也先申请 a，再申请 b。Audit 已经取得 a 时，Transfer 就在尚未占有 b 的情况下等待，Audit 能继续申请 b 并完成。

这种方法的原因可以从编号理解：一个事务持有较小编号后，只继续等待更大编号。若存在循环等待，就会要求编号沿环不断增大，最后又回到开始编号，无法满足严格递增。

预先知道全部访问集合时，可以先排序再取锁。动态计算的访问目标也需要保证后续申请符合顺序；若先取了较大编号，运行中才发现必须访问较小编号，就需要重启、提前取得更大范围的锁，或采用其他控制方案。

因此，统一取锁顺序并不要求所有程序都一次预知全部对象，但业务必须能够遵守它。一般的数据依赖事务实现这项规则可能较困难。PostgreSQL 锁文档也用统一访问顺序解释死锁预防。

等待图

另一种方法是记录当前等待关系，发现死锁后中止其中一笔事务。等待图（wait-for graph）以事务为节点：T1 当前等待 T2 持有的锁，就画 T1→T2。

本例中：

1
2
3

# 箭头表示当前等待的锁由另一个事务持有。
Transfer → Audit      # 等待 a
Audit → Transfer      # 等待 b

在本节每个锁只有一个持有者、等待者必须取得所需锁才能继续的模型中，图中存在环就表明循环等待。锁管理器可以定期或在等待达到一定条件时找环，选择一笔事务撤销。

撤销后需要恢复它已修改的数据，完成相关清理，再释放它持有的锁；剩余事务才能在合法状态中继续。直接释放一笔已做了一半的转账，会重新暴露中间状态，必须结合回滚机制。

等待图与冲突图有不同用途：

图	边表示什么	环检查的用途
冲突图	已发生的冲突访问要求哪个事务排在前面	判断该调度是否冲突可串行化
等待图	当前哪个事务等待另一个事务的锁	发现本模型中的死锁

两个图都以事务为节点，但边记录的事实不同。发生阻塞时，后一个冲突操作往往还没执行，所以还没有形成对应的已执行冲突边。

检测与维护等待图会消耗计算和共享状态管理资源。事务很多、锁请求频繁时，要在及时解除等待与检测成本之间安排频率。需要撤销哪笔，也可以结合已完成的工作量、优先级和重试次数选择。

主动中止

系统还可以用时间戳或等待时间，提前决定哪些事务继续等待、哪些事务先撤销。中止意味着本次事务放弃，需要按恢复规则清理修改，随后才允许重试。

例如一种按年龄决定等待的规则为：较老事务可以等较新事务；较新事务遇到较老事务持有的锁，则先撤销。这类规则通常称为 wait-die。时间戳用来建立年龄顺序，可以使用系统分配的递增编号。CMU 并发控制讲义

假设 T1 的时间戳为 10，T2 为 20，数值较小代表较老：

T1 等 T2 持有的锁，可以继续等。
T2 想取得 T1 持有的锁，按规则撤销 T2。

若所有事务一致遵守这项规则，保留的等待边始终从较老指向较新，就不能构成年龄不断增加又回到起点的环。它可能中止一笔本来稍等就能继续的事务，用额外重试减少循环等待。

重试时保留原事务的年龄，可以让它在之后遇到新事务时仍按较老者处理。若每次重试都取得最新时间戳，它就可能不断成为较新者并被撤销，增加饥饿的风险。

超时等启发式办法也能限制某次等待，但长时间等待可能只是锁持有者执行较慢。阈值过小会导致更多无必要的回滚。选择方法时需要说明何时中止、怎样回滚、重试保留什么身份，以及如何避免总是牺牲同一笔事务。

重试活性

活锁（livelock）表示执行者不断重试或调整状态，始终无法完成有效工作。例如两笔事务同时申请资源、同时放弃、马上同时重试，反复重复同一模式。

死锁中，执行者常停在等待；活锁中，它们可能持续执行取锁、撤销和重试，却没有提交事务。饥饿（starvation）则表示某个事务长期得不到完成机会，即使其他事务不断成功。

可以采用不同的重试延迟、等待队列、稳定优先级或更明确的取锁规则，让执行者取得不同的机会。随机退避有助于打散同时重试，也要结合协议的推进条件判断是否足够。

思考题：发现死锁后，两个事务同时撤销并立即重试，是否必然能成功？应检查哪些条件？

解答：

若两者再次按原来的相对时序申请资源，可能重新进入同样的等待，再一起撤销，形成持续重试而无进展的情况。

可以只选一笔撤销，让另一笔先完成；再配合退避、排队或稳定优先级。撤销时要恢复中间修改，重试时保持正确业务身份，并检查长期是否有事务总被中止。

方法选择

方法	主要协调规则	可获得的并发机会	需要处理的问题
全局锁	整笔动作共用一把锁	临界区外的独立工作可并行	所有受保护动作相互等待
单账户短锁	每次访问相应账户时取锁，访问后释放	不同账户可以并行	多账户事务可能暴露部分结果
静态加锁	数据访问前取得全部相关锁，结束后释放	对象集合不冲突时可以并行	提前确定集合，可能占用尚未使用的锁
基本 2PL	逐步取锁，首次释放后停止取新锁	可减少部分对象的持锁时间	死锁，以及撤销时的依赖处理
严格 2PL	遵守两阶段规则，写锁保留至事务结束	无冲突访问仍可并行	等待、死锁、提交与回滚成本

静态加锁如果通过安全的整体授予方式取得全部锁，可以避免部分持锁等待；如果实现为逐把申请，仍需共同顺序或其他死锁措施。锁协议的名称要与具体取得和释放过程一起检查。

分析一笔并发业务，可以按以下顺序进行：

写出单笔业务需要保持的条件，例如转账总额和审计结果。
将业务展开为共享读取、计算和写入，明确每笔事务边界。
列出相关事务的可能交错，追踪读取使用的版本。
检查锁保护范围，或构建冲突图寻找串行解释。
检查等待关系能否继续推进，以及撤销和重试怎样恢复状态。

本节小结

单线程服务在负载增加时会出现排队。吞吐量与请求到达的波动共同影响等待，处理资源需要满足应用的延迟目标。

并发执行让独立工作能够同时推进，也会让共享读写交错。存款可能丢失更新，转账期间的审计可能组合出半笔结果，设备配置与 DNS 更新同样需要维护跨步骤的依赖。

事务的可串行化要求并发历史能够按完整事务的某个串行顺序解释。判断时要检查读取来源和最终写入，冲突图提供了较容易维护的条件。2PL 通过限制锁的取得和释放阶段，保证相应调度冲突可串行化。

业务本身的计算、失败后的恢复，以及等待能否结束，各有对应要求。实际实现需要把正确的事务逻辑、并发控制、日志与重试规则配合起来。

参考资料

Kleinrock，1975，Queueing Systems, Volume 1: Theory，Wiley。
Harchol-Balter，2013，Performance Modeling and Design of Computer Systems: Queueing Theory in Action，Cambridge University Press。
MIT，M/M/1 模型与 M/D/1 等排队模型讲义。
Leveson 与 Turner，1993，An Investigation of the Therac-25 Accidents，Computer 26(7)，18–41；相关事故与编辑时序。
AWS，2025 年 us-east-1 服务中断事件总结。
Saltzer 与 Kaashoek，2009，Principles of Computer System Design: An Introduction，第 9.1.5 节。
Papadimitriou，1979，The Serializability of Concurrent Database Updates，Journal of the ACM 26(4)，631–653，出版信息。
CMU，并发控制与两阶段锁讲义。
Arpaci-Dusseau 与 Arpaci-Dusseau，OSTEP 锁章节。
PostgreSQL，锁与死锁文档。