## Linux 核心專題: 《Concurrency Primer》校訂和範例撰寫
> 執行人: yutingshih
> [專題解說影片](https://youtu.be/Hwc6HGfyCkQ)
## 任務簡介
針對《Concurrency Primer》，補充校訂和範例撰寫。
## 閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts)〉系列講座並紀錄問題
在開始進行教材修訂之前，先閱讀 [並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts) 系列講座，學習並行程式設計相關的背景知識，以下是針對各章節的筆記以及問題
### [並行和多執行緒程式設計 -- 概念](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts)
:::warning
- 在 [搶佔式與非強取式核心](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts#%E6%90%B6%E4%BD%94%E5%BC%8F%E8%88%87%E9%9D%9E%E5%BC%B7%E5%8F%96%E5%BC%8F%E6%A0%B8%E5%BF%83) 中，內文都是採用「非搶佔式核心」，但標題卻是「非強取式核心」，兩者不一致
:::
- 可再進入 (reentrancy) 的函式是可以被多個工作 (task) 同時呼叫而不會有資料不一致的問題。需要避免使用共享記憶體區 (例如 global memory)，所有資料都存在呼叫者或函式的堆疊區
- fork-join: 每個執行單元都有自己的 stack , 但跟本來的執行執行單元共用 text, heap 與 data section。
### [並行與多執行緒程式設計 -- 執行順序](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering)
- `x++` 會先做 value compuatation 再做 side effect
- `++x` 會先做 side effect 再做 value compuatation
- `=` 會先做兩個運算元的 value computation 再做 `=` 的 side effect，最後才是 `=` 的 value computation
```c
i = i++
```
因為 `i++` 的 side effect 發生在 value computation 之後，不能確定前者與 `=` 的 side effect 的先後順序，因此屬於未定義行為
```c
i = ++i
```
但 `++i` 的 side effect 發生在 value computation 之前，兩者皆發生在 `=` 的 side effect 之後，故沒有不確定的行為 (well-defined)
- [Order of evaluation - cppreference.com](https://en.cppreference.com/w/cpp/language/eval_order)
#### Happens Before
:::danger
修正圖片存取權限。
> [name=yutingshih] 似乎是因為近期 HackMD 更新，系統不穩定，重新整理網頁即可正常顯示
> $\to$ 以網頁瀏覽器的無痕模式確認
> [name=yutingshih] 我知道原因了，因為這部分內容是從我另一則筆記直接把 Markdown 原始碼複製過來的，重新上傳一次圖片或更新舊筆記的瀏覽權限就可以了
:::
:::warning
問題：
在〈並行程式設計: 執行順序〉的 [Happens-before](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering#Happens-before) 中，文字敘述有誤：
- 下面好像不是 Java 程式
- 與下面 happens-before 的描述矛盾，上一行的操作不必然得 sequenced-before 下一行
:::
:::warning
- total order 有四個屬性：reflexive, antisymmetric, trasitive, connected，講義只講到三個，但 Wikipedia 上的 total order 的定義還有包含 reflexive: $\forall a \in X, aRa$
:::
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 操作](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics)
#### Memory Ordering
<s>
閱讀 [cppreference: C++11 Memory Order](https://en.cppreference.com/w/c/atomic/memory_order)
</s>
:::danger
參照 C11 規格書。
:::
##### `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}`
```c
_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
```c
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??**==
<!-- #### `atomic_fetch_add` -->
<!-- #### `atomic_load` -->
<!-- #### `atomic_store` -->
<!-- #### `atomic_init` -->
<!-- #### `atomic_flag_test_and_set` -->
<!-- #### `atomic_flag_clear` -->
<!-- #### `atomic_is_lock_free` -->
<!-- #### `atomic_thread_fence` -->
<!-- #### `atomic_signal_fence` -->
### [並行程式設計: POSIX Thread](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fposix-threads)
作業系統領域常常都是較複雜的概念先出現，之後才有簡化的實作，例如 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)](https://github.com/iceqp/books-1/blob/master/The%20Design%20and%20Implementation%20of%20the%20FreeBSD%20Operating%20System%20(2nd%20Edition).pdf))」
GNU 又在 POSIX 標準之上進行擴充，可以看 `pthread.h` 中 `*_np` 結尾的函式，意思是 non-protable
[POSIX Threads Programming | LLNL HPC Tutorials](https://hpc-tutorials.llnl.gov/posix/)
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
:::danger
修正圖片存取權限
> [name=yutingshih] 似乎是因為近期 HackMD 更新，系統不穩定，重新整理網頁即可正常顯示
> [name=yutingshih] 已修正
:::
界定 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`](https://man7.org/linux/man-pages/man3/pthread_atfork.3.html) 可以用來註冊 fork 時的 callback function
```c
#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](https://github.com/angrave/SystemProgramming/wiki/Synchronization,-Part-1:-Mutex-Locks)
> [yutingshih/learn-pthreads](https://github.com/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
```c
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
```c
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
```c
int local = 0;
for (int i = 0; i < 1000000; i++) {
local += 1;
}
pthread_mutex_lock(&lock);
sum += local;
pthread_mutex_unlock(&lock);
```
:::warning
原本預期作法 3 應該比作法 2 快，因為兩個 threads 的 summation 可以同時進行，只有在把 `local` 結果加回去共用的 `sum` 才需要做同步，但實際測量發現時間卻是作法 2 比作法 3 還快，嘗試使用更多 threads (4 個)，卻也得到一樣的結果
:::
### 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`.
```c
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 進入
```c
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
```
| Time | Turn | Thread #1 | Thread #2 |
| ---- | ---- | -------------------------------------------------- | -------------------------------------------------------- |
| 1 | 2 | raise my flag | |
| 2 | 2 | if your flag is raised (false), wait until my turn | raise my flag |
| 3 | 2 | // Do Critical Section stuff | if your flag is raised (true), wait until my turn (true) |
| 4 | 2 | // Do Critical Section stuff | // Do Critical Section stuff (OOPS) |
#### 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
```
```clike
// 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 時是否可以修改為：
```clike
// 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: 修訂[並行程式設計: 執行順序](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering)
> 閱讀 [Hardware Memory Models](https://research.swtch.com/hwmm) 和 [Programming Language Memory Models](https://research.swtch.com/plmm)，紀錄你的認知並列出[並行程式設計: 執行順序](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering)的改進，至少涵蓋硬體和 C11 Atomics
### 閱讀 [Hardware Memory Models](https://research.swtch.com/hwmm)
#### 什麼是 Memory Models？
多執行緒程式的執行順序不僅取決於程式碼的撰寫，也高度受到硬體與編譯器優化的影響。
考慮以下 C 語言風格的 pseudocode，所有變數都被初始化為 0。
```clike
// 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](https://preshing.com/20120930/weak-vs-strong-memory-models/) 以及 [並行與多執行緒程式設計: 執行順序](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering#Memory-Consistency-Models)
為了享受多執行緒帶來的效能提升，同時確保程式運作符合預期，程式設計師需要知道程式會在硬體上如何運行，硬體和編譯器工程師也需要知道哪些優化是被允許的，以確保跨執行緒間的資料一致性 (consistency)，定義這件事的協議被稱為 memory consistency model，簡稱 memory model。
<!-- 定義硬體執行順序的稱為 hardware memory model；定義編譯器執行順序的稱為 programming language memory model。 -->
#### Sequential Consistency
Leslie Lamport 於 1979 年的論文 [How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs](https://www.microsoft.com/en-us/research/publication/make-multiprocessor-computer-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
```clike
// 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` 之前。
對於整支程式來說，那麼將會有以下六種可能的執行順序：
```clike
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。
<center><img src="https://hackmd.io/_uploads/ByCtaNE8A.png" width=75% /></center><br>
事實上 sequential consistent 的硬體不只一種實作方式，甚至可以有 cache、分 bank，只要能夠確保其結果和上述模型的行為相同即可。
#### x86 Total Store Order (x86-TSO)
現代 x86 的 memory model 的硬體大致如下：
<center><img src="https://hackmd.io/_uploads/H1FnUnHUR.png" width=75% /></center><br>
所有的處理器可以存取到單一的共享記憶體，但每個處理器在寫入時只會寫至自己的 write queue
Litmus Test: Write Queue (Store Buffer)
```clike
// 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 以前的寫入完成 (自佇列清空) 後才能進行後續的讀取操作。
```clike
// 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，每個執行緒都是都有自己的一份記憶體副本，每次讀寫都是以自己的副本做為對象，寫入自己記憶體的同時也會傳播到其他執行緒的記憶體。
<center><img src="https://hackmd.io/_uploads/rkXSAzvIA.png" width=45% /></center><br>
因此這樣的模型並不存在 total store order，更甚者，讀取的操作甚至可以延後到真正需要的時候才開始進行。
一個執行緒的寫入順序和其他執行緒所看到寫入順序不再一樣，因為寫入操作在傳播的過程中可能會被重排。
不過對於同一個記憶體位址的讀寫仍需要遵守 total order，也就是下面的 litmus test 不可能會發生 `r1 = 1`、`r2 = 2` 但 `r3 = 2`、`r4 = 1` 的狀況。哪個寫入被哪個寫入給覆蓋必須是所有 threads 都看得到的，這樣的保證被稱為 coherence，若沒有 coherence 的保證，將會很難為這樣的系統進行程式設計。
```clike
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](http:/citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.5567)，定義 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 的寫入或讀取同時發生。
<center><img src="https://hackmd.io/_uploads/Skwe9EvIC.png" width=30% /></center><br>
但加上了 memory barrier `S(a)` 就可以避免 data race。
<center><img src="https://hackmd.io/_uploads/BkW99VDUC.png" width=30% /></center><br>
<!-- <center><img src="https://hackmd.io/_uploads/r1jXiEP8C.png" width=30% /></center><br> -->
<!-- <center><img src="https://hackmd.io/_uploads/rk0XsNPIA.png" width=50% /></center><br> -->
<!-- <center><img src="https://hackmd.io/_uploads/Sk7EjNw80.png" width=50% /></center><br> -->
DRF model 說明了只要硬體有提供像是 memory barrier 的同步機制，而軟體的撰寫有適當的使用這些同步機制來避免 data race，硬體就能夠確保 sequentially consistent ordering (簡稱為 DRF-SC)。
<!-- [14.25-15.00-RISCVMemoryModelTutorial.pdf](https://riscv.org/wp-content/uploads/2018/05/14.25-15.00-RISCVMemoryModelTutorial.pdf) -->
### 閱讀 [Programming Language Memory Models](https://research.swtch.com/plmm)
#### 什麼是 Programming Language Memory Model
Programming language memory model 嘗試定義並行程式可以依靠哪些行為在執行緒之間共享記憶體。
考慮以下程式：
```clike
// 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?](https://www.cis.upenn.edu/~alur/DAC11.pdf)
這篇論文中以嚴謹的數學定義了並行程式的執行順序與 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 卻反過來)
```clike
// 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` 是全域變數：
```c
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
```c
atomic_int done;
```
等同於使用一般的變數搭配 atomic operation
```c
// Thread 1
atomic_store(&done, 1);
// Thread 2
while (atomic_load(&done) == 0) { /* loop */ }
```
C11 也提供了更寬鬆的 atomic 操作，使用 `atomic_store_explicit` 和 `atomic_load_explicit` 並明確指定所需的 memory order。上述例子相當於
```c
// 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 修改上述程式如下：
```cpp
// 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 的原則。
例如以下例子：
```c
/* 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` 的狀況發生。
<!-- ##### Example of Acquire/Release Atomics
```c
// TODO
``` -->
##### Relexed Atomics
除了 acquire/release 之外，C11 還引入了更寬鬆 (且非同步) 的 atomic 操作，稱為 relaxed atomic。使用 relaxed atomic 不會創造任何 happens-before 關係，也沒有任何排序的保證，意味著 relexed atomic 的讀寫操作和普通的讀寫沒有區別，可以被編譯器任意重排，差別只在於 relaxed atomic 操作本身會是 atomic 的，且在 relaxed atomic 上發生的 data race 不會被認為是 data race 而引發錯誤。
<!-- ##### Example of Relexed Atomics
```c
// TODO
``` -->
### [並行程式設計: 執行順序](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering)的改進
#### 簡述 [Memory Consistency Models](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering#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](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering#%E6%9C%80%E7%9B%B4%E8%A6%BA%E7%9A%84%E7%B4%84%E5%AE%9A-Sequential-Consistency)〉
目前講義對 sequential consistency 的定義說明較為抽象，後續的範例又太過複雜，不容易讓初學者在短時間內理解，因此建議在〈[最直覺的約定：Sequential Consistency](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering#%E6%9C%80%E7%9B%B4%E8%A6%BA%E7%9A%84%E7%B4%84%E5%AE%9A-Sequential-Consistency)〉小節保留前面 Leslie Lamport 提出的 sequential consistency 定義的說明，並新增以下描述：
:::info
值得注意的是，sequential consistency 並非指程式只有一種順序、一種結果，相反地，sequential consistency 只要求程式看起來像是以某種交錯的順序在單一執行緒上執行，因此 sequentially consistent 的程式仍可能會有多種可能的結果。
為了加強對 seuqential consistency 的理解，這裡舉一個簡單的例子，考慮以下 pseudocode，有兩個執行緒分別寫入和讀取兩個共享變數 `x` 和 `y`，兩個變數一開始都初始化為 `0`。
```clike
int x = 0
int y = 0
// Thread 1 // Thread 2
x = 1 r1 = y
y = 1 r2 = x
```
如果這支程式滿足 sequential consistency，那麼對單一執行緒 Thread 1 而言，`x = 1` 必定會發生在 `y = 1` 之前，對 Thread 2 而言，`r1 = y` 一定會發生在 `r2 = x` 之前。
而對於整支程式來說，將會有以下六種可能的執行順序：
```clike
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 |
```
觀察一下可以發現，沒有任何一個執行順序的結果是 `r1 = 1`、`r2 = 0`，也就是說 sequential consistency 只允許 `(r1, r2)` 為 `(1, 1)`、`(0, 1)` 和 `(0, 0)` 三種結果。有了這項約定，軟體可以預期不會出現 `(1, 0)` 這樣的結果，而硬體只要保證不會出現 `(1, 0)` 結果，便可以在「安全」的範圍內盡可能的做最佳化。
可以想像 sequentially consistent 的硬體如下，每個執行緒都可以直接存取共享記憶體，而記憶體一次只處理一個讀取或寫入操作，自然而然確保了 sequential consistency。
<center><img src="https://hackmd.io/_uploads/ByCtaNE8A.png" width=75% /></center>
事實上 sequential consistent 的硬體不只一種實作方式，甚至可以有 cache、分 bank，只要能夠確保其結果和上述模型的行為相同即可。
:::
#### 新增〈執行順序的數學描述〉
:::info
##### Total Order
前面提到 sequential consistency 的定義要求並行程式以「某種順序」在所有處理器上執行，這個順序在數學上稱為「total order」或「linear order」，[維基百科](https://en.wikipedia.org/wiki/Total_order) 的定義如下：
> A total order is a binary relation $\le$ on some set $X$, which satisfies the following for all $a$, $b$ and $c$ in $X$:
> 1. $a \le a$ (reflexive).
> 2. If $a \le b$ and $b \le c$ then $a \le c$ (transitive).
> 3. If $a \le b$ and $b \le a$ then $a = c$ (antisymmetric).
> 4. $a\leq b$ or $b \le a$ (strongly connected, formerly called **total**).
##### Partial Order
partial order 只比 total order strongly connected 的性質
> A total order is a binary relation $\le$ on some set $X$, which satisfies the following for all a, b and c in $X$:
> 1. $a \le a$ (reflexive).
> 2. If $a \le b$ and $b \le c$ then $a \le c$ (transitive).
> 3. If $a \le b$ and $b \le a$ then $a = c$ (antisymmetric).
##### 執行順序
論文 [Litmus Tests for Comparing Memory Consistency Models: How Long Do They Need to Be?](https://acg.cis.upenn.edu/papers/dac11_litmus.pdf) 嘗試使用數學嚴謹定義程式的執行順序，用以證明對於兩個執行緒的並行程式，只需要有限數量的 litmus tests 即可確認其 memory consistency 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$ 是 $M_2$ 的子集，就表示所有在 $M_1$ 中所允許的執行順序 $\alpha_P$ 同樣被 $M_2$ 所允許，也就是 $M_2$ 比 $M_1$ 更寬鬆，用數學表示如下：
$$
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$ 等價，反之，若存在 $\alpha_P \notin M_1$ 且 $\alpha_P \notin M_2$，則 $M_1$ 和 $M_2$ 是不同的 memory models
##### Must-not-reorder Function Predicates
而要定義 memory model，需要哪些執行順序是可以/不能被允許，論文中定義了 must-not-reorder function $F: (x,y) \rightarrow \{0,1\}$，用來表示指令 $x$ 和 $y$ 可否被重排，$F(x,y)=1$ 代表不能重排，只能依照 $\alpha_P$ 的順序執行，$F(x,y)=0$ 則可以。$F$ 由一系列的 predicates $d \in D$ 所構成，每個 predicate 用來標示指令的屬性或指令之間的關係，以下是常見的 predicates：
- $\text{Read}(x)$：表示指令 $x$ 是一個讀取操作
- $\text{Write}(x)$：表示指令 $x$ 是一個寫入操作
- $\text{Fence}(x)$：表示指令 $x$ 是一個 memory barrier 的同步操作
- $\text{DataDep}(x,y)$：表示 $x$ 和 $y$ 之間存在 data dependency
- $\text{CtrlDep}(x,y)$：表示 $x$ 和 $y$ 之間存在 control dependency
- $\text{SameAddr}(x,y)$：表示 $x$ 和 $y$ 存取同一個記憶體位址
##### Memory Model Examples
以下舉常見的 memory models 使用 must-not-reorder function $F$ 定義如下：
- Sequential consistency 不允許任何指令重排，也就是 $F_\text{SC} = \text{True}$.
- Total store order (TSO) 模型則是 $F_\text{TSO} = (\text{Write}(x) \land \text{Write}(y)) \lor \text{Read}(x) \lor \text{Fence}(x) \lor \text{Fence}(y)$
- Relaxed memory order (RMO) 模型則是 $F_\text{RMO} = (\text{Write}(y) \land \text{SameAddr}(x,y)) \lor \text{Fence}(x) \lor \text{Fence}(y) \lor \text{DataDep}(x,y) \lor \text{CtrlDep}(x,y)$
Sequential consistency 的定義很好理解，而 TSO 和 RMO 模型需要先了解其運作方式，這部分將於後續段落解釋。
##### Relations between Instruction Executions in a Program Order
定義兩個關係：
- read-from map $\rightarrow$
- happens-before order $\Rightarrow$
給定一個可能的 program execution $\alpha_P$ 和一個 must-not-reorder function $F$，則指令之間的 read-from relation「$\rightarrow$」可以定義如下：
- If $x \rightarrow y$, then $x$ is a write, $y$ is a read, and the value read by $y$ is the same as the value written by $x$.
- If $x \rightarrow y$ and $z \rightarrow y$, then $x = z$ (only one write is mapped to each read).
- If $x$ is a read and there is no write $y$ such that $y \rightarrow x$, then $x$ reads the initial value.
- if $x > y$, then $x \nrightarrow y$ (cannot read from a future write in the same thread).
給定一個 program execution $\alpha_P$、一個 must-not-reorder function $F$、一個 read-from map「$\rightarrow$」和一個 happens-before relation「$\Rightarrow$」，用來定義一個 $\alpha_P$ 所包含的指令之間的 **partial order**，有以下性質：
1. **Program order**: If $F(x,y)$ and $y > x$ then $x \Rightarrow y$.
2. **Write-write**: If $x$ and $y$ are both writes to the same address, then either $x \Rightarrow y$ or $y \Rightarrow x$.
3. **Write-read**: If $x \rightarrow y$ and $x$ and $y$ are from different threads, then $x \Rightarrow y$.
4. **Read-write**: If $x$ is a read and $y$ is a write to the same address such that $y \nrightarrow x$, and there is no write $z$ such that $z \nrightarrow x$ and $y \Rightarrow z$, then $x \Rightarrow y$.
5. **Ignore local**: If $x > y$ then $x \nRightarrow y$.
:::
#### 新增〈分辨不同的 memory consistency model: Litmus tests〉
:::info
```c
// Litmus Test: Message Passing
// Can this program see r1 = 1, r2 = 0?
// Thread 1 // Thread 2
x = 1; r1 = y;
y = 1; r2 = x;
```
```c
// 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;
```
```c
// 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;
```
```c
// 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;
```
```c
// 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〉
:::info
##### x86 Total Store Order (x86-TSO, Usually Strong)
Sequential consistency 雖然被作為多執行緒程式的「golden answer」，但因為太多的限制壓縮了效能優化的空間，因此在現代處理器中較少被實作，取而代之的是更寬鬆的 memory model，例如 x86 架構採用的 total store order (TSO) memory model，可以想像硬體大致如下：
<center><img src="https://hackmd.io/_uploads/H1FnUnHUR.png" width=75% /></center><br>
所有的處理器可以讀取單一的共享記憶體，但每個處理器在寫入時只會寫至自己的 write queue。
考慮以下 Litmus Test: Write Queue (Store Buffer)
```c
// Litmus Test: Write Queue (Store Buffer)
int x = 0;
int y = 0;
// 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 以前的寫入完成 (自佇列清空) 後才能進行後續的讀取操作。
```c
// 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)
```c
// 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;
```
一旦 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` 的寫入」。
:::
:::info
##### ARM/POWER Memory Consistency Model (Weak with Data Dependency Ordering)
ARM 和 POWER 指令集則採用更加寬鬆的 memory model，每個執行緒都是都有自己的一份記憶體副本，每次讀寫都是以自己的副本做為對象，寫入自己記憶體的同時也會傳播到其他執行緒的記憶體。
<center><img src="https://hackmd.io/_uploads/rkXSAzvIA.png" width=45% /></center>
因此這樣的模型並不存在 total store order，更甚者，讀取的操作甚至可以延後到真正需要的時候才開始進行。
一個執行緒的寫入順序和其他執行緒所看到寫入順序不再一樣，因為寫入操作在傳播的過程中可能會被重排。
不過對於同一個記憶體位址的讀寫仍需要遵守 total order，也就是下面的 litmus test 不可能會發生 `r1 = 1`、`r2 = 2` 但 `r3 = 2`、`r4 = 1` 的狀況。哪個寫入被哪個寫入給覆蓋必須是所有 threads 都看得到的，這樣的保證被稱為 coherence，若沒有 coherence 的保證，將會很難為這樣的系統進行程式設計。
上述提到的所有 litmus tests 在像 ARM/POWER 如此寬鬆的 memory model 下都被允許，除了以下這個例子：
```c
// 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;
```
不論是 ARM/POWER、x86-TSO 或 sequential consistency 都不會出現 `r1 = 1`、`r2 = 2`、`r3 = 2`、`r4 = 1` 的結果。
:::
:::info
##### Weak Ordering and Data-Race-Free Sequential Consistency (DRF-SC)
Sarita Adve 和 Mark Hill 於 1990 年發表論文 [Weak Ordering – A New Definition](http:/citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.5567)，定義 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 的寫入或讀取同時發生。
<center><img src="https://hackmd.io/_uploads/Skwe9EvIC.png" width=30% /></center>
但加上了 memory barrier `S(a)` 就可以避免 data race。
<center><img src="https://hackmd.io/_uploads/BkW99VDUC.png" width=30% /></center>
DRF model 說明了只要硬體有提供像是 memory barrier 的同步機制，而軟體的撰寫有適當的使用這些同步機制來避免 data race，硬體就能夠確保 sequentially consistent ordering (簡稱為 DRF-SC)。
:::
<!-- #### 新增〈確保執行順序 - C11 Atomics〉 -->
## TODO: 將執行順序納入《[Concurrency Primer](https://github.com/sysprog21/concurrency-primer)》
> 改進現有關於 memory order 的描述，改寫和整合上述內容
### Environment Setup and Preparation
1. Fork [sysprog21/concurrency-primer](https://github.com/sysprog21/concurrency-primer) as [yutingshih/concurrency-primer](https://github.com/yutingshih/concurrency-primer)
2. Clone repository
```shell
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)
```shell
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
```shell
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](https://github.com/sysprog21/concurrency-primer/pull/16)
Code review 過程
Sign in with Wallet
Connect another wallet