1 of 19

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

Yu-Ting Shi 施宇庭

MS in Intelligent Computing, NCKU

2 of 19

Outline

任務目標
任務一：修訂並行程式設計：執行順序
任務二：將執行順序納入《Concurrency Primer》

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

1

3 of 19

任務目標

修訂《並行程式設計：執行順序》及《Concurrency Primer》

閱讀並行程式設計系列教材並記錄問題
閱讀 Russ Cox 所寫的〈Hardware Memory Models〉和〈Programming Language Memory Models〉並記錄認知
改進上課教材《並行程式設計：執行順序》
將改進納入《Concurrency Primer》

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

2

4 of 19

任務一：修訂並行程式設計 — 執行順序

Memory consistency model: contract between hardware, compilers, and programs

Memory Consistency Models

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

3

首先要先了解執行順序

以前單核單執行緒的時候，硬體和編譯器會盡可能對原有的程式碼做指令重排等最佳化，但隨著 CPU 的設計逐漸往多核心發展，這樣的最佳化就會出問題，因此為了確保多執行緒程式的執行結果正確，我們需要定義哪些最佳化是允許的哪些不允許，有了這個協議以後，程式設計師只要照著規則寫程式，系統就能夠保證執行結果是正確的，這個協議就稱為 memory consistency model，簡稱 memory model

那常見的 memory models 依照規範的嚴格程度可以大致分為 strong model 和 weak memory model，像 x86 是比較強的 memory model，能夠允許重排的情況比較少，程式撰寫需要考慮的就比較少；相反的，ARM 是比較弱的 memory model，能夠允許重排的情況就比較多，但最佳化的空間也比較多

不論哪種 memory model，我們的最終目標都是希望在保證結果正確的前提下，盡可能做最佳化，那我們該怎麼定義所謂「正確的結果」呢

5 of 19

任務一：修訂並行程式設計 — 執行順序

1970s, proposed by Leslie Lamport

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.

Seqeuntial Consistency

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

4

6 of 19

任務一：修訂並行程式設計 — 執行順序

Message passing litmus test

not possible for r1 = 1, r2 = 0

Hardware model

all threads share a single memory which can only serve one read/write operation at a time

Seqeuntial Consistency

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

5

舉個例子來說，右上角這支程式，一開始把 x 和 y 初始化為 0，接著有兩個 threads，第一個依序對 x 和 y 寫入 1，另一個則是依序把 y 和 x 讀到 local variable r1 和 r2。

sequential consistency 要求單一執行緒不能有指令重排，對不同執行緒之間則是可以交錯執行，所以這支程式可能會有以下六種執行的順序和 (r1, r2) 等於 (1,1)、(0,1)、(0,0) 三種結果，但不會有 (r1, r2) 等於 (1,0) 這種結果。而用來分辨不同記憶體模型的測試程式被稱為 litmus test

右下角這張圖可以視為 sequential consistency 的硬體標準模型，多個執行緒共享一塊記憶體，並各自對共享記憶體做讀寫，但記憶體一次只會處理一筆讀或寫的要求，不同執行緒的執行互相獨立，所以會出現交錯的結果。

這樣的模型被視為多執行緒程式的「正確」結果，任何其他的 memory models 都需要表現得像是 sequential consistency 才算正確，但這樣的系統能做最佳化的空間不多，現代處理器也都不會以 sequential consistency 進行實作。

7 of 19

任務一：修訂並行程式設計 — 執行順序

Hardware model

write to a FIFO buffer
read from shared memory

Store buffer litmus test

x86-TSO allows r1 = r2 = 0, which is forbidden in sequential consistency

IRIW litmus test

x86-TSO denies r1 = 1, r2 = 0, r3 = 1, and r4 = 0.

Hardware Memory Models – x86 Total Store Order (TSO)

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

6

例如 x86 使用比 sequential consistency 寬鬆的 memory model，稱為 total store order (TSO)，他的硬體可以想像成右上角這張圖，每個執行緒在寫入 shared memory 以前有自己的 store buffer，但讀取就是直接從 shared memory 讀，由於每個 store buffer 是個 FIFO，因此來自單一執行緒寫入的順序會被確保，不同執行緒之間的 write 可能會交錯執行，這點和 sequential consistency 一樣，不同的地方在於，讀和寫之間是可以被重排的，如果來自 thread 1 的寫入還沒到達 shared memory，thread 2 就搶先去讀同一個記憶體位址，那 thread 2 就會讀到舊的值

舉例來說，右上的 write queue litmus test，thread 1 對 x 寫入，然後讀 y，thread 2 對 y 寫入，然後讀 x，sequential consistency 不允許這支程式出現 r1=r2=0 的狀況，r1 和 r2 至少一個會是 0，但 TSO 卻可以兩個都是 0，可以看到 TSO 比 sequential consistency 更多種執行順序，因此 TSO 比 sequential consistency 弱

再看一個例子， independent reads of independent writes，thread 1 寫入 x，thread 2 寫入 y，thread 3 先讀 x 再讀 y，thread 4 則是先讀 y 再讀 x，不管 sequential consistency 還是 total store order，都不會出現 (r1,r2,r3,r4)=(1,0,1,0)，原因是在這兩個 memory model 的約定下，一旦資料被寫入共享記憶體，就一定能被所有執行緒看到，因此當 thread 3 讀到 r1=1, r2=0，代表 x 已經被寫入，y 還沒，但當 thread 4 讀到 r3=1 的時候就代表 x 和 y 都已經被寫入，r4=0 顯然出現矛盾。

8 of 19

任務一：修訂並行程式設計 — 執行順序

Hardware model

read/write from/to local memory

Hardware Memory Models – ARM Relaxed Memory Order

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

7

Litmus test

allows IRIW to be r1 = 1, r2 = 0, r3 = 1, and r4 = 0.
denies coherence test to be r1 = 1, r2 = 2, r3 = 2, and r4 = 1.

再來看另一個常見的指令集，ARM 採用比 x86 更寬鬆的 memory model，在剛剛的 IRIW litmus test 當中，x86 不允許 (1,0,1,0) 結果，但 ARM 可以

我們可以把 ARM 的 memory model 想像成左邊這樣，每個執行緒有自己的 local memory，不同 local memory 之間也會互相交換資訊，所有的讀寫都是先對自己的 local memory 然後才更新別人的 local memory，因此就有可能發生當 thread 3 已經讀到 x 和 y 等於 1，但因為新的值還沒更新到 thread 4 的 local memory，所以 thread 4 讀到舊的 x 值等於 0 的狀況

這樣看起來 ARM 的 memory model 似乎毫無限制，但其實不是這樣，我們可以看右下角的 coherence litmus test，ARM 不允許出現 (1,2,2,1) 的結果，原因是 local memory 之間資訊傳遞是以 broadcast 的方式進行，並且單一執行緒對同一個位址的的存取不能被重排，也就是當 thread 3 能夠讀到 r2=2，thread4 也讀到 r3=2，就表示 x=2 的更新已經被反映在所有人的 local memory，且在 r3 的讀取前就已經被 thread 4 看到，因此 r4 的值只能是 2，不能是 1

9 of 19

任務一：修訂並行程式設計 — 執行順序

The Math of Memory Ordering – Must-not-reorder Funct.

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

8

剛才的例子都只是為了方便了解不同 memory model 的運作，真正作為程式、編譯器、和硬體之間協議的 memory model 還是需要有數學的嚴謹定義，因此接下來我們要來探討 memory consistency model 如何用數學定義

首先 memory model 需要定義哪些指令可以重排，哪些不行，所以我們先定義一個 must-not-reorder function F，輸入是單一個執行緒的兩個不同的指令 x 和 y，輸出則是一個布林值，如果是 1 代表 x 只能在 y 前面，不能被重排，如果是 0，代表 x 和 y 可以交換順序

而 F 是由一系列的 predicate 所組成，predicate 指的是一個標示指令的屬性或指令之間的關係的函數，輸出一樣是 0 或 1，常見的 predicates 有 read, write, fence，分別代表 x 是讀取、寫入或同步指令，還有 data depend, control depend, same address，分別代表 x 和 y 有 data dependency、control dependency 和是否存取相同位址

如此我們可以描述不同的 memory model 上指令之間能否被重排

10 of 19

任務一：修訂並行程式設計 — 執行順序

The Math of Memory Ordering – Must-not-reorder Funct.

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

9

x86 total store order (TSO)

ARM relaxed memory model (RMO)

11 of 19

任務一：修訂並行程式設計 — 執行順序

The Math of Memory Ordering – Read-from Map Relation

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

10

12 of 19

任務一：修訂並行程式設計 — 執行順序

The Math of Memory Ordering – Happens-before

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

11

13 of 19

任務一：修訂並行程式設計 — 執行順序

The Math of Memory Ordering – Happens-before

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

12

14 of 19

任務一：修訂並行程式設計 — 執行順序

The Math of Memory Ordering – Memory Models

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

13

綜合以上所說的，我們可以用 must-not-reorder function F，read-from map relation、happens-before relation 來定義 memory model 所允許的 instruction reordering

其中 x86 所有的 writes 都遵循著 total order，且一旦被寫入 shared memory，就能夠立刻被所有 threads 所看見，memory model 本身就自帶有 acquire 和 release 的限制

ARM 也是所有的 writes 都遵循著 total order，但因為有 local memory，所以不一定能馬上被其他 threads 所看見，不過一旦能夠被其中一個自己以外的 thread 看見，那所有 threads 都可以同時看見該寫入操作，因此需要有 acquire 和 release 的同步工具來確保讀寫操作的可見性

但很不幸地，雖然我們歷經千辛萬苦定義出了 memory consistency model 的嚴謹定義，並實際舉 x86 和 ARM 作為範例，但我們還是沒辦法寫一支程式，然後確定它能有正確的結果。也就是我們還是需要有一個機制，讓我們即使在 x86 或 ARM 的處理器上也能夠產生出和 sequential consistency 一樣的結果

15 of 19

任務一：修訂並行程式設計 — 執行順序

Sarita Adve and Mark Hill proposed “weak ordering” in 1990

If no data race in software, then weakly ordered hardware appears sequential consistency, even thought the hardware has weak memory consistency model.

Hardware: provide synchronization mechanisms for software to prevent data races.
Software: no write of a thread happens when there are other threads reading/writing (data-race-free).

e.g. Dekker’s algorithm, Peterson’s algorithm, Pthread, Atomic instructions

Data-Race-Free Sequential Consistency (DRF-SC)

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

14

Program may have data race

Program without data race

不過還好，早在 1990 年就有兩位大神，提出了 weak ordering 的定義，並幫我們證明了，只要在 weak ordering 的硬體上跑程式沒有 data race，就一定會表現得像是 sequential consistency memory model 一樣，而這項保證被稱為 data-race-free sequential consistency 簡稱 DRF-SC

DRF-SC 要求硬體要提供同步的機制來讓軟體避免 data race，而軟體要避免 data race 就是在避免一個執行緒的 write 操作不會和其他執行緒的 read 或 write 同時發生

如此一來，問題就從原本很困難的「如何在 weak memory model 寫出滿足 sequential consistency 的程式」變成「如何確保程式執行沒有 data race」，在上個世紀我們有 Dekker's algorithm 和 Peterson's algorithm，到了 21 世紀，我們有了 Pthread library 提供的同步機制還有 atomic instructions

16 of 19

任務一：修訂並行程式設計 — 執行順序

Strong synchronization (sequentially consistent)

memory_order_seq_cst：沒有指令重排，確保 sequential consistency

Weak synchronization (acquire/release, coherence-only)

memory_order_acquire：用於讀取操作，後面的存取不能重排到此同步之前
memory_order_release：用於寫入操作，前面的存取不能重排到此同步之後
memory_order_acq_rel：用於 RMW 操作，同時有 acquire + release 語意

No synchronization (relaxed, hiding races)

memory_order_relaxed：只保證操作的 atomicity

C11/C++11 Memory Consistency Models

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

15

17 of 19

任務二：將執行順序納入《Concurrency Primer》

Preparation for Contribution to Concurrency Primer

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

16

18 of 19

任務二：將執行順序納入《Concurrency Primer》

Detailed describe the sequential consistent, x86-TSO, and ARM memory models.
Litmus tests to differentiate between different memory models

Pull Requests and Code Review

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

17

19 of 19

Thanks for listening

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

18