作業系統›Ch6 行程同步（Process Synchronization）第 2 題／共 32 題
2. Synchronization、Mutual Exclusion、Bounded Waiting
#OS-06-002中SynchronizationMutual ExclusionBounded Waiting
關於同步（synchronization）， 與 是兩個共享 critical section 的 processes，假設：
- "load" 與 "store" 機器語言指令是 atomic 的。
- 這兩個 processes 共享一個變數 "turn" 來表示輪到誰。
給定下列兩種做法：
Approach 1（Process ）：
while (true) {
turn = i;
while (turn == j)
;
/* critical section */
turn = j;
/* remainder section */
}
（註： 交換 i 與 j）
Approach 2（Process ）：
while (true) {
while (turn == j)
;
/* critical section */
turn = j;
/* remainder section */
}
（註： 交換 i 與 j）
請選出正確的敘述。
參考答案與解析
答案 (C)(E)。
Approach 1： 先把 turn 設成 i，再在 turn == j 時等待。兩個行程都把 turn 設成自己，只要對方沒有在自己設定之後、檢查之前改掉 turn，檢查就會通過：
- 執行
turn = i，檢查 turn == j 不成立，進入 critical section。 - 執行
turn = j，檢查 turn == i 不成立，也進入 critical section。
兩者同時在 critical section 裡，mutual exclusion 不成立，(A) 錯。 等待時， 離開會設 turn = i，但下一輪一開始又把 turn 設回 j；只要 每次都沒在這段空檔被排到，就會一直等下去， 進入的次數沒有上限，bounded waiting 不成立，(B) 錯。
Approach 2 是嚴格輪流（strict alternation）：
- (C) 對：turn 同一時間只會是 i 或 j，只有 turn 指向的那個行程能離開等待迴圈。
- (E) 對： 離開 critical section 時設 turn = i，在 進去之前 不可能再進去， 最多等對方一次。
- (D) 錯：若 turn = j 而 停在 remainder section、不想進入， 即使想進入也只能一直等，critical section 空著卻沒人能進，不滿足 progress。
📄 台大115
▤完整推導請見《WH 資工筆記 · 作業系統》Ch6 行程同步（Process Synchronization）