叢集範圍的電源啟動/斷電競爭避免演算法¶

該檔案記錄了用於協調 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 關閉)

CPU_COMING_UP (CPU 啟動中)

CPU_UP (CPU 啟動)

CPU_GOING_DOWN (CPU 關閉中)

 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 準備好斷電時，它將達到 CPU_DOWN 狀態。達到此狀態後，CPU 通常會透過 WFI 指令或韌體呼叫來自行斷電或掛起。

下一個狀態

CPU_COMING_UP (CPU 啟動中)

條件

無

觸發事件

顯式的硬體上電操作，是由另一個 CPU 上的策略決策導致的；
硬體事件，例如中斷。

CPU_COMING_UP (CPU 啟動中)

在叢集設定和相干之前，CPU 無法開始參與硬體相干。如果叢集尚未準備好，則 CPU 將在 CPU_COMING_UP 狀態下等待，直到叢集已設定好。

下一個狀態: CPU_UP (CPU 啟動)
條件: CPU 的父叢集必須處於 CLUSTER_UP 狀態。
觸發事件: 父叢集過渡到 CLUSTER_UP 狀態。

有關 CLUSTER_UP 狀態的描述，請參閱“叢集狀態”部分。

CPU_UP (CPU 啟動)

當 CPU 達到 CPU_UP 狀態時，CPU 可以安全地開始參與本地相干。

這是透過跳轉到核心的 CPU 恢復程式碼來完成的。

請注意，此狀態的定義與基本模型定義略有不同：CPU_UP 並不意味著 CPU 已經相干，但確實意味著可以安全地恢復核心。核心處理剩餘的恢復過程，因此其餘步驟在競爭避免演算法中不可見。

CPU 將保持此狀態，直到做出明確的策略決策以關閉或掛起 CPU。

下一個狀態: CPU_GOING_DOWN (CPU 關閉中)
條件: 無
觸發事件: 顯式策略決策

CPU_GOING_DOWN (CPU 關閉中)

在此狀態下，CPU 會退出相干性，包括實現此目標所需的任何操作（例如，清理資料快取）。

下一個狀態: CPU_DOWN (CPU 關閉)
條件: 本地 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 是叢集實際上可以斷電的唯一狀態。

入站和出站 CPU 的並行性透過從 CLUSTER_GOING_DOWN/INBOUND_NOT_COMING_UP（對應於基本模型中的 GOING_DOWN）到 CLUSTER_DOWN/INBOUND_COMING_UP（對應於基本模型中的 COMING_UP）的兩條不同路徑的存在來觀察。第二條路徑完全避免了叢集拆卸。

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 狀態時，可以拆卸叢集，例如透過清理資料快取並退出叢集級別相干性。

為了避免浪費不必要的拆卸操作，出站 CPU 應檢查入站叢集狀態是否有非同步轉換到 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 核心

目錄

此頁面