並行程式設計: Atomics 操作

資料整理: jserv, qwe661234

點題

在並行程式設計中，常用 lock 避免多個執行緒在修改同一個資料時，遭遇 race condition 的狀況。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

考慮上圖，主記憶體某處原本內含值是 17，我們挪用作計數器 (counter) 這樣的共用變數。考慮有 2 個執行緒 Thread_A 和 Thread_B，倘若二者都對計數器遞增 1，預期計數器會得到 19，即

17 + 1 + 1

，但最終可能出現非預期的 18，為什麼？

其中一個可能是，Thread_A 自主記憶體讀取計數器內含值 (此時是 17) 後，觸發 context switch，切換到 Thread_B 執行，後者也從記憶體讀取計數器內含值 (即 17)，隨後遞增 1，並且寫回主記憶體中。爾後，切換到 Thread_A，依據程式碼的邏輯，要將計數器的數值遞增 1，之前已取得 17 (舊數值)，但 Thread_B 沒有察覺主記憶體裡頭的計數器內含值已變更，依然對 17 遞增 1，並寫回主記憶體，即 18。我們可發現，「寫回主記憶體」的操作分別在 Thread_A 和 Thread_B，但最終沒得到我們預期的 19。

為了便於探討上方案例，我們將 count 的初始值設為 0:

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

如今有二個執行緒讀取 count 變數的內容，再把 count 加 1，於是每個 count = count + 1 敘述可視為以下二個獨立的步驟:

temp = count + 1 (讀取 count 的值並且加 1)
count = temp (把計算好的值重新存回 count)

對照上方示意圖，在沒有任何限制的情況下，多個執行緒之間可能會交互執行指令，現在按照紅色箭頭的軌跡來分析：

Thread₀ 先取出 count 並且加 1，存到 temp0，於是 temp0 = 1
接著輪到 Thread₁ 取出 count 並且加 1，存到 temp1，亦即 temp1 = 1，Thread₀ 計算完 temp0 後尚未指派的動作就被切換，所以 Thread₁ 取到的 count 依舊是 0
再回到 Thread₀，把計算好的 temp0 指派到 count，於是 count = temp0 = 1，此時 count 被更新為 1
最後輪到 Thread₁，把計算好的 temp1 指派給 count，亦即 count = temp1 = 1，最後結果 count = 1，不符合我們的預期

我們把上述因執行緒競相變更資料，卻無法達到預期的結果，稱為 race condition，可簡稱 race。在多執行緒環境下，若缺乏適度的同步機制，會造成很多無法預期的結果，換言之，我們的目的就是不要讓執行緒之間隨意交互執行，所以我們應該要關注執行順序。

一味依賴 lock 易致使 lock contention，甚至當 lock 成為多核處理器的效能瓶頸時，我們不得不接觸到微處理器提供 atomic 專用指令，但要用 atomic 指令寫出正確的並行程式卻是困難的事，不僅要廣泛顧及 ABA 問題, memory barrier 及多核處理器特性，還要思索現有演算法的改寫和驗證。

本文回顧微處理器的 atomic 指令及軟硬體設計考量、memory ordering 及 memory barrier、C11 標準的 stdatomic.h 及 Linux 核心介面，和探討經典 lock-free 資料結構和演算法案例。

詞源和澄清

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

原子的英文 "atom" 源於希臘文 ἄτομος (拉丁轉寫為 atomos)，意思是「不可分割的單位」。最先提出原子學說的是古希臘米利都學派 (也稱為愛奧尼亞學派，被譽為是西方哲學的開創者) 中的留基伯 (Leucippus)，他的學生德謨克利斯 (Democritus) 繼承並發展原子學說，並用原子學說來解釋宇宙：宇宙由原子和虛空組成，所有物質都由不可再分割的微小粒子組成。因這個微小粒子已不能再分割，他將希臘文 τόμος (拉丁轉寫為 tomos，意思是分割) 加上了反義字首 a-，成為 "atomos"，即「不可分割的」。-os 是希臘文名詞的後綴，十五世紀晚期 atomos 這詞去除後綴轉寫為現代英語，成為 atom。

電腦科學進一步借用 atomic 一詞來表示「不可再拆分的」，於是 "atomic operation" 寓意為「不可再拆分的執行步驟」，也就是「最小操作」，即某個動作執行時，中間沒有辦法分割。既然提到 atomic，我們來看貌似不相關，但會影響到文意思考的詞彙 —— 原子筆，後者的英語書寫為 "ballpoint"。香港利豐有限公司當年把 ballpoint 從美國輸入香港時，產品並無中文名稱，「原子」一詞在當時有高新科技的意象，代理商將 ballpoint 取名為「原子筆」則表示該發明乃創新、突破性的尖端書寫技術。倘若我們將 atomic operation 翻譯為「原子操作」，可能會讓人聯想到高科技或者核能 (nuclear)，但事實根本不是這個意思！本文將 atomic operation 簡稱 atomics 或保留原文，避免用「原子操作」這樣無法望文生義的譯詞。

延伸閱讀: 香港利豐集團百年傳奇
atomic 的國際音標 (IPA) 是 [əˈtɑmɪk]
atom 的國際音標是 [ˈætəm]

阻塞式同步機制

為確保多個執行緒或行程之間得以符合預期地執行 (即成語「並行不悖」)，其中一種手段是讓某個執行緒執行，同個時間阻塞 (blocking) 其他執行緒，直到前者完成某一段會影響到共享資源存取的程式碼，後者方可繼續執行。這個策略稱為阻塞式同步 (blocking synchronization)，語意簡潔且易於開發，但缺點是:

就算硬體有能力處理多個執行緒，但只要涉及共享資源的存取，不免要藉由阻塞達到同步：被阻塞的執行緒，要不原地等待 (spin)，要不等待喚醒 (sleep/wake) 的訊號，無法充分運用硬體能力
非預期的狀況可能致使毫無進展 (progress)：某個持有阻塞式同步鎖 (lock) 的執行緒，若恰好因為非預期的原因致使崩潰，這樣 lock 就不會釋放 (除非系統管理者介入)，從而使得等待該 lock 的執行緒無法再執行下去，自然就不會有進展，這樣的程式會讓終端使用者認為「程式卡住了」，儘管微處理器其實仍在執行特定的程式
傳統 mutex 在即時或優先權導向的情境下可能引發 priority inversion 的議題，儘管存在 PIP (Priority Inheritance Protocol) 和 PCP (Priority Ceiling Protocol) 一類的解法，但執行時期的複雜度提升，甚至還要考慮 Runtime locking correctness validator 的機制

特別你想充分發揮多處理器的硬體能力，或不容許整個系統因為單一執行緒拖延整體進度，抑或是 scalability 是你迫切面對的議題，那就要考慮到阻塞式同步機制以外的方案。

Atomic 操作：非阻塞式同步的基石

"atom" 作為電腦術語，指無法再拆分為更小的執行步驟，這實際是對「硬體」的觀點，即微處理器的指令，並非從「軟體」的觀點來看。atomic 指令形式不一，我們可用較高階的語法來解釋: (即 C11)

_Atomic int cnt;
atomic_fetch_add_explicit(&cnt, 1, memory_order_relaxed);

從函式 atomic_fetch_add_explicit 的開頭不難猜出這是 atomic 操作，至於 explicit 涉及 memory order，稍後解釋。這裡的 fetch (自記憶體取值), add (執行加法，這裡就是 + 1 操作) 以及最終的寫回主記憶體等 3 個步驟必須是 atomic，意思是要不什麼都沒做，要不 fetch, add 和寫回主記憶體三者都完成，不會有中間狀態 —— 儘管概念上拆解為 3 個步驟，但視作 3 個步驟都是不可分割的最小單元。類似 atomic_fetch_add_explicit 的 atomic 操作，我們歸類為 read-modify-write 操作，簡稱 RMW。

不難聯想到，本文點題時提到計數器的案例，就該用 atomic RMW 操作來解決，但背後的演算法卻略為複雜 —— 既然 atomic 是將單一或若干步驟視作最小操作單元，實際上就會遇到「要不全部成功，要不全部失敗」的現象，於是我們需要變更原本執行緒的程式邏輯，當 atomic 操作不能成功時，就重來 (成語「一氣呵成」)，直到 RMW 一類的 atomic 操作成功為止。

在 single-core 下只要關閉 global interrupt，防止 CPU 被 preempt，就可確保 atomic，但在 multi-core 就要有特殊的硬體支援（且關閉 global interrupt 會影響回應時間，從而增加 latency）。其中很大一部分要確保 RMW operation 是 atomic，特別是在 lock 與 counter 的實作上面。

通常 CPU 會提供有別於一般 load/store memory 的特殊指令，以達成 RMW atomic。常見以下二種:

compare-and-swap (CAS) / swap (SWP): CAS 寫入時同時提供舊值 (之前自 target 讀出來的值，對應下方程式碼的 compare)，如果舊值和記憶體裡的相同，就將新值 (即下方程式碼的 new) 寫入，確保 RMW 的動作完整性，如 x86 的 CMPXCHG 指令。SWP 在寫入時讀回記憶體的值，可用於與之前讀出的值比對。如 ARMv5 (含) 之前的 SWP，ARMv8.1 也引入 CAS 指令
```
lock cmpxchg(target, compare, new):
    lock(memory_bus);
    register = load(target);
    if (register == compare)
        store(target, new);
    unlock(memory_bus);
    return register; 
```
load-link/store-conditional (LL/SC)：這類的指令成對使用。在 LL 讀取記憶體的值，同時標記進入 exclusive 狀態，SC 寫入時清除 exclusive 狀態。在 exclusive 狀態時如有其他 core 較早執行寫入，導致 exclusive 狀態被清除，則忽略這次的寫入並返回失敗。程式可在下一行發現失敗時重新執行 LL/SC 的動作直到成功為止。Power 和 Arm (ARMv6 以上) 提供這類的指令。

其他尚有如 test-and-set (簡稱 TAS) 和 Fetch-and-add (簡稱 FAA) 等指令。

ARM 早期 CPU 使用的 SWP 指令在多核處理器中會遇上效能瓶頸

詳見 ARM Synchronization Primitives Development Article

ARMv6 以上改用 LL/SC 指令，即 ldrex/strex。針對 x86 記憶體存取的指令，可加上 LOCK 前綴，以轉成 atomic 的存取。

CAS 的關鍵概念是，目前執行緒先載入共用變數的內含值，然後對其修改，最後寫入之際確保操作為 atomic —— 判定之前載入的共用記憶體內含值和目前操作是否一致，若相同，則將新變更的值寫回，否則就失敗。程式可搭配流程控制，確認 CAS 和資料變更符合預期地完成。

以下是示範程式碼:

void atomic_sum_of_squares(volatile int *atom, int b)
{
    int org, dst;
    do {
        org = *atom;
        dst = org * org + b * b;
    } while (!CAS(atom, &org, dst));
    /*            |      |    |
     *            |      |    +-- 比較成功後，寫入指定地址
     *            |      +-- 之前載入的數值   
     *            +-- atomic 物件
     */
}

CAS 指令對其所操作的 atomic 物件是「即刻生效」(或「即刻退回」)，只要沒有其他執行緒對該 atomic 物件進行變更，CAS 操作就會成功，當然就可結束，反之，lock 的實作內部通常也有 atomic 操作 (軟體演算法如 Dekker's Algorithm 儘管可達成 mutual exclusion，因效率太差且對 memory order 做了限制，現代系統通常不用)，但其邏輯是等待 atomic 物件的狀態 (如 lock 和 unlock，或者 wait/signal)。換言之，CAS 的指令設計即考慮 race condition 的議題。

延伸閱讀:

video: A Pragmatic Introduction to Multicore Synchronization, 08:23 起

藉由 atomic 指令，我們可以實現一些基本的 counter 操作與簡單的 SMP lock，如 spinlock, rwlock 等，並確保程式狀態維護的正確性。然而當競爭相同 lock 的處理器數量增長時，卻可能會造成 scalability 不佳的問題。

C11 Atomics

C11 標準引入 _Atomic 關鍵字，將特定的型態轉變為對應的 atomic 型態，如:

char
$\to$ _Atomic char 且等同於 atomic_char
int
$\to$ _Atomic int 且等同於 atomic_int

C11 提供的 atomic 操作函式常見二種版本:

沒有 memory order 參數
指定 memory order 參數，並以 _explicit 結尾

以下是 C11 示範程式: (檔名 atomic.c)




























































#include <pthread.h>
#include <stdalign.h>
#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

#if defined(__x86_64__) || defined(__i386__)
#define CPU_PAUSE() asm("pause")
#elif defined(__aarch64__)
#define CPU_PAUSE() asm("isb")
#else
#define CPU_PAUSE() do { /* nop */ } while (0)
#endif

struct atomic_float {
    volatile atomic_flag flag;
    int padding; /* avoid false sharing */
    alignas(16) float value;
};

static volatile struct atomic_float atomic_float_obj;

static void atomic_val_inc(int nLoops)
{
    for (int loop = 0; loop < nLoops; loop++) {
        while (atomic_flag_test_and_set(&atomic_float_obj.flag))
            CPU_PAUSE();
        atomic_float_obj.value += 1.0f;
        atomic_flag_clear(&atomic_float_obj.flag);
    }
}

static void *func(void *args)
{
    atomic_val_inc(10000);
    return NULL;
}

int main(int argc, const char *argv[])
{
    printf("The size is: %zu, `value` offset is: %zu\n",
           sizeof(atomic_float_obj), offsetof(struct atomic_float, value));

    atomic_float_obj.flag = (atomic_flag) ATOMIC_FLAG_INIT;
    atomic_float_obj.value = 0.0f;

    pthread_t tid;
    if (pthread_create(&tid, NULL, func, NULL) != 0) {
        puts("Failed to create a thread!");
        return 1;
    }

    atomic_val_inc(10000);

    pthread_join(tid, NULL);
    printf("The final result is: %f\n", atomic_float_obj.value);
    return 0;
}

預期執行結果: (編譯時記得加上 -lpthread 參數)

The size is: 32, `value` offset is: 16
The final result is: 20000.000000

倘若我們將第 28 行 while (atomic_flag_test_and_set(&atomic_float_obj.flag)) 改為 while (0)

編譯後，利用 watch -n 1 ./atomic 命令觀察，會發現執行輸出不一，即前述的 race condition。

若編譯時加上 -fsanitize=thread -g 選項，搭配上述第 28 行的 while (0) 程式碼變更，執行後會遇到以下警告:

WARNING: ThreadSanitizer: data race (pid=2473325)
  Read of size 4 at 0x5603a6108050 by main thread:
    #0 atomic_val_inc atomic.c:28 (atomic+0x1339)
    #1 main atomic.c:53 (atomic+0x14e7)

  Previous write of size 4 at 0x5603a6108050 by thread T1:
    #0 atomic_val_inc atomic.c:28 (atomic+0x135e)
    #1 func atomic.c:35 (atomic+0x13bc)

  Location is global 'atomic_float_obj' of size 32 at 0x5603a6108040 (atomic+0x000000004050)

留意上方程式碼第 2 行的 #include <stdalign.h> 和第 20 行的 alignas(16)，這是 C11 規範的記憶體對齊 (alignment) 操作，以下定義於 <stdalign.h>:

alignas : 對齊記憶體地址
alignof : 取得變數的對齊基數

考慮以下程式碼:

alignas(16) int x;

printBinary(&x);
printf("%ld\n", alignof(x));

對應的執行輸出:

_0000_0000_0000_0000_0000_0000_1010_1101_1001_0100_1111_1111_1111_1000_1101_0000
16

因為 int x 變數的地址會對齊 16 (單位：位元組_，亦即 2⁴，在其二進位表示中，低位元處 4 個位元皆為 0，此處使用 alignas 以避免 false sharing。

考慮以下結構體:

struct Par {
    int n1;
    int n2;
};

在並行程式設計中，可能會改為:

struct Par {
    alignas(64) int n1;
    alignas(64) int n2;
};

看似後者佔用更多記憶體空間 (64 + 64 > 4 + 4)，但後者效率較前者好，因為記憶體存取以 cacheline 為單位 (x86-64 為 64B，在 Arm 架構會依據組態而有不同表現，可見 Detect L1 cache size at compile time)，上方程式碼刻意將成員變數 n1 和 n2 置於不同的 cacheline，可避免頻繁的 cache coherence。

在 <stdatomic.h> 中，有個特別的變數 atomic_flag，其定義如下，是個被結構化的 unsigned char:

typedef _Atomic struct {
#if __GCC_ATOMIC_TEST_AND_SET_TRUEVAL == 1
    _Bool __val;
#else
    unsigned char __val;
#endif
} atomic_flag;

可用巨集來初始化:

#define ATOMIC_FLAG_INIT        { 0 }

搭配以下函式操作 atomic_flag

atomic_test_and_set();
atomic_test_and_set_explicit();
atomic_flag_clear();
atomic_flag_clear_explicit();

背後作祟的 cache

"There are only two hard things in Computer Science: cache invalidation and naming things." – Phil Karlton

電腦發展之初，CPU 和主記憶體都很慢，但後來 CPU 速度大幅提升，主記憶體讀寫速度反而沒有顯著提升，因此主記憶體的存取就比 CPU 緩慢，於是現代電腦加上 cache 以降低讀寫主記憶體的次數，從〈Latency Numbers Every Programmer Should Know〉可知，存取主記憶體的時間是 100 ns，L1 cache 是 0.5 ns，兩者相距 200 倍。

延伸閱讀: Napkin Math / 演講

顯然，不存在任何競爭或只被一個執行緒存取的 atomic 操作較快，此處的「競爭」指的是多個執行緒同時存取同一個 cacheline 。

接下來我們藉由實驗來回顧，給定程式碼: (檔名: cacheline.c)
































































#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#ifndef min
#define min(x, y) (x) < (y) ? (x) : (y)
#endif

#define N_THREADS 128
static int64_t loop_count = 0;

#pragma pack(1)
struct data {
    int32_t pad[15];
    int64_t v;
};

static struct data value __attribute__((aligned(64)));
static int64_t counter[N_THREADS];

static void worker(int *cnt) {
    for (int64_t i = 0; i < loop_count; ++i) {
        const int64_t t = value.v;

        if (t != 0L || t != ~0L)
            *cnt += 1;

        value.v = ~t;
        /* creates a compiler level memory barrier
         * forcing optimizer to not re-order memory
         * accesses across the barrier. */
        __asm__ volatile("" ::: "memory");
    }
}

int main(int argc, char *argv[]) {
    pthread_t threads[N_THREADS];

    if (argc != 3) {
        fprintf(stderr, "USAGE: %s <threads> <loopcount>\n", argv[0]);
        return 1;
    }

    /* Parse argument */
    int64_t n = min(atol(argv[1]), N_THREADS);
    loop_count = atol(argv[2]);

    /* Start the threads */
    for (int64_t i = 0L; i < n; ++i)
        pthread_create(&threads[i], NULL, (void *(*) (void *) ) worker,
                       &counter[i]);

    int64_t count = 0L;
    for (int64_t i = 0L; i < n; ++i) {
        pthread_join(threads[i], NULL);
        count += counter[i];
    }

    printf("iteration: %lu\n", count);
    printf("data size: %lu\n", sizeof(value));
    printf("final: %016lX\n", value.v);

    return 0;
}

這段程式碼操作貌似簡單：建立執行緒，不斷對全域變數進行 NOT (第 28 行)，這樣最終的結果 (即第 58 行的輸出) 為何？

倘若我們不做實驗，只用臆測，會歸納出在 int64_t 資料寬度的內容，不是全為 0，就是全為 1，但真實狀況會如何呢？

編譯方式:

$ gcc -o cacheline cacheline.c -lpthread

在真正的多核處理器硬體 (注意: 不能在虛擬機器上測試)，這個程式預期指定執行緒和測試總量，例如在 AMD Ryzen Threadripper 2990WX 32-Core Processor 執行:

$ ./cacheline 24 10000
iteration: 240000
data size: 68
final: ?

可用以下命令持續觀察:

$ watch -n 1 "./cacheline 24 10000"

其中 final 那行有 4 種可能:

FFFFFFFFFFFFFFFF
0000000000000000
00000000FFFFFFFF
FFFFFFFF00000000

前 2 者是我們不用執行程式即可臆測的結果，但後 2 者該如何解釋？

注意看上述程式碼的第 12 到第 16 行，成員變數 v 恰好放在跨越 2 個 cacheline (在 x86_64 架構中，cacheline 為 64 bytes)，從而引出違反直覺的事實：存取一個 64 位元寬度的資料，對 CPU 需要 2 個存取。

延伸閱讀: 你所不知道的 C 語言：記憶體管理、對齊及硬體特性

硬體的 cache coherence 操作的基本單元就是 cache line，為了寫進記憶體，CPU 必須 exclusive 地佔有該 cacheline，而若一個變數座落於在 2 個不同的 cacheline 上，則 cacheline 之間的競爭是「沒有」atomic 特性保證，資料讀取也類似。

《Intel® 64 and IA-32 architectures software developer's manual》的第 3 卷提及:

Intel 64 memory ordering guarantees that for each of the following memory-access instructions, the constituent memory operation appears to execute as a single memory access regardless of memory type:

Instructions that read or write a single byte.

Instructions that read or write a word (2 bytes) whose address is aligned on a 2 byte boundary.

Instructions that read or write a doubleword (4 bytes) whose address is aligned on a 4 byte boundary.

Instructions that read or write a quadword (8 bytes) whose address is aligned on an 8 byte boundary.
All locked instructions (the implicitly locked xchg instruction and other read-modify-write instructions with a lock prefix) are an indivisible and uninterruptible sequence of load(s) followed by store(s) regardless of memory type and alignment.

Other instructions may be implemented with multiple memory accesses. From a memory-ordering point of view, there are no guarantees regarding the relative order in which the constituent memory accesses are made. There is also no guarantee that the constituent operations of a store are executed in the same order as the constituent operations of a load.

上述描述可知，Intel 微處理器架構只保證滿足 alignment 規則的變數存取的 atomic 特性，但不能保證跨越多個 cacheline 的狀況。

多核處理器之間的 cache coherence

多核和單核究竟有什麼差異？多數問題就來自 cache!

在多核處理器的機器中，每個 CPU 都有自己的 cache，以彌補 CPU 和主記憶體之間較慢的存取速度，當個特定資料首次被特定的 CPU 讀取時，此資料顯然不存在於該 CPU 的 cache 中 (即 cache miss)，意味著 CPU 需要自主記憶體中讀取資料 (為此，CPU 通常要等待數百個 cycle)，此資料最終將會存放於 CPU 的 cache 中，這樣後續就能直接自 cache 上快速存取，不用再透過主記憶體。因為每個 CPU 上的 cache 資料是 private 的，因此在進行寫入操作時，會造成其他 CPU 上的 cache 資料不一致的問題。

示意如下：

取自 MIT 6.004 L25: Cache Coherence

解說：

Core₀ load memory from address 0xA，資料內容為 2
Core₂ store memory to address 0xA，更新資料在自己的 cache 上，並在稍後補回 memory，而更新內容為 3
Core₂ 的更新不被 Core₀ 得知，因此 Core₀ 還以為 0xA 上所存的資料是 2，但顯然這份資料已過時。

為了確保所有 CPU 上的 cache 資料是一致的，當某個 CPU 進行寫入操作時，它必須保證其他 CPU 已將資料從他的 cache 中移除 (方可確保一致性)，僅在移除操作完成後，此 CPU 才能安全的修改資料。專門處理一致性協定統稱為 cache-coherence protocol。透過 cache-coherence protocol，任何一個 CPU 要寫入資料前，都要先確保其他 CPU 已 invalid 同一位置的 cache 後 (希望寫入的 CPU 廣播 invalidate，其它 CPU 回 invalidate ack)，方可寫資料到自己的 cache，並在稍後補寫回主記憶體。

一個處理器寫入自己的 (private) L1 cache 非常快 (4 cycles, ~2ns)，但當另一個處理器讀取或寫入同一處記憶體時，它要確認看到其他處理器核對應的 cacheline。

這帶來新的問題：同一個資料有可能會分佈在多個 CPU 的 cache 中，從而會有一致性 (consistency) 問題，更明確來說，在同一時間，同一變數在不同的 CPU 可能會有不同的值，如下圖：

試想一個情境：當 CPU₀ 剛修改記憶體某處的資料，最新的數值是先寫入到 CPU₀ 的 cache，等待 cache line 被標註為 invalidate，才會寫入到主記憶體，若此時另一個 CPU (如 CPU₇) 打算存取主記憶體中同一位置的資料，則不論是 CPU₇ 的 cache，抑或是主記憶體中都沒有最新值，後者只存在於 CPU₀ 的 cache中，是此，我們需要一個機制來確保 cache 在不同 CPU 間的一致性，以軟體的觀點，這個過程也該是 atomic，即不能在中間穿插其他程式碼，只能等待處理器完成 cache coherence，這個複雜的硬體操作會讓 atomic 指令成本大幅提升，atomic_fetch_add 可能因此需要 700 ns。

像是 x = 1; 和 y = x; 這樣的 C 語言敘述看似簡單，但對 CPU 來說，可能要做非常多的工作，因為 CPU 既要保證存取效率 (藉由 cache)，還要保證 cache 內部資料的一致。因此，對於現代處理器架構來說，都在其系統中引入更 weak (注意: 這不是說能力的 weak，而是「順序」的 weak，可詮釋為「身段的柔軟」) 的 memory order，從而使整體的存取效率得以提升。

不同 CPU 間是如何進行溝通的。CPU 之間的溝通主要是透過 system bus，後者是連接 CPU、主記憶體和其他 I/O 裝置，因為 CPU 中的 cache 進行 cache coherency 時，也是透過 system bus 來廣播 Probe Read 以及 Probe Write 請求，其他 CPU 也是透過 system bus 進行相對應的回應。因此，我們也稱 system bus 為 cache coherent interconnect (CCI)。

取自 OpenMP, Cache Coherence

當一個特定資料首次被特定的 CPU 讀取時，此資料顯然不存在於該 CPU 的 cache 中 (即 cache miss)，意味著 CPU 需要自主記憶體中讀取資料 (為此，CPU 通常要等待數百個週期)，此資料最終將會存放於 CPU 的 cache 中，這樣後續就能直接自 cache 上快速存取。當某個 CPU 進行寫入操作時，它必須保證其他 CPU 已將資料從它們的 cache 中移除 (方可確保 一致性)，僅在移除操作完成後，此 CPU 才能安全的修改資料。顯然，倘若存在多個 cache 時，勢必要有個專門處理一致性的機制，排除潛在的資料不一致問題，也正因如此，可能會導致記憶體存取的亂序議題。

使用 cache 時，要確保個別 CPU 有看到「一致 (coherent) 的資料」(注意重點放在 CPU 之間的順序，而非讓 cache 和 memory 保持同步 [synchronous]，如此概念差異會影響到架構設計)。維護這點的協定統稱為 cache-coherence protocol。

「一致性」(coherent) 確保同一記憶體位址的所有複本必須保持相同值。以下摘錄自《Is Parallel Programming Hard, And, If So, What Can You Do About It?》第 15 章：

In cache-coherent systems, if the caches hold multiple copies of a given variable, all the copies of that variable must have the same value.

不過，並行程式要達到整體正確性，仍仰賴更高層的同步機制與記憶體一致性模型：

同步操作（如 lock、C11 Atomics、fence 等）負責定義不同行位址間的可見順序，防止資料競爭
硬體記憶體模型 (如 TSO 和 Armv8 的 Load-Acquire and Store-Release) 決定處理器可對讀寫重新排序的範圍

快取一致性雖是處理器確保資料正確的關鍵手段，但不足以單獨保證並行程式的語意正確，軟體開發者必須結合適當的手法。

實作 cache-coherence protocol 時，系統設計者會定義一系列請求，這些請求有 CPU 對於自己的 cache 的請求，也有 CPU 對於其他 CPU 的 cache 的請求。定義如下:

Read Hit: CPU 要讀取資料時，發現自己的 cache 中含有這份資料
Write Hit: CPU 要寫入資料時，發現自己的 cache 中含有這份資料
Read Miss: CPU 要讀取資料時，發現自己的 cache 中沒有這份資料
Write Miss: CPU 要讀取資料時，發現自己的 cache 中沒有這份資料
Probe Read: 某一 CPU 要讀取資料時，先去看其他 CPU 中的 cache 有沒有更新這份資料
Probe Write: 某一 CPU 要寫入資料時，去看其他 CPU 中的 cache 是否存有這份資料
Probe Read Hit: 其他 CPU 中的 cache 打算讀取這份資料，且該 CPU 含有這份資料
Probe Write Hit: 其他 CPU 中的 cache 打算寫入這份資料，且該 CPU 含有這份資料

MESI protocol

MESI protocol 是個基本形式，從 MESI protocol 可了解 CPU 之間如何維持看到一致的資料。

	M	E	S	I
M	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →
E	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →
S	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →
I	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →	Image Not Showing Possible Reasons The image file may be corrupted The server hosting the image is unavailable The image path is incorrect The image format is not supported Learn More →

簡述 4 個狀態意思:

Modified(M)
- 這份資料是最新且被修改過的，這份資料可以被寫回主記憶體
- 其他 CPU 上的 cache 沒有這份資料
- 在主記憶體中的這份資料是過時的
Exclusive(E)
- 其他 CPU 上的 cache 沒有這份資料
- 在主記憶體中的這份資料和 cache 中存有的這份資料是一樣的
- 其他 CPU 上的 cache 發 probe read 時，會將資料提供給他
Shared(S)
- 其他 CPU 上的 cache 必定含有同一份資料
- 在主記憶體中的這份資料和 cache 中存有的這份資料是一樣的
Invalid(I)
- cache 中存有的這份資料是過時的

CPU 對自己的 cache 下請求的狀態圖

取自 OpenMP, Cache Coherence

收到其他 CPU 上的 cache 下請求的狀態圖

取自 OpenMP, Cache Coherence

實作上，用 3 個位元來表示該 cacheline 的狀態，分別是 valid bit, dirty bit 和 shared bit，由這三個 bit 來組合出 MESI 4 個不同的狀態:

	Valid bit	Dirty bit	Shared bit
Modified	1	1	0
Exclusive	1	0	0
Shared	1	0	1
Invalid	0	X	X

X 指 doesn't matter

舉例說明 MESI protocol 的流程:

CPU₀ 對主記憶體中的 Block 0 進行讀取，因為 CPU₀ 是第一個且第一次進行讀取，因此這個 cacheline 的狀態會設定成 Exclusive
CPU₁ 想對 Block 0 進行讀取，他會發 Probe read 給 CPU₀，接著 CPU₀ 會收到 Probe read hit，因為其 cache 中有 Block 0 的資料，CPU₁ 從 CPU₀ 讀取資料，並將其 cacheline 狀態設定成 Shared
CPU₀ 想對 Block 0 進行寫入，CPU₀ 含有 Block 0 的 cacheline 被設定成 Modified，他必須發 Probe Write 給 CPU₁，去看 CPU₁ 的 cache 中是否含有 Block 0。接著 CPU₁ 會收到 Probe write hit，因為其 cache 中有 Block 0 的資料。此時，CPU₁ 含有 Block 0 的 cacheline 也會被設定成 Invalid，因為其資料已過時。
CPU₁ 想對 Block 0 進行讀取，他會發 Probe read 給 CPU₀，接著 CPU₀ 會收到 Probe read hit，因為其 cache 中有 Block 0 的資料。因為這個 cacheline 的狀態是 Modified，當收到 Probe read hit 時，會將這份資料寫回主記憶體中，並將狀態改為 Shared，接著 CPU₁ 從 CPU₀ 讀取資料，並將其 cacheline 狀態設定成 Shared

MESI protocol 的缺點就是每次發送 Probe read 讀到一個狀態為 Modified 的 cacheline 時，就要將資料更新回主記憶體，但將資料寫回主記憶體是非常浪費時間的。

MOESI protocol

為了避免將資料寫回主記憶體，MOESI protocol 加入新的狀態 Owner，並略為修改 Shared 狀態的定義:

Owner(O)
- 其他 CPU 上的 cache 含有這份資料
- 在主記憶體中的這份資料和 cache 中存有的這份資料不一樣 (Owner 擁有的資料比較新)
- 其他 CPU 上的 cache 發 probe read 時，會將資料提供給他且不會寫回 memory
Shared(S)
- 其他 CPU 上的 cache 必定含有同一份資料
- 在主記憶體中的這份資料和 cache 中存有的這份資料可能是一樣的

CPU 對自己的 cache 下請求的狀態圖

取自 OpenMP, Cache Coherence

收到其他 CPU 上的 cache 下請求的狀態圖

取自 OpenMP, Cache Coherence

實作上，用 3 個 bit 來表示該 cacheline 的狀態，分別是 valid bit、dirty bit 和 shared bit，由這三個 bit 來組合出 MOESI 5 個不同的狀態:

	Valid bit	Dirty bit	Shared bit
Modified	1	1	0
Owner	1	1	1
Exclusive	1	0	0
Shared	1	0	1
Invalid	0	X	X

X 表示 doesn't matter

我們也舉例說明 MOESI protocol 的流程:

CPU₀ 對主記憶體中的 Block 0 進行讀取，因為 CPU₀ 是第一個且第一次進行讀取，因此這個 cacheline 的狀態會設定成 Exclusive
CPU₀ 想對 Block 0 進行寫入，CPU₀ 含有 Block 0 的 cacheline 被設定成 Modified，他必須發 Probe Write 給 CPU₁，但因為 CPU₁ 的 cache 中是空的，所以沒有任何改變。
CPU₁ 想對 Block 0 進行讀取，他會發 Probe read 給 CPU₀，接著 CPU₀ 會收到 Probe read hit，因為其 cache 中有 Block 0 的資料，CPU₁ 直接從 CPU₀ 讀取資料，並將其 cacheline 狀態設定成 Shared，而 CPU₀ 上的 cacheline 狀態則會從 Modified 變為 Owner。
CPU₀ 想對 Block 0 進行寫入，CPU₀ 含有 Block 0 的 cacheline 從 Owner 被設定成 Modified，他必須發 Probe Write 給 CPU₁，去看 CPU₁ 的 cache 中是否含有 Block 0。接著 CPU₁ 會收到 Probe write hit，因為其 cache 中有 Block 0 的資料。此時，CPU₁ 含有 Block 0 的 cacheline 也會被設定成 Invalid，因為其資料已過時。
CPU₁ 想對 Block 0 進行讀取，它會發 Probe read 給 CPU₀，接著 CPU₀ 會收到 Probe read hit，因為其 cache 中有 Block 0 的資料，CPU₁ 直接從 CPU₀ 讀取資料，並將其 cacheline 狀態設定成 Shared，而 CPU₀ 上的 cacheline 狀態則會從 Modified 變為 Owner。

透過上述案例我們可發現，整個過程中並沒有涉及到任何將 cache 中資料更新回主記憶體的動作，因此，MOESI protocol 成功解決要將資料寫回主記憶體的問題。

cache coherence 對程式效能的衝擊

接著我們考慮一個具備 3 層 cache 且有 2 個處理器核的系統，向下箭頭表示儲存 (即 write) 操作、向上箭頭表示載入 (即 read) 操作，對 CPU₀ 和 CPU₁ 來說，同顆 CPU 其左側操作的時序先於右側操作。如下圖:

在上圖中，有二個被原生執行緒 (native thread，指執行緒被作業系統核心識別，且納入排程的執行單元，在本例中，分別執行在 CPU₀ 和 CPU₁) 共享的變數 x 和 y，同時假定 CPU₁ 的執行緒先做 y = 0; 的儲存操作，使得在它的 cache 中都安排好存放變數 y 的 cache 內容 (entry)，且假定此時沒有關於任何針對變數 x 的 cache 內容。

首先，CPU₁ 的執行緒先對 y 進行 y = 0 的儲存操作，等該操作完畢後，CPU₀ 的執行緒才有動作。CPU₀ 的執行緒先做 x = 1 的儲存操作，接著做 y = 2 的儲存操作。完成之後，CPU₁ 的執行緒立即對 x 和 y 進行讀取。

我們從圖中可見，x 和 y 的儲存操作依次經過 CPU₀ 的 L1 cache, L2 cache，再是 CPU₀ 和 CPU₁ 共用的 L3 cache，最後到外部記憶體。此時，L3 cache 中已有 x 和 y 這兩個變數對應的 cache 內容。因此在 CPU₁ 讀取時，x 和 y 的寫入順序是一致的。

到了 CPU₁ 的 L2 Cache 時，由於之前沒有 x 相關的 cache 內容，因此此時 L2 cache 控制器會進行判斷是直接將它分配給一個空白的 cache 條目，抑或將已有的 cache 內容進行逐出 (evict)，然後將變數 x 所處的 cacheline 增添到到 cache 內容中。這裡就會有一些延遲與記憶體重新安排的情況。此時，由於變數 y 已處於 cache 內容中，因此它有可能被直接寫回（write back），只要之前針對 x 的 cacheline 的安排過程，不將 y 所處的 cacheline 予以逐出 (evict)。如此一來，右側執行緒所觀察到的寫入順序，就會變為先寫 y 再寫 x。

注意：上述情況僅僅是 memory order 的其中一種，x86 和 Arm 處理器中均引入 Non-Temporal 的載入和儲存操作，這些操作不會經由 cache，而是直接針對外部記憶體控制器進行存取。而它們的存取順序就是典型的 weak memory order，因為即便在匯流排上，都會有各種不同情況發生。這就好比說，在網際網路通訊時，先發送的請求反而後送達的情況，特別在無線網路訊號不佳的狀況，我們之前在通訊聊天軟體中發送的幾則訊息尚在「轉圈」(即等待發送)，等訊號品質變好時，往往是前次最後發送的那則訊息，率先送達予對方。

存取被多個執行緒頻繁共享的主記憶體往往很慢。在某些情境中，critical section (CS) 看似很短，但 spinlock 卻承受嚴重的效能問題，因為 spinlock 使用的 CAS 指令必須等待最新的 cacheline，看上去只有幾條指令，花費數千數萬 ns 也有可能。

要提高速度，就要避免讓 CPU 頻繁進行 cache coherence。這不單和 atomic 指令本身有關，還會影響到程式的整體表現。最有效的解決方法就是降低共享。

一個依賴全域 multi-producer/multiple-consumer (MPMC) 的程式難有好的 scalability，因為 MPMC 的極限吞吐量 (throughput) 取決於 cache coherence 的成本，而非處理器的個數! 最好是用多個 SPMC 或多個 MPSC，甚至多個 SPSC 代替，在源頭就規避掉競爭。
另一個例子是計數器，如果所有執行緒都頻繁修改一個計數器，性能就會大受影響，同樣是因不同的處理器不停地進行 cache coherence。若這個計數器只是用於輸出流水號碼，我們可用 thread-local storage (TLS) 改寫程式碼，然後規範特定時機點合併所有執行緒的數值，這樣相較之前，可能會有數十倍的效能落差。

相關的程式設計陷阱是 false sharing，示意如下:

cache line 的「所有權」獲取過程涉及到多個 CPU 之間的訊息傳遞，相較直接在單核進行操作，執行成本必定居高不下，然而此處有個陷阱：程式開發過程中，我們通常以變數作為「思想」操作的單元，但 CPU 之間競爭的單元卻是 cacheline (常見 64 個位元組)，於是上圖展示一種狀況：在並行的程式中，一個執行緒不斷寫入變數 X，另一個執行緒不斷寫入變數 Y，二者本來相互不衝突，但 X 和 Y 這二個變數在記憶體中的排列如果落在同一個 cache line 範圍，導致執行過程中，在兩個 CPU 之間不斷發生該 cacheline 的競爭，從而程式效率低落。如此本該「不分享」的二個變數，卻因 cacheline 而「分享」，影響到記憶體存取，就稱為 false sharing。

我們可用簡單的程式來測試

$ wget https://raw.githubusercontent.com/Zeosleus/False_Sharing/main/false_sharing.c
$ gcc -o false_sharing false_sharing.c -lpthread

在 AMD Ryzen Threadripper 2990WX 32-Core Processor 實驗:

有 false sharing 的狀況

$ ./false_sharing
Total wtime elapsed = 7.093128	seconds

抑制 false sharing

$ ./false_sharing --nofalse-sharing
Total wtime elapsed = 2.976462	seconds

我們可見 7.09 到 2.97 秒這樣顯著的落差。

用 $ sudo perf stat -d <執行檔和參數> 觀察:

有 false sharing

     175,3222,0759      L1-dcache-loads           # 1208.436 M/sec                    (62.51%)
      18,0305,0951      L1-dcache-load-misses     #   10.28% of all L1-dcache hits    (62.45%)

抑制 false sharing

     140,1115,6709      L1-dcache-loads           # 2353.822 M/sec                    (62.41%)
           48,4434      L1-dcache-load-misses     #    0.00% of all L1-dcache hits    (62.32%)

延伸閱讀:

Memory Ordering 和 Barrier

僅靠 atomic 指令，無法達到對共用資源的存取控制，即使簡單如 spinlock 或 reference count，看上去正確的程式碼也可能會出錯。為何？因為 memory (re)ordering:

為何有 memory reordering 呢？動機非常自然，CPU 要盡量塞滿每個 cycle，在單位時間內運行盡量多的指令。如前述，存取指令在等待 cache coherence 時，可能要花費數百 ns，最高效且直觀的策略是同時處理多個 cache coherence，而非一個接著一個。一個執行緒在程式碼中對多個變數的依次修改，可能會以不同的次序 cohere (coherence 的動詞) 到另一個執行緒所在的處理器上。不同處理器對資料的需求不同，也會導致 cacheline 的讀取和寫入順序的落差。

既然 CPU 會 reorder 指令的執行順序，為何沒有造成混亂？
因為有個前提：對於前後有資料的相依 (dependency) 的指令，CPU 通常不會去做 reorder (Alpha 架構除外)，可看作處理器提升速度所做最佳化策略的「底線」。

上圖中，前一道指令將 1 指派給變數 x，後一道指令將變數 x 的值指派給變數 y，那麼這兩道指令的執行順序 (通常) 不會被 CPU 改變。

對於沒有這種相依關係的指令，CPU 就有發揮的空間，不同架構的處理器的策略不同，這也是 CPU 的 memory ordering 要顧及的議題。

在 Arm 架構中，只要沒有相依關係，對指令的執行順序沒有要求，load 指令 (以 L 表示) 和 store 指令 (以 S 表示) 可任意交換，屬於 relaxed model，即 weak order。

$↑$ Arm: weak order

在 x86 中，對於同一 CPU 執行的 load 指令後接 load 指令 (即 L-L)，store 指令後接 store指令 (即 S-S)，load 指令後接 store 指令 (即 L-S)，都禁止交換指令的執行順序，只有 store 指令後接 load 指令 (即 S-L) 時才可。這種 memory order 被稱為 TSO (Total Store Order)，即 strong order。

$↑$ x86: TSO / strong order

為何唯獨 store 指令後接 load 指令這種情況，被 x86 允許重排呢？因為寫入一則資料的動作若尚未完成，一般沒多大影響，反之，如果讀取一則資料的操作沒完成，就可能對後面依賴這個資料的指令的繼續執行，造成影響，也就是 "stall"，因此 CPU 會優先保證讀取操作的完成。

換言之，「讀取」會比「寫入」重要，因此 load 可跑到 store 前面去執行，而 TSO (Total Store Order) 其他的三種情況，要不重要性相當，要不後面的一道指令較不重要。

不精準來說，memory order 一旦越 weak (不嚴格)，達到同等速度的硬體成本則越低。但也不要死板認定 x86 僅有 strong order，它也支持對 memory order 的動態調整 —— 處理硬體周邊 I/O 時，memory order 則 strong，其他時候則可適當地 weak，以獲取更好的速度。

依據 AMD 公司的手冊《AMD64 ArchitectureProgrammer's Manual Volume 2》第 7.1 節，AMD64 允許部分 out-of-order reads (L-L 形式的 reorder)，這與記憶體型態相關，詳見該手冊第 7.4.2 節 "Memory Barrier Interaction with Memory Types"。

延伸閱讀:

在亂序 (out-of-order) 執行時，一個處理器真正執行指令的順序，是由可用的輸入資料決定，而非程式開發者在程式碼規範的順序。現代處理器可分 in-order 和 out-of-order 等二種實作。

In-order processors (循序) 執行步驟

instruction fetch (IF)
若指令的 input operands 可用 (例如已在暫存器中)，則將此指令分派 (dispatch) 到適當的功能單元中。若一個或多個 input operands 不可用 (通常因為要從主記憶體獲取)，則處理器會等待直到它們可用
指令被適當的功能單元執行 (IE)
功能單元將結果寫回到 register file (CPU 的一組暫存器)

Out-of-order processors (亂序) 執行步驟

instruction fetch (IF)
指令被分派 (dispatch) 到 instruction queue
指令在 instruction queue 中等待，直到 input operands 可用 (一旦 input operands 可用，指令即可離開 instruction queue，即便更早的指令尚未執行)
指令被分派到適當的功能單元並執行 (IE)
執行結果被放入 queue 中，而非立即寫入 register file
只有所有更早請求執行的指令的執行結果被寫入 register file 後，指令執行的結果才被寫入 register file (即執行結果重排，讓執行看起來是有序的)

由上可見，亂序執行相比循序執行能夠避免等待不可用的 input operands (即上述 in-order 執行的第二步)，從而提高執行速度。現代電腦系統中，處理器執行的速度遠高於主記憶體，in-order 處理器花在等待可用資料的時間中，out-of-order 處理器已可處理大量指令。

總結 out-of-order 處理器的流程:

對單個 CPU 來說，instruction fetch (IF) 是循序的 (藉由 queue 實作)
對單個 CPU 來說，指令執行結果也是依序寫回 register file (也藉由 queue 實作)

由此可知，在單一處理器，不考慮編譯器優化，多執行緒執行不存在記憶體亂序存取的議題。從 Linux 核心原始程式碼中，也可得到類似的結論 (檔案: include/asm-generic/barrier.h)

#ifdef CONFIG_SMP
#define smp_mb() mb()
#else /* !CONFIG_SMP */
#define smp_mb() barrier()
#endif

若是 SMP 則使用 mb，即 CPU Memory barrier，而非 SMP 時，直接使用 compiler barrier。

前面討論 cache coherence 時，提到 MESI 一類的 protocol，我們知道，一個 CPU 要寫入資料前，必須發送 Probe write 去確保其他 CPU 已 invalid 同一位置的 cache，等到其他 CPU 回應 invalidate ack 後，才能寫資料到自己的 cache 中。這個設計確保資料的一致性，不用擔心同一時間同一個位置的資料會有不同的值，但是代價是寫入 cache 的速度較慢，讓 CPU 閒置。

假設 CPU₀ 打算寫入資料到位置 X，CPU₁ 的 cache 有 X 的內含值。存取延遲 (stall) 的原因如下：

CPU₀ 要等 CPU₁ 回應 invalidate ack
CPU₁ 的 cache 可能太忙而拖慢了回覆時間 (比方同時從 cache 大量的讀寫資料，或是短時間收到大量 invalidate ack)。

Store Buffer

針對上述問題，引入 store buffer 可縮短 CPU₀ 的閒置時間：

CPU₀ 不等 invalidate ack: 先寫入 store buffer，然後繼續作事。之後收到 invalidate ack 再更新 cache 的狀態。因為最新的資料可能存在 store buffer，CPU 讀資料的順序變成 store buffer
$\to$ cache
$\to$ memory。
CPU₁ 立即回覆 invalidate ack: 收到 invalidate 時，記錄到 invalidate queue 裡，先回 invalidate ack，稍後再處理 invalidate。

對應的 cache 架構如下：

更新資料時，CPU 會先將更新後的資料置於 store buffer，由於訊號發送是非同步，cache 和 store buffer 內部資料可能不一致，於是需要先讀取 store buffer 裡頭的資料，即 cache with store forwarding。

然而，某些問題無法藉由 store buffer forwarding 解決。考慮以下程式碼: (foobar.c)

int a = 0, b = 0;
void foo(void)
{ 
    a = 1; 
    b = 1;
}

void bar(void)
{ 
    while (b == 0)
        continue; 
    assert(a == 1);
}

變數 a 和 b 起初都是 0。假設 CPU₀ 執行 foo()， CPU₁ 執行 bar()，且 cache 的狀態如下:

CPU	`a`	`b`
CPU₀	Shared	Modified
CPU₁	Shared	Invalid

步驟如下:

CPU₀ 即將執行 a = 1 但 CPU₀ cache 中不存在 a，於是寫入 a 的值 (= 1) 到 store buffer (但 cache 裡仍是 0)
CPU₀ 廣播 "invalidate a"，注意這個操作的成本較高，先發送廣播，但 CPU₀ 不會等待廣播完成，而是繼續執行
CPU₁ 執行 while (b == 0) continue 時，CPU₁ cache 不存在 b，因此 CPU₁ 要發送訊息向 CPU₀ 取值。
CPU₀ 繼續執行，遇到 b = 1，因為 b 只在 CPU₀ cache 中，CPU 直接更新 cache 內容
CPU₀ 收到讀取的訊息，將 b 最新內容 (即 1) 傳遞給 CPU₁
CPU₁ 收到 CPU₀ 的訊息後，將 b 更新為 1
CPU₁ 再次執行 while (b == 0) continue 時，b 為 1，於是接著準備執行 assert(a == 1)
CPU₁ 準備執行 assert(a == 1) 時，a 的值仍為 0 (invalidate 訊息處理較慢)，這會使得 assert 失敗
CPU₁ 收到 CPU₀ 送來 "invalidate a" 的訊息，但已太遲，前一步驟的 assert 失敗已造成

歸納可知，a = 1 對 CPU₁ 來說還不知道，但 CPU₀ 卻早知道 b = 1。問題出在 store buffer 破壞 cache coherence，資料不再是同一時間只有一份值。於是 CPU 需要提供 write memory barrier (簡稱 wmb)，讓軟體得以避免這個問題。

write memory barrier 確保之前在 store buffer 裡的資料會先更新到 cache，然後才能寫入 barrier 之後的資料到 cache。假設我們在 foo() 的 a = 1 和 b = 1 之間插一個 write memory barrier，如 smp_mb:

void foo(void)
{
    a = 1;
    smp_mb();
    b = 1;
}

實作方式如下:

write memory barrier 先設定 store buffer 裡的資料為 "marked" (即 a = 1)
寫入 b 時 (即 b = 1)，因發現 store buffer 裡有 marked 的欄位，所以即使 b 已處於 Modified，仍需寫入 b = 1 到 store buffer，不過狀態是 "unmarked"，所以 b = 1 不會寫到 cache
CPU₁ 向 CPU₀ 要求 b 的內含值時，仍是 0
直到 CPU₀ 收到 CPU₁ 對 a 的 invalidate ack 後，cache 中 a 的狀態改為 Modified，接著先寫入有 marked 欄位的值到 cache，再寫入 unmarked 欄位的值到 cache。
更新 a = 1 到 cacheline 後，才會更新 b = 1 到 cacheline

這樣其它 CPU 就會依序看到 a 和 b 更新的值，也就不會觸發 assert 失敗。

延伸閱讀:

x86 TSO: A Programmer's Model for x86 Multiprocessors

invalidate queue

由於若要更新特定的 cacheline，就要讓其他 CPU 對應的 cacheline 變成 invalid。收到 invalidate 訊息的 cache 可能來不及處理，又因為 store buffer 很小，store buffer 一旦填滿時，CPU₀ 還是得等 invalidate ack，所以加上 invalidate queue，雙管齊下縮減 CPU₀ 等待時間。

擴展後的 cache 架構如下：

cache 會將收到的 invalidate 訊息先放置於 invalidate queue，並回報 ACK 的訊息。這樣的設計使得多個 CPU 之間的關係更複雜，由於 invalidate queue導致 Invalidate 訊息的處理會被延遲，所以 CPU 先發出的 load 操作可能在讀出之際，已被確認 Invalidate 但在本地 CPU 狀態尚未切換 cache line，導致 CPU 的 load 操作也會是重排。

換言之，invalidate queue 會導致新的問題：若 CPU 需要對其他 CPU 發送 Probe Write 前，必須要先檢查 invalidate queue 中有無該 cacheline 的 invalidate 請求，若有，則需要先行處理。若不先處理invalidate queue 中對應的 Invalidate 消息直接對其他 CPU 發送 Probe Write，那麼，這次的寫入操作就會直接被送到 store buffer 中，後續 CPU 再進行處理時，store buffer 有寫該 cacheline 的請求，而 invalidate queue 有讓該 cacheline 狀態改為 Invalid 的請求，那到底該以哪個為準？若都以 store buffer 為準，假如 invalidate queue 中的請求是後於 store buffer 產生的，表示其他 CPU 後續又對該cacheline 進行了寫入，但此時 store buffer 中的舊值會被寫到 cacheline 且標示 Modified，這顯然是錯的。反之，以 invalidate queue 為準，那 store buffer 的請求後於 invalidate queue，那一樣也會產生錯誤。

回顧稍早提及的 foobar.c 程式碼。初始情況假定 a 和 b 都為 0，且 a 同時在 CPU 0 和 CPU 1 的cacheline 中，b 只在 CPU 0 的 cacheline 中。由此，a 對應的 cacheline 狀態為Shared，b 對應的 cacheline 狀態為 Exclusive，CPU 0 執行 foo()，CPU 1 執行 bar()。

void foo()
{ 
    a = 1;
    smp_mb();
    b = 1;
}
void bar() 
{
    while(b == 0) 
        continue;
    assert(a == 1);
}

假設程式執行順序如下:

CPU₀ 執行 a = 1，發現 a 在 cache 中但 cacheline 狀態為 Shared，便發送 Probe Write 給其他 CPU，同時將 a 的值 1 寫入store buffer
CPU₁ 執行 while loop，發現 b 不在 cache 中(cache miss)，便發送 Probe Read 給其他 CPU
CPU₁ 收到來自 CPU₀ 的 Probe Write 消息，將這個請求加到 invalidate queue中並立即回應 invalidate ack 給 CPU₀
CPU₀ 執行 smp_mb，將目前在 store buffer 中的 entry 做標記
CPU₀ 收到 invalidate ack，將 store buffer 中的 a = 1 寫入到 cacheline 中，並將狀態改為 Modified
CPU₀ 執行 b = 1，因為 store buffer 為空，沒有任何被標記的 entry，b 也已在 cache 中且狀態是 Exclusive，故可以直接將值 1 寫入 cacheline，將cacheline 狀態變更為 Modified
CPU₁ 收到變數 b 的資料，並將消息中的 cacheline 放入到自身的 cache
CPU₁ 從 cache 中載入 b 值，發現為 1，結束 while 迴圈
CPU₁ 執行 assert，從 cache 中讀取 a 值，發現為 0，觸發assert 錯誤
CPU₁ 處理 invalidate queue 中的 Probe Write，將 a 所在的 cacheline 設為 Invalid
CPU₁ 執行 assert，因為剛剛 a 所在的 cacheline 狀便被改為 Invalid 了，等同於 a 不在 cache 中，所以 CPU₁ 會發送 Probe Read

從上述執行結果來看，引入 invalidate queue 確實加速 CPU₀ 的執行，但即使加上 memory barrier，對 CPU₁ 來說，CPU₀ 仍然發生了 I/O reordering。原因在於兩者對於 invalidate cacheline 的理解不一致，CPU₀ 認為既然發出了 invalidate acknowledge，你的 cache 中就不會有 a 對應的 cacheline，因為那條 cacheline 被設定為 Invalid，而 CPU₁ 則認為將 invalidate 消息放入 invalidate queue，已讓 a 的 cacheline 失效。

為了讓這二個 CPU 執行程式時達成一致，我們仍然是透過 memory barrier，後者要求該 CPU 必須先處理完在 invalidate queue 中所有的請求，修改後程式碼如下:

void foo()
{ 
    a = 1;
    smp_mb();
    b = 1;
}
void bar() 
{
    while(b == 0) 
        continue;
    smp_mb();
    assert(a == 1);
}

加入 memory barrier 後程式執行順序如下:

CPU₀ 執行 a = 1，發現 a 在 cache 中但 cacheline 狀態為 Shared，便發送 Probe Write 給其他 CPU，同時將 a 的值 1 寫入store buffer
CPU₁ 執行 while loop，發現 b 不在 cache 中 (即 cache miss)，便發送 Probe Read 給其他 CPU
CPU₁ 收到來自 CPU₀ 的 Probe Write 消息，將這個請求加到 invalidate queue 中並立即回應 invalidate ack 給 CPU₀
CPU₀ 執行 smp_mb，將目前在 store buffer 中的 entry 做標記
CPU₀ 收到 invalidate ack，將 store buffer 中的 a = 1 寫入到 cacheline 中，並將狀態改為 Modified
CPU₀ 執行 b = 1，因為 store buffer 為空，沒有任何被標記的 entry，b 也已在 cache 中且狀態是 Exclusive，故可以直接將值 1 寫入 cacheline，將 cacheline 狀態變更為 Modified
CPU₁ 收到變數 b 的資料，並將消息中的 cacheline 放入到自身的 cache
CPU₁ 從 cache 中載入 b 值，發現為 1，結束 while 迴圈
CPU₁ 執行 smp_mb，後者要求 CPU₁ 必須先處理完 invalidate queue 中的請求，於是 Probe Write 的請求是關於 a 的，故將 a 對應的 cacheline 設為 Invalid
CPU₁ 執行 assert，從 cache 中讀取 a 值發現是 Invalid，於是發出 Probe Read
CPU₀ 處理來自 CPU₁ 的 Probe Read，將 a 所在的 cacheline 設為 Shared，將 a 的資料送給 CPU₁
CPU₁ 收到變數 a 的資料，並將消息中的 cacheline 放入到自身的 cache
CPU₁ 從 cache 中載入 a 值，發現為 1，不再觸發 assert 錯誤

從上述執行結果來看，smp_mb 再次保證多處理器程式的執行達到預期結果。當然，使用 smp_mb 會增加執行成本，因為必須先處理 store buffer 或是 invalidate queue，且以上問題也是在特定的執行順序才會發生。不過，當執行次數夠多時，上述情形必然會發生，而且資料的正確是我們首要議題。

為了約束與 store buffer 和 invalidate queue，用到smp_mb。也就是說，CPU 執行指令中如果遇到 smp_mb，則需要處理 store buffer 和 invalidate queue。但其實從程式碼來看，foo( ) 中的 smp_mb 其實只需要處理 store buffer 的部分，而 bar( ) 中的則只需要處理 invalidate queue 。有些 CPU 提供更為細分的 smp_mb，細分為 read memory barrier 和 write memory barrier，前者只會處理 invalidate queue，而後者只會處理 store buffer。顯然，只處理其中之一肯定比同時處理二者效率要高，不過約束就會更少，可能的行為也就越多。

硬體實作策略

從 sequential consistency (SC) 的角度來說明什麼順序對 SC 來說是不允許的。sequential consistency 的定義最初是 Leslie Lamport 在 1979 年提出：

… the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.
Leslie Lamport, 1979

考慮以下程式碼：

從 SC 的角度來說，the order specified by its program 這句話的意思就是在說 {b,d,a,c} 這種順序是不會發生的。但在並非嚴格 SC 的現代處理器中，foo == bar == 0 可能會發生。

硬體為了減少讀寫 memory 而有 cache。有 cache 就要確保 cache 之間的資料一致 (同一時間同一位置只有一個值)。但確保 cache 資料完全一致容易讓 CPU 閒置，於是有了 store buffer 和 invalidate queue 降少 CPU 閒置。代價是只保證 CPU 自己會讀到自己寫入的最新資料，但其它 CPU 不一定。

為了讓其它 CPU 有需要的時候也能讀到最新的資料，針對 store buffer 和 invalidate queue 的副作用設計了 write/read memory barrier。於是寫軟體的人在需要的時候可以用 memory barrier 確保關鍵的資料有依正確的順序更新 (無法保證更新的時間)。CPU 在多數情況下仍能避免閒置。

到此可理解為何這二種操作搭配，較符合現代處理器架構：

一個執行緒「先 write X，後執行 write memory barrier」
另一個執行緒「先執行 read memory barrier，後 read X」

二者合起來構成 happens-before 關係。由此可理解 sequential consistency (SC) 和多核硬體的運作方式差太多，會太常讓多個 CPU 閒置，無法發揮多 CPU 的效能。因此程式開發者應儘量避免依賴 SC。

延伸閱讀: 並行程式設計: 執行順序

硬體設計者引入 read memory barrier 和 write memory barrier，其中 read memory barrier 只對 invalidate queue 有效，write memory barrier 只對 store buffer 有效。

延伸閱讀:

Memory Barriers: a Hardware View for Software Hackers

參考 I/O ordering 學習紀錄中的實驗，我們利用 litmus7 在硬體架構為 arm64 的機器上進行實驗，實驗程式碼如下： (arm000.litmus)

ARM arm000
"PodWW Rfe PodRR Fre"
Cycle=Rfe PodRR Fre PodWW
Relax=
Safe=Rfe Fre PodWW PodRR
Generator=diy7 (version 7.56.2)
Prefetch=0:x=F,0:y=W,1:y=F,1:x=T
Com=Rf Fr
Orig=PodWW Rfe PodRR Fre
{
%x0=x; %y0=y;
%y1=y; %x1=x;
}
 P0           | P1           ;
 MOV R0,#1    | MOV R1,#1    ;
 STR R0,[%x0] | STR R1,[%y1] ;
 LDR R0,[%y0] | LDR R1,[%x1] ;
exists (0:R0=0 /\ 1:R1=0)

上方程式碼是 litmus7 的語法，首先宣告兩個共享變數 x, y，且初始化為 0，接著，CPU₀ 所做的事情是寫入 a = 1 和讀取 b，而 CPU₁ 所做的事情是寫入 b = 1 和讀取 a，二個 CPU 都是做一個 store 指令接著一個 load 指令，我們藉由本實驗，想觀察是否出現「CPU₀ 讀到的 b 是 0，而 CPU₁ 讀到的 a 也是 0」的情況。

利用 litmus7 執行上面提供的測試程式，並重複執行 1000000 次，結果如下:

Test arm000 Allowed
Histogram (3 states)
15    *>0:R0=0; 1:R1=0;
499994:>0:R0=1; 1:R1=0;
499991:>0:R0=0; 1:R1=1;
Ok

Witnesses
Positive: 15, Negative: 999985
Condition exists (0:R0=0 /\ 1:R1=0) is validated
...
Time arm000 0.38
...

根據上述實驗結果，可發現出現 15 次 CPU₀ 讀到的 b 是 0，而 CPU₁ 讀到的 a 也是 0 的情況，代表其中一個或兩個 CPU 發生 memory reordering 的情況，否則正常執行下至少會有一個 CPU 讀到的值為 1。

為了測試 memory barrier 是否有效，我們在 store 指令與 load 指令之間加上 arm64 架構提供的 memory barrier 指令 DMB。

摘錄 ARM Compiler toolchain Assembler Reference Version 4.1：

Data Memory Barrier acts as a memory barrier. It ensures that all explicit memory accesses that appear in program order before the DMB instruction are observed before any explicit memory accesses that appear in program order after the DMB instruction. It does not affect the ordering of any other instructions executing on the processor.

也就是說 DMB 指令的作用是，保證在 DMB 之後記憶體存取相關的指令都「看到」DMB 之前記憶體存取相關的指令的結果。

加入 DMB 指令:

  P0           | P1           ;
  MOV R0,#1    | MOV R1,#1    ;
  STR R0,[%x0] | STR R1,[%y1] ;
+ DMB          | DMB          ;
  LDR R0,[%y0] | LDR R1,[%x1] ;
 exists (0:R0=0 /\ 1:R1=0)

利用 litmus7 執行上面提供的測試程式，並重複執行 1000000 次，結果如下:

Test arm000 Allowed
Histogram (3 states)
499998:>0:R0=1; 1:R1=0;
500000:>0:R0=0; 1:R1=1;
2     :>0:R0=1; 1:R1=1;
No

Witnesses
Positive: 0, Negative: 1000000
Condition exists (0:R0=0 /\ 1:R1=0) is NOT validated
...
Time arm000 0.46
...

透過實驗結果可發現加入 memory barrier 之後，不再出現 CPU₀ 讀到的 b 是 0，而 CPU₁ 讀到的 a 也是 0 的情況。另外，也可發現，加入 memory barrier 之後的執行時間較長。由實驗證實，雖然加入 memory barrier 確實會影響效能，但為了保證資料的正確性，這是必要的犧牲。

軟體觀點

現代編譯器進行最佳化時，會引入多種策略。考慮到以下程式碼:

int x, y;

void foo()
{
    x = y + 1;
    y = 0;
}

我們藉由 gcc 來編譯並比較有無最佳化的組合語言 (以 Arm64 為探討標的)。

抑制最佳化

$ gcc -S foo.c
$ cat foo.s
...
foo:
.LFB0:
    .cfi_startproc
    adrp	x0, :got:y
    ldr	x0, [x0, #:got_lo12:y]  // load y to x0
    ldr	w0, [x0]                // load y to w0
    add	w1, w0, 1               // add w0 with 1 to w1
    adrp	x0, :got:x
    ldr	x0, [x0, #:got_lo12:x]  // load x to x0
    str	w1, [x0]                // store w1 to x 
    adrp	x0, :got:y
    ldr	x0, [x0, #:got_lo12:y]  // load y to x0
    str	wzr, [x0]               // store 0 to y
    nop
    ret
...

啟用 -O2 最佳化等級

$ gcc -S -O2 foo.c -o foo1.s
$ cat foo1.s
...
foo:
.LFB0:
    .cfi_startproc
    adrp	x0, :got:y
    adrp	x1, :got:x
    ldr	x0, [x0, #:got_lo12:y] // load y to x0
    ldr	x1, [x1, #:got_lo12:x] // load x to x1
    ldr	w2, [x0]               // load y to w2 
    str	wzr, [x0]              // store 0 to x
    add	w0, w2, 1              // add w2 with 1 to w0
    str	w0, [x1]               // store w0 to x
    ret
...

觀察以上 Arm64 組合語言可知，在沒有最佳化下，程式會先做完 x = y + 1 的 store 指令接著再完成 y = 0 的 store 指令，但在利用 O2 最佳化的情況下，程式先做 y = 0 的 store 指令，再做x = y + 1 的 store 指令，因為程式把 y 的值先存在暫存器 w2 中，後續的計算直接從暫存器 w2 取值，這樣的指令重排不影響單一執行緒的資料正確性。

然而，在並行多執行緒程式中將可能導致資料的不正確，試想，如果程式中的 y 作用如果是 lock，在設成 0 之後其他執行緒才能進入 critical section 中更改 x 的資料，但在指令重排之後，某一執行緒把 y 先被設成 0，才改動 x 的資料，而另一執行緒看到 y 變成了 0，也馬上進到 critical section 中去改 x 的資料，同時讓兩個執行緒進入 critical section 修改同一份資料顯然違反了程式的正確性。

如果我們想要讓程式運作符合預期，就要有辦法明確告知編譯器，特定的讀寫操作都要確實地去記憶體位置上讀寫，不能用臨時結果，例如用 -O2 最佳化後的測試程式用存在暫存器 w2 中的結果。

讀到這裡，你是否覺得處理器和編譯器的設計者為了提升速度，真是無所不用其極，這樣軟體開發如何安心地撰寫程式呢？慶幸的是，處理器和編譯器的設計者除了做出這些激進的速度提升方案，也給留下後路，讓我們能夠在需要時，運用這些機制來抑制對處理器和編譯器施加的激進手段，從而確保程式的正確。

圖片出處

對於編譯器來說，compiler barrier 有如前述程式 cacheline.c 第 29 行的 asm volatile("" ::: "memory");，其作用是告訴編譯器，不管進行何種最佳化手段，程式的讀寫操作影響不該跨越這個「屏障」，更白話來說是，要求編譯器不要自作聰明，在 asm volatile("" ::: "memory"); 出現後的讀寫都確實地去記憶體位置上讀寫，不能偷懶用「屏障」之前的臨時結果。

另一個由 Linus Torvalds 提出的 compiler barrier 的例子，考慮以下程式碼:

local_cpu_lock = 1;
// .. do something critical ..
local_cpu_lock = 0;

對於編譯器來說，一旦發現 local_cpu_lock 跟 .. do something critical .. 裡頭的程式沒有任何的相關性。在沒有 barrier() 的情況下，local_cpu_lock 可能被編譯器重排，甚至 local_cpu_lock = 1 這行程式碼可能會在編譯器最佳化時被移除，畢竟 local_cpu_lock = 1 後再設定為 local_cpu_lock = 0，第一個動作可能被認定是無效操作 (NOP)。為了確保程式邏輯的正確性，就該加入 barrier() 來抑制編譯器最佳化。

Linux 核心針對 compiler barrier 的巨集是 barrier()，對應 gcc 的定義如下: (詳見 include/linux/compiler-gcc.h:

/* The "volatile" is due to gcc bugs */
#define barrier() __asm__ __volatile__("": : :"memory")

你或許好奇，空的指令要怎麼發揮作用？

barrier 巨集利用 inline assembly 的 clobber list 裡的 "memory"，clobber list 是 gcc 和 gas (GNU Assembler) 的介面，用於 gas 通知 gcc 對暫存器和記憶體的修改情況。此處 "memory" 就是告知 gcc，在組合語言中，實際修改記憶體中的內容，之前和其後的 C 程式碼所見的記憶體內容不同，對記憶體的存取不能依賴此前暫存器的內容，編譯器應當自記憶體讀取資料。

要注意的事情是，compiler barrier 無法避免 CPU 在執行指令時，對指令進行重排。如果要避免 CPU 在執行期間對於指令進行重排，需要利用 memory barrier 來達成（詳見下文中 Dekker's algorithm 的實作）。

CPU 針對可能出現的重排，一般可分類為 3 種 memory barrier:

儲存屏障 (store barrier/fence)：維持 barrier 前後的 store 操作的順序，即 barrier 後的 store 一定發生在 barrier 前的 store 之後。
- 呼應前述處理器設計，store barrier 的作用在於在 Store Buffer
- 實作既可等待 Store Buffer 清空，亦可在 Store Buffer 中寫入一個標記，並禁止後續的 store 指令直接寫入 cache，轉而寫入 Store Buffer 中，直到 Store Buffer 中沒有標記，才恢復正常
讀取屏障 (load barrier/fence): 維持 barrier 前後的 load 操作的順序，即 barrier 後的 load 一定發生在 barrier 前的 load 之後。
- 呼應前述處理器機制，load barrier 的作用在於 Invalidate Queue
- load barrier 會強制等待 Invalidate Queue 清空才繼續執行，這樣可消除其引發的讀取重排問題
全屏障 (full barrier/fence): 作用相當於前二者之和

Full Fence : std::atomic_thread_fence()，可防止任二種操作的 reordering，除了 StoreLoad 以外。
![Full Fence]

Acquire Fence : atomic_thread_fence(std::memory_order_acquire)，可防止 Load 被排到 barrier 後面。或是 barrier 後面的read(load) / write(store) 不可重排到 barrier 前面的 load。

Release Fence : atomic_thread_fence(std::memory_order_release)，可防止後面的 Store 被排到前面。或是 barrier 前面的 read(load) / write(store) 不可重排到 barrier 後面的 store。

於是:

acquire fence = LoadLoad + LoadStore barrier
release fence = LoadStore + StoreStore barrier.

歸納可得到以下關係圖。

Arm 架構中，針對 memory barrier 提供 DMB, DSB, ISB 等指令。

以 Inner Shareable (IS) 為例，使用 DSB 指令加上 ISH，可防止所有 load 指令和 store 指令的 reorder (即 full memory reorder)。若只想抑制 L-L 和 L-S 之間的 reorder (即 read memory barrier)，應用ISHLD。若只想抑制 S-S 之間的重排 (write memory barrier)，則該用 ISHST。Arm 用 ISHLD + ISHST 的效果，等同於 x86 預設 memory order。

指令	場景	特徵
`ISHLD`	Load-Load, Load-Store	Inner Shareable
`ISHST`	Store-Store	-
`ISH`	Any-Any	-

$↑$ Arm: memory barrier 指令

x86 中用於設定 "full memory barrier" 的指令是 fence，依據 x86 預設的 memory order，只在防止 S-L 這種情況的 reorder 才要特別處理，但前面提過，x86 的 memory order 強度可調整，因此仍有針對 write memory barrier 的 sfence 指令和設定 read memory barrier 的 lfence 指令。

關於 memory barrier，我們要留意以下:

memory barrier 不提供時間保證
- store barrier/fence 指令執行結束並不代表 Store Buffer 已清空並寫入 cache 中 (所謂的「全區域可見」)，memory barrier 只提供 barrier 前後指令的順序保證
memory barrier 沒有辦法對其他 CPU 產生影響
- 在某個 CPU 執行的 memory barrier 指令，無法對其他 CPU 的 cache 和執行產生直接影響，只會改變其他 CPU 看到的本 CPU 的記憶體存取順序
memory barrier 需要成對使用
- 即使藉由 store barrier/fence 維持 barrier 前後的 store 操作順序，由於 Invaliate Queue 的影響，其他 CPU 可能仍無法看到正確的順序，因此在程式碼中，store barrier/fence 仍要和 load barrier/fence 成對使用

我們考慮一個程式場景：若其中首個變數扮演開關的作用，控制對後續變數的存取，那麼當這些變數被一起 cohere 到其他處理器時，更新順序可能變，第一個變數未必是第一個更新的，然而其他執行緒還認為它代表著其他變數有效，去存取實際已被刪除的變數，從而導致未定義的行為。程式碼列表如下:

struct object *p;

/* Thread 1 */ {
    /* ready was initialized to false */
    p = init();
    ready = true;
    ...
}

/* Thread2 */ {
    if (ready) {
        p->bar();
    }
}

乍看之下，這似乎沒錯，因為 Thread₂ 在 ready 為 true 時，才會存取 p，按 Thread₁ 的邏輯，此時 p 應完成初始化。但對多核處理器來說，上述程式碼執行結果可能無法符合我們的預期:

Thread₁ 中的 ready = true 可能會被編譯器或處理器 reorder 到 p = init() 之前，從而使 Thread₂ 看到 ready 為 true 時，p 尚未初始化。這種情況同樣也會在 Thread₂ 中發生，p->bar() 裡頭部分程式碼可能被 reorder 到檢查 ready 之前。
即使不存在 reorder，ready 和 p 的值也會獨立地 cohere 到 Thread₂ 所在處理器的 cache，Thread₂ 仍然可能在看到 ready 為 true 時，看到未初始化的 p

注：x86 和 x64 的 load 具備 acquire 語意，store 具備 release 語意，上面的程式碼扣除編譯器因素，可符合預期地執行。

CPU 和編譯器提供 memory barrier，讓開發者得以指定指令間的 visibility 關係:

memory order	作用
memory_order_relaxed	沒有 memory barrier，允許編譯器和處理器充分發揮。若目前操作為 atomic，則只保證該 atomic 操作的順序
memory_order_consume	後面依賴此 atomic 變數的存取指令，不得重排至此條指令之前
memory_order_acquire	後面存取指令不得重排至此條指令之前
memory_order_release	前面存取指令不得重排至此條指令之後。當此條指令的結果對其他執行緒可見後，之前的所有指令都可見
memory_order_acq_rel	acquire + release 語意
memory_order_seq_cst	acq_rel 語意外加所有使用 seq_cst 的指令有嚴格地順序，若沒指定 memory order，則預設採用

以上 6 種 memory order 的 weak 及 strong 關係，如下圖:

memory_order_acquire (用於記憶體資料「讀取」，即 load) 與 memory_order_release (用於記憶體資料「寫入」，即 store) 成對使用時，建立 Release-Acquire ordering，其效果是抑制指令重排:

在 load 之後的讀寫將被禁止重排到此操作之前
在 store 之前的讀寫將被禁止重排此操作之後

主要效果是，確保在 Thread_A 的 store 之前對記憶體的操作，對 Thread_B 的 load 是可見的 (visible)。

上圖展示 acquire 和 release 語意，可發現沒有用到 store-load barrier，而 x86 剛好只有 store load 重排，因此 x86 架構確保 Lock Acquire 和 Unlock Release。但對於 Aarch64 之類的處理器架構，又有不同的表現。

memory_order_consume (用於記憶體資料「讀取」，即 load) 與 memory_order_release 成對使用時，建立 Release-Consume ordering，後者相較於 Release-Acquire ordering 的限制更弱，因此允許編譯器和處理器做更多調整。在 load 之後與操作變數有相依性的其他讀寫將被限制重排，反之，沒有相依性的操作則不在此限。

有了 memory order，上面的例子可更正如下:

/* Thread1 */ {
/* ready was initialized to false */
    p = init();
    atomic_store_explicit(&ready, true, memory_order_release);
}

/* Thread2 */ {
    if (atomic_load_explicit(&ready, memory_order_acquire)) {
        p->bar();
    }
}

Thread₂ 中的 acquire 和 Thread₁ 的 release 配對，確保 Thread₂ 在看到 ready == true 時，能看到 Thread₁ 的 release 之前，所有的存取操作。

注意，memory barrier 不等於「立即可見」，即使 Thread₂ 恰好在 Thread₁ 處於將 ready 設定為 true 後，讀取 ready 也不意味著它能看到 true，因為 cache coherence 會有時間差！memory barrier 保證的是可見性的順序：「假如我看到 a 的最新值，那我一定也得看到 b 的最新值」。

這又帶出另一個問題：如何得知數值是新或舊？一般分兩種情況：

值是特殊的。在例子，ready = true 是個特殊值，只要 Thread₂ 看到 ready 為 true 就意味著更新。只要設定特殊值，讀到或沒有讀到特殊值都代表一種意義。
總是累加。一些場景下沒有特殊值，那我們就用 atomic_fetch_add 之類的 atomic 操作累加一個變數，只要變數的值域足夠大，在很長一段時間內，新值和之前所有的舊值都會不相同，我們就能區分彼此。

C11 標準 (5.1.2.4 和 7.17.4 章節) 描述 fence-to-fence 和 fence-to-atomic 同步 (即 "synchronizes with" 語意)，若只用 memory fence/barrier 不足以同步 non-atomic 或 relaxed atomic load/store 操作，因為這些必須要有成對的 atomic 操作 (規格書原文: "… if there exist atomic operations …" and ".. is sequenced before ..")。

C11 刻意不將 acquire/release fences 定義為 "acquire/release operations"，相反地，C11 定義 "acquire/release semantics" —— 看似只是文字遊戲，但實際行為大異其趣。在 C11 規範中，memory fence 必須搭配 atomic_{load,store}_*() 使用，即便 load/store 已是 memory_order_relaxed。

接下來思考二個範例，都是共用記憶體的存取。

經典的 publisher (訊息發布者) 和 subsriber (訊息訂閱者) 模式

/* Thread A */
    *val = 1;
    atomic_thread_fence(memory_order_release);
    atomic_store_explicit(published, 1, memory_order_relaxed);

/* Thread B */
   if (atomic_load_explicit(published, memory_order_relaxed) == 1) {
        atomic_thread_fence(memory_order_acquire);
        assert(*val == 1); /* 不會失敗 */
    }

但若改寫為以下:

/* Thread A */
    *val = 1;
    atomic_thread_fence(memory_order_release);
    *published = 1;

/* Thread B */
    if (*published == 1) {
        atomic_thread_fence(memory_order_acquire);
        assert(*val == 1); /* 可能會失敗 */
    }

裡頭的 assert 可能會失敗，正因 memory fence 沒有搭配正確的 atomic_store。

延伸閱讀:

Memory fences, atomics and C11 memory model

易於誤用 `volatile` 關鍵字

使用 C 或 C++ 程式語言的開發者應該對 volatile 關鍵字不陌生，但後者在多執行緒的環境中很容易被誤用。我們先回顧 volatile 的作用：在變數宣告前加上該關鍵字，表示這個變數「可能被意外地修改」，並要求編譯器每次使用該變數時，都要從記憶體地址中讀出最新內容。

換言之，volatile 的使用意味著抑制編譯器最佳化，不少人忽略到一個事實：程式中對 volatile 的使用，有時無法達到預期效果。這是因為僅保證編譯器不進行最佳化，不能保證 CPU 不會遭遇重排，若讀取操作被提前，即使抑制最佳化，也可能讀出意料之外的資料。

以下是 Dekker's Algorithm 的實作程式碼: (檔名: dekker.c)

















































































#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

static volatile int flag1 = 0, flag2 = 0, turn = 1;
static volatile int counter = 0;
int loop_cnt;

static void dekker1(void)
{
    flag1 = 1;
    turn = 2;
    // __atomic_thread_fence(__ATOMIC_SEQ_CST);
    while ((flag2 == 1) && (turn == 2))
        ;
    /* critical section */
    counter++;
    /* let the other task run */
    flag1 = 0;
}

static void dekker2(void)
{
    flag2 = 1;
    turn = 1;
    // __atomic_thread_fence(__ATOMIC_SEQ_CST);
    while ((flag1 == 1) && (turn == 1))
        ;
    /* critical section */
    counter++;
    /* leave critical section */
    flag2 = 0;
}

static void *task1(void *arg)
{
    printf("Starting %s\n", __func__);
    for (int i = loop_cnt; i > 0; i--)
        dekker1();
    return NULL;
}

static void *task2(void *arg)
{
    printf("Starting %s\n", __func__);
    for (int i = loop_cnt; i > 0; i--)
        dekker2();
    return NULL;
}

int main(int argc, char **argv)
{
    pthread_t thread1, thread2;

    if (argc != 2) {
        fprintf(stderr, "Usage: %s <loopcount>\n", argv[0]);
        exit(1);
    }

    loop_cnt = atoi(argv[1]); /* FIXME: format checks */
    int expected_sum = 2 * loop_cnt;

    (void) pthread_create(&thread1, NULL, task1, NULL);
    (void) pthread_create(&thread2, NULL, task2, NULL);

    void *ret;
    (void) pthread_join(thread1, &ret);
    (void) pthread_join(thread2, &ret);
    printf("Both threads terminated\n");

    /* Check result */
    if (counter != expected_sum) {
        printf("[-] Dekker did not work, sum %d rather than %d.\n", counter,
               expected_sum);
        printf("%d missed updates due to memory consistency races.\n",
               (expected_sum - counter));
        return 1;
    }
    printf("[+] Dekker worked.\n");
    return 0;
}

這個程式碼中，我們可見變數 flag1, flag2 和 turn 皆已宣告為 volatile，倘若就此認為執行緒總能讀到這 3 個變數的「最新數值」，既然 Dekker's Algorithm 已被證明理論是正確的，那麼程式執行結果如何？一樣在 AMD Ryzen Threadripper 2990WX 32-Core Processor 實驗:

$ ./dekker 10000000
Starting task1
Starting task2
Both threads terminated
[-] Dekker did not work, sum 19164869 rather than 20000000.
835131 missed updates due to memory consistency races.

顯然結果不正確，問題在於 volatile 不能保證能夠讀到「最新」的資料，它只保證編譯器每次都產生 load 操作，而 CPU 在執行過程中重排，使得該 load 操作讀到「舊值」，從而導致混亂。倘若我們修改上述程式碼的第 13 和第 26 行，使得 __atomic_thread_fence(__ATOMIC_SEQ_CST); 作為 memory barrier 得以執行，才會得到符合預期的 Dekker's Algorithm 的實作。

上例說明單獨使用 volatile 關鍵字，很有可能無法得到預期結果。因此，當我們要使用 volatile 時，一定要想楚究竟「為什麼要用」？是否需要使用 memory barrier？是否對編譯器最佳化產生無謂的抑制？

Linux 核心文件〈Why the "volatile" type class should not be used〉提到，在 Linux 核心使用 volatile 的場景，絕大部分是誤用。

在 Linux Kernel Memory Barriers 提到巨集 READ_ONCE 和 WRITE_ONCE，定義於 include/asm-generic/rwonce.h:

/*
 * Use __READ_ONCE() instead of READ_ONCE() if you do not require any
 * atomicity. Note that this may result in tears!
 */
#ifndef __READ_ONCE
#define __READ_ONCE(x)  (*(const volatile __unqual_scalar_typeof(x) *)&(x))
#endif

#define READ_ONCE(x) \
({ \
    compiletime_assert_rwonce_type(x); \
    __READ_ONCE(x); \
})

我們撰寫簡單的 C 程式來試驗: (檔名: t.c)








int a, b;
int i, j;

void foo()
{
    a = i;
    b = j / 16;
}

在開啟編譯器最佳化的狀態，進行編譯:

$ gcc -S -O2 t.c

對應的組合語言輸出:

movl    j(%rip), %edx ; 讀取 j
movl    i(%rip), %eax ; 讀取 i
testl   %edx, %edx
movl    %eax, a(%rip)
leal    15(%rdx), %eax
cmovns  %edx, %eax
sarl    $4, %eax
movl    %eax, b(%rip)

在 C 程式中，第 6 行先是讀取變數 i，再來是第 7 行讀取變數 j 的值，卻跟組合語言輸出不同，換言之，這就是編譯器最佳化的效果。

我們在第 6 行之後新增一行: (即前述的 compiler barrier)


__asm__ __volatile__("": : :"memory");

產生的組合語言就變更:

movl	i(%rip), %eax ; 先讀取 i
movl	%eax, a(%rip) ; i 的內容指派到變數 a 中
movl	j(%rip), %edx ; 再來才讀取 j
testl	%edx, %edx
...

也就是說，compiler barrier 告訴編譯器：在 barrier() 前後必須明確區隔：barrier 之前的操作不可跑到 barrier 後，反之亦然。所以，「讀取 i 並寫入 a」和「讀取 j 並寫入 b」這兩組操作被 barrier 所隔離。

接下來引入 Linux 核心的 READ_ONCE 巨集，使用到 volatile 關鍵字，繼續實驗:

#define __READ_ONCE(x)  (*(const volatile int *) &(x))
int a, b;
int i, j;

void foo()
{
    a = __READ_ONCE(i);
    b = __READ_ONCE(j) / 16;
}

產生的組合語言如下:

movl    i(%rip), %eax ; 讀取 i
movl    j(%rip), %edx ; 讀取 j
movl    %eax, a(%rip) ; 寫入 a
testl   %edx, %edx
leal    15(%rdx), %eax
cmovns  %edx, %eax
sarl    $4, %eax
movl    %eax, b(%rip) ; 寫入 b

可見 i 和 j 的讀取順序被保證，但 volatile 畢竟不是 compiler barrier ，不能把 a = i 和 b = j / 16 完全隔離，因此用 __READ_ONCE 能保證的也只是 i 和 j 的讀取順序，其他的寫入順序或者讀寫之間的順序，就無法保證，以上例來說，讀取 j 和寫入 a，就不同於 C 程式原本的順序。

摘錄 C 語言規格:

The least requirements on a conforming implementation are:
At sequence points, volatile objects are stable in the sense that previous accesses are complete and subsequent accesses have not yet occurred.

The following are the sequence points described in 5.1.2.3:

The end of a full expression: an initializer (6.7.8); the expression in an expression statement (6.8.3); the controlling expression of a selection statement (if or switch) (6.8.4); the controlling expression of a while or do statement (6.8.5); each of the expressions of a for statement (6.8.5.3); the expression in a return statement (6.8.6.4).

這裡引出 sequence point 的概念：sequence point 之前的表達式所造成的影響，不能擴散到 sequence point 之後。尤其是對於 volatile 變數來說，以一個 sequence point 為分界點，對於前面 volatile 變數的存取必須完成，且對於後面 volatile 變數的存取必須尚未開始。

依循上述 C 語言規範，常見的 ; (分號) 就是個 sequence point，於是 a = __READ_ONCE(i) 和 b = __READ_ONCE(j) / 16 之間隔著一個 sequence point，因此對變數 i 的讀取必須放在變數 j 之前。

但要注意的是，編譯器只是保證 2 個 volatile 變數之間讀取不會被亂序，但是 non-volatile 變數和 volatile 變數的讀取順序，依舊允許亂序。讀者可試著將上述程式碼裡頭第二個 __READ_ONCE 巨集移除，就會發現 i 和 j 的讀取順序又顛倒。

處理器架構和其 Memory Order

即使有用來抑制編譯器最佳化的工具，你是否仍然感覺難以寫出正確的程式碼呢？可能發生指令重排的情況如此多，似乎在任何時候都要考慮 memory barrier 的使用，實在困難。誠然，針對多核處理器的並行程式設計就是如此複雜，但前提是你打算撰寫跨越多種處理器架構的可攜性 (portable) 程式碼。

不同處理器架構的順序保證往往不同的，x86 架構實際上已提供很強的順序性保證，如下圖：

可見 x86 架構結構中只會發生一種重排 (先不討論最右邊欄位，是探討指令 cache 的一致性)，即 store-load 重排。考慮下圖的案例，在 2 個 CPU 並行的程式碼:

上圖中，2 個執行緒都是先執行 store 操作 (變數 x 和 y 的初始值都是 0)，再執行 load 操作，於是我們可確認執行完畢後，r1 和 r2 的值至少有一個是 1。然而在 x86 結構中，由於會出現 store-load 重排，所以 2 個執行緒的 store-load 執行順序可能產生變化，如下圖：

由於重排，可能會產生 r1 和 r2 都為 0 的執行結果 —— 這和原本的程式邏輯牴觸。

以下我們撰寫程式來觀察處理器重排的狀況: (檔名: reorder.c)

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

static int loop_count;
static int A, B, X, Y;

static void *worker1(void *arg)
{
    X = 1;
    asm volatile("" ::: "memory");
    A = Y;
}

static void *worker2(void *arg)
{
    Y = 1;
    asm volatile("" ::: "memory");
    B = X;
}

int main(int argc, char *argv[])
{
    pthread_t thread_1, thread_2;

    int64_t count = 0;

    if (argc != 2) {
        fprintf(stderr, "USAGE: %s <loop_count>\n", argv[0]);
        exit(1);
    }

    loop_count = atoi(argv[1]); /* FIXME: format checks */

    for (int i = 0; i < loop_count; ++i) {
        X = 0;
        Y = 0;

        /* Start the threads */
        pthread_create(&thread_1, NULL, (void *(*) (void *) ) worker1, NULL);
        pthread_create(&thread_2, NULL, (void *(*) (void *) ) worker2, NULL);

        /* Wait for the threads to end */
        pthread_join(thread_1, NULL);
        pthread_join(thread_2, NULL);

        if (A == 0 && B == 0) /* reorder caught */
            count++;
    }

    printf("%d reorder caught in %d iterations.\n", count, loop_count);

    return 0;
}

在 AMD Ryzen Threadripper 2990WX 32-Core Processor 實驗: (Ubuntu Linux 20.04)

$ ./reorder 100000
34 reorder caught in 100000 iterations.

10 萬次迴圈中，Threadripper 2990WX 重排發生 34 次。

在 Intel® Xeon® CPU E5-2650 實驗: (Ubuntu Linux 20.04)

$ ./reorder 100000
267 reorder caught in 100000 iterations.

10 萬次迴圈中，Xenon E5-2650 重排發生 267 次。

在 AWS Graviton 處理器 (Aarch64 架構) 實驗: (Ubuntu Linux 20.04)

$ ./reorder 100000
1114 reorder caught in 100000 iterations.

10 萬次迴圈中，Graviton2 重排發生 1114 次。

在 Intel Core i5 + macOS 測試:

$ ./reorder 100000
0 reorder caught in 100000 iterations.

在 Apple M1 晶片 + macOS 測試:

$ ./reorder 100000
2 reorder caught in 100000 iterations.

macOS 的結果很有趣，其 POSIX Thread 實作中，主動安插 memory barrier。

延伸閱讀:

wait-free & lock-free

Non-blocking algorithm: wait-free 是 lock-free 之中具備更嚴格的條件

atomic 指令可作為 wait-free 和 lock-free 演算法的基礎建設。wait-free 指無論作業系統如何排程，每個執行緒始終有進展；lock-free 的規範則較前者弱，指無論作業系統如何排程，至少有一個 執行緒有進展。若在我們的服務中使用 lock，那麼作業系統可能將一個剛獲取 lock 的執行緒切換出去，這時所有依賴這個 lock 的執行緒都在等待，因而沒進展，因此依賴 lock 的操作難以達到 lock-free ，更不會是 wait-free。

Non-blocking algorithm 尚有 obstruction-free 方案。英語 "obstruction" 有「阻礙」和「阻擋」的意涵，obstruction-free 指在任何時間點，一個孤立執行執行緒的每個操作可在有限步之內結束。只要沒有競爭，執行緒就可持續執行。一旦共用資料被修改，obstruction-free 要求中止已完成的部分操作，並進行回復 (rollback)。所有 Lock-Free 演算法都滿足 obstruction-free 要求。

值得注意的是，或許有人會認定 lock-free 或 wait-free 演算法會較快，但事實可能恰好相反，因為：

lock-free 和 wait-free 必須處理更多更複雜的 race condition 和 ABA problem，完成相同目的的程式碼比用 lock 更複雜。程式碼越多，執行路徑也會增長。
使用 mutex 的演算法具備「後退」(backoff) 的效果，即出現競爭時嘗試另一個途徑，以便臨時避免競爭，mutex 出現競爭時會讓嘗試獲取 lock 者進入睡眠，使拿到 lock 的那個執行緒得以很快地獨占完成一系列流程，吞吐量反而因此提高。。

mutex 導致效能下降的因素，往往是因臨界區過長且過於頻繁，也就限制並行程度，或競爭過於激烈 (context switch 開銷大幅增加)。lock-free/wait-free 演算法的價值在於，其保證一個或所有執行緒始終有進展，而非絕對的高效率。lock-free 和 wait-free 演算法在一種狀況會獲得更好的效率：演算法本身可用少量 atomic 指令實作 —— 實作 lock 也要用到 atomic 指令，當演算法本身用少數指令即可完成時，相比額外用 lock 當然就會有優勢。

案例探討: SPSC

ringbuffer.c 是一個 lock-less 的 Ring buffer 範例實作，並且適用於 SPSC (single-producer and single-consumer) 情境。

typedef struct {
    struct {                          /** Ring producer status. */
        uint32_t watermark;           /**< Maximum items before EDQUOT. */
        uint32_t size;                /**< Size of ring. */
        uint32_t mask;                /**< Mask (size - 1) of ring. */
        volatile uint32_t head, tail; /**< Producer head and tail. */
    } prod __attribute__((__aligned__(CACHE_LINE_SIZE)));

    struct {                          /** Ring consumer status. */
        uint32_t size;                /**< Size of the ring. */
        uint32_t mask;                /**< Mask (size - 1) of ring. */
        volatile uint32_t head, tail; /**< Consumer head and tail. */
    } cons __attribute__((__aligned__(CACHE_LINE_SIZE)));

    void *ring[] __attribute__((__aligned__(CACHE_LINE_SIZE)));
} ringbuf_t;

ringbuf_t 是該程式的主體結構，可見結構中除了儲存指標的 buffer 本身 (ring)，分別還有與生產者/消費者工作相關的 prod 和 cons 兩個結構。其中，個別的 head 和 tail 的設計是為了滿足 lock-less 的考量，下面的程式碼更清楚展示如何使用。

static inline int ringbuffer_sp_do_enqueue(ringbuf_t *r,
                                           void *const *obj_table,
                                           const unsigned n)
{
    uint32_t mask = r->prod.mask;
    uint32_t prod_head = r->prod.head, cons_tail = r->cons.tail;
    /* The subtraction is done between two unsigned 32-bits value (the result
     * is always modulo 32 bits even if we have prod_head > cons_tail). So
     * @free_entries is always between 0 and size(ring) - 1.
     */
    uint32_t free_entries = mask + cons_tail - prod_head;

    /* check that we have enough room in ring buffer */
    if ((n > free_entries))
        return -ENOBUFS;

    uint32_t prod_next = prod_head + n;
    r->prod.head = prod_next;

    /* write entries in ring buffer */
    ENQUEUE_PTRS();
    __compiler_barrier();

    r->prod.tail = prod_next;

    /* if we exceed the watermark */
    return ((mask + 1) - free_entries + n) > r->prod.watermark ? -EDQUOT : 0;
}

ringbuffer_sp_do_enqueue 是生產者所運作的主要任務。在進入這個函式之前，r->cons.head 和 r->cons.tail 數值相同，代表著前一次結束生產的 index 位置。進入函式後，首先計算出 free_entries，它是允許生產的最大數量。然後生產者會先更新 r->cons.head 到生產結束後的 index 位置，直到主體操作 ENQUEUE_PTRS() 結束，再把 r->cons.tail 也一併更新為產出完成後的 index 位置。

換言之，當 r->cons.tail 和 r->cons.head 在某個執行的時間點有差異，兩個變數之間的範圍表示「生產者正在存取的有效 buffer 範圍」，消費者可藉由兩個變數的差異得知無法操作的 buffer 區域。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

關於 free_entries 如何而得:

注意 head 和 tail 的數值範圍實際上並不總是小於 buffer 大小，其範圍恆為 uint32_t 可表示之大小(

0

到

2^{32} - 1

)。然而受益於此程式要求 buffer 必須是

2^{n}

大小的限制(n 為整數)，可藉由 mask 是

2^{n} - 1

的性質，以 mask + cons_tail - prod_head (modulo) 來計算出正確 free_entries 數量。

案例探討: SPMC

談及更複雜的 SPMC (single-producer, multiple-consumer)，就要思索新議題: 對於 dequeue 操作，消費者執行緒除了要確保存取的 buffer 範圍沒有生產者嘗試建立新的元素，還要保證不與其他消費者同時消費相同的元素。spmc.c 就是一個針對SPMC(single-producer, multiple-consumer) 情境的 concurrent queue 案例。

typedef struct __spmc_node {
    size_t cap; /* One more than the number of slots available */
    _Atomic size_t front, back;
    struct __spmc_node *_Atomic next;
    uintptr_t buf[];
} spmc_node_t;

typedef void (*spmc_destructor_t)(uintptr_t);
struct spmc_base {
    /* current node which enqueues/dequeues */
    spmc_node_t *_Atomic curr_enqueue, *_Atomic curr_dequeue;
    uint8_t last_power;
    spmc_destructor_t destructor;
};
typedef struct spmc_base *spmc_ref_t;

struct spmc_base 是該程式的主體結構，其中需要關注的成員包含:

curr_enqueue 和 curr_dequeue 都是 _Atomic 類型的 spmc_node_t *，指向在 buffer 中要消費或者生產的目標節點
last_power: 是最近一次建立的 spmc_node_t 中之 buffer 的大小 (cap=
$2^{l a s t_p o w e r}$ )

而 spmc_node_t 是包含 buffer 的節點，這些節點同時還會形成一個 linked list，當節點中的 buffer 已達生產上限(尚未被消費掉)，就產生一個新的節點並配置一個更大的 buffer:

buf[] 是實際要操作的元素之 buffer，這是 Arrays of Length Zero 語法，允許對一個 struct 分配變數長度大小的空間
front 是消費者對該 node 的 buffer 所操作的下個 index，back 是生產者對該 node 的 buffer 所操作的下個 index，兩者需要搭配使用確認 buffer 是否是空或滿狀態
next 是下一個 spmc_node_t 節點
cap 是節點中 buffer 的大小

對此程式的資料結構有一定的認知後，我們關注其 dequeue 操作與 SPSC 版本的差異之處:




















bool spmc_dequeue(spmc_ref_t spmc, uintptr_t *slot)
{
    spmc_node_t *node =
        atomic_load_explicit(&spmc->curr_dequeue, memory_order_consume);
    size_t idx;
no_increment:
    do {
        idx = atomic_load_explicit(&node->front, memory_order_consume);
        if (!IS_READABLE(idx, node)) {
            if (node != spmc->curr_enqueue)
                atomic_compare_exchange_strong(
                    &spmc->curr_dequeue, &node,
                    atomic_load_explicit(&node->next, memory_order_relaxed));
            goto no_increment;
        } else
            *slot = node->buf[INDEX_OF(idx, node)];
    } while (
        !atomic_compare_exchange_weak(&node->front, &(size_t){idx}, idx + 1));
    return true;
}

spmc_dequeue 消費 buffer 中的元素，再次注意 SPMC 情境下會有多個 thread 同時在進行 spmc_dequeue。最開始，atomic_load_explicit atomically 的載入 spmc->curr_dequeue 指向的節點，並使用 atomic_load_explicit 載入該節點的 node->front 的值。

接著 IS_READABLE(idx, node) 檢查讀出來的 node->front 與 node->back 是否相同，這表示該 node 中之 buffer 為空狀態，根據狀況可以區分成:

如果 buffer 不為空，先直接取出 buffer 中的元素即可 (第 16 行)
如果 buffer 為空，且 spmc->curr_dequeue 指向的也是目前的 spmc->curr_enqueue 所指向，表示確實沒有新的元素可以消費，則只能 goto 持續等待 queue 被填入(第 10 行條件為 false)
如果 buffer 為空，但 spmc->curr_dequeue 與 spmc->curr_enqueue 是不同的節點，表示其他節點上可能存在可以消費的元素，則嘗試將 spmc->curr_dequeue 移動到下個 node(第 11 行)，之所以需要 compare-and-swap (CAS)，是因為多消費者的 spmc->curr_dequeue 會有多個 thread 嘗試改寫

最後要 CAS 的更新 node->front，將其加 1，這個操作是與 SPSC 的差異關鍵，在 SPSC 中，我們只要確保取得元素的 buffer 位置不要同時被生產者存取。但在 SPMC 情境下，還要確保消費者互相不會重複的取到同個元素，為此需要 CAS 或者類似的操作去競爭該元素的消費權利，競爭到的執行緒之 CAS 會成功並得以返回，其他執行緒則需再次留在 while 迴圈直到競爭到下一個元素。

並行程式設計: Atomics 操作

點題

詞源和澄清

阻塞式同步機制

Atomic 操作：非阻塞式同步的基石

C11 Atomics

背後作祟的 cache

多核處理器之間的 cache coherence

MESI protocol

MOESI protocol

cache coherence 對程式效能的衝擊

Memory Ordering 和 Barrier

Store Buffer

invalidate queue

硬體實作策略

軟體觀點

易於誤用 volatile 關鍵字

處理器架構和其 Memory Order

wait-free & lock-free

案例探討: SPSC

案例探討: SPMC

Read more

淺談 Microkernel 設計和真實世界中的應用

並行程式設計: 概念

並行程式設計: Lock-Free Programming

2025 年 Linux 核心設計課程期末專題

易於誤用 `volatile` 關鍵字