並行程式設計練習題 (Practice - Concurrent Programming)

Processes:kernel 自動排程,各自擁有私有的 virtual address space(共享須顯式 IPC)。I/O multiplexing:應用程式自行顯式排程,所有邏輯流在單一行程內共享整個位址空間。Threads:kernel 自動排程,且在單一行程內共享位址空間。
Threads 是混合體:「像 process」的地方是 kernel 自動排程、有整數 TID;「像 I/O multiplexing」的地方是共享單一 process 的完整位址空間。

私有(thread context):TID、stack、stack pointer、PC、通用暫存器、condition codes。
共享:整個 process 的 virtual address space——code(text)、data、heap、shared libraries,以及 open files。
注意:registers 永不共享,virtual memory 永遠共享;thread stack 只是「通常」私有,並無硬體保護。

四種方式:(1) top-level thread routine return(隱式);(2) 呼叫 pthread_exit(顯式);(3) 某 peer 呼叫 Linux exit——終止整個 process 及所有 threads;(4) 其他 peer 呼叫 pthread_cancel(tid)。
main thread 呼叫 pthread_exit 會先等待所有其他 peer threads 終止,才終止 main thread 與整個 process;呼叫 exit 則立即終止所有 threads。

(a) 對描述子 k 讀取 1 byte 的請求不會阻塞,即為 ready for reading。
(b) select 有副作用:它會就地修改 fdset,把 read set 改寫成 ready set(read set 中已 ready 的子集),回傳值即 ready set 的 cardinality。若不每輪還原,read set 會逐漸只剩上一輪 ready 的描述子——這是經典 bug。

定義:變數 v 是 shared ⟺ v 的某一個 instance 被多於一個 thread 參考。
Global 與 local static:恰好 1 份 instance,位於 read/write data 區;local automatic:每個 thread 的 stack 各 1 份。
注意:local automatic 也可能是 shared——例如透過 global 指標間接參考他人 stack 上的陣列(sharing.c 的 msgs)。

P(s):若 s 非零,不可分割地遞減 s 後返回;若 s 為零,掛起該 thread,直到 s 變非零且被某個 V 重啟,重啟後完成遞減再返回。
V(s):不可分割地把 s 加 1;若有 threads 阻塞在 P,恰好重啟其中一個,但重啟順序未定義、不可預測。
Semaphore invariant:執行中的程式永遠不會使正確初始化的 semaphore 變成負值。

First:除非 writer 已獲准使用物件,reader 不等待;reader 不因「有 writer 在等」而等。Second:writer 就緒後盡快寫,晚於 writer 到達的 reader 必須等,即使該 writer 也在等待。
Starvation:某 thread 無限期阻塞。例如 first 解中 readers 連續到達可讓 writer 無限期等待;且因 V(w) 重啟哪個等待者不可預測,一串 writers 也可能餓死 reader。

Class 1:不保護共享變數(如遞增未保護的全域 counter)→ 用 P/V 保護。Class 2:跨呼叫保留 static state(如 rand、strtok)→ 唯一解法是改寫成 reentrant(caller 以參數傳入 state),lock-and-copy 無效。Class 3:回傳指向 static variable 的指標(如 ctime、gethostbyname)→ lock-and-copy 或 _r 版本。Class 4:呼叫 thread-unsafe function 的函式——若被呼叫者是 Class 2 則 f 也 unsafe;若是 Class 1/3,以 mutex 保護 call site 即可 safe。

Reentrant function:被多條 threads 呼叫時不引用任何 shared data 的函式;reentrant 是 thread-safe 的 proper subset,且因不需同步操作通常更快。
Explicitly reentrant:所有參數 pass by value 且只存取區域自動變數——僅看程式碼即可判定。Implicitly reentrant:允許部分參數傳指標(如 rand_r),僅當 caller 傳入非共享資料的指標時才 reentrant——是 caller 與 callee 共同的屬性。

accept 回傳:0→1;fork(描述子表複製、指向同一 file table entry):1→2;parent Close(connfd):2→1;child 端關閉(或 child exit 時 kernel 自動關閉):1→0,連線才真正終止。
parent 不 close:長駐的 parent 永不終止,該 entry refcount 永不歸零、永不釋放 → memory leak,最終耗盡記憶體使系統 crash。child 那行 close 可省,因為行程終止時 kernel 會自動關閉所有 open descriptors。

$S_4=T_1/T_4=16/8=2$,$E_4=S_4/4=50\mathrm{\%}$;$S_8=16/4=4$,$E_8=4/8=50\mathrm{\%}$。
Absolute speedup($T_1$ 取循序版)較真實:relative speedup 的 $T_1$ 取平行版跑單核,而平行版即使單核也有同步開銷,分子被灌大,數字會人為膨脹;但 relative 量測較容易(absolute 需要另一份循序程式)。

(a) mutex 初始 1(binary semaphore,保護 buf 等共享狀態的互斥);slots 初始 n(counting,計數空 slot);items 初始 0(counting,計數可用 item)。insert:P(slots)→P(mutex)→放入→V(mutex)→V(items);remove 對稱。
(b) 不必要。n = 1 時 slots(初值 1)/items 已保證任一時刻只有一方能進入 buffer(強制交替存取),即使 p>1、c>1 亦然。事實上 PP 12.9 的三種情境(含 p=1/c=1/n>1)皆不需要 mutex——單一 producer 只改 rear、單一 consumer 只改 front,寫入的空 slot 與讀取的滿 slot 必為不同索引;決定因素是「單生產者/單消費者」或 n=1 的序列化,而非 n 值本身。

$L_1$: %rdx1=0;$L_2$: %rdx2=0;$U_2$: %rdx2=1;$S_2$: cnt=1;$U_1$: %rdx1=1;$S_1$: cnt=1。最終 cnt = 1,錯誤(應為 2)——thread 2 的更新被覆蓋,即 lost update。
一般準則:只看 L、U、S 三段,若某 thread 的 L 落在另一 thread 的 L 與 S 之間,結果必錯;兩個 critical sections 完全不交錯才正確。而 OS 選哪種排程順序不可預測,故必須以同步(如 mutex)強制互斥。

兩 threads 以不同順序取得兩個 mutexes,使 s 與 t 的 forbidden regions(s<0 或 t<0 的狀態)在 progress graph 上重疊,重疊處誘發 deadlock region:軌跡一旦進入(Thread 1 拿到 s、Thread 2 拿到 t 的狀態),向右與向上都被 forbidden region 擋住——各自等待對方永遠不會執行的 V,進得去出不來。
不一定死結:有些幸運軌跡繞過 deadlock region(某 thread 一口氣拿到兩把鎖),故 bug 不可預測、難重現。
修正:mutex lock ordering rule——給所有 mutexes 一個 total ordering,每條 thread 依序取得、反序釋放(如兩邊都改成先 P(s) 再 P(t)),兩個 forbidden regions 便不再重疊,程式 deadlock-free。