PV 原語實現進程互斥與同步：從理論到經典案例全解析

PV 原語基礎

Dijkstra 提出。信號量 S：整數變量，僅通過兩種原子操作訪問：

• P(S) (wait/proberen)：S--; if (S < 0) block(); —— 申請資源/進入臨界區
• V(S) (signal/verhogen)：S++; if (S <= 0) wakeup(); —— 釋放資源/喚醒等待者

關鍵性質：P/V 原子不可分割；成對使用；S ≥ 0 表可用資源數，S < 0 表等待進程數 (|S|)。

互斥模式：公有信號量

所有進程共享同一信號量 mutex，初值 = 可用資源實體數 (通常為 1)。

P(mutex);
critical_section();
V(mutex);

案例 1：單資源互斥 (黑白棋子分揀)

一箱子混合黑白子，進程 A 揀黑，B 揀白，同一時刻只能一個進程進箱子。
mutex = 1。雙進程 P(mutex) -> 揀子 -> V(mutex) 循環。

案例 2：多實體資源互斥 (售票廳 20 座位)

售票廳最多容納 20 人。mutex = 20。進程 P(mutex) -> 進入購票 -> 離開 -> V(mutex)。
本質：信號量計數器直接建模「可用槽位數」。

同步模式：私有信號量

進程間協作順序，信號量初值通常為 0 或 1，不代表資源數，代表「條件是否滿足」。

案例 3：嚴格輪替 (黑白子必須輪流揀)

在案例 1 基礎上增加：A 揀完必讓 B 揀，B 揀完必讓 A 揀。
兩私有信號量：s1=1 (A 可揀), s2=0 (B 待揀)。
A: P(s1) -> 揀黑 -> V(s2)；B: P(s2) -> 揀白 -> V(s1)。
關鍵：V 在 P 之後，釋放對方的等待條件。

案例 4：司機-售票員協作 (P 不必在 V 前)

流程：售票員上客→關門→V(run)→司機啟動→行駛→停車→V(stop)→售票員開門→下客→循環。
run=0, stop=0。
司機: P(run) -> 駕駛 -> V(stop)
售票員: 上客關門 -> V(run) -> 售票 -> P(stop) -> 開門下客
啟示：V 可先於 P 執行 (信號量變 1)，後續 P 直接通過，實現「預發信號」。

綜合經典：生產者-消費者 (有界緩衝區)

緩衝區大小 N。三信號量：
empty = N (空槽位)，full = 0 (數據項)，mutex = 1 (緩衝區互斥)。
生產者: P(empty) -> P(mutex) -> 放入 -> V(mutex) -> V(full)
消費者: P(full) -> P(mutex) -> 取出 -> V(mutex) -> V(empty)
順序鐵律：先申請資源信號量，再申請互斥信號量，否則死鎖。

PV 操作設計步驟總結

1. 分析進程關係：互斥(共享資源) / 同步(協作順序) / 混合。
2. 確定信號量類型與初值：公有(資源數) / 私有(條件初態 0/1)。
3. 編寫 P/V 位置：互斥區前後 P/V 同一信號量；同步前驅 V、後繼 P 不同信號量。
4. 檢查死鎖/活鎖：循環等待、信號量順序、資源釋放完整性。

結語

PV 原語是並發編程的「組合邏輯門」。掌握公有信號量建模資源互斥、私有信號量建模同步條件、生產者-消費者三信號量模式三大核心範式，即可應對絕大多數教科書級與工程級同步問題。