共享變數與號誌 (Shared Variables & Semaphores)

#csapp #concurrency #semaphores #race-condition #threads #concept

Overview Table

主題	核心概念	關鍵結論	書頁
Threads 記憶體模型	各 thread 有獨立 context(registers、stack),共享其餘 process context	Registers 永不共享;virtual memory 永遠共享;stack「通常」私有但無保護	p.1029-1030
變數映射	依 storage class 決定 run-time instance 數量	global / local static 恰好 1 份;local automatic 每 thread 一份	p.1030-1031
共享變數定義	變數 v 的某個 instance 被多於一個 thread 參考 ⟺ v 是 shared	local automatic(如 `msgs`)也可能被共享	p.1031
badcnt.c	未同步的 `cnt++` 被編譯為 Load–Update–Store 三指令	不同 interleaving 產生不同結果 → race	p.1031-1034
Progress graph	n 個 thread 的執行 = n 維空間中的 trajectory	觸碰 unsafe region 的 trajectory 結果錯誤	p.1035-1037
Semaphore	非負整數 + 不可分割的 P/V 操作(Dijkstra)	semaphore invariant:正確初始化的 s 永不為負	p.1037-1038
Mutex(互斥)	二元號誌初始 1,critical section 用 P/V 包夾	P/V 造出 forbidden region(s<0)包住 unsafe region	p.1038-1040
排程共享資源	counting semaphore 通知「條件已成立」	Producer–Consumer(Sbuf)、Readers–Writers	p.1040-1045
Prethreading	Master thread 生產 connfd,worker pool 消費	免除 per-client 建 thread 的成本;`pthread_once` 做一次性初始化	p.1044-1049

12.3 尾聲:傳遞 connfd 給 peer thread 的競爭 (p.1028)

Thread-based server 把 accept() 回傳的 connected descriptor 傳給 peer thread 時,若直接傳 &connfd 指標,peer thread 的解參考(*((int *)vargp))與 main thread 的下一次 accept 之間存在 race:

解參考先於下一次 accept 完成 → 拿到正確 descriptor。
解參考晚於下一次 accept → 兩個 threads 對同一個 descriptor 做 I/O。
正解:每個 connfd 用 Malloc 動態配置獨立記憶體區塊再傳指標;peer thread 讀取後 Free。
因為不 join,peer thread 必須 Pthread_detach 自己,終止時資源才會自動回收(否則 memory leak,對照 Practice Problem 12.5:刪 detach 或 free 都會漏)。

12.4 Shared Variables in Threaded Programs (p.1028-1031)

判斷 C 程式中的變數是否共享,要依序回答三個問題:(1) threads 的記憶體模型為何?(2) 變數的 instance 如何映射到記憶體?(3) 每個 instance 被幾個 threads 參考?

12.4.1 Threads Memory Model (p.1029-1030)

一組 concurrent threads 在同一個 process context 中執行:

        Process virtual address space(全部 threads 共享)
+--------------------------------------------------------------+
|  read-only text (code)  |  read/write data  |  heap           |
|  shared library code/data                                     |
|--------------------------------------------------------------|
|  Stack area                                                   |
|   +-------------+  +-------------+  +-------------+           |
|   | main stack  |  | peer0 stack |  | peer1 stack |  <- 「通常」|
|   | (tid.m ...) |  | (myid.p0)   |  | (myid.p1)   |    各自存取 |
|   +-------------+  +-------------+  +-------------+           |
+--------------------------------------------------------------+
  每 thread 私有(thread context):thread ID、stack、stack pointer、
  PC、condition codes、general-purpose registers

Registers 永不共享:一個 thread 在操作上不可能讀寫另一 thread 的暫存器值。
Virtual memory 永遠共享:任一 thread 修改某記憶體位置,其他 thread 讀取時終將(eventually)看到改變。
各 thread 也共享同一組 open files。

「stack 私有」只是慣例,不是保護

各 thread stack 都位於同一個 stack area,彼此之間沒有硬體保護。只要某 thread 取得指向他人 stack 的指標(例如 sharing.c 中 global ptr 指向 main thread stack 上的 msgs 陣列),就能任意讀寫該 stack。「usually」≠「always」。

12.4.2 Mapping Variables to Memory (p.1030-1031)

以書中 sharing.c 為例(main thread 建立 2 個 peer threads;global char **ptr 指向 main stack 上的 msgs[];thread routine 內有 static int cnt):

Storage class	定義	Run-time instances	所在區域	例子(標記法)
Global variable	函式外宣告	恰好 1 份,任何 thread 皆可參考	read/write data 區	`ptr`
Local automatic	函式內、無 `static`	每個 thread 的 stack 各一份(即使執行同一 routine)	各 thread stack	`tid.m`、`myid.p0`、`myid.p1`
Local static	函式內、有 `static`	恰好 1 份(與 global 相同)	read/write data 區	`cnt`(兩個 peer 共用同一份)

標記法:v.t 表示變數 v 位於 thread t stack 上的 instance,t ∈ {m, p0, p1}。

12.4.3 Shared Variables (p.1031)

共享的定義

變數 v 是 shared ⟺ v 的某一個 instance 被多於一個 thread 參考。

cnt:只有 1 個 instance,被 peer0、peer1 都參考 → shared。
myid:2 個 instances(myid.p0、myid.p1)各只被一個 thread 參考 → 不 shared。
msgs.m:雖是 local automatic,但透過 ptr 被 main 與兩個 peers 間接參考 → shared(Practice Problem 12.6:shared 的是 ptr、cnt、msgs;i、myid 不是)。

12.5 Synchronizing Threads with Semaphores (p.1031-1049)

badcnt.c:同步錯誤的典型 (p.1031-1034)

兩個 threads 各對 global volatile long cnt 執行 cnt++ 共 niters 次,預期 cnt = 2 × niters;實際上每次執行結果不同且都錯(如 BOOM! cnt=1445085)。原因:cnt++ 在組合語言層被拆為多條指令,thread i 的迴圈可分成五段:

記號	意義	操作對象
$H_{i}$	迴圈開頭指令區塊 (Head)	只碰 local stack 變數
$L_{i}$	Load:`cnt` 載入 %rdx $_{i}$	shared cnt
$U_{i}$	Update:%rdx $_{i}$ 加 1	shared cnt
$S_{i}$	Store:%rdx $_{i}$ 寫回 `cnt`	shared cnt
$T_{i}$	迴圈尾端指令區塊 (Tail)	只碰 local stack 變數

在 uniprocessor 上,兩 threads 的指令依某種**全序(total ordering / interleaving)**逐一完成;有些順序正確、有些錯誤。
錯誤情境(Fig 12.18b):thread 2 在 thread 1 的 $L_{1}$ 之後、 $S_{1}$ 之前執行 $L_{2}$ → 兩者都載入 0、都寫回 1,一次遞增遺失(lost update)。
你無法預測 OS 會選擇哪種順序;Practice Problem 12.7 的順序 $L_{1}$ 後插入 $L_{2} U_{2} S_{2}$ 同樣得到 cnt=1(錯誤)。

判斷 interleaving 正確與否的口訣

只看 $L, U, S$ 三段:若某 thread 的 $L$ 落在另一 thread 的 $L$ 與 $S$ 之間,結果必錯;兩個 critical sections 完全不交錯才正確。

12.5.1 Progress Graphs (p.1035-1037)

Progress graph 把 n 個 threads 的執行建模為 n 維笛卡兒空間中的 trajectory;軸 k 是 thread k 的進度,點 $(I_{1}, I_{2}, \dots, I_{n})$ 表示 thread k 已完成指令 $I_{k}$ ,原點為初始狀態。

合法轉移:向右(thread 1 完成一指令)或向上(thread 2 完成一指令);不允許對角線(兩指令不能同時完成)、不允許向左/向下(程式不倒退)。
Thread i 操作共享變數 cnt 的指令 $(L_{i}, U_{i}, S_{i})$ 構成(對 cnt 而言的)critical section,不得與另一 thread 的 critical section 交錯 —— 即 mutual exclusion(互斥)。
兩 critical sections 的交集在狀態空間中定義 unsafe region;unsafe region 緊鄰但不包含其周邊狀態(如 $(H_{1}, H_{2})$ 、 $(S_{1}, U_{2})$ 不屬於它)。
Safe trajectory:繞過 unsafe region → 必得正確結果;unsafe trajectory:觸碰 unsafe region 任一部分 → 錯誤。

 Thread 2
   T2 |  .   .   .   .   .      safe trajectory: 沿 unsafe region
   S2 |  .  [#===#===#]  .      左側與上方繞過
   U2 |  .  [# unsafe #]  .     unsafe trajectory: 穿越 [#...#]
   L2 |  .  [#===#===#]  .
   H2 |  .   .   .   .   .
      +------------------------ Thread 1
         H1  L1  U1  S1  T1
      [#..#] = L,U,S 兩軸 critical sections 的交集

Progress graph 的限制(multiprocessor)

Progress graph 只適合視覺化 uniprocessor 上的並行執行。Multiprocessor(多組 CPU/cache 共享主記憶體)的記憶體系統可能處於不對應任何 trajectory 的狀態。但結論不變:不論單核或多核,對共享變數的存取一律要同步 (p.1040)。

12.5.2 Semaphores (p.1037-1038)

Dijkstra 提出的 semaphore s:具非負整數值的全域變數,只能透過兩個特殊操作存取:

P(s)(荷語 proberen,test):若 s 非零,遞減 s 後立即返回;若 s 為零,掛起(suspend)該 thread 直到 s 變為非零且被某個 V 重啟,重啟後完成遞減再返回。
V(s)(荷語 verhogen,increment):s 加 1;若有 threads 阻塞在 P 等待,恰好重啟其中一個,該 thread 完成其 P 的遞減。
P 的 test+decrement、V 的 load+increment+store 都是**不可分割(indivisibly)**執行。
V 不定義重啟順序:多個 threads 等待同一 semaphore 時,無法預測誰被重啟。

Semaphore invariant

P/V 的定義保證:執行中的程式永遠不會使正確初始化的 semaphore 變成負值。這是控制並行程式 trajectory 的核心工具。

Posix 介面與 CS:APP wrappers:

#include <semaphore.h>
int sem_init(sem_t *sem, 0, unsigned int value);  /* 使用前必須初始化;中間引數恆為 0 */
int sem_wait(sem_t *s);   /* P(s) */   /* 皆傳回 0 若 OK,-1 為錯誤 */
int sem_post(sem_t *s);   /* V(s) */

#include "csapp.h"
void P(sem_t *s);   /* sem_wait 的 wrapper */
void V(sem_t *s);   /* sem_post 的 wrapper */

12.5.3 Using Semaphores for Mutual Exclusion (p.1038-1040)

作法:為每個共享變數(或相關集合)配一個初始值為 1 的 semaphore s,critical section 前後包上 P(s) / V(s)。

術語	定義
Binary semaphore	值恆為 0 或 1 的 semaphore
Mutex	用於互斥的 binary semaphore
Lock / Unlock	對 mutex 做 P / 做 V
Holding the mutex	已 lock 尚未 unlock 的狀態
Counting semaphore	作為可用資源計數器的 semaphore

Progress graph 上,每個狀態標上該狀態的 s 值;P/V 的組合造出 forbidden region(s < 0 的狀態集合)。
由 semaphore invariant,可行 trajectory 不可能進入 forbidden region;forbidden region 完全包住 unsafe region → 每條可行 trajectory 都是 safe → 不論 run-time 指令順序,計數必正確。

修正 badcnt.c → goodcnt.c:

volatile long cnt = 0;          /* 計數器 */
sem_t mutex;                    /* 保護 cnt 的 semaphore */
Sem_init(&mutex, 0, 1);         /* main 中初始化 mutex = 1 */

for (i = 0; i < niters; i++) {  /* thread routine */
    P(&mutex);
    cnt++;                      /* critical section */
    V(&mutex);
}
/* 執行結果每次都是 OK cnt=2000000 */

12.5.4 Using Semaphores to Schedule Shared Resources (p.1040-1045)

第二種用途:用 semaphore 通知另一 thread「程式狀態中某條件已成立」,即排程共享資源的存取。兩個經典問題:

Producer–Consumer Problem 與 Sbuf 套件

Producer 與 consumer 共享一個 n 個 slots 的 bounded buffer;producer 產生 item 插入,consumer 移除並消費。除了互斥,還需排程:buffer 滿 → producer 等待空 slot;buffer 空 → consumer 等待 item。實例:多媒體系統(編碼/解碼 frame,buffer 消除 jitter)、GUI 事件佇列。

 Producer ---insert--> [ bounded buffer, n slots ] ---remove--> Consumer

sbuf_t 結構與三個 semaphores:

typedef struct {
    int *buf;      /* buffer 陣列(動態配置) */
    int n;         /* slots 上限 */
    int front;     /* buf[(front+1)%n] 是第一個 item */
    int rear;      /* buf[rear%n] 是最後一個 item */
    sem_t mutex;   /* 互斥保護 buf,初始 1 */
    sem_t slots;   /* counting: 空 slot 數,初始 n */
    sem_t items;   /* counting: 可用 item 數,初始 0 */
} sbuf_t;          /* front == rear ⟺ buffer 空 */

操作	步驟(順序即正確性關鍵)
`sbuf_insert`	`P(&slots)` 等空 slot → `P(&mutex)` 上鎖 → `buf[(++rear)%n]=item` → `V(&mutex)` → `V(&items)` 宣告新 item
`sbuf_remove`	`P(&items)` 等 item → `P(&mutex)` 上鎖 → `item=buf[(++front)%n]` → `V(&mutex)` → `V(&slots)` 宣告新空 slot

mutex 何時可省?(Practice Problem 12.9)

sbuf 的三種情境其實都不需要 mutex:(A) p=1, c=1, n>1——單一 producer 只改 rear、單一 consumer 只改 front,且 producer 寫入的空 slot 與 consumer 讀取的滿 slot 必為不同索引;(B) p=1, c=1, n=1——同理,且 slots/items 強制嚴格交替;(C) p>1, c>1, n=1——slots(初值 1)與 items 已序列化,任一時刻至多一個 producer、一個 consumer 進入 buffer。關鍵在「單生產者/單消費者」或「n=1 的序列化」,而非單純的 n 值。

Readers–Writers Problem

互斥問題的一般化:多 threads 存取共享物件(記憶體資料結構、磁碟資料庫),writer(修改者)須獨占,readers(唯讀者)可與無上限的其他 readers 共享。實例:訂位系統(查詢 vs 訂位)、多執行緒 caching Web proxy。

變體	優先權	規則
First readers-writers problem	偏袒 readers	除非 writer 已獲准使用物件,否則 reader 不等待;reader 不因「writer 在等」而等
Second readers-writers problem	偏袒 writers	writer 就緒後盡快寫;晚於 writer 到達的 reader 必須等,即使 writer 也在等

First problem 的解(favors readers;readcnt 初始 0,mutex、w 初始 1):

void reader(void) {                    void writer(void) {
  while (1) {                            while (1) {
    P(&mutex);                             P(&w);
    readcnt++;                             /* 寫入 critical section */
    if (readcnt == 1) P(&w);  /*首進*/     V(&w);
    V(&mutex);                           }
    /* 讀取 critical section */         }
    P(&mutex);
    readcnt--;
    if (readcnt == 0) V(&w);  /*末出*/
    V(&mutex);
  }
}

w 控制對共享物件 critical section 的存取;mutex 保護共享計數器 readcnt。
Writer 每次進出都 lock/unlock w → 任一時刻至多一個 writer。
只有第一個進入的 reader lock w、最後一個離開的 reader unlock w;中間進出的 readers 無視 w → 只要有一個 reader 持有 w,無上限的 readers 可暢行。

Starvation(飢餓)

兩種 readers-writers 問題的正確解都可能導致 starvation:某 thread 無限期阻塞、無法前進。上述解中,readers 連續到達的流可讓 writer 無限期等待。且此 reader 優先權是「弱」的:writer 離開時可能重啟等待中的 writer 而非 reader(Practice Problem 12.10 —— 一串 writers 也可能餓死 reader,因 V(w) 重啟哪個 thread 不可預測)。

12.5.5 Prethreading:綜合應用的並行伺服器 (p.1044-1049)

Fig 12.14 的 server 為每個 client 建立新 thread,成本不小。Prethreading 用 producer–consumer 模型消除此開銷:

                     +--------- Pool of worker threads ---------+
 Client --\  accept  +--------+  insert   +--------+  remove    | Worker |--service
           >-------->| Master |---------->| Buffer |----------->| thread |
 Client --/          | thread |  connfd   | (sbuf) |   connfd   +--------+
                     +--------+           +--------+            | Worker |--service
                                                                +--------+

Master thread(producer):迴圈 Accept 連線,sbuf_insert(&sbuf, connfd) 放入 bounded buffer。
Worker threads(consumers,啟動時預先建立 NTHREADS 個並 Pthread_detach 自己):迴圈 sbuf_remove 取出 connfd → echo_cnt(connfd) 服務 → Close(connfd)。
echo_cnt 在 global byte_cnt 累計所有 clients 送來的位元組數,byte_cnt += n 與列印以 P(&mutex)/V(&mutex) 保護。

一次性初始化的兩種技巧(package 被 thread routines 呼叫時):

方法	作法	優缺點
顯式 init 函式	main thread 明確呼叫(Sbuf、Rio 的作法)	呼叫端要記得初始化
`pthread_once`	`static pthread_once_t once = PTHREAD_ONCE_INIT;` `Pthread_once(&once, init_fn);` 第一個呼叫的 thread 觸發 init	套件易用;但每次呼叫都執行 pthread_once,多數時候做白工

Prethreaded server 其實是事件驅動程式 (p.1049 Aside)

I/O multiplexing 不是寫 event-driven 程式的唯一方式。此 server 等價於狀態機:main thread 兩個狀態(等連線請求/等空 slot)、兩個 I/O 事件、兩個轉移;每個 worker 一個狀態(等可用 item)、一個事件、一個轉移。參見 12-Concurrent-Programming/01-Process-and-Event-Based-Concurrency。

Exam/Test Patterns

情境 / 關鍵字	答案
「哪些變數是 shared?」給 sharing.c 型程式	逐變數列 instances(global/static 1 份、automatic 每 thread 1 份),再數每個 instance 被幾個 threads 參考;>1 即 shared。注意透過指標間接參考也算
thread routine 內 `static` 變數	只有 1 份 instance,所有 threads 共用 → shared,需要同步
傳 `&connfd` 給 pthread_create	Race:peer 解參考 vs main 下一次 accept;正解 `Malloc` 專屬區塊(peer 用畢 `Free`)+ `Pthread_detach`
`cnt++` 為何會錯	拆成 $L_{i}, U_{i}, S_{i}$ 三步; $L_{2}$ 插入 $L_{1}$ ~ $S_{1}$ 之間 → lost update;OS 排程順序不可預測
給指令 ordering 填表(如 PP 12.7)	逐步追蹤 %rdx1、%rdx2、cnt;檢查兩 critical sections 是否交錯
判斷 trajectory safe/unsafe(如 PP 12.8)	畫/想 progress graph:碰到 unsafe region(兩 critical sections 交集)即 unsafe;貼邊(abut)不算碰到
P(s) 在 s=0	掛起 thread 直到被 V 重啟;重啟後才遞減並返回
V(s) 重啟誰?	恰好一個等待中的 thread,順序未定義、不可預測
semaphore invariant	正確初始化的 semaphore 值永不為負;forbidden region = s<0 的狀態,包住 unsafe region
mutex 初始值	1(binary semaphore);Sbuf 中 `slots` 初始 n、`items` 初始 0
Producer-consumer 何時需要 mutex(PP 12.9)	sbuf 三情境(含 p=1/c=1/n>1 與 p>1/c>1/n=1)皆不需要:單一 producer 只碰 rear、單一 consumer 只碰 front;多方時由 slots/items 序列化
readers-writers 誰優先、會不會餓死	第一型偏 readers、第二型偏 writers;兩型正確解皆可能 starvation
prethreading 的好處	免除 per-connection thread 建立成本;master=producer、workers=consumers,以 Sbuf 傳遞 connfd
套件一次性初始化	`pthread_once` + `PTHREAD_ONCE_INIT`(易用但每次呼叫都付檢查成本)vs 顯式 init