平行化與執行緒安全 (Parallelism & Thread Safety)

Overview Table

12.6 用執行緒實現平行化 (p.1049)

現代機器多為 multi-core processor,kernel 會把 concurrent threads 排程到多個核心「平行」執行,而非在單核上循序切換。三種程式集合的關係:

• sequential program:單一 logical flow。
• concurrent program:多個 concurrent flows(與 sequential 互斥、共同構成所有程式)。
• parallel program:跑在多個 processors 上的 concurrent program → parallel programs 是 concurrent programs 的 proper subset。

+--------------------------------------------------+
|                All programs                      |
|  +----------------------------+  +------------+  |
|  |    Concurrent programs     |  | Sequential |  |
|  |  +----------------------+  |  |  programs  |  |
|  |  |  Parallel programs   |  |  +------------+  |
|  |  +----------------------+  |                  |
|  +----------------------------+                  |
+--------------------------------------------------+

平行加總範例:三個版本的演進 (p.1050-1053)

問題:用 $t$ 條執行緒平行計算 $0+1+\cdots +(n-1)$(有閉式解 $n(n-1)/2$ 可驗證結果)。作法:把序列切成 $t$ 個不相交區域,每條執行緒負責 $n/t$ 個元素;main thread 傳給每條 peer thread 一個小整數 thread ID(myid[i] = i 再傳 &myid[i]),thread 用 ID 算出自己的區間 start = myid * nelems_per_thread、end = start + nelems_per_thread。這種「傳唯一 thread ID」是平行程式的通用技巧。

四核心、$n=2^{31}$ 的實測執行時間(秒):

平行程式效能的量測 (p.1054-1056)

psum-local 的執行時間隨 thread 數下降,到 4 threads(= 核心數)後持平甚至微升——因為同一核心上多 threads 的 context switch 開銷。因此平行程式常寫成每核恰好一條 thread。

threads:   1      2      4      8     16
time(s): 1.06   0.54   0.28   0.29   0.30
          |      |      |      |      |
          ██████ ███    █▌     █▌     █▌   ← 4 核用滿後不再下降
                 ↑ 理想:threads 加倍、時間減半(直到 t > 4)

• Speedup(加速比):$S_p={\displaystyle \frac{T_1}{T_p}}$,$p$ 為核心數,$T_k$ 為 $k$ 核上的執行時間。此式稱為 strong scaling(問題大小固定)。
  • $T_1$ 取「循序版程式」→ absolute speedup:較能真實反映平行化的效益。
  • $T_1$ 取「平行版跑在單核」→ relative speedup:平行版即使單核也有同步開銷,會灌大分子、人為膨脹加速數字;但量測容易(absolute 需要兩份程式,複雜程式可能無循序版可用)。
• Efficiency(效率):$E_p={\displaystyle \frac{S_p}{p}}={\displaystyle \frac{T_1}{p{T}_p}}$,以百分比表示,範圍 $(0,100]$;衡量平行化的 overhead——高效率代表花在有用計算的時間多、花在同步與通訊的時間少。
• 範例程式效率 88-100%(見下表)很漂亮,但那是因為問題「trivially easy to parallelize」;實務上通常沒這麼好。

• Weak scaling:核心數增加時同步放大問題規模,使每核工作量固定;speedup/efficiency 改以「單位時間完成的總工作量」表示——核心加倍且每小時做兩倍的工作 = linear speedup、100% efficiency。

12.7.1 Thread Safety(執行緒安全)(p.1056-1058)

函式是 thread-safe ⟺ 被多條 concurrent threads 重複呼叫時永遠產生正確結果;否則為 thread-unsafe。四類(非互斥,一個函式可同時屬多類)thread-unsafe functions:

• Class 3 的災難情境:多 thread 同時呼叫 ctime,一條 thread 正在使用的結果被另一條默默覆寫。
• Lock-and-copy:為 thread-unsafe function 配一個 mutex;在 call site「上鎖 → 呼叫 → 把結果複製到私有記憶體 → 解鎖」。實務上包成 thread-safe wrapper(如 ctime_ts(timep, privatep):P(&mutex); sharedp = ctime(timep); strcpy(privatep, sharedp); V(&mutex); return privatep;),再把所有呼叫改成呼叫 wrapper,對 caller 改動最小。
• Class 4 判定:f 呼叫 thread-unsafe 的 g,f 是否 unsafe?It depends——
  • g 是 Class 2 → f 也 thread-unsafe,除了改寫 g 別無他法。
  • g 是 Class 1 或 3 → 用 mutex 保護 call site 與所有相關 shared data,f 仍可 thread-safe(lock-and-copy 即為此例)。

12.7.2 Reentrancy(可重入性)(p.1059-1060)

Reentrant function:被多條 threads 呼叫時不引用任何 shared data 的函式。thread-safe 與 reentrant 常被(錯誤地)當同義詞,實際上有明確技術區別:

+---------------------------------------------+
|               All functions                 |
|  +------------------------+  +-----------+  |
|  |  Thread-safe functions |  |  Thread-  |  |
|  |  +------------------+  |  |  unsafe   |  |
|  |  |    Reentrant     |  |  | functions |  |
|  |  |    functions     |  |  +-----------+  |
|  |  +------------------+  |                 |
|  +------------------------+                 |
+---------------------------------------------+
   reentrant ⊂ thread-safe;thread-safe 與 thread-unsafe 互斥

• Reentrant functions 通常比 non-reentrant 的 thread-safe functions 更有效率:不需要任何同步操作。
• 把 Class 2 函式變 thread-safe 的唯一方法就是改寫成 reentrant。例:rand_r(unsigned int *nextp) 把 static 的 seed 換成 caller 傳入的指標:*nextp = *nextp * 1103515245 + 12345; return (unsigned)(*nextp / 65536) % 32768;。

12.7.3 在多執行緒程式中使用既有函式庫 (p.1060-1061)

大多數 Linux/標準 C 函式庫函式(malloc、free、realloc、printf、scanf⋯)都是 thread-safe,只有少數例外:

• 除 rand、strtok(Class 2)外皆為 Class 3(回傳 static 指標)。strtok 已 deprecated;gethostbyaddr / gethostbyname / inet_ntoa 是過時的網路函式,已被 reentrant 的 getaddrinfo / getnameinfo / inet_ntop 取代(見 11-Network-Programming/03-Sockets-Interface)。
• 對 caller 最不擾動的作法是 lock-and-copy,但缺點:(1) 額外同步變慢;(2) 回傳「結構中還有結構」的指標時需 deep copy 整個階層;(3) 對 Class 2(如 rand)完全無效——它依賴跨呼叫的 static state。
• 因此 Linux 提供多數 thread-unsafe 函式的 reentrant 版本,名稱一律以 _r 結尾;建議能用就用。

12.7.4 Races(競爭)(p.1061-1063)

Race:程式的正確性依賴「thread A 先到達控制流中的 x 點、thread B 才到達 y 點」。成因通常是程式設計者假設 threads 會走某條特定的執行軌跡,忘了黃金法則:threaded 程式必須對任何可行的 trajectory 都正確(progress graph 觀點見 12-Concurrent-Programming/03-Shared-Variables-and-Semaphores)。

經典 bug(race.c):main thread 以 Pthread_create(&tid[i], NULL, thread, &i) 把區域堆疊變數 i 的指標傳給 peer thread;peer thread 執行 myid = *((int *)vargp)。

main thread                      peer thread i
-----------                      -------------
for i = 0..N-1:
  Pthread_create(..., &i) ──┐
  i++  ←─── RACE! ───────────┼──→ myid = *vargp   (解參考 &i)
                             │
  若 i++ 先發生 → peer 讀到別條 thread 的 ID(輸出重複/跳號)
  若解參考先發生 → 恰好正確 —— 取決於 kernel 排程,不可預期

• 實測輸出可能出現 Hello from thread 3 兩次而 0 消失——且換一台機器可能就正常,讓 bug 潛伏。
• 修法(norace.c):每次迴圈 ptr = Malloc(sizeof(int)); *ptr = i; 再傳 ptr——為每個 ID 動態配置獨立區塊;peer thread 讀完後必須 Free(vargp) 避免 memory leak。
• 為何不能由 main thread 在 Pthread_create 後立刻 free?因為 peer thread 可能尚未解參考該區塊,free 後再讀是 use-after-free race(Practice Problem 12.13;memory bug 分類見 09-Virtual-Memory/06-Garbage-Collection-and-Memory-Bugs)。
• 不用 malloc/free 的替代方案(Practice Problem 12.14):如同 12.6 的 psum 程式,用全域陣列 myid[i] = i 再傳 &myid[i],每條 thread 有專屬元素;優點是不需動態配置,缺點是需事先知道 thread 數上限且陣列生命週期必須涵蓋所有 threads。

12.7.5 Deadlocks(死結)(p.1063-1066)

Deadlock:一群 threads 全部 blocked,等待一個永遠不會為真的條件。Semaphore 的引入帶來這種 run-time error 的可能。Progress graph 是理解 deadlock 的利器:

Thread 2
  ^
V(s)|                                . . . ←不死結的軌跡
V(t)|        +----------------+
    |        |  Forbidden     |
    |        |  region for s  |
P(s)|   +----|---+============|      d = deadlock state
    |   |    | d |  Forbidden |      ▓ = deadlock region:
P(t)|   | ▓▓▓+---+  region for t         進得去、出不來
    |   | ▓▓▓|                |
    +---+----+----------------+--→ Thread 1
  s=1     P(s)  P(t)  V(s)  V(t)
  t=1    (兩 thread 以「不同順序」P 兩個 mutex 時,
          兩個 forbidden regions 重疊 → 產生 deadlock region)

由 progress graph 可得三個洞見:

• P/V 順序排錯使兩個 semaphores 的 forbidden regions 重疊;軌跡一旦到達 deadlock state $d$,每個合法方向都被擋住,無法再前進——每條 thread 都在等對方做一個永遠不會發生的 V。
• 重疊區誘發 deadlock region:軌跡碰到其中任何狀態,死結不可避免;軌跡進得了 deadlock region 卻永遠出不來。
• Deadlock 不總是可預測:有些幸運軌跡繞過 deadlock region,有些被困住。同一程式跑一千次沒事,第一千零一次死結;在這台機器正常、換一台就死結;且不易重現(每次執行軌跡不同)。

12.8 Summary (p.1066)

• 三種建構 concurrent programs 的機制比較(本章總結):

• 無論用哪種機制,同步共享資料的存取都是難題;semaphore 的 P/V 可提供 mutual exclusion,也可排程資源存取(producer-consumer 的 bounded buffer、readers-writers 的共享物件)。
• Thread 呼叫的函式必須 thread-safe;四類 thread-unsafe functions 各有對策。Reentrant functions 是 thread-safe functions 的 proper subset,因不碰 shared data、無需同步原語而通常更快。
• Races:程式設計者對 logical flows 的排程做了錯誤假設。Deadlocks:flow 等待永遠不會發生的事件。

Exam/Test Patterns

Related Notes

• 12-Concurrent-Programming/01-Process-and-Event-Based-Concurrency
• 12-Concurrent-Programming/02-Threads
• 12-Concurrent-Programming/03-Shared-Variables-and-Semaphores
• 12-Concurrent-Programming/Practice-Concurrent-Programming
• 01-Computer-Systems-Tour/04-Amdahls-Law-and-Concurrency-Themes
• 05-Program-Optimization/04-Limiting-Factors-and-Memory-Performance
• 09-Virtual-Memory/06-Garbage-Collection-and-Memory-Bugs
• 11-Network-Programming/03-Sockets-Interface