集群范围上下电竞争避免算法¶

本文件记录了用于协调 CPU 和集群的启动与关闭操作，并安全管理硬件一致性（coherency）控制的算法。

“原理（Rationale）”一节解释了该算法的用途以及为什么需要它。“基本模型（Basic model）”通过系统的简化视图解释了通用概念。其他各节则解释了算法实际使用的具体细节。

设计初衷¶

在包含多个 CPU 的系统中，人们希望能够在系统空闲时关闭单个 CPU，以降低功耗和散热。

在包含多个 CPU 集群的系统中，人们同样希望具有关闭整个集群的能力。

关闭和打开整个集群是一项有风险的操作，因为它涉及到对一组独立运行的 CPU 执行可能具有破坏性的操作，而此时操作系统仍在继续运行。这意味着我们需要进行一些协调，以确保仅在真正安全的时候才执行关键的集群级操作。

简单的锁可能不足以解决这个问题，因为诸如 Linux 自旋锁（spinlocks）之类的机制可能依赖于在集群上电时不会立即启用的一致性机制。由于启用或禁用这些机制本身可能是一个非原子操作（例如写入某些硬件寄存器和使大型缓存失效），因此需要其他协调方法来保证集群级安全地下电和上电。

本文档中介绍的机制描述了一种基于一致性内存（coherent memory）的协议，用于执行所需的协调。它旨在尽可能轻量级，同时提供所需的安全性属性。

基本模型¶

每个集群和 CPU 都被分配了一个状态，如下所示

DOWN

COMING_UP

UP

GOING_DOWN

    +---------> UP ----------+
    |                        v

COMING_UP                GOING_DOWN

    ^                        |
    +--------- DOWN <--------+

DOWN: CPU 或集群不具备一致性（not coherent），并且已经断电或挂起，或者已准备好断电或挂起。
COMING_UP: CPU 或集群已承诺（committed）转入 UP 状态。它可能正处于初始化和启用一致性过程的某个阶段。
UP: CPU 或集群在硬件级别处于活动状态且具备一致性。处于此状态的 CPU 不一定正在被内核积极使用。
GOING_DOWN: CPU 或集群已承诺转入 DOWN 状态。它可能正处于拆除（teardown）和退出一致性过程的某个阶段。

在任何时间点，每个 CPU 都被指定了其中一个状态。CPU 状态将在下文的“CPU 状态”一节中描述。

每个集群也被指定了一个状态，但为了避免集群中不同 CPU 同时修改状态时产生竞争，必须将状态值拆分为两部分（“cluster”状态和“inbound”状态）并引入额外的状态。集群级状态将在“集群状态”一节中描述。

为了在本次讨论中帮助区分 CPU 状态和集群状态，CPU 状态的名称前会加上 CPU_ 前缀，而集群状态则会加上 CLUSTER_ 或 INBOUND_ 前缀。

CPU 状态¶

在该算法中，多核处理器中的每个独立核心都被称为“CPU”。假定 CPU 是单线程的：因此，在一个时间点上，一个 CPU 只能做一件事。

这意味着 CPU 高度符合基本模型。

该算法为系统中的每个 CPU 定义了以下状态

CPU_DOWN

CPU_COMING_UP

CPU_UP

CPU_GOING_DOWN

 cluster setup and
CPU setup complete          policy decision
      +-----------> CPU_UP ------------+
      |                                v

CPU_COMING_UP                   CPU_GOING_DOWN

      ^                                |
      +----------- CPU_DOWN <----------+
 policy decision           CPU teardown complete
or hardware event

这四种状态的定义与基本模型的状态紧密对应。

状态之间的转换如下发生。

触发事件（自发，spontaneous）意味着 CPU 仅由于取得了本地进展就可以转换到下一个状态，而不需要发生任何外部事件。

CPU_DOWN

当 CPU 准备好下电时，它会达到 CPU_DOWN 状态。达到此状态后，CPU 通常会通过 WFI 指令或固件调用自行下电或挂起。

下一个状态

CPU_COMING_UP

条件

无

触发事件

显式的硬件上电操作，由另一个 CPU 上的策略决策引起；
硬件事件，例如中断。

CPU_COMING_UP

在集群设置完毕并具备一致性之前，CPU 不能开始参与硬件一致性。如果集群尚未准备好，则 CPU 将在 CPU_COMING_UP 状态下等待，直到集群设置完毕。

下一个状态: CPU_UP
条件: CPU 的父集群必须处于 CLUSTER_UP 状态。
触发事件: 父集群转换为 CLUSTER_UP。

有关 CLUSTER_UP 状态的描述，请参阅“集群状态”一节。

CPU_UP

当 CPU 达到 CPU_UP 状态时，CPU 可以安全地开始参与本地一致性。

这是通过跳转到内核的 CPU 恢复（resume）代码来完成的。

请注意，此状态的定义与基本模型的定义略有不同：CPU_UP 并不意味着 CPU 已经具备一致性，但它确实意味着恢复内核是安全的。内核会处理其余的恢复过程，因此其余步骤作为竞争避免算法的一部分是不可见的。

CPU 将保持在此状态，直到作出关闭或挂起 CPU 的显式策略决策。

下一个状态: CPU_GOING_DOWN
条件: 无
触发事件: 显式策略决策

CPU_GOING_DOWN

在此状态下，CPU 退出一致性，包括实现这一点所需的任何操作（例如清理数据缓存）。

下一个状态: CPU_DOWN
条件: 本地 CPU 拆除完成
触发事件: （自发）

集群状态¶

集群是一组具有某些公共资源的相连 CPU。由于集群包含多个 CPU，它可以同时做多件事情。这带来了一些影响。特别是，当一个 CPU 正在拆除集群时，另一个 CPU 可能会启动。

在本次讨论中，“outbound（离开）侧”是正在拆除集群的 CPU 所看到的集群状态视图。“inbound（进入）侧”是正在设置集群的 CPU 所看到的集群状态视图。

为了在此类情况下实现安全的协调，重要的是：正在设置集群的 CPU 能够独立于正在拆除集群的 CPU 来宣告其状态。出于这个原因，集群状态被拆分为两部分

“cluster（集群）”状态：集群的全局状态；或者 outbound 侧的状态

CLUSTER_DOWN

CLUSTER_UP

CLUSTER_GOING_DOWN

“inbound（入站）”状态：inbound 侧的集群状态。

INBOUND_NOT_COMING_UP

INBOUND_COMING_UP

这些状态的不同配对导致整个集群有六种可能的状态
                          CLUSTER_UP
        +==========> INBOUND_NOT_COMING_UP -------------+
        #                                               |
                                                        |
   CLUSTER_UP     <----+                                |
INBOUND_COMING_UP      |                                v

        ^             CLUSTER_GOING_DOWN       CLUSTER_GOING_DOWN
        #              INBOUND_COMING_UP <=== INBOUND_NOT_COMING_UP

  CLUSTER_DOWN         |                                |
INBOUND_COMING_UP <----+                                |
                                                        |
        ^                                               |
        +===========     CLUSTER_DOWN      <------------+
                     INBOUND_NOT_COMING_UP
转换 -----> 只能由 outbound CPU 进行，并且只涉及对“cluster”状态的更改。

转换 ===##> 只能由 inbound CPU 进行，并且只涉及对“inbound”状态的更改，但在 outbound 侧不可能再发生进一步转换的情况除外（即 outbound CPU 已将集群置于 CLUSTER_DOWN 状态）。

竞争避免算法没有提供确定集群内的哪些具体 CPU 扮演这些角色的方法。这必须通过其他手段提前决定。更多解释请参阅“最后一人与第一人选择”一节。

CLUSTER_DOWN/INBOUND_NOT_COMING_UP 是集群实际上可以断电的唯一状态。

通过从 CLUSTER_GOING_DOWN/ INBOUND_NOT_COMING_UP（对应于基本模型中的 GOING_DOWN）到 CLUSTER_DOWN/INBOUND_COMING_UP（对应于基本模型中的 COMING_UP）存在两条不同路径，可以看出 inbound 和 outbound CPU 的并行性。第二条路径完全避免了集群拆除。

CLUSTER_UP/INBOUND_COMING_UP 相当于基本模型中的 UP。最终转换为 CLUSTER_UP/INBOUND_NOT_COMING_UP 是微不足道的，它只是重置状态机以准备好下一个周期。

允许转换的细节如下。

每种情况下的下一个状态记为

<集群状态>/<inbound 状态> (<转换者>)

其中 <转换者> 是可以发生转换的一侧；即 inbound 或 outbound 侧。

CLUSTER_DOWN/INBOUND_NOT_COMING_UP

下一个状态

CLUSTER_DOWN/INBOUND_COMING_UP (inbound)

条件

无

触发事件

显式的硬件上电操作，由另一个 CPU 上的策略决策引起；
硬件事件，例如中断。

CLUSTER_DOWN/INBOUND_COMING_UP

在此状态下，inbound CPU 设置集群，包括在集群级别启用硬件一致性以及实现此目的所需的任何其他操作（例如缓存失效）。

此状态的目的是进行足够的集群级设置，以使集群中的其他 CPU 能够安全地进入一致性。

下一个状态
CLUSTER_UP/INBOUND_COMING_UP (inbound)

条件
集群级设置和硬件一致性完成

触发事件
（自发）

CLUSTER_UP/INBOUND_COMING_UP

集群级设置已完成，并且已为集群启用硬件一致性。集群中的其他 CPU 可以安全地进入一致性。

这是一个瞬态（transient）状态，立即通向 CLUSTER_UP/INBOUND_NOT_COMING_UP。集群上的所有其他 CPU 都应将这两种状态视为等效。

下一个状态
CLUSTER_UP/INBOUND_NOT_COMING_UP (inbound)

条件
无

触发事件
（自发）

CLUSTER_UP/INBOUND_NOT_COMING_UP

集群级设置已完成，并且已为集群启用硬件一致性。集群中的其他 CPU 可以安全地进入一致性。

集群将保持在此状态，直到作出将集群下电的策略决策。

下一个状态
CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP (outbound)

条件
无

触发事件
将集群下电的策略决策

CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP

outbound CPU 正在拆除集群。所选的 CPU 必须在此状态下等待，直到集群中的所有 CPU 都处于 CPU_DOWN 状态。

当所有 CPU 都处于 CPU_DOWN 状态时，可以拆除集群，例如通过清理数据缓存和退出集群级一致性。

为了避免浪费且不必要的拆除操作，outbound 应检查 inbound 集群状态是否存在向 INBOUND_COMING_UP 的异步转换。或者，可以检查各个 CPU 是否进入了 CPU_COMING_UP 或 CPU_UP。

下一个状态

CLUSTER_DOWN/INBOUND_NOT_COMING_UP (outbound)

条件
集群已拆除并准备好断电

触发事件
（自发）

CLUSTER_GOING_DOWN/INBOUND_COMING_UP (inbound)

条件
无

触发事件

显式的硬件上电操作，由另一个 CPU 上的策略决策引起；

硬件事件，例如中断。

CLUSTER_GOING_DOWN/INBOUND_COMING_UP

集群正在（或曾经）被拆除，但与此同时另一个 CPU 已上线，并正尝试再次设置集群。

如果 outbound CPU 观察到此状态，它有两个选择

退出拆除操作，将集群恢复到 CLUSTER_UP 状态；

完成集群拆除并将集群置于 CLUSTER_DOWN 状态；inbound CPU 将从该状态再次设置集群。

在集群实际上不会下电的情况下，选项 (a) 通过避免不必要的拆除和设置操作来减少一些延迟。

下一个状态

CLUSTER_UP/INBOUND_COMING_UP (outbound)

条件
集群级设置和硬件一致性完成

触发事件
（自发）

CLUSTER_DOWN/INBOUND_COMING_UP (outbound)

条件
集群已拆除并准备好断电

触发事件
（自发）

最后一人（Last man）与第一人（First man）的选择¶

在 outbound 侧执行集群拆除操作的 CPU 通常被称为“最后一人（last man）”。

在 inbound 侧执行集群设置的 CPU 通常被称为“第一人（first man）”。

上文记录的竞争避免算法没有提供选择哪些 CPU 应扮演这些角色的机制。

最后一人

在关闭集群时，涉及的所有 CPU 最初都在执行 Linux，因此具备一致性。因此，在 CPU 变得不具备一致性之前，可以使用普通的自旋锁来安全地选择最后一人。

第一人

由于 CPU 可能会响应外部唤醒事件而异步上电，因此需要一种动态机制来确保只有一个 CPU 尝试扮演第一人角色并进行集群级初始化：任何其他 CPU 都必须等待此过程完成后才能继续。

集群级初始化可能涉及诸如在总线结构（bus fabric）中配置一致性控制之类的操作。

mcpm_head.S 中的当前实现使用单独的互斥机制来进行此仲裁。该机制在 vlocks for Bare-Metal Mutual Exclusion 中有详细文档记录。

特性与限制¶

实现

当前基于 ARM 的实现分散在 arch/arm/common/mcpm_head.S（低级 inbound CPU 操作）和 arch/arm/common/mcpm_entry.c（其他所有内容）之间

__mcpm_cpu_going_down() 发出 CPU 转换到 CPU_GOING_DOWN 状态的信号。

__mcpm_cpu_down() 发出 CPU 转换到 CPU_DOWN 状态的信号。

CPU 通过 mcpm_head.S 中的低级上电代码转换到 CPU_COMING_UP，然后转换到 CPU_UP。这可能涉及 CPU 特定的设置代码，但在当前实现中没有。

__mcpm_outbound_enter_critical() 和 __mcpm_outbound_leave_critical() 处理从 CLUSTER_UP 到 CLUSTER_GOING_DOWN 的转换，以及从那里到 CLUSTER_DOWN 或返回 CLUSTER_UP（在集群下电中止的情况下）的转换。

由于在集群级别进行安全转换所需的额外 CPU 间协调，这些函数比 __mcpm_cpu_*() 函数更复杂。

集群通过 mcpm_head.S 中的低级上电代码从 CLUSTER_DOWN 转换回 CLUSTER_UP。这通常涉及平台特定的设置代码，该代码由通过 mcpm_sync_init 注册的平台特定 power_up_setup 函数提供。

深层拓扑

按照目前的描述和实现，该算法不支持涉及两个以上级别的 CPU 拓扑（即不支持集群的集群）。该算法可以通过为附加的拓扑级别复制集群级状态，并修改中间（非最外层）集群级别的转换规则来扩展。

题记¶

最初由 Linaro Limited 的 Dave Martin 创建并记录，由 Nicolas Pitre 和 Achin Gupta 协作完成。

Linux 内核

目录

本页