裸機互斥的 vlocks¶

投票鎖，或“vlocks”，提供了一種簡單的低階互斥機制，對記憶體系統具有合理但最小的要求。

它們旨在用於協調 CPU 之間原本不一致的關鍵活動，在硬體不提供其他機制來支援此活動並且無法使用普通自旋鎖的情況下。

vlocks 利用記憶體系統為寫入單個記憶體位置提供的原子性。為了仲裁，每個 CPU 透過將唯一的數字儲存到公共記憶體位置來“為自己投票”。當所有投票都已投出時，在該記憶體位置看到的最終值標識獲勝者。

為了確保選舉在有限時間內產生明確的結果，CPU 只會在尚未選擇獲勝者並且選舉似乎尚未開始的情況下才首先進入選舉。

演算法¶

解釋 vlocks 演算法的最簡單方法是使用一些虛擬碼

int currently_voting[NR_CPUS] = { 0, };
int last_vote = -1; /* no votes yet */

bool vlock_trylock(int this_cpu)
{
        /* signal our desire to vote */
        currently_voting[this_cpu] = 1;
        if (last_vote != -1) {
                /* someone already volunteered himself */
                currently_voting[this_cpu] = 0;
                return false; /* not ourself */
        }

        /* let's suggest ourself */
        last_vote = this_cpu;
        currently_voting[this_cpu] = 0;

        /* then wait until everyone else is done voting */
        for_each_cpu(i) {
                while (currently_voting[i] != 0)
                        /* wait */;
        }

        /* result */
        if (last_vote == this_cpu)
                return true; /* we won */
        return false;
}

bool vlock_unlock(void)
{
        last_vote = -1;
}

currently_voting[] 陣列為 CPU 提供了一種確定選舉是否正在進行的方式，並且扮演著類似於 Lamport 的麵包店演算法 [1] 中“entering”陣列的角色。

但是，一旦選舉開始，底層記憶體系統原子性用於選擇獲勝者。這避免了需要使用靜態優先順序規則來充當決勝局，或者任何可能溢位的計數器。

只要 last_vote 變數對所有 CPU 全域性可見，它將只包含一個值，該值一旦每個 CPU 清除其 currently_voting 標誌就不會更改。

特性和限制¶

vlocks 並非旨在公平。在爭用情況下，嘗試獲取鎖的_last_ CPU 最有可能獲勝。

因此，vlocks 最適合需要選擇唯一獲勝者，但哪個 CPU 實際獲勝無關緊要的情況。
與其他類似機制一樣，vlocks 不能很好地擴充套件到大量 CPU。

vlocks 可以在投票層次結構中級聯，以便在必要時實現更好的擴充套件，如下面的 4096 個 CPU 的假設示例所示
/* first level: local election */
my_town = towns[(this_cpu >> 4) & 0xf];
I_won = vlock_trylock(my_town, this_cpu & 0xf);
if (I_won) {
        /* we won the town election, let's go for the state */
        my_state = states[(this_cpu >> 8) & 0xf];
        I_won = vlock_lock(my_state, this_cpu & 0xf));
        if (I_won) {
                /* and so on */
                I_won = vlock_lock(the_whole_country, this_cpu & 0xf];
                if (I_won) {
                        /* ... */
                }
                vlock_unlock(the_whole_country);
        }
        vlock_unlock(my_state);
}
vlock_unlock(my_town);

ARM 實現¶

當前的 ARM 實現 [2] 包含一些超出基本演算法的最佳化

透過將 currently_voting 陣列的成員緊密地打包在一起，我們可以在一個事務中讀取整個陣列（前提是可能爭用鎖的 CPU 數量足夠小）。這減少了外部記憶體所需的往返次數。

在 ARM 實現中，這意味著我們可以使用單個載入和比較
LDR     Rt, [Rn]
CMP     Rt, #0
...代替等效於以下程式碼：
LDRB    Rt, [Rn]
CMP     Rt, #0
LDRBEQ  Rt, [Rn, #1]
CMPEQ   Rt, #0
LDRBEQ  Rt, [Rn, #2]
CMPEQ   Rt, #0
LDRBEQ  Rt, [Rn, #3]
CMPEQ   Rt, #0
這減少了快速路徑延遲，以及可能減少爭用情況下的匯流排爭用。

該最佳化依賴於 ARM 記憶體系統保證不同大小的重疊記憶體訪問之間的一致性這一事實，類似於許多其他架構。請注意，我們不關心 currently_voting 的哪個元素出現在 Rt 的哪些位中，因此無需擔心此最佳化中的位元組序。

如果有太多的 CPU 無法在一個事務中讀取 currently_voting 陣列，那麼仍然需要多個事務。該實現為此情況使用一個簡單的字大小載入迴圈。事務的數量仍然少於單獨載入位元組所需的數量。

原則上，我們可以透過使用 LDRD 或 LDM 進一步聚合，但為了保持程式碼的簡單性，在初始實現中沒有嘗試這樣做。
vlocks 目前僅用於在無法啟用其快取的 CPU 之間進行協調。這意味著該實現刪除了在快取記憶體中執行該演算法時所需的許多屏障。

除非所有爭用鎖的 CPU 都是快取一致的，否則 currently_voting 陣列的打包不適用於快取記憶體，因為一個 CPU 的快取寫回會破壞其他 CPU 寫入的值。（雖然如果所有 CPU 都是快取一致的，那麼您可能應該改用正確的自旋鎖）。

用於 last_vote 變數的“尚無投票”值為 0（而不是虛擬碼中的 -1）。這允許透過簡單地將靜態分配的 vlocks 放入 .bss 中來將其隱式初始化為未鎖定狀態。

為了設定此變數，將偏移量新增到每個 CPU 的 ID，以便沒有 CPU 將值 0 用於其 ID。

版權頁¶

最初由 Dave Martin 為 Linaro Limited 建立和記錄，用於基於 ARM 的 big.LITTLE 平臺，並衷心感謝 Nicolas Pitre 和 Achin Gupta 的審查和意見。感謝 Nicolas 從相關的郵件執行緒中獲取了大部分文字並編寫了虛擬碼。

參考文獻¶

[1] Lamport, L. "Dijkstra 併發程式設計的新解決方案"

問題”，ACM 通訊 17, 8 (1974 年 8 月), 453-455。

https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm

[2] linux/arch/arm/common/vlock.S, www.kernel.org.

Linux 核心

目錄

本頁