Linux 核心專題: 《Concurrency Primer》校訂和範例撰寫

執行人: yutingshih
專題解說影片

任務簡介

針對《Concurrency Primer》，補充校訂和範例撰寫。

閱讀〈並行和多執行緒程式設計〉系列講座並紀錄問題

在開始進行教材修訂之前，先閱讀 並行和多執行緒程式設計 系列講座，學習並行程式設計相關的背景知識，以下是針對各章節的筆記以及問題

並行和多執行緒程式設計 – 概念

• 可再進入 (reentrancy) 的函式是可以被多個工作 (task) 同時呼叫而不會有資料不一致的問題。需要避免使用共享記憶體區 (例如 global memory)，所有資料都存在呼叫者或函式的堆疊區
• fork-join: 每個執行單元都有自己的 stack , 但跟本來的執行執行單元共用 text, heap 與 data section。

並行與多執行緒程式設計 – 執行順序

• x++ 會先做 value compuatation 再做 side effect
• ++x 會先做 side effect 再做 value compuatation
• = 會先做兩個運算元的 value computation 再做 = 的 side effect，最後才是 = 的 value computation

i = i++

因為 i++ 的 side effect 發生在 value computation 之後，不能確定前者與 = 的 side effect 的先後順序，因此屬於未定義行為

i = ++i

但 ++i 的 side effect 發生在 value computation 之前，兩者皆發生在 = 的 side effect 之後，故沒有不確定的行為 (well-defined)

• Order of evaluation - cppreference.com

Happens Before

mutex lock 不只是為了保護共享資源，還是為了確保 happens-before 語意的操作

Memory Consistency Model

編譯器和處理器可能會改變程式執行的順序以求最佳化，但必須遵循一定的協定才能確保程式的撰寫、編譯、執行能有正確且一致的結果，memory consistency model 就是在定義允許哪些重排的協定

• weak memory model: 可能存在所有 memory reordering
• weak with data dependency ordering: 允許 storeload 和 storestore 的 reordering，也就是 load 的順序能被保證
• usually strong: 允許 storeload reordering，也就是保證 acquire and release sementic 的執行
• seqentially consistent: 全部保證順序

https://preshing.com/20120930/weak-vs-strong-memory-models/
https://preshing.com/20120913/acquire-and-release-semantics/

並行程式設計 - Atomic 操作

Memory Ordering

memory_order_relaxed

• Relaxed operation: there are no synchronization or ordering constraints imposed on other reads or writes, only this operation's atomicity is guaranteed.

memory_order_consume

• A load operation with this memory order performs a consume operation on the affected memory location: no reads or writes in the current thread dependent on the value currently loaded can be reordered before this load.
• Writes to data-dependent variables in other threads that release the same atomic variable are visible in the current thread.
• On most platforms, this affects compiler optimizations only.

memory_order_acquire

• A load operation with this memory order performs the acquire operation on the affected memory location: no reads or writes in the current thread can be reordered before this load.
• All writes in other threads that release the same atomic variable are visible in the current thread.

memory_order_release

• A store operation with this memory order performs the release operation: no reads or writes in the current thread can be reordered after this store.
• All writes in the current thread are visible in other threads that acquire the same atomic variable and writes that carry a dependency into the atomic variable become visible in other threads that consume the same atomic.

memory_order_acq_rel

• A read-modify-write operation with this memory order is both an acquire operation and a release operation. No memory reads or writes in the current thread can be reordered before the load, nor after the store. All writes in other threads that release the same atomic variable are visible before the modification and the modification is visible in other threads that acquire the same atomic variable.

memory_order_seq_cst

• A load operation with this memory order performs an acquire operation, a store performs a release operation, and read-modify-write performs both an acquire operation and a release operation, plus a single total order exists in which all threads observe all modifications in the same order.

Atomic Operations

C11 的 atomic 操作有兩種形式的函式，有 memory order 參數和沒有 memory order 參數的版本 (以 _explicit 結尾)，沒有指定 memory order 的函式預設都是 sequentially consistent 的 memory order (memory_order_seq_cst)

atomic_exchange

是一種 read-modify-write operation

atomic_compare_exchange_{weak|strong}

_Bool atomic_compare_exchange_strong(
    volatile A* obj,
    C* expected, C desired
);
_Bool atomic_compare_exchange_weak(
    volatile A* obj,
    C* expected, C desired
);
_Bool atomic_compare_exchange_strong_explicit(
    volatile A* obj,
    C* expected, C desired,
    memory_order succ,
    memory_order fail
);
_Bool atomic_compare_exchange_weak_explicit(
    volatile A* obj,
    C* expected, C desired,
    memory_order succ,
    memory_order fail
);

read-modify-write operation

if (memcmp(obj, expected, sizeof *obj) == 0) {
    memcpy(obj, &desired, sizeof *obj);
    return true;
} else {
    memcpy(expected, obj, sizeof *obj);
    return false;
}

The weak forms of the functions are allowed to fail spuriously, that is, act as if *obj != *expected even if they are equal. When a compare-and-exchange is in a loop, the weak version will yield better performance on some platforms. When a weak compare-and-exchange would require a loop and a strong one would not, the strong one is preferable.

• strong 版本在 obj == desired 時一定會成功
• weak 版本在 obj == desired 時不一定會成功 WHY??

並行程式設計: POSIX Thread

作業系統領域常常都是較複雜的概念先出現，之後才有簡化的實作，例如 process 先於 thread、semaphore 先於 mutex

coroutine 與作業系統、硬體支援無關，甚至可以用 C 語言的 switch-case 來實作 user-level thread

Thread vs Process:

• thread 會共享 address space，process 則需要花心思處理 address space 的隔離
• 但每個 thread 還是有獨立的空間，叫做 thread control block (TCB)

thread 可以處理獨立的 control flow，並且可以被排程 (schedulable)，因為 thread 擁有以下資訊：

• stack pointer
• register
• scheduling properties (e.g. policy, priority)
• pending blocked signals
• thread specific data

雖然同個 process 的 threads 間會共享 address space，但有時候還是希望 thread 有自己的空間，例如：errno, file manipulation 不希望在存取時被其他人改寫，解決方案就是 thread-local storage (TLS)

PThreads (POSIX Threads)

• 1995 年以前 UNIX 分裂得很嚴重，因此有了 POSIX 標準 (PThread 定義在 IEEE POSIX 1003.1c)
• 1981 年 MS-DOS 推出、Jserv 出生、唐鳳出生
• 1980 年代就有 thread 的概念，但 1995 年才有 POSIX Thread 標準

Jserv：「如果有心要研究 Linux 或 OS，強烈建議要連同 BSD 一起看，而且 BSD 開發者有比較會寫文章的趨勢 (The Design and Implementation of the FreeBSD Operating System (2nd Edition))」

GNU 又在 POSIX 標準之上進行擴充，可以看 pthread.h 中 *_np 結尾的函式，意思是 non-protable

POSIX Threads Programming | LLNL HPC Tutorials

Linux 用的 Native POSIX Thread Library (NPTL) 是採用 1:1 的 thread mapping，可以處理很多獨立的系統呼叫

但美國國家實驗室較多是在做科學計算，有大量的計算，反而系統呼叫的機會沒那麼多，因此自行開發了 QThread library，採用 1:N mapping (多個 user-level threads 對應到一個 kernel thread)

PThread Attributes

Pthread 可以設定 attribute，像剛剛前面講到的 scheduling properties，例如 processor affinity

pthread_exit：直接結束，不 join
pthread_detach：讓 thread 自生自滅，不用 join

Condition Variable

condition variable 總是搭配 mutex 使用，當資源釋放時會通知其他執行緒，e.g. pthread_cond_broadcast()，monitor mutex

mutex 有 ownership，但 semaphore 沒有
mutex + condvar 可以有 signal 的機制

semaphore 的機制建立在 counter 之上
mutex + condvar 可以更加彈性，設定不同的狀態，比如停機維修等等

Synchronization

• mutex locks
• condition variables
• semaphores

撰寫 PThread 程式會大量使用到指標，很容易會出現指標相關的錯誤，例如指標轉型、非法記憶體存取、alignment 等，可以參照「你所不知道的 C 語言：指標篇」

mutex attribute

• recursive locking
• deadlock report/detection

Semaphore

mutex：所有權、誰握有資源
condition variable：為 mutex 提供通知的機制、狀態的機制
semaphore：總量監控

mutex 和 semaphore 都可以實作生產者消費者模型，SPSC 時 semaphore 比較簡單，但 MPMC 時 semaphore 就會變得非常複雜

SPMC：資料庫、檔案系統 (單一寫入、多讀取)

Synchronization

CS231，CSAPP 最後一章 concurrent programming

界定 CS 的範圍大小對於撰寫並行程式來說很重要，CS 的有效區域取決於程式的執行路徑，還得考慮到 kernel 的行為，因為不是每個 function call 都是 thread-safety 的

如果在 fork 之前就已經有 mutex lock 了？
fork 會複製 (duplicate) parent process 的內容給 child process (除了 PID 等資訊例外)，那 mutex lock 也會複製嗎？lock 所保護的 memory region 也會複製嗎？
其實 parent process 和 child process 是有機會共享 mutex lock 及其所保護的 memory region，但有時候不希望共享，有時候希望共享，因此有了 pthread_atfork 可以用來註冊 fork 時的 callback function

#include <pthread.h>

int pthread_atfork(
    void (*prepare)(void), /* nullable */
    void (*parent)(void),  /* nullable */
    void (*child)(void)    /* nullable */
);

// link with -lpthread

撰寫多執行緒程式時可以也常常會使用多個 mutex locks，但這會讓程式行為難以預測、很難 debug，而 thread-sanitizer 可以讓開發者得知一些執行時期的資訊

coarse-grained lock

fine-grained lock 乍看會比較慢，但可以創造出公平的情境

Semaphore

SystemV semaphore
POSIX semaphore

• sem_post：遞增
• sem_wait：遞減

Mutex & Semaphore

Critical Section Problem

現在的 mutex 不會用 Dekker's algorithm 和 Paterson's algorithm 實作，但若未來從事硬體或系統軟體設計工作可能會需要驗證新的 mutex 實作的結果，就需要拿這兩個演算法來比對

這兩個演算法的適用場景不同

Critical section problem 解法必須具備以下性質：

• mutual exclusion
• real-time: 不是「快」，而是 latency 可以在一個範圍內 (bounded wait)，可以用 WCET (worst-case execution time)，firm real-time/hard real-time 是最高等級的 real-time
• progress

Peterson's algorithm (1981) 不是一般的演算法，是狀態的描述

raise my flag
turn = your_id
wait while your flag is raised and turn is your_id
// do critical section stuff
lower my flag

Peterson's algorithm 可以針對更多 threads，只是這邊的例子是兩個 threads

Dekker's algorithm

raise my flag
while (your flag is raised):
    

D 較複雜，P 較簡單

軟體的解決方案成本很高，因此現在的解決方案大多有硬體支援，也就是要有 interrupt controller 搭配

interrupt controller 負責篩選哪些中斷可以傳送到 CPU，可以 disable/re-enable，這件事會和 synchronization 有關，例如：

disable_interrups
// critical section code
enable_interrupts

只要把中斷 disable 掉，就可以霸佔 CPU 資源，可以滿足 mutual exclusion, bounded-wait 和 progress

若不想要用中斷控制器的方式來處理，因為會牽涉到和周邊裝置相關的議題，還可以使用 atomic instructions (uninterruptable operation)

作法是有個 global exclusive monitor 的硬體，來確保 mutual exclusion

mutex 和 semaphore 是因為不同理念而設計，但實作面卻是 interchangable

早期 Linux 是用 semaphore 來實作 mutex

Reader-Writer Problem

當讀取者和寫入者有大落差時，例如 RCU

SystemProgramming - Synchronization

yutingshih/learn-pthreads

Part 1: Mutex Locks

• critical section: 一段一次只能被一個執行緒執行才能確保執行結果正確的程式碼
• 使用 mutex 不會停住所有的 threads，只有當 mutex 被鎖上時，會讓其他再次嘗試上鎖的 threads 等待，直到被解鎖後才能上鎖
• 兩種方式創建 mutex
  • pthread_t lock = PTHREAD_MUTEX_INITIALIZER;
  • pthread_mutex_init(&lock, NULL); 較多 overhead，但可以較多彈性，例如 error-checking、sharing 等等
• 對同個 lock 多次 init 或 destroy 是未定義行為
• 對鎖上的 lock destroy 是未定義行為
• 上鎖和解鎖的 thread 必須是同一個
• 把 pthread_mutex_t 的資料 copy 到一個新的 memory location 是不支援的

Mutex Granularity

1. fine-grained mutex: frequently lock and unlock

for (int i = 0; i < 1000000; i++) {
    pthread_mutex_lock(&lock);
    sum += 1;
    pthread_mutex_unlock(&lock);
}

2. coarse-grained mutex: less-frequently lock and unlock, but sequential execution

pthread_mutex_lock(&lock);
for (int i = 0; i < 1000000; i++) {
    sum += 1;
}
pthread_mutex_unlock(&lock);

3. intermediate value: concurrent execution when summation, only sequantial when update the global value

int local = 0;
for (int i = 0; i < 1000000; i++) {
    local += 1;
}

pthread_mutex_lock(&lock);
sum += local;
pthread_mutex_unlock(&lock);

Part 2: Counting Semaphores

• semaphore: non-negative counter
  • post: increment
  • wait: if zero then wait, otherwise decrement
• semaphore can be increased/decreased by different threads.
• 可以用 semaphore 代替 mutex，但 overhead 較大
  • 用 sem_wait 代替 mutex_lock
  • 用 sem_post 代替 mutex_unlock

A mutex is an initialized semaphore that always wait before it post.

sem_t s;
sem_init(&s, 0, 1);

sem_wait(&s);
// critical section
sem_post(&s);

semaphore 也可以在 signal handler 當中使用，但注意盡量不要在多執行緒的程式中使用 signal，根據 man 2 signal: "The effect of signal() in a multithreaded process are unspecified."，比較正確的作法是使用 sigaction

pthread_exit、exit、return 的差別

• pthread_exit 用來在一個 child thread 結束時呼叫，可以執行 thread 的清理程序 pthread_cleanup_push，並將值 (須存在 heap 上) 回傳給 parent thread
• return 一樣可以將 thread function 的值傳回給 parent thread，但通常用於一般 function 的結束
• exit 則是會停掉整個 process，而非只有當前的 thread

Part 3: Working with Mutexes And Semaphores

• atomic operation
• thread-safe data structrue

Thread-Safe Stack

• 用 mutex 確保 stack 的讀寫是 mutual exclusion
• 用 semaphore 確保不會 overflow/underflow (push to full stack/pop from empty stack)

Gotchas

常見的錯誤

• Locking/unlocking the wrong mutex (due to a silly typo)
• Not unlocking a mutex (due to say an early return during an error condition)
• Resource leak (not calling pthread_mutex_destroy)
• Using an uninitialized mutex (or using a mutex that has already been destroyed)
• Locking a mutex twice on a thread (without unlocking first)
• Deadlock and Priority Inversion (we will talk about these later)
• Assuming the sem_wait, sem_trywait, sem_timedwait succeeded instead of checking return code for EINTR or ETIMEDOUT

Part 4: The Critical Section Problem

What is Critical Section Problem

在 multithreaded program 中可以用 mutex 來保護 critical section 一次只會有一個 thread/process 進入

pthread_mutex_lock();
// ...
pthread_mutex_unlock();

那麼要如何實作 mutex lock/unlock 函式呢？
critical section (CS) problem 就是如何確保一次只會有一個 thread 進入 critical section

Candidate Solutions

1. check-first

沒有 mutual exclusion，依然可能會有兩個以上的 threads 同時進入 CS

// Candidate #1
wait until your flag is lowered
raise my flag
// Do Critical Section stuff
lower my flag 

2. lock-first

有 mutual exclusion，但是會有 deadlock

// Candidate #2
raise my flag
wait until your flag is lowered
// Do Critical Section stuff
lower my flag 

3. turn-based

滿足 mutual exclusion，但可能會有 thread 已經離開 CS，下一個 thread 卻還在等待它的 turn 而不進入 CS (doesn't make progress)，尤其是不同 threads 在 CS 中所需時間差異很大時

// Candidate #3
wait until my turn is myid
// Do Critical Section stuff
turn = yourid

4. turn & flag

還是可能沒有 mutual exclusion

// Candidate #4
raise my flag
if your flag is raised, wait until my turn
// Do Critical Section stuff
turn = yourid
lower my flag

Desired Properties for Solutions to the CS Problem

• mutual exclusion：當有 thread/process 進入 CS，其他想進入 CS 的 threads/processes 就必須等待
• bounded wait：threads 等待進入 CS 的時間必須是有限的 (有 upper bound)
• progress：如果 CS 中沒有 thread/process 正在執行，那想進入 CS 的 thread/process 就不需要再等待

Peterson's Algorithm

// Candidate #5
raise my flag
turn = your_id
wait while your flag is raised and turn is your_id
// Do Critical Section stuff
lower my flag

// Candidate #5
bool flag1, flag2  //both initially false
int flag = 1

thread1:                          thread2:
  flag1 = true                      flag2 = true
  turn = 2                          turn = 1
  while(flag2 && turn == 2) {}      while(flag1 && turn == 1) {}
  Critical Section                  Critical Section
  flag1 = false                     flag2 = false

• flag1 = true 和 flag2 = true 宣告自己有意願進入 CS
• turn 設為對方的 ID，意思是先預設對方已經進到 CS，或可以視為「禮讓對方先執行」
• 如果對方沒有想要進入 CS，或是對方也「禮讓」，那自己就可以進入 CS

那更多 threads 時是否可以修改為：

// Candidate #5
bool flag1, flag2  //both initially false
int flag = 1

thread1:                          thread2:
  flag1 = true                      flag2 = true
  turn = 2                          turn = 1
  while(flag2 && turn != 1) {}      while(flag1 && turn != 2) {}
  Critical Section                  Critical Section
  flag1 = false                     flag2 = false

Dekker's Algorithm

raise my flag
while(your flag is raised) :
   if it's your turn to win :
     lower my flag
     wait while your turn
     raise my flag
// Do Critical Section stuff
set your turn to win
lower my flag

Hardware Support

• single core CPU: temporarily disable interrupts

disable_interrupt
// critical section code
enable_interrupt

因為現代 CPU 往往有多個核心，且 disable interrupts 屬於特權指令 (privilege instruction) 所以上述作法不適合

• multi-core CPU: atomic instructions

假設硬體有提供 atomic 指令 __exch，可以交換兩個記憶體位址中的資料，則 mutex 的實作如下方 pseudocode 所示：

my_mutex_init(int* m)  { *m = 0; }

my_mutex_lock(int* m) {
  for (int q = 1; q; ) {  __exch(&m , &q); }
} // when this returns it is safe to enter your critical section

// After you critical section is finished,call unlock...
my_mutex_unlock(int* m)  { *m = 0; }

Part 5: Condition Variables

• condition variable 通常會和與 mutex 及 loop 搭配使用
• 提供「通知」和「狀態」的機制 (pthread_cond_boardcast 和 pthread_cond_signal)

What does pthread_cond_wait do?

1. unlock the mutex
2. wait until pthread_cond_signal or pthread_cond_boardcast is called
3. lock the mutex, and then return

The step 1 and step 2 are done atomically.

Why do condition variables need a mutex

1. 避免 wake-up message (signal or boardcast) 遺失，理想上 wait 應該發生在其他 thread 呼叫 signal 之前，但沒有 mutex 的話，有可能 wait 在其他 thread 的 signal 之後，如此一來就永遠收不到 signal 了
2. 保護共享資源 (e.g. 用來記錄狀態的變數會被多個 threads 修改)
3. real-time

TODO: 修訂並行程式設計: 執行順序

閱讀 Hardware Memory Models 和 Programming Language Memory Models，紀錄你的認知並列出並行程式設計: 執行順序的改進，至少涵蓋硬體和 C11 Atomics

閱讀 Hardware Memory Models

什麼是 Memory Models？

多執行緒程式的執行順序不僅取決於程式碼的撰寫，也高度受到硬體與編譯器優化的影響。

考慮以下 C 語言風格的 pseudocode，所有變數都被初始化為 0。

// Thread 1        // Thread 2
x = 1;             while (done == 0) { /* loop */ }
done = 1;          print(x);

預期上述程式會輸出 1，這在 x86 (或其他 usually-strong memory model 的處理器) 上成立，但在 ARM (或其他 weak memory model 的處理器) 上則有可能會輸出 0，考慮編譯器優化後，上述程式碼也有可能會進入無窮迴圈。

關於 memory model 的分類與定義可以參考 Weak vs. Strong Memory Models 以及 並行與多執行緒程式設計: 執行順序

為了享受多執行緒帶來的效能提升，同時確保程式運作符合預期，程式設計師需要知道程式會在硬體上如何運行，硬體和編譯器工程師也需要知道哪些優化是被允許的，以確保跨執行緒間的資料一致性 (consistency)，定義這件事的協議被稱為 memory consistency model，簡稱 memory model。

Sequential Consistency

Leslie Lamport 於 1979 年的論文 How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs 提出了最常見的 memory consistency model –– sequential consistency (SC)，定義如下：

A multiprocessor system is sequentially consistent if 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.

以上定義可以分成兩個層面來看，只要系統同時滿足以下兩個條件就可以稱為 sequentially consistent：

1. 對所有處理單元而言：所有可能發生的執行順序，其執行結果都和循序執行 (sequential execution) 的一樣
2. 對單一處理單元而言：所有分配到該執行單元的操作的執行順序和程式碼撰寫的順序一樣

為了加強對 seuqential consistency 的理解，這裡舉一個例子，Litmus Test: Message Passing

// Thread 1        // Thread 2
x = 1              r1 = y
y = 1              r2 = x

如果是這個 litmus test 滿足 sequential consistency，那麼對單一執行緒 Thread 1 而言，x = 1 必定會發生在 y = 1 之前，對 Thread 2 而言，r1 = y 一定會發生在 r2 = x 之前。

對於整支程式來說，那麼將會有以下六種可能的執行順序：

x = 1             |  x = 1             |  x = 1            |        r1 = x(0)  |        r1 = x(0)  |        r1 = x(0)  |
y = 1             |        r1 = y (0)  |        r1 = y(0)  |  x = 1            |  x = 1            |        r2 = x(0)  |
      r1 = y (1)  |  y = 1             |        r2 = x(1)  |  y = 1            |        r2 = x(1)  |  x = 1            |
      r2 = y (1)  |        r2 = y (1)  |  y = 1            |        r2 = x(1)  |  y = 1            |  y = 1            |

沒有任何一個執行順序的結果是 r1 = 1、r2 = 0，所以 litmus test 的結果顯示 sequentially consistent hardware 只允許 (r1, r2) 為 (1, 1)、(0, 1) 和 (0, 0) 三種結果。

可以想像 sequentially consistent 的硬體如下，每個執行緒都可以直接存取共享記憶體，而記憶體一次只處理一個讀取或寫入操作，自然而然確保了 sequential consistency。

事實上 sequential consistent 的硬體不只一種實作方式，甚至可以有 cache、分 bank，只要能夠確保其結果和上述模型的行為相同即可。

x86 Total Store Order (x86-TSO)

現代 x86 的 memory model 的硬體大致如下：

所有的處理器可以存取到單一的共享記憶體，但每個處理器在寫入時只會寫至自己的 write queue

Litmus Test: Write Queue (Store Buffer)

// Thread 1        // Thread 2
x = 1              y = 1
r1 = y             r2 = x

sequential consistency 不會有 r1 = r2 = 0 的狀況，但 TSO 會。因為 sequentially consistent 的 memory model 下，x = 1 或 y = 1 一定會先寫入，後面才會有讀取的動作，因此不會有 r1 = r2 = 0 的狀況，但在 TSO 的 memory model 下，兩個執行緒的寫入操作可能都還在佇列當中，讀取就先發生，因此可能會有 r1 = r2 = 0 的狀況。

非 sequentially consistent 的硬體通常會支援額外的 memory barrier (fence) 指令來控制讀寫操作的順序，限制 memory barrier 以前的寫入完成 (自佇列清空) 後才能進行後續的讀取操作。

// Thread 1           // Thread 2
x = 1                 y = 1
barrier               barrier
r1 = y                r2 = x

Total store order 之所以叫 total store order，原因在於一旦一個寫入操作抵達共享記憶體，就代表所有的處理器都已經認知到該值已寫入，不會有不同處理器看到的值不同的狀況。也就是說，下方的 litmus test 不會有 r1 = 1、r2 = 0、r3 = 1，但 r4 = 0 狀況。

Litmus Test: Independent Reads of Independent Writes (IRIW)

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1          y = 1          r1 = x         r3 = y
                              r2 = y         r4 = x

一旦 Thread 3 讀到 r1 = 1、r2 = 0 就代表，x = 1 的寫入比 y = 1 早抵達共享記憶體，若此時 Thread 4 讀到的 r3 = 1，就代表 y = 1 和 x = 1 的寫入都已經可以被 Thread 4 所看見，因此 r4 就只能為 1。我們可以說 Thread 1 對 x 的寫入「happens before」Thread 2 對 y 的寫入。

ARM/POWER Relaxed Memory Model

ARM 和 POWER 指令集則採用更加寬鬆的 memory model，每個執行緒都是都有自己的一份記憶體副本，每次讀寫都是以自己的副本做為對象，寫入自己記憶體的同時也會傳播到其他執行緒的記憶體。

因此這樣的模型並不存在 total store order，更甚者，讀取的操作甚至可以延後到真正需要的時候才開始進行。

一個執行緒的寫入順序和其他執行緒所看到寫入順序不再一樣，因為寫入操作在傳播的過程中可能會被重排。

不過對於同一個記憶體位址的讀寫仍需要遵守 total order，也就是下面的 litmus test 不可能會發生 r1 = 1、r2 = 2 但 r3 = 2、r4 = 1 的狀況。哪個寫入被哪個寫入給覆蓋必須是所有 threads 都看得到的，這樣的保證被稱為 coherence，若沒有 coherence 的保證，將會很難為這樣的系統進行程式設計。

Litmus Test: Coherence
Can this program see r1 = 1, r2 = 2, r3 = 2, r4 = 1? No
(Can Thread 3 see x = 1 before x = 2 while Thread 4 sees the reverse?)

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1          x = 2          r1 = x         r3 = x
                              r2 = x         r4 = x

Weak Ordering and Data-Race-Free Sequential Consistency (DRF-SC)

Sarita Adve 和 Mark Hill 於 1990 年發表論文 Weak Ordering – A New Definition，定義 weak ordering 如下：

• Let a synchronization model be a set of constraints on memory accesses that specify how and when synchronization needs to be done.
• Hardware is weakly ordered with respect to a synchronization model if and only if it appears sequentially consistent to all software that obey the synchronization model.

嘗試解讀上述定義，可以發現 weak ordering 是軟硬體間的協定 (contract)，只要軟體遵守 synchronization model 的限制，那硬體就會展現 sequential consistency，即便該硬體本身具有更為寬鬆的 memory order。

Sarita Adve 和 Mark Hill 提出一種 synchronization model 稱為 data-race-free (DRF) model，其假設硬體有 memory barrier 作為記憶體存取同步的操作，所有 memory barrier 之間的讀寫操作都可以被重排，但重排的範圍不能跨越 memory barrier。

而 data-race-free 指的是任兩個來自不同執行緒對同一記憶體位置的記憶體存取，要嘛都是讀取，要嘛會有 memory barrier 來強制兩個操作一前一後發生。

例如下方例子會發生 data race，因為 Thread 2 的寫入可能會和 Thread 1 的寫入或讀取同時發生。

但加上了 memory barrier S(a) 就可以避免 data race。

DRF model 說明了只要硬體有提供像是 memory barrier 的同步機制，而軟體的撰寫有適當的使用這些同步機制來避免 data race，硬體就能夠確保 sequentially consistent ordering (簡稱為 DRF-SC)。

閱讀 Programming Language Memory Models

什麼是 Programming Language Memory Model

Programming language memory model 嘗試定義並行程式可以依靠哪些行為在執行緒之間共享記憶體。

考慮以下程式：

// Thread 1           // Thread 2
x = 1;                while(done == 0) { /* loop */ }
done = 1;             print(x);

Thread 1 嘗試將透過共享的變數 x 將訊息傳遞給 Thread 2，預期 Thread 2 會印出 1，但編譯器最佳化可能會讓結果不符合預期。

如果 done 是普通變數，那 Thread 2 的迴圈有可能永遠不會停止，原因是編譯器在進行最佳化時，會在第一次使用到 done 變數時將其載入至暫存器中，並盡可能重複利用，當 Thread 1 更新 done 中的數值時，Thread 2 就不會注意到 done 已經變更。其次，編譯器有可能 x = 1 和 done = 1 進行重排，導致 x = 1 有可能在 print(x) 之後才執行，因此印出 0。

為了解決這樣的問題，許多現代程式語言當中有定義 atomic 變數或 atomic 操作，讓 done 成為 atomic 變數可以有以下效果：

1. Thread 1 在對 done 寫入之前，要確保 x 寫入已經完成並且可以被其他執行緒看見
2. Thread 2 每次迭代需要重新從記憶體讀取 x，而非重用暫存器中的值
3. Thread 2 要在 done 讀取後才能讀取 x
4. 一些可能造成問題的編譯器最佳化和硬體最佳化會被停用

如此一來 atomic 變數 done 就表現得像是前面提到的 memory barrier 一樣，避免了 data race 的發生，進一步確保了程式執行的 sequential consistency。換句話說在 programming language memory model 中，DRF-SC 也適用，只要確保程式沒有 data race，就能夠預期程式以 sequentially consistent 的方式執行。

Litmus Tests

Litmus Tests for Comparing Memory Consistency Models: How Long Do They Need to Be?

這篇論文中以嚴謹的數學定義了並行程式的執行順序與 memory model，以下是相關概念的定義：

• parallel program \(P\): a set of concurrently executed threads, where each thread is a sequence of instructions
• program execution \(\alpha_P\): specifies the sequence of instruction that were executed in each thread, annotated with the actual values for all the involved registers
• instruction execution: an instance of instruction \(i\), annotated with the values for all the involved registers
• thread execution \(\alpha_t\): a sequence of instructions in the order they executed in thread \(t\)
• program ordrer: the order of two instructions \(x\) and \(y\) with respect to a given thread execution \(\alpha_t\)
• memory model \(M\): a set of allowed program executions

假設有兩個 memory models \(M_1\) 和 \(M_2\)，

\[ M_1 \subseteq M_2 \iff \forall \alpha_P \in M_1 , \alpha_P \in M_2 \]

如果 \(M_1 \subseteq M_2\) 且 \(M_2 \subseteq M_1\), 則 \(M_1\) 和 \(M_2\) 等價

定義 memory model 還需要以下定義：

must-not-reorder function \(F: (x, y) \rightarrow \{0, 1\}\)，表示兩條在同一個 thread 上執行的指令 \(x\) 和 \(y\) 是否被允許重排，\(F(x, y) = 1\) 代表不能重排，一定只能依照 program order \(\alpha_P\) 的順序執行，\(F(x, y) = 0\) 則反之

定義關係
read-from map \(\rightarrow\)：假設 \(x\) 是 store 指令、\(y\) 是 load 指令，\(x \rightarrow y\) 代表 \(y\) 會從 \(x\) 寫入的同一個暫存器讀取資料
happens-before order \(\Rightarrow\)：表示指令間的先後順序，\(x \Rightarrow y\) 代表 \(x\) 比 \(y\) 先發生

如果兩個 memory model 在同樣的 limus test 中表現出不一樣的行為，就可以證明這兩個 memory model 是不同的，

Theorem 1. For every two memory models, \(M_1\) and \(M_2\), that are defined via a must-not-reorder function, if \(M_2 \subseteq M_1\), then there is a test \(P\) and an execution \(\alpha_P\) with two threads and up to six memory access operations, such that \(\alpha_P \notin M_1\), \(\alpha_P \in M_2\).

Compilers and Optimizations

編譯器的指令重排讓程式語言的 memory model 比任何硬體架構都還要弱，考慮以下程式碼，即便是最弱的 ARM/POWER memory model 都不會出現 r1 = 1、r2 = 2、r3 = 2、r4 = 1 的狀況 (也就是 Thread 3 先看見 x = 1 然後 x = 2，但 Thread 4 卻反過來)

// Litmus Test: Coherence

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1          x = 2          r1 = x         r3 = x
                              r2 = x         r4 = x

但如果編譯器認為是兩個獨立的讀取指令，進而把 r3 = x 和 r4 = x 重排，就會打破這項保證。

C11/C++11 Atomics

C11 和 C++11 提供了三種 atomic 操作：

• strong synchronization (sequentially consistent)
• weak synchronization (acquire/release, coherence-only)
• no synchronization (relexed)

此外 C++ 還提供了 memory fence 作為 atomic 變數的另一種做法，但較少用。

DRF-SC or Catch Fire

和其他程式語言 (如 Java) 不同，C++ 對存在 data race 的程式的行為完全不提供任何保證，也就是說 data race 屬於未定義行為。這麼定義有以下理由：

• 未定義行為可以提供編譯器進行優化的空間
• 現有的編譯器和函式庫在編寫時應對 race condition 的方式並不統一，找到並修復所有問題太困難
• 保留程式設計師使用 relexed atomic 的彈性
• 允許實現 rece detection 並停止執行程式

考慮以下程式，其中 x 是全域變數：

unsigned i = x;

if (i < 2) {
    foo: ...
    switch (i) {
    case 0:
        ...;
        break;
    case 1:
        ...;
        break;
    }
}

假如 foo 區塊的程式碼非常複雜，需要重複使用有限的暫存器，編譯器可能會在執行 switch 時再次從全域變數 x 中讀值，但此時 x 可能被其他執行緒變更，導致i < 2 不再成立。如果編譯器又剛好把 switch 編譯成 lookup table 來進行跳轉，那就有可能跳到非預期的位址，導致嚴重後果。

對於既有為單一執行緒編寫的 C/C++ 編譯器，期望找到所有問題並修復是不切實際的，但在新語言中，應該要設定更高的目標。

Sequentially Consistent Atomics

在 C11 中採用了 sequentially consistent 的 atomic variable

atomic_int done;

等同於使用一般的變數搭配 atomic operation

// Thread 1
atomic_store(&done, 1);

// Thread 2
while (atomic_load(&done) == 0) { /* loop */ }

C11 也提供了更寬鬆的 atomic 操作，使用 atomic_store_explicit 和 atomic_load_explicit 並明確指定所需的 memory order。上述例子相當於

// Thread 1
atomic_store_explicit(&done, 1, memory_order_seq_cst);

// Thread 2
while (atomic_load_explicit(&done, memory_order_seq_cst) == 0) { /* loop */ }

Acquire/Release Atomics

在 acquire/release atomics 中，所有在 release 之前的寫入操作必須能夠被 acquire 之後同一個變數的讀取操作所看見，也就是從 release 到 acquire 之間建立了 happens-before 的關係。我們使用 acquire/release atomic 修改上述程式如下：

// Thread 1
atomic_store_explicit(&done, 1, memory_order_release);

// Thread 2
while (atomic_load_explicit(&done, memory_order_acquire) == 0) { /* loop */ }

值得注意的是，sequentially consistent 的 atomic 操作，要求程式的執行順序要與 total order 一致。但 acquire/release 則是只要求對某個記憶體位址 (如上述程式碼中的 done) 的讀寫是 sequentially consistent，可以說是違背了 DRF-SC 的原則。

例如以下例子：

/* Litmus Test: Store Buffering
 * Can this program see r1 = 0, r2 = 0?
 */

// Thread 1           // Thread 2
x = 1                 y = 1
r1 = y                r2 = x

/*
 * On sequentially consistent hardware: no.
 * On x86 (or other TSO): yes!
 * On ARM/POWER: yes!
 * On Java (using volatiles): no.
 * On C++11 (sequentially consistent atomics): no.
 * On C++11 (acquire/release atomics): yes!
 */

r1 = y 建立 acquire，在其後的讀取操作都可以見到 x = 1，但卻不保證可以見到 y = 1，同理，r2 = x 建立 acqure，執行時也不保證會見到 x = 1， 因此可能會有 r1 = r2 = 0 的狀況發生。

Relexed Atomics

除了 acquire/release 之外，C11 還引入了更寬鬆 (且非同步) 的 atomic 操作，稱為 relaxed atomic。使用 relaxed atomic 不會創造任何 happens-before 關係，也沒有任何排序的保證，意味著 relexed atomic 的讀寫操作和普通的讀寫沒有區別，可以被編譯器任意重排，差別只在於 relaxed atomic 操作本身會是 atomic 的，且在 relaxed atomic 上發生的 data race 不會被認為是 data race 而引發錯誤。

並行程式設計: 執行順序的改進

簡述 Memory Consistency Models 的改進

目前的架構如下：

• memory consistency model 簡介
• sequential consistency
  • Leslie Lamport 對 sequential consistency 的定義和說明
• weak memory model v.s. strong memory model
• 確保執行順序
  • Dekker's Algorithm
  • Peterson's Algorithm
• 確保對所有處理器都是一致的
• Cache Coherence and Sequential Consistency

建議調整架構如下：

• memory consistency model 簡介
• (修改) 最直覺的約定：sequential consistency
  • Leslie Lamport 對 sequential consistency 的定義和說明
  • (新增) 撰寫 example pseudocode 以理解 sequential consistency 的執行結果
  • (新增) 新增 sequential consistent 的硬體模型
• (修改) weak memory model v.s. strong memory model
  • (刪除範例說明，改由以下 Litmus test 和 x86-TSO 及 ARM/PowerPC memory model 代替)
• (新增) 執行順序的數學描述
• (新增) 分辨不同的 memory consistency model: Litmus tests
• (新增) Hardware memory consistency models
  • x86-TSO
  • ARM/POWER
  • DRF-SC
• 確保執行順序
  • Dekker's Algorithm
  • Peterson's Algorithm
• 確保對所有處理器都是一致的
• Cache Coherence and Sequential Consistency

修改〈最直覺的約定：Sequential Consistency〉

目前講義對 sequential consistency 的定義說明較為抽象，後續的範例又太過複雜，不容易讓初學者在短時間內理解，因此建議在〈最直覺的約定：Sequential Consistency〉小節保留前面 Leslie Lamport 提出的 sequential consistency 定義的說明，並新增以下描述：

int x = 0
int y = 0
    
// Thread 1        // Thread 2
x = 1              r1 = y
y = 1              r2 = x

x = 1             |  x = 1             |  x = 1            |        r1 = y(0)  |        r1 = y(0)  |        r1 = y(0)  |
y = 1             |        r1 = y (0)  |        r1 = y(0)  |  x = 1            |  x = 1            |        r2 = x(0)  |
      r1 = y (1)  |  y = 1             |        r2 = x(1)  |  y = 1            |        r2 = x(1)  |  x = 1            |
      r2 = x (1)  |        r2 = x (1)  |  y = 1            |        r2 = x(1)  |  y = 1            |  y = 1            |

新增〈執行順序的數學描述〉

新增〈分辨不同的 memory consistency model: Litmus tests〉

// Litmus Test: Message Passing
// Can this program see r1 = 1, r2 = 0?

// Thread 1           // Thread 2
x = 1;                r1 = y;
y = 1;                r2 = x;

// Litmus Test: Write Queue (also called Store Buffer)
// Can this program see r1 = 0, r2 = 0?

// Thread 1           // Thread 2
x = 1;                y = 1;
r1 = y;               r2 = x;

// Litmus Test: Independent Reads of Independent Writes (IRIW)
// Can this program see r1 = 1, r2 = 0, r3 = 1, r4 = 0?
// (Can Threads 3 and 4 see x and y change in different orders?)

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1;         y = 1;         r1 = x;        r3 = y;
                              r2 = y;        r4 = x;

// Litmus Test: Load Buffering
// Can this program see r1 = 1, r2 = 1?
// (Can each thread's read happen after the other thread's write?)

// Thread 1    // Thread 2
r1 = x;        r2 = y;
y = 1;         x = 1;

// Litmus Test: Coherence
// Can this program see r1 = 1, r2 = 2, r3 = 2, r4 = 1?
// (Can Thread 3 see x = 1 before x = 2 while Thread 4 sees the reverse?)

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1;         x = 2;         r1 = x;        r3 = x;
                              r2 = x;        r4 = x;

新增〈Hardware Memory Consistency Models〉

// Litmus Test: Write Queue (Store Buffer)
int x = 0;
int y = 0;

// Thread 1        // Thread 2
x = 1;             y = 1;
r1 = y;            r2 = x;

// Thread 1           // Thread 2
x = 1;                y = 1;
barrier;              barrier;
r1 = y;               r2 = x;

// Litmus Test: Independent Reads of Independent Writes (IRIW)
int x = 0;
int y = 0;

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1;         y = 1;         r1 = x;        r3 = y;
                              r2 = y;        r4 = x;

// Litmus Test: Coherence
int x = 0;

// Thread 1    // Thread 2    // Thread 3    // Thread 4
x = 1;         x = 2;         r1 = x;        r3 = x;
                              r2 = x;        r4 = x;

TODO: 將執行順序納入《Concurrency Primer》

改進現有關於 memory order 的描述，改寫和整合上述內容

Environment Setup and Preparation

1. Fork sysprog21/concurrency-primer as yutingshih/concurrency-primer
2. Clone repository

git clone git@github.com:yutingshih/concurrency-primer.git
git clone git@github.com:sysprog21/arm-assembler-latex-listings.git
cd concurrency-primer
mv ../arm-assembler-latex-listings/lstlangarm.sty .

3. Install LaTeX compiler and packages (on Ubuntu 22.04 with kernel 6.5.0)

sudo apt update
sudo apt install -y texlive-base texlive-core
lualatex --version

sudo tlmgr update --self
sudo tlmgr install mathastext selnolig footmisc bigfoot enumitem minted changepage

python3 -m venv venv
. ./venv/bin/activate
pip install Pygments

4. Compile LaTeX source code

lualatex -halt-on-error -shell-escape concurrency-primer.tex

Improvement of §10 Memory Orderings

原本第 10 章 Memory Orderings 只提到 C++11 所提供的 memory orders，缺乏對於 memory consistency model 的描述，因此計畫改進如下：

• §10 - Memory orderings
  • 10.1 - Memory consistency models (新增)
    • Sequential consistency (SC)
    • Total store order (TSO)
    • Relaxed memory order (RMO)
  • 10.2 - C11/C++11 atomics
    • Acquire and release
    • relaxed
    • Acquire-release
    • Consume
    • Hc Svnt Dracones

詳見 PR #16

Code review 過程