I.4 同步：向更大规模扩展

本节先讨论较大规模多处理器中的同步性能问题，再讨论解决办法。

同步性能的挑战

要理解第 5 章介绍的简单自旋锁为什么难以扩展，可以设想一台大型多处理器中，全部处理器都争用同一把锁。目录或总线成为所有处理器必须串行通过的点，导致大量争用和通信流量。下面的例题展示情况可能有多糟。

例题 一条总线上有 10 个处理器，每个处理器同时尝试给一个变量加锁。假设每个总线事务，不论读未命中还是写未命中，都持续 100 个时钟周期。可以忽略对已在缓存中的锁实际读写所需的时间，也可以忽略持锁时间——这两项影响都不大！假设时刻 0 锁释放时，所有处理器都在自旋。求全部 10 个处理器依次获得锁所需的总线事务数，以及处理这 10 个请求大约需要多久。总线完全公平：所有未完成请求都先于新请求得到服务；各处理器速度相同。

解答 当有 $i$ 个进程争用锁时，它们依次执行下列动作，每个动作都产生一个总线事务：

• $i$ 次链接加载（load linked），用于访问锁。
• $i$ 次条件存储（store conditional），尝试获得锁。
• 1 次存储，释放锁。

因此，$i$ 个进程共需要 $2i+1$ 个总线事务。这里假定临界区执行时间可以忽略，因而锁会在其他条件存储失败的处理器再次尝试链接加载前释放。

对 $n$ 个进程，总线操作总数为：

对 10 个进程，共有 120 个总线事务，需要 12,000 个时钟周期；原书接着写作“每次获取锁 120 个时钟周期”。

译注： 最后一个平均值有算术错误：$12{,}000/10=1200$，即每次获取锁平均 1200 个时钟周期，不是 120。

例题中的困难来自锁争用、锁访问的串行化，以及总线访问延迟。总线的公平性实际上还使情况更糟，因为它推迟了获得锁的处理器释放锁的时机；遗憾的是，无论采用何种总线仲裁，都存在某种最坏情况。自旋锁原本的两个主要优点——占用较少的总线或网络周期，以及同一处理器反复使用锁时性能良好——在这个例子中都消失了。下一部分将考虑其他实现；在此之前，先看看如何用自旋锁实现另一种常见的高层同步原语。

屏障同步

带有并行循环的程序中，另一种常见同步操作是屏障（barrier）。屏障迫使各进程等待，直到所有进程都到达屏障，才一起放行。典型实现可以使用两个自旋等待机制：一个锁保护到达计数器，另一个让各进程等待，直到最后一个进程到达。实现屏障时，通常让进程反复检查变量，直到满足条件；这里用 spin(condition) 表示这一操作。图 I.2 给出一种典型实现，假设 lock、unlock 提供基本自旋锁，total 是必须到达屏障的进程数。

lock(counterlock);            /* 保证更新的原子性 */
if (count == 0) release = 0;   /* 第一个到达者重置 release */
count = count + 1;            /* 统计到达数量 */
unlock(counterlock);          /* 释放锁 */
if (count == total) {         /* 全部到达 */
    count = 0;                /* 重置计数器 */
    release = 1;              /* 放行进程 */
}
else {                       /* 还有进程未到 */
    spin(release == 1);       /* 等待其余进程到达 */
}

实际中还有一个因素会使屏障实现更复杂。屏障经常用在循环内：从屏障中放行的进程执行一些工作，随后再次到达同一屏障。假设某个进程实际上一直没有离开屏障，仍停留在 spin 操作中；例如，操作系统可能暂时调度了另一个进程。此时，某个进程可能跑得很快，在最后一个进程离开前，就再次到达屏障。这个“快”进程重置 release 标志，将仍未离开的“慢”进程困在屏障内。于是，所有进程都会在下一轮屏障中无限等待：一个进程仍被困在上一轮，计数永远无法达到 total。

这里重要的是，应用程序员没有做错任何事；出错的是屏障实现者，他对执行进展作了不能成立的假设。一种显然的解决办法是，在进程退出屏障时也进行计数，就像进入时一样；上一轮所有进程都离开之前，不允许任何进程再次进入并重新初始化屏障。但这个额外步骤会显著增加屏障延迟和争用，而我们很快就会看到，二者原本已经很大。另一种办法是sense-reversing barrier，即通过翻转标志含义来复用的屏障。它为每个进程设置私有变量 local_sense，初值为 1。图 I.3 给出代码。这个版本可以安全复用，但下面的例题表明，其性能仍然可能很差。

local_sense = !local_sense;       /* 翻转本地标志 */
lock(counterlock);               /* 保证更新的原子性 */
count = count + 1;               /* 统计到达数量 */
if (count == total) {            /* 全部到达 */
    count = 0;                   /* 重置计数器 */
    release = local_sense;       /* 放行进程 */
}
unlock(counterlock);             /* 解锁 */
spin(release == local_sense);    /* 等待信号 */
}

译注： 原图 I.3 末尾额外印有一个右花括号，未给出对应的左花括号。

例题 总线上有 10 个处理器，同时尝试执行屏障。与前例一样，每个总线事务为 100 个时钟周期。忽略对缓存中锁的实际读写时间，也忽略屏障实现中其他非同步操作的时间。求全部 10 个处理器到达屏障、获得放行并退出屏障所需的总线事务数。总线完全公平，所有待处理请求均先于新请求得到服务；处理器速度相同。不必考虑进程退出屏障时的计数。整个过程需要多久？

解答 假设 lock 和 unlock 用链接加载与条件存储实现。图 I.4 列出一个处理器通过屏障时的总线事件序列，假设最先抢到总线的进程尚未持锁。最后到达屏障的进程略有不同，见图注。

对于第 $i$ 个进程，总线事务数为 $3i+4$；最后到达的进程少一次。因此，对 $n$ 个进程，总线事务数为：

10 个进程需要 204 个总线周期，也就是 20,400 个时钟周期！该屏障操作花费的时间，接近 10 个处理器依次加锁、解锁所需时间的两倍。

这些例子表明，多进程之间存在严重争用时，同步性能确实可能成为瓶颈。如果争用很少，同步操作也不频繁，我们主要关心同步原语的延迟，即单个进程完成一次同步需要多久。基本自旋锁需要两个总线周期：一个首次读取锁，一个写入锁。可以通过多种方法将它减少到一个周期，例如直接在交换操作上自旋。如果锁几乎总是空闲，这样可能更好；但如果锁不空闲，每次尝试都会产生总线周期，造成大量总线流量。实际中，自旋锁延迟也没有前例表现得那么差，因为对缓存中已有数据项的写未命中会作为权限升级处理，比真正的读未命中便宜。

这些例子中更严重的问题是，每个进程完成同步的尝试都被串行化。有争用时，这会大幅增加完成同步的时间。例如，若全部 10 次加锁、解锁仅受无争用延迟制约，那么原文指出，完成同步只需 1000 个周期，而不是 15,000 个周期。屏障的情况同样糟糕，有些方面甚至更差，因为它极有可能产生争用。总线互连加剧了这些问题，但目录式多处理器中串行化也可能同样严重，而且延迟很大。下一部分介绍一些适用于高争用或处理器数量较多情况的解决办法。

译注： 这里的 15,000 个周期与前例算出的 12,000 个周期不一致；1000 的比较值也未说明具体计入哪些加锁、解锁事务。保留原文比较，不将它与前例强行合并成同一次计算。

面向更大规模多处理器的同步机制

我们希望同步机制在无争用时延迟低，在争用严重时又能尽量减少串行化。先讨论软件如何改善高争用下锁和屏障的性能，再介绍两种能够在维持低延迟的同时减少串行化的基本硬件原语。

软件实现

前述自旋锁实现的主要困难，是许多进程同时自旋时，由争用造成的延迟。一种办法是在进程获取锁失败时，主动让它延迟一段时间。每次获取失败后按指数增加延迟，可取得最佳性能。图 I.5 展示带指数退避的自旋锁。指数退避是减少共享资源争用的常用技术，也适用于共享网络与总线访问，见 F.4–F.8 节。该实现不延迟最初的自旋循环，以便在争用较小时维持低延迟。因此，即使有许多进程等待，退避也不影响它们第一次尝试获取锁。也可以延迟首次尝试，但如果只有两个进程使用锁、其中一个首次检查时恰好发现锁被占用，这样反而会损害性能。

        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:  使用由锁保护的数据

延迟可通过将 R3 值的一份副本逐次递减到 0 来实现。具体时间取决于多处理器，但初始时间单位应约等于执行临界区并释放锁所需的时间。PAUSE R3 应延迟 R3 个这样的时间单位。每次条件存储失败，R3 都乘以 2，让进程再次尝试前等待两倍的时间。争用处理器执行指令速率的微小差别，通常足以避免各进程持续碰撞。如果执行时间的自然扰动还不够，可以用一个较小随机值初始化 R3，增大连续退避时间的差异，降低连续碰撞的概率。

另一种技术是队列锁：把等待的处理器排成队列；每当一个处理器释放锁，就让队列中的下一个处理器尝试访问。这消除了释放锁时的争用。下一部分用硬件实现说明队列锁的工作原理；采用数组的软件实现，也能获得其中大部分收益。在介绍硬件原语之前，先看更好的屏障机制。

前述屏障在两个阶段都有争用：汇集阶段需要原子更新计数器，放行阶段则要求所有进程读取 release 标志。前者更严重，因为它要求对同步变量独占访问，产生更多串行化；后者相比之下只有读争用。可以用合并树（combining tree）减少争用：多个请求按树状结构在局部逐级合并。同样的合并树也可以用于放行，降低该阶段的争用。

这里的合并树屏障采用预先确定的多叉树结构，用 $k$ 表示汇入数；实践中 $k=4$ 效果不错。当第 $k$ 个进程到达某节点时，向树的上一层发信号；当一个进程到达根时，放行全部等待进程。与前例一样，仍采用 sense-reversing 技术。图 I.6 的树形屏障用树汇集进程，并用一个信号解除屏障。一些 MPP，如 T3D、CM-5，还提供了屏障硬件支持；较新的机器则依赖软件库。

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);

当第 $k$ 个进程到达树中一个节点时，它继续进入父节点，递增父节点的计数；原图注接着说，父节点计数达到 $k$ 时设置 release。每个节点的计数由最后到达的进程清零。与简单屏障一样，使用 sense-reversing 避免竞争。初始化树时，应将 tree[root].parent 设为 −1。

译注： 原图 I.6 是不完整的类 C 伪代码：if (count == k) 缺明确的闭合括号，barrier 定义有两个参数而两处调用只传一个，数组声明也使用区间记号。这段伪代码不能直接用作可编译实现。图注关于父节点计数达到 k 即设置 release 的说法，应结合递归代码中仅在根节点放行来理解。

硬件原语

下面考察两个硬件同步原语。第一个处理锁，第二个可用于屏障，以及其他需要计数或分配不同索引的用户层操作。两种情况下都能建立这样的硬件原语：延迟基本与前述版本一致，但串行化大幅减少，因此在争用时具有更好的扩展性。

最初锁实现的主要问题，是产生了大量不必要的争用。例如，锁释放时，所有处理器都会产生读未命中和写未命中，尽管至多只有一个处理器能成功拿到未锁定状态的锁。前例的十次加锁／解锁中，每次都会发生这种情况。

可以通过显式地把锁从一个等待处理器交给下一个，改善这一点。每次释放锁时，不再让所有处理器竞逐，而是保留等待者列表，到谁的轮次就把锁明确交给谁。这就是队列锁。它可以用本节所述硬件实现，也可以用数组跟踪等待进程，以软件实现；两者基本思想相同。这里的硬件实现假定使用目录式多处理器，能够按地址访问各处理器的缓存。在总线式多处理器中，软件实现更合适：让每个处理器为锁使用不同地址，就能将锁从一个进程显式传给另一个。

队列锁如何工作？第一次访问锁变量未命中时，将未命中请求发给同步控制器；控制器可以集成到存储器控制器中，例如总线式系统，也可以集成到目录控制器。如果锁空闲，就直接将它返回给处理器。如果不可用，控制器就记录该节点的请求，例如在向量中置一位，然后向处理器返回表示“已锁定”的值，让它在该值上自旋。锁释放时，控制器从等待列表中选出一个处理器继续执行。随后可以更新该处理器缓存中的锁变量，也可以使其副本失效，让处理器再次未命中并取回可用的锁。

例题 使用通过更新锁副本来交接的队列锁，让 10 个处理器依次加锁、解锁，需要多少总线事务、多少时间？系统的其他假设与前面的锁例题相同。

解答 对 $n$ 个处理器，每个处理器最初都尝试访问锁，产生一个总线事务；其中一个成功并释放锁，因此第一个处理器完成前共 $n+1$ 个事务。后续每个处理器需要两个事务：一个接收锁，一个释放锁。因此总事务数为：

现在事务数与争用处理器数呈线性关系，而不像此前自旋锁那样呈二次关系。10 个处理器需要 29 个总线周期，也就是 2900 个时钟周期。

实现这种队列锁，有几个关键点。首先，要能区分对锁的首次访问，以便执行入队操作；也要区分释放锁，以便把锁交给其他处理器。等待进程队列可以用多种机制实现。对于目录式多处理器，该队列类似共享者集合，可以用相似硬件实现目录和队列锁操作。一个复杂之处在于，硬件必须能够收回这样的锁：请求锁的进程可能已经被上下文切换，甚至不会再次被调度到同一个处理器。

队列锁可以改善屏障的性能。也可以引入一种原语，缩短递增屏障计数器所需的时间，减少这个瓶颈处的串行化，预期取得与队列锁类似的性能。一种用于这一目的、也用于构造其他同步操作的原语是 fetch-and-increment，即原子地取出变量并将其值加一。返回值既可以是增加后的值，也可以是原先取出的值。与简单的 sense-reversing 屏障相比，利用该原语可以显著改善屏障实现。

例题 用 fetch-and-increment 编写屏障代码。在与前例相同的假设下，另假设一次返回递增后值的 fetch-and-increment 操作耗时 100 个时钟周期，求 10 个处理器通过屏障的时间，以及所需总线周期数。

local_sense = !local_sense;       /* 翻转本地标志 */
fetch_and_increment(count);      /* 原子更新 */
if (count == total) {            /* 全部到达 */
    count = 0;                   /* 重置计数器 */
    release = local_sense;       /* 放行进程 */
}
else {                          /* 还有进程未到 */
    spin(release == local_sense); /* 等待信号 */
}

解答 代码如图 I.7。对 $n$ 个处理器，实现需要 $n$ 次 fetch-and-increment、$n$ 次访问 count 的缓存未命中，以及 $n$ 次放行操作的缓存未命中，共 $3n$ 个总线事务。10 个处理器需要 30 个总线事务，也就是 3000 个时钟周期。与队列锁一样，时间随处理器数线性增长。当然，fetch-and-increment 也可用于合并树屏障，减少各树节点处的串行化。

译注： 图 I.7 原代码没有保存原子操作的返回值，而是随后读取共享的 count；这与题设强调返回递增后值不一致，还可能让多个进程同时观察到 total 并竞争清零。实际实现需要用本次原子操作的返回值唯一确定最后到达者，并满足相应内存顺序要求。

如上所见，大规模多处理器中的同步问题可能相当尖锐。再把长内存访问延迟，以及计算中可能发生的负载不均衡考虑进来，就不难理解为什么高效利用大规模并行处理器如此具有挑战性。