# I.4 同步：向更大规模扩展 本节先讨论较大规模多处理器中的同步性能问题，再讨论解决办法。 ## 同步性能的挑战 要理解第 5 章介绍的简单自旋锁为什么难以扩展，可以设想一台大型多处理器中，全部处理器都争用同一把锁。目录或总线成为所有处理器必须串行通过的点，导致大量争用和通信流量。下面的例题展示情况可能有多糟。 **例题** 一条总线上有 10 个处理器，每个处理器同时尝试给一个变量加锁。假设每个总线事务，不论读未命中还是写未命中，都持续 100 个时钟周期。可以忽略对已在缓存中的锁实际读写所需的时间，也可以忽略持锁时间——这两项影响都不大！假设时刻 0 锁释放时，所有处理器都在自旋。求全部 10 个处理器依次获得锁所需的总线事务数，以及处理这 10 个请求大约需要多久。总线完全公平：所有未完成请求都先于新请求得到服务；各处理器速度相同。 **解答** 当有 \(i\) 个进程争用锁时，它们依次执行下列动作，每个动作都产生一个总线事务： - \(i\) 次链接加载（load linked），用于访问锁。 - \(i\) 次条件存储（store conditional），尝试获得锁。 - 1 次存储，释放锁。 因此，\(i\) 个进程共需要 \(2i+1\) 个总线事务。这里假定临界区执行时间可以忽略，因而锁会在其他条件存储失败的处理器再次尝试链接加载前释放。 对 \(n\) 个进程，总线操作总数为： $$ \sum_{i=1}^{n}(2i+1)=n(n+1)+n=n^2+2n $$ 对 10 个进程，共有 120 个总线事务，需要 12,000 个时钟周期；原书接着写作“每次获取锁 120 个时钟周期”。 > **译注：** 最后一个平均值有算术错误：\(12{,}000/10=1200\)，即每次获取锁平均 1200 个时钟周期，不是 120。 例题中的困难来自锁争用、锁访问的串行化，以及总线访问延迟。总线的公平性实际上还使情况更糟，因为它推迟了获得锁的处理器释放锁的时机；遗憾的是，无论采用何种总线仲裁，都存在某种最坏情况。自旋锁原本的两个主要优点——占用较少的总线或网络周期，以及同一处理器反复使用锁时性能良好——在这个例子中都消失了。下一部分将考虑其他实现；在此之前，先看看如何用自旋锁实现另一种常见的高层同步原语。 ### 屏障同步 带有并行循环的程序中，另一种常见同步操作是**屏障**（barrier）。屏障迫使各进程等待，直到所有进程都到达屏障，才一起放行。典型实现可以使用两个自旋等待机制：一个锁保护到达计数器，另一个让各进程等待，直到最后一个进程到达。实现屏障时，通常让进程反复检查变量，直到满足条件；这里用 `spin(condition)` 表示这一操作。图 I.2 给出一种典型实现，假设 `lock`、`unlock` 提供基本自旋锁，`total` 是必须到达屏障的进程数。 ~~~c lock(counterlock); /* 保证更新的原子性 */ if (count == 0) release = 0; /* 第一个到达者重置 release */ count = count + 1; /* 统计到达数量 */ unlock(counterlock); /* 释放锁 */ if (count == total) { /* 全部到达 */ count = 0; /* 重置计数器 */ release = 1; /* 放行进程 */ } else { /* 还有进程未到 */ spin(release == 1); /* 等待其余进程到达 */ } ~~~ {#fig-I.2 .wide .expand num="I.2" caption="简单屏障的代码。counterlock 保护计数器，使它可以原子递增；count 记录已到达的进程数；release 让进程等待，直到最后一个进程到达。spin(release == 1) 使进程等到所有进程到达屏障。"} 实际中还有一个因素会使屏障实现更复杂。屏障经常用在循环内：从屏障中放行的进程执行一些工作，随后再次到达同一屏障。假设某个进程实际上一直没有离开屏障，仍停留在 `spin` 操作中；例如，操作系统可能暂时调度了另一个进程。此时，某个进程可能跑得很快，在最后一个进程离开前，就再次到达屏障。这个“快”进程重置 `release` 标志，将仍未离开的“慢”进程困在屏障内。于是，所有进程都会在下一轮屏障中无限等待：一个进程仍被困在上一轮，计数永远无法达到 `total`。 这里重要的是，应用程序员没有做错任何事；出错的是屏障实现者，他对执行进展作了不能成立的假设。一种显然的解决办法是，在进程退出屏障时也进行计数，就像进入时一样；上一轮所有进程都离开之前，不允许任何进程再次进入并重新初始化屏障。但这个额外步骤会显著增加屏障延迟和争用，而我们很快就会看到，二者原本已经很大。另一种办法是**sense-reversing barrier**，即通过翻转标志含义来复用的屏障。它为每个进程设置私有变量 `local_sense`，初值为 1。图 I.3 给出代码。这个版本可以安全复用，但下面的例题表明，其性能仍然可能很差。 ~~~c local_sense = !local_sense; /* 翻转本地标志 */ lock(counterlock); /* 保证更新的原子性 */ count = count + 1; /* 统计到达数量 */ if (count == total) { /* 全部到达 */ count = 0; /* 重置计数器 */ release = local_sense; /* 放行进程 */ } unlock(counterlock); /* 解锁 */ spin(release == local_sense); /* 等待信号 */ } ~~~ {#fig-I.3 .wide .expand num="I.3" caption="sense-reversing 屏障的代码。让控制退出的 release 标志交替取值，是使屏障可以复用的关键。某个进程即使提前进入下一轮，也不会像图 I.2 那样重置 release、困住仍在上一轮中的其他进程。"} > **译注：** 原图 I.3 末尾额外印有一个右花括号，未给出对应的左花括号。 **例题** 总线上有 10 个处理器，同时尝试执行屏障。与前例一样，每个总线事务为 100 个时钟周期。忽略对缓存中锁的实际读写时间，也忽略屏障实现中其他非同步操作的时间。求全部 10 个处理器到达屏障、获得放行并退出屏障所需的总线事务数。总线完全公平，所有待处理请求均先于新请求得到服务；处理器速度相同。不必考虑进程退出屏障时的计数。整个过程需要多久？ **解答** 假设 `lock` 和 `unlock` 用链接加载与条件存储实现。图 I.4 列出一个处理器通过屏障时的总线事件序列，假设最先抢到总线的进程尚未持锁。最后到达屏障的进程略有不同，见图注。 对于第 \(i\) 个进程，总线事务数为 \(3i+4\)；最后到达的进程少一次。因此，对 \(n\) 个进程，总线事务数为： $$ \left(\sum_{i=1}^{n}(3i+4)\right)-1=\frac{3n^2+11n}{2}-1 $$ 10 个进程需要 204 个总线周期，也就是 20,400 个时钟周期！该屏障操作花费的时间，接近 10 个处理器依次加锁、解锁所需时间的两倍。 | 事件 | 进程 \(i\) 的次数 | 对应源码行 | 说明 | | --- | ---: | --- | --- | | `LL counterlock` | \(i\) | `lock(counterlock);` | 所有进程尝试获取锁。 | | 条件存储 | \(i\) | `lock(counterlock);` | 所有进程尝试获取锁。 | | `LD count` | 1 | `count = count + 1;` | 成功获得锁的进程。 | | 链接加载 | \(i-1\) | `lock(counterlock);` | 未成功的进程再次尝试。 | | `SD count` | 1 | `count = count + 1;` | 因获得独占访问权而未命中。 | | `SD counterlock` | 1 | `unlock(counterlock);` | 获取锁数据时发生未命中。 | | `LD release` | 2 | `spin(release == local_sense);` | 读取 release：首次读取时未命中，最终被写入后再未命中一次。 | {#fig-I.4 .wide .expand num="I.4" caption="第 i 个进程到达屏障时，需要总线事务的动作。最后到达的进程少一个事务，因为它在自旋中读取 release 会命中缓存。"} 这些例子表明，多进程之间存在严重争用时，同步性能确实可能成为瓶颈。如果争用很少，同步操作也不频繁，我们主要关心同步原语的延迟，即单个进程完成一次同步需要多久。基本自旋锁需要两个总线周期：一个首次读取锁，一个写入锁。可以通过多种方法将它减少到一个周期，例如直接在交换操作上自旋。如果锁几乎总是空闲，这样可能更好；但如果锁不空闲，每次尝试都会产生总线周期，造成大量总线流量。实际中，自旋锁延迟也没有前例表现得那么差，因为对缓存中已有数据项的写未命中会作为权限升级处理，比真正的读未命中便宜。 这些例子中更严重的问题是，每个进程完成同步的尝试都被串行化。有争用时，这会大幅增加完成同步的时间。例如，若全部 10 次加锁、解锁仅受无争用延迟制约，那么原文指出，完成同步只需 1000 个周期，而不是 15,000 个周期。屏障的情况同样糟糕，有些方面甚至更差，因为它极有可能产生争用。总线互连加剧了这些问题，但目录式多处理器中串行化也可能同样严重，而且延迟很大。下一部分介绍一些适用于高争用或处理器数量较多情况的解决办法。 > **译注：** 这里的 15,000 个周期与前例算出的 12,000 个周期不一致；1000 的比较值也未说明具体计入哪些加锁、解锁事务。保留原文比较，不将它与前例强行合并成同一次计算。 ## 面向更大规模多处理器的同步机制 我们希望同步机制在无争用时延迟低，在争用严重时又能尽量减少串行化。先讨论软件如何改善高争用下锁和屏障的性能，再介绍两种能够在维持低延迟的同时减少串行化的基本硬件原语。 ### 软件实现 前述自旋锁实现的主要困难，是许多进程同时自旋时，由争用造成的延迟。一种办法是在进程获取锁失败时，主动让它延迟一段时间。每次获取失败后按指数增加延迟，可取得最佳性能。图 I.5 展示带**指数退避**的自旋锁。指数退避是减少共享资源争用的常用技术，也适用于共享网络与总线访问，见 F.4–F.8 节。该实现不延迟最初的自旋循环，以便在争用较小时维持低延迟。因此，即使有许多进程等待，退避也不影响它们第一次尝试获取锁。也可以延迟首次尝试，但如果只有两个进程使用锁、其中一个首次检查时恰好发现锁被占用，这样反而会损害性能。 ~~~asm DADDUI R3,R0,#1 ; R3 = 初始延迟 lockit: LL R2,0(R1) ; 链接加载 BNEZ R2,lockit ; 不可用：自旋 DADDUI R2,R2,#1 ; 取得表示已加锁的值 SC R2,0(R1) ; 条件存储 BNEZ R2,gotit ; 存储成功则跳转 DSLL R3,R3,#1 ; 延迟扩大两倍 PAUSE R3 ; 按 R3 的值延迟 J lockit gotit: 使用由锁保护的数据 ~~~ {#fig-I.5 .wide .expand num="I.5" caption="采用指数退避的自旋锁。条件存储失败后，进程按 R3 中的值延迟。"} 延迟可通过将 R3 值的一份副本逐次递减到 0 来实现。具体时间取决于多处理器，但初始时间单位应约等于执行临界区并释放锁所需的时间。`PAUSE R3` 应延迟 R3 个这样的时间单位。每次条件存储失败，R3 都乘以 2，让进程再次尝试前等待两倍的时间。争用处理器执行指令速率的微小差别，通常足以避免各进程持续碰撞。如果执行时间的自然扰动还不够，可以用一个较小随机值初始化 R3，增大连续退避时间的差异，降低连续碰撞的概率。 另一种技术是**队列锁**：把等待的处理器排成队列；每当一个处理器释放锁，就让队列中的下一个处理器尝试访问。这消除了释放锁时的争用。下一部分用硬件实现说明队列锁的工作原理；采用数组的软件实现，也能获得其中大部分收益。在介绍硬件原语之前，先看更好的屏障机制。 前述屏障在两个阶段都有争用：汇集阶段需要原子更新计数器，放行阶段则要求所有进程读取 `release` 标志。前者更严重，因为它要求对同步变量独占访问，产生更多串行化；后者相比之下只有读争用。可以用**合并树**（combining tree）减少争用：多个请求按树状结构在局部逐级合并。同样的合并树也可以用于放行，降低该阶段的争用。 这里的合并树屏障采用预先确定的多叉树结构，用 \(k\) 表示汇入数；实践中 \(k=4\) 效果不错。当第 \(k\) 个进程到达某节点时，向树的上一层发信号；当一个进程到达根时，放行全部等待进程。与前例一样，仍采用 sense-reversing 技术。图 I.6 的树形屏障用树汇集进程，并用一个信号解除屏障。一些 MPP，如 T3D、CM-5，还提供了屏障硬件支持；较新的机器则依赖软件库。 ~~~c struct node { /* 合并树中的一个节点 */ int counterlock; /* 此节点的锁 */ int count; /* 此节点的计数器 */ int parent; /* 父节点：除根外为 0..P-1 */ }; struct node tree[0..P-1]; /* 节点组成的树 */ int local_sense; /* 每个处理器私有 */ int release; /* 全局放行标志 */ /* 实现屏障的函数 */ barrier(int mynode, int local_sense) { lock(tree[mynode].counterlock); /* 保护计数器 */ tree[mynode].count = tree[mynode].count + 1; /* 计数器递增 */ if (tree[mynode].count == k) { /* 此节点全部到达 */ if (tree[mynode].parent >= 0) { barrier(tree[mynode].parent); } else { release = local_sense; }; tree[mynode].count = 0; /* 为下一次重置 */ unlock(tree[mynode].counterlock); /* 解锁 */ spin(release == local_sense); /* 等待 */ }; /* 处理器进入屏障时执行的代码 */ local_sense = !local_sense; barrier(mynode); ~~~ {#fig-I.6 .wide .expand num="I.6" caption="树形屏障能够显著减少争用。假设事先用 tree 数组中的节点静态建好树。每个节点汇集 k 个进程，并具有单独的计数器与锁，因此每节点最多只有 k 个进程争用。"} 当第 \(k\) 个进程到达树中一个节点时，它继续进入父节点，递增父节点的计数；原图注接着说，父节点计数达到 \(k\) 时设置 `release`。每个节点的计数由最后到达的进程清零。与简单屏障一样，使用 sense-reversing 避免竞争。初始化树时，应将 `tree[root].parent` 设为 −1。 > **译注：** 原图 I.6 是不完整的类 C 伪代码：`if (count == k)` 缺明确的闭合括号，`barrier` 定义有两个参数而两处调用只传一个，数组声明也使用区间记号。这段伪代码不能直接用作可编译实现。图注关于父节点计数达到 k 即设置 release 的说法，应结合递归代码中仅在根节点放行来理解。 ### 硬件原语 下面考察两个硬件同步原语。第一个处理锁，第二个可用于屏障，以及其他需要计数或分配不同索引的用户层操作。两种情况下都能建立这样的硬件原语：延迟基本与前述版本一致，但串行化大幅减少，因此在争用时具有更好的扩展性。 最初锁实现的主要问题，是产生了大量不必要的争用。例如，锁释放时，所有处理器都会产生读未命中和写未命中，尽管至多只有一个处理器能成功拿到未锁定状态的锁。前例的十次加锁／解锁中，每次都会发生这种情况。 可以通过显式地把锁从一个等待处理器交给下一个，改善这一点。每次释放锁时，不再让所有处理器竞逐，而是保留等待者列表，到谁的轮次就把锁明确交给谁。这就是队列锁。它可以用本节所述硬件实现，也可以用数组跟踪等待进程，以软件实现；两者基本思想相同。这里的硬件实现假定使用目录式多处理器，能够按地址访问各处理器的缓存。在总线式多处理器中，软件实现更合适：让每个处理器为锁使用不同地址，就能将锁从一个进程显式传给另一个。 队列锁如何工作？第一次访问锁变量未命中时，将未命中请求发给同步控制器；控制器可以集成到存储器控制器中，例如总线式系统，也可以集成到目录控制器。如果锁空闲，就直接将它返回给处理器。如果不可用，控制器就记录该节点的请求，例如在向量中置一位，然后向处理器返回表示“已锁定”的值，让它在该值上自旋。锁释放时，控制器从等待列表中选出一个处理器继续执行。随后可以更新该处理器缓存中的锁变量，也可以使其副本失效，让处理器再次未命中并取回可用的锁。 **例题** 使用通过更新锁副本来交接的队列锁，让 10 个处理器依次加锁、解锁，需要多少总线事务、多少时间？系统的其他假设与前面的锁例题相同。 **解答** 对 \(n\) 个处理器，每个处理器最初都尝试访问锁，产生一个总线事务；其中一个成功并释放锁，因此第一个处理器完成前共 \(n+1\) 个事务。后续每个处理器需要两个事务：一个接收锁，一个释放锁。因此总事务数为： $$ (n+1)+2(n-1)=3n-1 $$ 现在事务数与争用处理器数呈线性关系，而不像此前自旋锁那样呈二次关系。10 个处理器需要 29 个总线周期，也就是 2900 个时钟周期。 实现这种队列锁，有几个关键点。首先，要能区分对锁的首次访问，以便执行入队操作；也要区分释放锁，以便把锁交给其他处理器。等待进程队列可以用多种机制实现。对于目录式多处理器，该队列类似共享者集合，可以用相似硬件实现目录和队列锁操作。一个复杂之处在于，硬件必须能够收回这样的锁：请求锁的进程可能已经被上下文切换，甚至不会再次被调度到同一个处理器。 队列锁可以改善屏障的性能。也可以引入一种原语，缩短递增屏障计数器所需的时间，减少这个瓶颈处的串行化，预期取得与队列锁类似的性能。一种用于这一目的、也用于构造其他同步操作的原语是 **fetch-and-increment**，即原子地取出变量并将其值加一。返回值既可以是增加后的值，也可以是原先取出的值。与简单的 sense-reversing 屏障相比，利用该原语可以显著改善屏障实现。 **例题** 用 fetch-and-increment 编写屏障代码。在与前例相同的假设下，另假设一次返回递增后值的 fetch-and-increment 操作耗时 100 个时钟周期，求 10 个处理器通过屏障的时间，以及所需总线周期数。 ~~~c local_sense = !local_sense; /* 翻转本地标志 */ fetch_and_increment(count); /* 原子更新 */ if (count == total) { /* 全部到达 */ count = 0; /* 重置计数器 */ release = local_sense; /* 放行进程 */ } else { /* 还有进程未到 */ spin(release == local_sense); /* 等待信号 */ } ~~~ {#fig-I.7 .wide .expand num="I.7" caption="采用 fetch-and-increment 计数的 sense-reversing 屏障。"} **解答** 代码如图 I.7。对 \(n\) 个处理器，实现需要 \(n\) 次 fetch-and-increment、\(n\) 次访问 `count` 的缓存未命中，以及 \(n\) 次放行操作的缓存未命中，共 \(3n\) 个总线事务。10 个处理器需要 30 个总线事务，也就是 3000 个时钟周期。与队列锁一样，时间随处理器数线性增长。当然，fetch-and-increment 也可用于合并树屏障，减少各树节点处的串行化。 > **译注：** 图 I.7 原代码没有保存原子操作的返回值，而是随后读取共享的 count；这与题设强调返回递增后值不一致，还可能让多个进程同时观察到 total 并竞争清零。实际实现需要用本次原子操作的返回值唯一确定最后到达者，并满足相应内存顺序要求。 如上所见，大规模多处理器中的同步问题可能相当尖锐。再把长内存访问延迟，以及计算中可能发生的负载不均衡考虑进来，就不难理解为什么高效利用大规模并行处理器如此具有挑战性。