集群范围的启动/关闭竞争避免算法¶

本文档介绍了用于协调 CPU 和集群的设置和拆卸操作，以及安全管理硬件一致性控制的算法。

“原理”部分解释了该算法的用途及其必要性。“基本模型”使用系统的简化视图解释了通用概念。其他部分解释了正在使用的算法的实际细节。

原理¶

在包含多个 CPU 的系统中，需要能够在系统空闲时关闭单个 CPU，从而降低功耗和散热。

在包含多个 CPU 集群的系统中，还需要能够关闭整个集群。

打开和关闭整个集群是一项危险的操作，因为它涉及执行可能破坏正在独立运行的 CPU 组的操作，同时操作系统继续运行。这意味着我们需要一些协调，以确保仅在真正安全的情况下执行关键的集群级操作。

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

本文档中介绍的机制描述了一种基于连贯内存的协议，用于执行所需的协调。它的目标是在提供所需安全属性的同时，尽可能轻量。

基本模型¶

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

DOWN（关闭）

COMING_UP（启动中）

UP（启动）

GOING_DOWN（关闭中）

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

COMING_UP                GOING_DOWN

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

DOWN（关闭）: CPU 或集群不连贯，并且已断电或挂起，或者准备断电或挂起。
COMING_UP（启动中）: CPU 或集群已承诺移动到 UP 状态。它可能正在进行初始化和启用连贯性的过程。
UP（启动）: CPU 或集群在硬件级别是活动且连贯的。处于此状态的 CPU 不一定会被内核主动使用。
GOING_DOWN（关闭中）: CPU 或集群已承诺移动到 DOWN 状态。它可能正在进行拆卸和连贯性退出的过程。

每个 CPU 在任何时间点都被分配了这些状态之一。CPU 状态在下面的“CPU 状态”部分中介绍。

每个集群也被分配一个状态，但是有必要将状态值拆分为两个部分（“集群”状态和“入站”状态），并引入其他状态，以避免集群中不同 CPU 同时修改状态之间的竞争。集群级状态在“集群状态”部分中介绍。

为了帮助区分本讨论中的 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

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

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

触发事件（自发）意味着 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 恢复代码来完成的。

请注意，此状态的定义与基本模型定义略有不同：CPU_UP 并不表示 CPU 已连贯，但确实意味着可以安全地恢复内核。内核处理其余的恢复过程，因此其余步骤在竞争避免算法中不可见。

CPU 保持此状态，直到做出明确的策略决定以关闭或挂起 CPU。

下一个状态: CPU_GOING_DOWN
条件: 无
触发事件: 明确的策略决定

CPU_GOING_DOWN

在此状态下，CPU 退出连贯性，包括实现此目的所需的任何操作（例如清除数据缓存）。

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

集群状态¶

集群是一组具有一些公共资源的连接 CPU。由于集群包含多个 CPU，因此它可以同时执行多项操作。这有一些含义。特别是，一个 CPU 可以在另一个 CPU 拆卸集群时启动。

在此讨论中，“出站侧”是拆卸集群的 CPU 所看到的集群状态视图。“入站侧”是设置 CPU 的 CPU 所看到的集群状态视图。

为了在这种情况下实现安全协调，重要的是，正在设置集群的 CPU 可以独立于正在拆卸集群的 CPU 来声明其状态。因此，集群状态分为两个部分

“集群”状态：集群的全局状态；或出站侧的状态

CLUSTER_DOWN

CLUSTER_UP

CLUSTER_GOING_DOWN

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

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
转换 -----> 只能由出站 CPU 执行，并且仅涉及更改“集群”状态。

转换 ===##> 只能由入站 CPU 执行，并且仅涉及更改“入站”状态，除非出站侧没有进一步的转换（即，出站 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）存在两条不同的路径，观察到入站和出站 CPU 的并行性。第二条路径完全避免了集群拆卸。

CLUSTER_UP/INBOUND_COMING_UP 等效于基本模型中的 UP。最终转换为 CLUSTER_UP/INBOUND_NOT_COMING_UP 是微不足道的，只是重置状态机以准备下一次循环。

允许的转换的详细信息如下。

在每种情况下，下一个状态都被标记为

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

其中 <转换者> 是可以发生转换的一侧；入站侧或出站侧。

CLUSTER_DOWN/INBOUND_NOT_COMING_UP

下一个状态

CLUSTER_DOWN/INBOUND_COMING_UP (入站)

条件

无

触发事件

显式的硬件启动操作，由另一 CPU 上的策略决定导致；
硬件事件，例如中断。

CLUSTER_DOWN/INBOUND_COMING_UP

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

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

下一个状态
CLUSTER_UP/INBOUND_COMING_UP (入站)

条件
集群级设置和硬件连贯性完成

触发事件
（自发）

CLUSTER_UP/INBOUND_COMING_UP

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

这是一个瞬态状态，会立即导致 CLUSTER_UP/INBOUND_NOT_COMING_UP。集群上的所有其他 CPU 都应将这两个状态视为等效状态。

下一个状态
CLUSTER_UP/INBOUND_NOT_COMING_UP (入站)

条件
无

触发事件
（自发）

CLUSTER_UP/INBOUND_NOT_COMING_UP

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

集群将保持此状态，直到做出策略决定关闭集群电源。

下一个状态
CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP (出站)

条件
无

触发事件
关闭集群电源的策略决定

CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP

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

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

为了避免浪费不必要的拆卸操作，出站应检查入站集群状态，以进行异步转换为 INBOUND_COMING_UP。或者，可以检查各个 CPU 是否进入 CPU_COMING_UP 或 CPU_UP。

下一个状态

CLUSTER_DOWN/INBOUND_NOT_COMING_UP (出站)

条件
集群已拆卸并准备关闭电源

触发事件
（自发）

CLUSTER_GOING_DOWN/INBOUND_COMING_UP (入站)

条件
无

触发事件

显式的硬件启动操作，由另一 CPU 上的策略决定导致；

硬件事件，例如中断。

CLUSTER_GOING_DOWN/INBOUND_COMING_UP

集群正在（或曾经）被拆除，但与此同时，另一个 CPU 上线并尝试重新建立集群。

如果出站 CPU 观察到此状态，它有两种选择

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

完成集群的拆除，并将集群置于 CLUSTER_DOWN 状态；入站 CPU 将从那里重新建立集群。

选择 (a) 允许通过避免在集群并非真正要断电的情况下进行不必要的拆除和设置操作来减少一些延迟。

下一个状态

CLUSTER_UP/INBOUND_COMING_UP（出站）

条件
集群级设置和硬件连贯性完成

触发事件
（自发）

CLUSTER_DOWN/INBOUND_COMING_UP（出站）

条件
集群已拆卸并准备关闭电源

触发事件
（自发）

最后执行者和第一个执行者的选择¶

在出站端执行集群拆除操作的 CPU 通常被称为“最后执行者”。

在入站端执行集群设置的 CPU 通常被称为“第一个执行者”。

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

最后执行者

关闭集群时，所有涉及的 CPU 最初都在执行 Linux，因此是连贯的。因此，在 CPU 变得不连贯之前，可以使用普通的自旋锁安全地选择最后执行者。

第一个执行者

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

集群级别的初始化可能涉及在总线结构中配置一致性控制等操作。

mcpm_head.S 中的当前实现使用单独的互斥机制来进行仲裁。此机制在用于裸机互斥的 vlocks 中有详细记录。

特性和限制¶

实现

当前基于 ARM 的实现分为 arch/arm/common/mcpm_head.S（低级入站 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 拓扑（即，不支持集群的集群）。可以通过复制其他拓扑级别的集群级状态，并修改中间（非最外层）集群级别的转换规则来扩展该算法。

出版信息¶

最初由 Dave Martin 为 Linaro Limited 创建和记录，与 Nicolas Pitre 和 Achin Gupta 合作完成。

Linux 内核

目录

本页