# 5.5 同步：基础 同步机制通常由用户级软件例程构建，并依靠硬件提供的同步指令。对于较小的多处理器或争用较低的情形，关键硬件能力是一条不可中断的指令，或一组指令序列，能够以原子方式读取并修改某个值。软件同步机制再利用这一能力建立。本节重点介绍加锁与解锁同步操作的实现。它们既能直接构建互斥，也可实现更复杂的同步机制。 争用较高时，同步会成为性能瓶颈：争用带来额外延迟，而更大规模多处理器本身的延迟也可能更高。附录 I 讨论如何把本节的基本同步机制扩展到更多处理器。 ## 基本硬件原语 在多处理器中实现同步，需要一组能原子地读取并修改内存位置的硬件原语。没有这一能力，构建基本同步原语的成本会过高，并随处理器数量增加而增长。 基本硬件原语有几种不同形式，都能以原子方式读取并修改一个位置，并提供某种办法，判断读与写是否原子地执行。这些原语是各种用户级同步操作的构件，例如锁和屏障。体系结构设计者通常不期待用户直接使用基本硬件原语，而是希望系统程序员用它们建立同步库；这一过程往往复杂而棘手。先来看一种原语，以及如何用它构建基本同步操作。 一种典型操作是**原子交换（atomic exchange）**，交换一个寄存器中的值与内存中的值。假设要构建简单的锁，用 0 表示空闲，1 表示不可用。处理器尝试加锁时，将寄存器中的 1 与锁对应的内存位置交换。如果已有其他处理器取得访问权，交换返回 1；否则返回 0。后一种情况下，锁的值也被改成 1，阻止其他竞争的交换操作再得到 0。 例如，两个处理器同时尝试交换时，必定恰有一个先执行，返回 0；第二个执行交换时便返回 1，竞争由此分出结果。用 exchange 或 swap 原语实现同步，关键在于操作具有原子性：交换不可分割，两个同时发生的交换由写串行化机制确定顺序。采用这种方式设置同步变量的两个处理器，不可能都认定自己同时成功设置了变量。 还有一些其他原子原语可用于同步。它们的共同关键性质，是读取并更新内存值，而且我们能够知道这两项操作是否原子地执行。许多较早的多处理器提供 **test-and-set（测试并置位）**：测试一个值，如果满足测试条件，就设置它。例如，可以定义为测试值是否为 0，然后置为 1，使用方法类似原子交换。另一个原语是 **fetch-and-increment（取值并递增）**：返回某内存位置的值，同时原子地将它加一。用 0 表示同步变量尚未被占用，就可以像使用交换一样使用这一原语。取值并递增还有其他用途，稍后会看到。 单条原子内存操作的实现存在挑战，因为它要求在一条不可中断的指令中完成一次内存读和一次内存写。这使一致性实现复杂化：硬件既不能让其他操作插入读写之间，又不能造成死锁。 另一种办法是使用一对指令，由第二条返回一个值，据此判断这一对指令是否表现得像原子操作。如果任意处理器执行的所有其他操作，看起来都发生在这一对指令之前或之后，那么这对指令就有效地具有原子性。因此，原子性成立时，其他处理器不能在二者之间改变该值。MIPS 和 RISC-V 采用这种方式。 RISC-V 的这对指令包括特殊的加载 **load reserved**，也称 load linked 或 load locked，以及特殊的存储 **store conditional**。Load reserved 将 rs1 指定内存地址的内容加载到 rd，并对该地址建立保留（reservation）。Store conditional 将 rs2 中的值存入 rs1 指定地址。如果对同一内存位置的写入破坏了加载建立的保留，条件存储失败，并向 rd 写入非零值；成功则写入 0。如果处理器在这两条指令之间发生上下文切换，条件存储总是失败。 这两条指令按次序使用。由于保留加载返回初始值，条件存储仅在成功时返回 0，下面的序列可将 x4 中的值与 x1 指定的内存位置原子交换： ```asm try: mov x3,x4 ; 复制要交换的值 lr x2,0(x1) ; 从 x1 指定地址执行保留加载 sc x3,0(x1),x5 ; 存储 x3；成功时 x5 = 0 bnez x5,try ; 存储失败则再次尝试 mov x4,x2 ; 将加载的值放入 x4 ``` 序列结束时，x4 的内容与 x1 指定内存位置的内容已经原子交换。只要某处理器在 `lr` 与 `sc` 之间介入并修改内存值，`sc` 就向 x5 返回非零值，令代码重试。 保留加载/条件存储机制的一个优点，是可以构建其他同步原语。例如，下面是原子取值并递增： ```asm try: lr x2,0(x1) ; 对 0(x1) 执行保留加载 addi x3,x2,1 ; 递增 sc x3,0(x1),x4 ; 条件存储 bnez x4,try ; 存储失败则重试 ``` 这些指令通常通过一个寄存器跟踪 `lr` 指定的地址，常称为**保留寄存器（reserved register）**。发生中断，或者与该寄存器地址匹配的缓存块失效，例如由于另一个 `sc`，就清除这一寄存器；原文在此也称它为 link register。`sc` 只需检查自己的地址是否与保留寄存器匹配。匹配就成功，否则失败。由于对保留地址的其他存储尝试或任何异常，都可能导致条件存储失败，因此必须谨慎选择插在两条指令之间的指令。原书要求只允许寄存器—寄存器指令，以免出现处理器始终无法完成 `sc` 的死锁情形。此外，两条指令之间的指令数量应尽量少，以降低无关事件或竞争处理器使条件存储频繁失败的概率。[^lr-sc-notation] ## 利用一致性实现锁 有了原子操作，就可以利用多处理器的一致性机制实现**自旋锁（spin lock）**：处理器不断尝试取得锁，在循环中“自旋”，直至成功。程序员预计锁只持有很短时间，并希望锁可用时加锁延迟很低，便会采用自旋锁。因为它会占住处理器，在循环中等待锁释放，所以并不适用于所有场合。 最简单的实现，是把锁变量保存在内存中；没有缓存一致性时会采用这一方法。处理器不断用原子交换等操作尝试加锁，并检查交换返回的值是否表示锁空闲。释放锁只需向锁写入 0。下面为 x1 中保存地址的自旋锁加锁，`EXCH` 是前述原子交换序列的宏。 ```asm lockit: addi x2,R0,#1 ; 装入“已加锁”的值 EXCH x2,0(x1) ; 原子交换 bnez x2,lockit; 是否已经加锁？ ``` 如果多处理器支持缓存一致性，就可以缓存锁，并由一致性机制维护锁值。这样有两个优势。第一，自旋，也就是在紧循环中测试并尝试取得锁，可以在本地缓存副本上进行，而无须每次尝试都访问全局内存。第二，锁访问往往具有局部性：上一次使用锁的处理器，很快又会使用它。此时锁值可能仍在该处理器的缓存中，显著缩短加锁时间。 要获得第一项优势，即在本地副本上自旋而不必每次尝试都生成内存请求，需要改变上述简单过程。前面的循环每次交换都要求写入。如果多个处理器竞争锁，它们都会产生写操作，而且大多数会写未命中，因为每个处理器都试图取得锁变量的独占状态。 因此，应修改自旋过程，先持续读取锁的本地副本，直到看到锁可用，再用交换操作尝试取得锁。处理器不停读取和测试，直到值表明锁已释放。接着，它与所有同样处于“自旋等待”的进程竞争，看谁先锁住变量。所有进程都使用交换指令，读取旧值并写入 1。唯一胜者得到 0，其他竞争者得到胜者写入的 1。失败者还会继续把变量设置为已加锁值，但这没有关系。胜者执行锁后的代码，完成后向锁写入 0 以释放锁，下一轮竞争随即开始。代码如下，记住 0 表示未加锁，1 表示已加锁： ```asm lockit: ld x2,0(x1) ; 加载锁 bnez x2,lockit ; 不可用，继续自旋 addi x2,R0,#1 ; 装入“已加锁”的值 EXCH x2,0(x1) ; 交换 bnez x2,lockit ; 如果锁原值不为 0，则跳转 ``` 来看看这种方案怎样使用缓存一致性机制。图 5.21 列出多个进程用原子交换竞争锁时，处理器与总线或目录的操作。持锁处理器向锁写入 0 后，其他所有缓存副本失效，必须取回新值来更新自己的副本。其中一个缓存先取得未加锁值 0，再执行交换。等其他处理器的缓存未命中得到满足时，发现变量已加锁，只能继续测试和自旋。 | 步骤 | P0 | P1 | P2 | 步骤结束时锁变量的缓存一致性状态 | 总线／目录操作 | | ---: | --- | --- | --- | --- | --- | | 1 | 持有锁 | 开始自旋，测试 lock＝0 | 开始自旋，测试 lock＝0 | 共享 | 以任意次序满足 P1、P2 的缓存未命中；锁变量转为共享。 | | 2 | 将 lock 置为 0 | 收到失效请求 | 收到失效请求 | 独占（P0） | P0 发出锁变量的写失效。 | | 3 | | 缓存未命中 | 缓存未命中 | 共享 | 总线／目录处理 P2 的未命中；P0 写回；状态为共享。 | | 4 | | 总线／目录忙，等待 | lock＝0 测试成功 | 共享 | P2 的缓存未命中得到满足。 | | 5 | | lock＝0 | 执行交换，缓存未命中 | 共享 | P1 的缓存未命中得到满足。 | | 6 | | 执行交换，缓存未命中 | 完成交换：返回 0，并置 lock＝1 | 独占（P2） | 总线／目录处理 P2 的未命中；生成失效请求；锁变量为独占。 | | 7 | | 交换完成，返回 1，并置 lock＝1 | 进入临界区 | 独占（P1） | 总线／目录处理 P1 的未命中；发送失效请求，使 P2 写回。 | | 8 | | 自旋，测试 lock＝0 | | | 无。 | {#fig-5.21 num="5.21" caption="三个处理器 P0、P1、P2 的缓存一致性步骤与总线流量。假定采用写失效一致性。" .wide .expand} **图 5.21（续）。** P0 起初持有锁，第 1 步时锁值为 1，即已加锁；在第 1 步开始前，锁变量由 P0 独占。P0 退出并释放锁，第 2 步。P1、P2 竞争，看看谁在交换时读到未加锁值，第 3–5 步。P2 获胜并进入临界区，第 6、7 步；P1 尝试失败，开始自旋等待，第 7、8 步。真实系统中，这些事件耗时远超过八个时钟节拍，因为获取总线及响应未命中需要更长时间。到第 8 步后，这一过程可以重复，最终由 P2 再次取得独占访问权，将锁置为 0。 这个例子还说明保留加载/条件存储的另一个优势：读和写显式分离。保留加载不必产生总线流量，因此可以使用下面这个简单序列，达到优化后交换版本的同样效果。x1 保存锁地址，`lr` 代替 `LD`，`sc` 代替 `EXCH`。 ```asm lockit: lr x2,0(x1) ; 保留加载 bnez x2,lockit ; 不可用，继续自旋 addi x2,R0,#1 ; 已加锁值 sc x2,0(x1),x3 ; 存储 bnez x3,lockit ; 存储失败则跳转 ``` 第一个分支构成自旋循环；第二个分支处理两个处理器同时看到锁可用时的竞争。 [^lr-sc-notation]: **译注：** 本节代码保留原书的指令名、寄存器名、操作数顺序及立即数记法，仅翻译注释，未改写为某个汇编器的可执行语法。原文交替使用 reserved register 与 link register 指称跟踪保留地址的寄存器，译文明确保留这一用词关系。