以 double-checked locking 為例，了解 memory barrier 的作用以及thread 之間何時會同步資料

在 multi-thread 程式實作 singleton 的時候，需要留意 singleton 只能初始化一次。我偏好的作法是在程式還是 single thread 的時候先完成初始化。這個作法簡單易懂。不過我想藉由延遲初始化的實作來說明「thread 之間何時會同步資料」。注意，本文的例子只是用來說明多 CPU 執行 multi-thread 底層發生了什麼事，不見得是 singleton 最好的作法。

延遲初始化基本版

基本版用 lock 保證只會初始化一次，這裡用 C++ 的語法表示：

Singleton* s_instance;
Singleton* Singleton::GetInstance()
{
    ScopeLock lock;
    if (s_instance == nullptr)
        s_instance = new Singleton();
    return s_instance;
}

方便說明起見，這裡用 ScopeLock 自動取得和釋放 lock。它會在 constructor 取得 lock，然後在 destructor 釋放 lock。lock 不只保證同一時間內只有一個 thread 會執行這段程式，同時也保證進入 lock 的 thread 會看到最新的資料。CPU 為了加速執行，平時其實不會互相同步資料，所以在不同 CPU 執行的 thread，不見得會得知其它 thread 的更新。想想 pthread lock 真是偉大，隱藏了不同平台多 CPU 之間同步資料的問題，多數人可以在不察覺這些事的情況下使用 multi-thread 提升執行效率。

使用 Double-Checked Locking 實作延遲初始化 (錯誤版)

如果覺得每次呼叫 GetInstance() 都要用 lock，好像很慢 (實際上不會，因為 lock contention 極少)，因此想在初始化的時候用 lock 保護，之後都不要用 lock。那麼我們可以這麼改寫 (錯誤示範)：

Singleton* s_instance;
Singleton* Singleton::GetInstance()
{
    Singleton* tmp = s_instance;  // (a)
    if (tmp == nullptr) {
        ScopeLock lock;  // (b)
        tmp = s_instance;  // (c)
        if (tmp == nullptr) {
            tmp = new Singleton();  // (d)
        }
        s_instance = tmp; // (e)
    }
    return tmp;
}

同一時間只有一個 thread 執行自 (b) 開始的 code block，並且 s_instance 指向初始化完的 Singleton 之後才會釋放 lock，這時其它卡在 (b) 的 thread 才會執行。也因此 (c )會拿到初始化好的 Singleton，然後在 (e) 寫回 s_instance。看起來一切很美好。

問題出在 CPU 執行的方式其實和我們想的不太一樣。撇除多 CPU 之間何時會同步資料的問題，就算 CPU 每次執行完 store 都會寫入主記憶體，每次執行 load 也會從主記憶體讀資料，指令執行的順序仍會造成問題。

(d) 可拆成幾個動作：

1. 配置 Singleton 需要的空間，位置為 X。
2. 執行 Singleton constructor，會寫入一些資料到 X 指向的位置。
3. 設 tmp 的值為 X。

CPU 為了提升效率，有可能更動指令執行的順序，只要最後結果和 single thread 預期的結果一樣即可。如果 CPU 執行 (d) 和 (e) 的順序如下：

1. 配置 Singleton 需要的空間，位置為 X。
2. 設 tmp 的值為 X。
3. 設 s_instance 的值為 X。
4. 執行 Singleton constructor，會寫入一些資料到 X 指向的位置。

這個執行順序對 single thread 沒有差別，但對 multi-thread 就有差了。如果在第 3 步之後到第 4 步之前，剛好有另一個 thread 執行 GetInstance()，因為 s_instance 已有值了，所以不用等 lock，會直接回傳結果。這樣另一個 thread 會拿到未初始化完的 Singleton，使用未初始化完的 Singleton 可能會有非預期的結果。

程式碼到執行結果之間的轉換

出自《C++ and Beyond 2012: Herb Sutter — atomic<> Weapons》

由上圖可知程式碼和執行的結果中間多了幾層轉換。每一層轉換都有保證在 single thread 有一樣的結果，但在 multi-thread 的情況會出事。所以程式要特別保護有 data race 的部份，轉換後的結果才不會出錯。

為什麼 CPU 會更動指令的執行順序？

想像依序執行兩個計算式：

a = b + c;
d = e + f;

我們知道 CPU 執行加法極快，但讀寫記憶體很慢 (差了百倍以上)。compiler 編譯這兩個算式產生的組語可能如下：

load R1, b
load R2, c
add R3, R1, R2  (1)
store a, R3
load R4, e  # (2)
load R5, f  # (3)
add R6, R4, R5
store d, R6

• R1 ~ R6 是 register。
• a ~ f 表示變數的記憶體位置。
• load/add/store 第一個參數是目的地。

如果 CPU 執行 (1) 的時候先執行 (2) 和 (3)，可以提早備好資料，縮短整體的執行時間。

附帶一提，compiler 也會作一樣的事，藉由調整程式的順序，加速執行。我們無法確定 compiler 會怎麼調整程式順序產生更有效率的組語，也無法確定 CPU 是否會怎麼調整執行組語的順序。 compiler 和 CPU 唯一提供的保證是 single thread 執行的結果會和他們調整順序之前一樣。

Memory Barrier

如果我們希望 compiler 和 CPU 照我們所想的順序執行，需要在程式之間插入 memory barrier。memory barrier 有分 compiler memory barrier 和 CPU 的 memory barrier。前者是要求 compiler 不要將 barrier 之前的程式搬到 barrier 後，也不要將之後的搬到之前；後者類似，不過有分幾種不同類型的 memory barrier，這裡不仔細討論。另外，CPU memory barrier 也會有 compiler memory barrier 的效果，反之則不成立。

回到原本的問題，我們需要補上 CPU 的 memory barrier 才能作到正確的 double-checked locking，但是 memory barrier 和程式語言和 CPU 的 memory model 有關，在討論特定語言或特定 architecture 之前，無法討論如何使用 memory barrier。

Memory Model

程式語言的 memory model 讓使用該語言的人和實作 compiler 的人有個依據，知道如何遵守同一協定，實作出跨平台的 multi-thread 程式。Java 5、C11、C++11 各自訂了完備的 memory model，並基於它們所訂的 memory model 提供函式庫讓開發者使用。如此一來，軟體開發者不用在意各家平台的 memory model，只要了解 Java/C/C++ 的 memory model 即可。

下面以 C++ 11 為例說明如何用 std::atomic 作出安全的 double-checked locking。程式改自 《Double-Checked Locking is Fixed In C++11》 (將變數名稱改得和前面例子一致)，這篇文章和作者的其它文章都相當值得一讀。

std::atomic<Singleton*> Singleton::s_instance;
std::mutex Singleton::s_mutex;

Singleton* Singleton::GetInstance() {
    Singleton* tmp = s_instance.load();
    if (tmp == nullptr) {
        std::lock_guard<std::mutex> lock(s_mutex);
        tmp = s_instance.load();
        if (tmp == nullptr) {
            tmp = new Singleton();
            s_instance.store(tmp);
        }
    }
    return tmp;
}

這裡的 atomic load/store 帶有以下的效果：

• load/store 是 atomic operation，不會有 thread 讀到寫到一半的值。
• (副作用) load/store 前後的程式不能移到 load/store 的另一側。
• (副作用) load 之後會看到另一個 thread store 之前寫入的值。

注意 load/store 要用同一個 atomic 物件才會有第三個效果。

load/store 帶有一個參數 memory_order，可使用不同的 memory model。預設參數的同步效果最強，不過速度也較其它 memory_order 慢一點。有興趣深入了解的話，可以看 GCC Wiki — Memory model synchronization modes 和 Practical Usage。大概是我看到解釋 C++11 memory model/barrier 最清楚的文章，而且不長。或是參考《簡介 C++11 atomic 和 memory order》。

compiler 會依平台產生對應的 memory barrier，有些效果可能會比 C++11 規範的還強，C/C++11 mappings to processors 有 C/C++11 atomic operations 轉成 x86, PowerPC, ARMv7, ARMv8, Itanium 的指令對照表。可以交錯查詢對應指令的效果是什麼。

2020/02/24 更新

Java 透過 JVM 初始化 class 規則的保證，可以簡單地作到安全又高效率的延遲初始化，詳情見 Initialization-on-demand holder idiom。

參考資料

• Memory Barriers Are Like Source Control Operations、Acquire and Release Semantics 和 Weak vs. Strong Memory Models：介紹 #LoadLoad、#LoadStore、#StoreLoad、#StoreStore 四種基礎 memory barrier，透過它們的組合了解 acquire/release model 以及常見 architecture 的 memory model。從 architecture 的角度理解 memory barrier。這幾篇都很容易讀。
• Relaxed memory model：摘要幾種 architectures 的 memory model。architecture 的 memory model 分類似乎還沒公認的說法，再找時間消化。
• C++ and Beyond 2012: Herb Sutter — atomic<> Weapons, 1 和 2：留著待看。
• N1525: Memory-Order Rationale：提供 C11 各種 model 的小例子。
• C++ 11 Memory Model 標準文件的主要部份：只是留著備忘。
• C/C++11 mappings to processors：方便查 compiler 在各平台使用的指令。

相關文章

• 以 double-checked locking 為例，了解 memory barrier 的作用以及thread 之間何時會同步資料
• 簡介 C++11 atomic 和 memory order
• SC-DRF load/store 在各平台的實作
• 從硬體觀點了解 memory barrier 的實作和效果