(作業系統) Process and Concurrency - Synchronization Concepts

簡短說明：

• 主題：Synchronization Concepts
• 本章重點：
  • 什麼情況下會發生 Race Condition？
  • 作業系統必須滿足哪些條件，才能正確管理共享資源？
  • 有哪些同步機制（Synchronization Mechanisms）可以保證程式正確性？

---

Background

問題與解決

• The Problem :

  • Concurrent access to shared data may result in data inconsistency
  • Outcome depends on the order of execution(race condition)

• The Solution :

  • Ensure orderly execution
  • Synchronization : 協調資源的分享與存取
  • 保證 Data Integrity 和 Correctness

Consumer and Producer Problem :

• 變數意義 :

  • in：下一個要放入的位置（next free position）
  • out：下一個要取出的項目位置（first available item）
  • buffer 是 circular queue（環狀），所以會用 % BUFFER_SIZE

• Consumer and Producer Problem :

  • Producer 端邏輯
    • while (((in+1) % BUFFER_SIZE) == out) {}
      → 代表 buffer 滿了（下一格就是 out，表示沒有空位）所以一直等
  • Consumer 端邏輯
    • while (in == out) {}
      → 代表 buffer 空（沒有可取的）

• 如果加上 Counter : 直接記錄 buffer 內「目前有幾個 item」

  • 新增變數 : counter = 0：buffer 目前 item 數量
  • Producer（用 counter）
    • while (counter == BUFFER_SIZE) {} → 滿了就等
    • 放入後 counter++
  • Consumer（用 counter）
    • while (counter == 0) {} → 空了就等
    • 取走後 counter--

• 簡化法 : counter ++ 與 counter – 其實是3步驟

  • 把 counter 從記憶體讀到暫存器
  • 暫存器 +1
  • 寫回記憶體

• Problem :

  • 在這 3 步之間，可能發生 context switch 各自讀到舊的值，最後互相覆蓋對方寫回的結果 => Race Condition

Race Condition

• Race Condition 會發生在以下情況 :

  1. Multiple processes access and manipulate shared data concurrently
  2. The final value depends on which process finishes last
  3. Outcome is unpredictable（timing-dependent）

• Prevention : Synchronization（同步）

  • Ensure only one process accesses shared data at a time

• Simple Prevention (只適用於單核心)

  1. Disable Interrupts（關閉中斷）
     • 關閉中斷 → CPU 不會發生 context switch
     • 如果多核心 要全部關 很耗效能
     • 如果關掉之後，他不開啟了就完蛋了
  2. Non-Preemptive Scheduling（非搶占式排程）
     • Process 一旦開始執行，不會被 OS 強制切換

• Both only work on single-processor systems

DeadLock

• 一開始為假設count = 0
• Consumer 進入 CS First
  1. entry-section() → 拿到鎖
  2. while (counter == 0) { }
  3. Producer 想進來 ， entry-section()（鎖被 Consumer 拿走）
  • Result:
    • Consumer：等 Producer 產生資料
    • Producer：等 Consumer 放鎖
  • 互相等待 → Deadlock

原則

• 原則 1
  • 不要在 critical section 裡面「等條件」 → 會 deadlock
• 原則 2
  • critical section 要「越小越好」，只包真正需要保護的共享資料
• 原則3
  • 互斥 ≠ 同步

IPC (Process Communicatioin)

執行中的Process可以有兩種型態

• Independent Processes : 不跟其他Process Shared Data
• Cooperating Processes : 可以影響或被影響by 其他Process

允許Process Cooperation 的理由 (很少考)

• information sharing
• computation speedup
• Modularity

2 Fundamental Model

shared memory

• 向OS要求配置一塊記憶體空間

Message Passing

• 建立通訊連結
• 訊息互傳
• 釋放Link

比較項目	Message Passing 訊息傳遞	Shared Memory 共享記憶體
適用	少量資料交換	大量資料交換
通訊速度	較慢	較快
分散式系統下	容易、適合	較不適合
共享變數存取之互斥控制	不需要	需要，避免 Race Condition

Critical-Section

The Critical-Section Problem

• Purpose（目的）:
  • Design a protocol : 允許處理器們協調與安全的存取共用的資料
• Problem Discription :
  • N processes compete to use shared data
  • Each process has a critical section - 每個 process 都有一段程式碼，會「讀 / 寫共享資料」
  • Challenge（挑戰）: 當某個 process 正在 critical section ， 其他 process 不能 同時進入它們的 critical section
  • 這個性質叫 mutual exclusion（互斥）
• 其他程式碼之間則稱為 Remainder Section (RS;剩餘區間)

Requirements for a Valid Solution

1. Mutual Exclusion(互斥性):
   • 同一時間最多一個 process 在 critical section
   • 目的 : 防止 Race condition 、 確保資料完整性
2. Progress (進展性):
   • 如果：critical section 是空的，有 process 想進去
   • 那麼：不能無限期拖延「誰可以進去」的決定
   • 決定一定要在 有限時間內完成
   • 目的 : 防止 DeadLock
3. Bounded Waiting(有界等待):

• 一個 process 請求進入後 ， 其他 process 最多只能插隊有限次
• 目的 : 防止 starvation（飢餓）

Busy waiting

Process 使用Loop，讓Processes 等待無法往下執行

• 缺點 : 浪費CPU
• 優點 :
  • 沒有context switch
  • 在multicore，如果卡住時間小於2次context switch 則spinlock 有利

Non-Busy Waiting

將Running -> Waiting，直到同步事件發生後才變成Ready

• 優點 : 避免Waiting 去跟其他Process爭奪CPU Time
• 缺點 : 付出兩次context switch代價
  • Running -> Waiting
  • ready -> Running

context switch 大部分都是跟 Running 有關

系統	Disable Interrupt	Spinlock
Uniprocessor 單核心	✅ 適合	❌ 不適合
Multiprocessor / Multicore	❌ 單獨使用不適合	✅ 適合

	Busy Waiting（Spinlock）	Non-Busy Waiting
等待方式	while(lock) 一直檢查	進 Waiting 睡眠
CPU	❌ 等待時仍占 CPU	✅ 不浪費 CPU
Context Switch	不需要因為「睡眠/喚醒」而做那兩次切換	需要付出約 2 次 context switch overhead
適合	等待很短	等待很久

Critical Section Solutions – Software Solutions

1. Software Solutions

   • Characteristics:

     • Use only softwarealgorithms
     • 在任何系統都能用

   • Example:

     • Peterson’s Algorithm（2 個 process）
     • Dekker’s Algorithm（2 個）
     • Bakery Algorithm（N 個）

2. Synchronization Hardware（硬體支援）

   • Characteristics:
     • Relies on atomic hardware instructions

     atomic hardware instructions（原子硬體指令） :
     是由 CPU 保證「整個操作不可被中斷、不可被拆開」的一條指令（或指令組）。
     要嘛 全部做完，要嘛 完全沒做

   • Hardware Support
     • Test-and-Set
     • Compare-and-Swap (CAS)
     • Atomic variables

     這些保證「一整個操作不可被切割」

3. Semaphore

   • Characteristics:
     • 一個 整數變數，透過兩個原子操作(atomic operation) 存取
     • 提供By OS
     • More abstract than hardware instructions
   • Operations:
     • wait() / P() - dercrement and block : 會嘗試將 semaphore 減 1 並 阻塞。
     • signal() / V() - increment and wake up wating process : 會將 semaphore 加 1 並喚醒等待者。
   • Types:
     • Binary semaphore(0 / 1) - 類似 mutex
     • Counting semaphore(0 ~ N) - resource counting

     Mutex（互斥鎖）: Mutex 保證「同一時間只有一個 thread 能進 critical section」

   • Mutual exclusion

4. Monitor

   • Characteristics:

     • 高階抽象（High-level abstraction）
     • 封裝共享資料與程序 - 共享變數不能被外面直接存取
     • 自動保證 Mutual Exclusion - 同一時間，只能一個 process / thread 在 monitor 裡
       • 進入 Monitor → 自動上鎖
       • 離開 Monitor → 自動解鎖
     • Synchronization : 使用 condition variable，使用 wait()、signal()

   • Features :

     • Only one process can be active
     • Condition Variables（條件變數）for waiting and signaling
     • Compiler enforces synchronization rules

Comparison

方法	抽象層級	複雜度	主要問題
Software	低	高	複雜、busy waiting
Hardware	低	中	只是基礎積木
Semaphore	中	中	很容易誤用
Monitor	高	低	需要語言/編譯器支援

• Key Points
  • Hardware instructions 是一切的基礎
  • Semaphore 與 Monitor 是不同抽象建於硬體之上

Software Solutions

Algorithm for two Processes

• Setup : Two Processes(P0 and P1)
• Shared Variables : int turn;
  • $ turn_i $ 代表 輪到 Pi 可以進 critical section;
• How It Work : Processes Alternate entering the critical section
  • Process P0:
    • 一直等到 turn == 0 才進去 ， 出來後把 turn = 1
  • Process P1:
    • 一直等到 turn == 1 才進去出來後把 turn = 0
• Analysis:
  • Mutual Exclusion : ✅
  • Progress : ❌（強制輪流），即使 critical section 是空的也不能進
  • Bound Waiting : ✅

Peterson’s Solution

• 不只看「輪到誰」，還看對方想不想進

• Shared variables

  • Boolean Flag[2]
    • flag[i] = true：Pi 想進 CS（有意圖）
    • flag[i] = false：Pi 不想進
  • int turn
    • 用來在「兩個都想進」時決定誰先

• How It Work :

  1. flag[i] = true; → 宣告：「我想進」
  2. turn = j; → 禮讓：「如果你也想進，那先讓你」
  3. while (flag[j] && turn == j) ; → 只有在「對方想進」而且「輪到對方」時才等

• Key :

  • 如果兩個同時想進:
    • Both set their flag to ture
    • Last Process to set turn will wait

• Analysis:

  • Mutual Exclusion : ✅
    • 只有其中一個能進
  • Progress : ✅
    • 優先權會給對方
  • Bound Waiting : ✅
    • 做完flag會轉成False

• Cons :

  • Busy waiting（一直 while 空轉浪費 CPU）
  • 只適用 2 個 process

Correctness Proof of Peterson’s Solution

• Mutual Exclusion : Contradiction(矛盾)
  • 假設一個不可能的事 => P0、P1同時在 critical section
  • flag[0]、flag[1] = true ， 只能靠turn來決定誰能進
  • 但turn不能同時是 0 or 1 => 矛盾！
• Progress :
  • Scenario 1：只有 P0 想進
    • flag[1]=false
    • P0 while：flag[1] && turn==1 → false
    • ✅ P0 立刻進 → 不會被無限拖延
  • Scenario 2：兩個都想進
    • Flag[0] Flag[1] = true;
    • 決定只看turn，而turn 只能是 0 or 1，所以只有一個人會進 ✅
• Bounded waiting :
  • Case 1：P1 退出後不再回來
    • P1 出來會 flag[1]=false
    • P0 的 while 立刻變 false
    • ✅ P0 直接進
  • Case 2：P1 退出後又想再進
    • P1 再次想進時會：
      • flag[1]=true
      • 並且 設 turn=0（禮讓 P0）
      • 這會覆蓋掉 P0 可能設的 turn=1
      • 此時對 P0 而言：
        • while：flag[1] && turn==1
        • 因為 turn 已經變 0 → false ✅ → P0 進
  • P0 請求進入後，P1 最多只能進一次，P0 不會無限等待。

Peterson’s 缺點

在現代電腦下，不保證一定可以正確，因為Compiler有可能對調程式執行，讓程式最佳化

• 也可能影響Mutual Exculusion
• 解法就不用Software，而要用適當的同步機制
  • Primitive support in H.W.
  • Proceeds 透過 abstract , high-level,software-based APIs,給Kernel,application 工程師

Turn Algorithm V.S. Peterson’s Algorithm

Feature（特性）	Turn Algorithm（Strict Alternation）	Peterson’s Algorithm
Mutual Exclusion（互斥）	✓ 滿足	✓ 滿足
Progress（進展性）	✗ 不滿足 （對方不想進也會被卡）	✓ 滿足
Bounded Waiting（有界等待）	✓ 滿足	✓ 滿足
Flexibility（彈性）	Low（只看 turn）	High（看 intent + priority）

項目	Turn Algorithm	Peterson’s Algorithm
使用的變數	只有 turn	flag[] + turn
解決的問題	只保證互斥	同時保證互斥、進展、公平
最大缺陷	違反 Progress	無（理論上正確）
核心概念	嚴格輪流	意圖（intent）＋優先權（priority）

Dekker’s Algorithm

• 使用的共享變數
• 第一個「完全正確」的純軟體 critical section 解法（1960s）

變數	意義
flag[i]	Pi 是否「想進」 critical section
turn	當兩個都想進時，誰優先

• Dekker 的 Entry Section（重點流程表）
• 假設 Pi 想進，Pj 是對方：

步驟	程式動作	白話解釋
1	flag[i] = true	我想進
2	while (flag[j])	如果對方也想進
3	if (turn == j)	而且現在輪到他
4	flag[i] = false	那我先退讓（暫時不想進）
5	while (turn == j)	等對方用完
6	flag[i] = true	再次宣告我想進
7	進 critical section	條件滿足才進

• Dekker 最特別的地方
  → 會「暫時撤回意圖（withdraw interest）」

Dekker vs Peterson

Feature	Dekker’s Algorithm	Peterson’s Algorithm
歷史	第一個正確解（1960s）	後來提出
Entry protocol	退讓＋重新宣告	宣告一次即可
複雜度	❌ 複雜	✅ 簡潔
Correctness	✓	✓

• 關鍵差異

比較點	Dekker	Peterson
等待時的行為	會暫時放棄意圖	一直保持想進
flag 的使用	可能變 false 再 true	一次設 true
可讀性	差	好

Limitations of Dekker’s Algorithm

缺點	說明
太複雜	entry protocol 很難寫對
Busy waiting	浪費 CPU
只適用 2 processes	無法擴充
記憶體排序要求高	現代 CPU 可能壞掉
實務不使用	被 mutex / semaphore 取代

Bakery Algorithm

• 第一個能解「N 個 processes」的純軟體 critical section 解法
• 核心比喻

現實世界	Bakery Algorithm
客人抽號碼	Process 取 ticket
號碼小的先服務	ticket 小的先進 CS
號碼一樣比先後	用 process ID 當 tiebreaker
公平、不插隊	無 starvation

• Numbering scheme :
  • Generate numbers in non-decresing order (後一個數字 <= 前一個數字)
  • Duplicate numbers are possible!
• Tie-breaking rule:
  • Use Process ID as the tiebreaker

排序規則：Lexicographic Ordering (字典順序)

• Bakery 比較的是 (number, process_id)

• Definition:
  $$
  (a,b) < (c,d)　if　a < c　OR　(a==c　AND　b<d)
  $$

• 先比號碼 ， 號碼一樣 → 比 process ID

• 共享變數

變數	意義
number[i]	Pi 的號碼牌（0 = 不想進）
choosing[i]	Pi 是否正在選號碼

Bakery Entry Section

• Step 1：拿號碼（Get Ticket）

程式碼	目的
choosing[i] = true	告訴大家：我在選號碼
number[i] = max(number[]) + 1	拿一個比目前最大還大的
choosing[i] = false	我選完了

• Step 2：等輪到我（Wait for Turn）

等待條件	意義
while (choosing[j])	等對方選完號碼
while (number[j] != 0 && (number[j], j) < (number[i], i))	如果對方號碼比較小 → 等

• Step 3：進入 CS

  • 當「所有優先權比我高的都完成」→ 我就能進

• Exit Section（Release Ticket）

程式碼	意義
number[i] = 0	退還號碼，不想進了

為什麼一定要 choosing[]?

• 沒有 choosing[]

步驟	發生的事
1	P0 讀 number → max=0
2	context switch
3	P1 讀 number → max=0
4	P1 設 number=1，進 CS
5	context switch
6	P0 設 number=1，也進 CS ❌

• 兩個人拿到一樣的號碼，還同時進去

• 加上 choosing[] 後

步驟	改善
P0 choosing=true	P1 看到，先等
P0 完成 choosing	number[0]=1
P1 再選	拿到 number=2

Correctness Proof

1. Mutual Exclusion

• 假設 P0、P1 同時在 CS：

推論	結果
P0 通過等待	(number[1],1) ≥ (number[0],0)
P1 通過等待	(number[0],0) ≥ (number[1],1)
合併	兩者互相小於 ❌
結論	字典序不可能 → 矛盾

2. Progress

理由	說明
有限 number	一定存在最小 (number,id)
最小者	不會再等任何人
結果	一定能進（finite time）

3. Bounded Waiting

性質	說明
FIFO	依 ticket 排隊
上限	Pi 拿號後，最多 n−1 人先進
結果	無 starvation

Bekery’s algorithm優缺點總表

• ✅ 優點

項目	說明
支援 N processes	✔
公平	First-come, first-served
無 starvation	✔
純軟體	不靠硬體

• ❌ 缺點

項目	說明
Busy waiting	浪費 CPU
Entry O(n)	要檢查所有 process
Space O(n)	number[], choosing[]
不實用	現代系統不用

前面的總結

Algorithm	Processes	Mutual	Progress	Bounded	實用性
Turn	2	✓	✗	✓	❌
Peterson	2	✓	✓	✓	教學
Dekker	2	✓	✓	✓	歷史
Bakery	N	✓	✓	✓	理論

Pthread Lock/Mutex Routines

• 在 Unix/Linux 用 POSIX Threads（pthread）寫多執行緒時，最常用的互斥工具就是 mutex
  • 保證同一時間只有一個 thread 進入 critical section（共享資料區） = Mutual Exclusion（互斥）

Mutex（互斥鎖）: Mutex 保證「同一時間只有一個 thread 能進 critical section」
🔒 mutex = 鎖
🚶 thread = 人

• Pthread Mutex 的基本流程

  pthread_mutex_t mutex;
  
  // 1. 初始化
  pthread_mutex_init(&mutex, NULL);
  
  // 2. 上鎖（進 critical section）
  pthread_mutex_lock(&mutex);
  
  /* CRITICAL SECTION
  存取 shared data
  */
  
  // 3. 解鎖（離開 critical section）
  pthread_mutex_unlock(&mutex);
  
  // 4. 不用時銷毀
  pthread_mutex_destroy(&mutex);

Condition Variables（CV）

• CV:
  • Thread 想要等「某個條件成立」再繼續做事
  • Notify other waiting thread that the condition has occured
• 三個核心操作:
  • wait() : 讓呼叫者「睡著」，直到有人通知它 、 wait 會原子性地「釋放 mutex 並進入等待
  • signal() : 喚醒 一個 正在 wait 的 thread 、 如果沒人 wait：訊號會消失
  • broadcast() : 喚醒 全部 wait 的 threads、大家會搶 mutex ， 仍是一次一個能真正繼續

Hardware Support for Synchronization

純軟體的限制

• ❌　共享變數的修改會被「中斷」可能被 → context switch 打斷

• ❌　多步驟操作不是 atomic → load → modify → store 不是不可分割的

• ❌　純軟體解法太依賴「嚴格記憶體順序」

• 需要硬體支援的 atomic operations（原子操作）

Memory barriers

• Stringly ordered : 修改馬上被其他processor看見
• Weekly ordered : 修改不一定馬上被其他processor看見
  Barrier 要求前面排序好的memory operation 不能被後面的memory operatoins 跳過

Hardware Instruction

Approach 1: Disable Interrupts

• Logic : 不讓中斷發生 → 就不會被 context switch → critical section 安全

• 單核心問題 :

  • ⛔ clock interrupt 被關 → 系統時間亂掉
  • ⛔ I/O interrupt 被吃掉 → 裝置可能壞掉
  • ⛔ 安全風險：user process 若能關中斷，系統直接爆炸

• 多核心問題 :

  • ⛔ 關的是「本 CPU」的中斷 → 其他 CPU 還是能同時存取 shared data

• ❌ 關中斷 不是通用解法

Approach 2: Hardware Atomic Instructions

• Atomic Instruction :

  • 一次完成
  • 不可被中斷
  • CPU 硬體保證

• Common Atomic Instruction :

  1. Test-and-Set
     • 讀＋寫一次完成
  2. Compare-and-Swap (CAS)
     • 只有在「值沒變」時才更新
  3. Swap / Exchange
     • 直接交換兩個值

Test and set(param)

• 傳回參數舊值，並同時將參數設為1，且保證atomically executed

bool test_and_set(bool *target){
    bool *ret = *target
    *target = true
    return ret
}

• mutual exclution : T
• Progress : T
• 違反Bounded Waiting : F
  • Pi比Pj早進去，Pj等待中，Pi做完離開後企圖立刻進去，則Pi有可能先搶到

Test_and_set (algo2) (正確) (背)

• lock = False
• Bool waiting[0…n-1] , 初值為False;
  • 初值表: Pi想進C.S且等待中
  • 後表可(已)進入C.S.表不用等

while (true){
    // <!-- entry section -->
    waiting [i] = true; // pi想進
    key = ture;
    while(waiting[i] && key)
        key = test_and_set(&lock); // 1st Process  傳回F，且Lock設T，if 2nd 3rd processes傳回T，Lock設T key仍為 T 卡住
    waiting[i] = false //不用等可以進
//critical section
    //Exit sec
    j = (i+1) % n //找下一個
    while((j!=i)&&!waiting[j])//找下一個想進的
        j = (j+1)%n;
    if (j==i)//沒有其他想進的
        lock = false'
    else 
        waiting[j] = false
// RS

}

Pi 想進
 ↓
waiting[i] = T
 ↓
嘗試 TestAndSet
 ↓
┌─────────────────┐
│                 │
自己搶到          別人交棒
key = F           waiting[i] = F
│                 │
└────────┬────────┘
         ↓
       進 C.S.
         ↓
找下一個 waiting = T
         ↓
   ┌─────┴─────┐
   │           │
 有人等       沒人等
   ↓           ↓
交棒給他     lock = F
waiting[j]=F   釋放鎖

• key = false
  → 原本 lock = false
  → 代表我成功搶到鎖
  → 可以進 C.S.

• key = true
  → 原本 lock = true
  → 代表別人已經有鎖
  → 繼續等

CAS (Compare and set)

int CAS(int *value, int expected, int new_value)
{
    int temp = *value;

    if (*value == expected)
        *value = new_value;

    return temp;
}

參數	意思
value	我要檢查、修改的變數
expected	我期待它現在的值
new_value	如果符合期待，要改成的新值

Mutual Exclusion 3 Common Atomic Instruction

項目	Test-and-Set	Compare-and-Swap (CAS)	Swap / Exchange
原子指令功能	讀舊值並設為 true	比較後才交換	直接交換兩個值
是否硬體原子操作	✅	✅	✅
共享變數	boolean lock	boolean lock	boolean lock
輔助變數	無	無	boolean key
lock 初始值	false	false	false
進入臨界區條件	TestAndSet 回傳 false	CAS 成功（false → true）	Swap 後 key == false
失敗時行為	一直 spin	一直 spin	一直 spin
等待方式	Busy waiting (spin)	Busy waiting (spin)	Busy waiting (spin)
解鎖方式	lock = false	lock = false	lock = false
Mutual Exclusion	✅	✅	✅
Progress	✅	✅	✅
Bounded Waiting	❌	❌	❌
公平性	❌	❌	❌
CPU 使用效率	低（浪費 CPU）	低	低
現代實務使用	基本 spinlock	⭐ 最常用（lock-free）	少（舊系統）

• Key Points:
  • 硬體支援讓同步變簡單又快
  • Atomic instructions 是 mutex 、 semaphore的地基
  • busy waiting 仍存在 、 bounded waiting 仍需設計

Mutex Lock

提供兩個Atomic operation

• acquire()
• Release()

Lock Contention (不重要)

Lock contention = 多個 Threads 競爭同一個 Lock。

• Uncontended：
  Thread 要取得 Lock 時，Lock 可直接取得。

• Contended：
  Thread 要取得 Lock 時，因 Lock 被占用而必須等待。

  • Low contention：少量 Threads 競爭
  • High contention：大量 Threads 競爭

Semaphore

• Purpose（目的）

  • 它是一個「同步工具」，用來一般化 critical section 問題
  • 比硬體原子指令更高階

• Definition

  • 本質是一個 整數 counter
  • 存取只能透過兩個原子操作 : wait() 、 signal()
  • Key property：Operations are indivisible（不可分割/原子）
  • wait/signal 一定要 atomic

Type of Semaphore

• Binary Semaphore（值只有 0 或 1）

  • value=1：資源可用 / 沒鎖（unlocked）
  • value=0：資源不可用 / 上鎖（locked）
  • 用途：互斥（mutex lock）（一次只能一個人進 CS）

• Counting Semaphore（值是 2…N）

  • 代表「同時允許最多 N 個」使用資源
  • 用途：資源數量控制

Two Atomic Operation :

• wait(S) / P(S) / down(S)

  • 做的事：S–
  • 如果 S 變成負數 → 表示「資源不夠」→ 呼叫者要 block（睡眠）

• signal(S) / V(S) / up(S)

  • 做的事：S++
  • 如果有人在等 → wakeup 一個

• Spinlock Implementation :

  • wait(S)：當 S->value <= 0 就一直 while 轉圈（busy waiting），直到有資源再 value–
  • signal(S)：value++

Issue

• 浪費 CPU cycles：一直 while 檢查
• 單核心更糟：等的人一直占 CPU，持鎖者可能根本拿不到 CPU 去解鎖

適合時機

• critical section 很短（一下就解鎖）
• 多核心 multiprocessor：別的 CPU 仍能前進（持鎖者能跑）

不適合時機

• CS 很長
• CPU 資源少
• 單核心

Semaphore考題 (就考這一種)

use Binary Semaphore to implement the counting semaphore

• int C
• Binary_Semaphore S1 = 1 給C互斥控制
• Binary_Semaphore S2 = 0 卡住Processes

Wait(c){
    Wait(S1);
    C--;
    if(C<0){
        signal(S1);
        wait(S2);
    }
    Else signal(S1);
}

Signal(c){
    Wait(S1)
    C++;
    if(C <= 0){
        signal(S2);
    }
    signal(S1);
}

Non-busy waiting（有等待隊列的 semaphore，真正 OS 會用）

• 不要忙等，改成 block/wakeup

• wait(S)：先 S->value–

  • 如果變成 < 0：代表要等
    → 把自己放到等待隊列 S->list
    → 呼叫 block()（睡眠，OS 把你移出 ready queue）

• signal(S)：先 S->value++

  • 如果結果 <= 0：表示「還有人在等」（因為負值代表等待人數）
    → 從 S->list 取出一個
    → wakeup(P) 把它放回 ready queue

• Value意義:

  • S > 0：還有 S 個資源可用（下一個 wait 不會 block）
  • S = 0：資源剛好用完（下一個 wait 會 block）
  • S < 0：
    • |S| = 正在等待（被 block）的 process 數量
      例：S = -3 代表有 3 個 process 被擋在 wait 上

• waiting process : 可以借助link field in each PCB，為了確保bounded waiting 可以用FIFO queue

Semaphore 4 種實作

方法	Atomic 的做法	等待方式
Algorithm 1	Disable Interrupt	Non-busy waiting
Algorithm 2	Test-and-Set／CAS	Non-busy waiting
Algorithm 3	Disable Interrupt	Busy waiting
Algorithm 4	Test-and-Set／CAS	Busy waiting

Algorithm 1

Wait(s){
    disable interrupt;
    s -> Value--;
    if(S-> value <0){
        add Process P to S -> list
        Enable interrupt
        sleep();
    }
    else enable interrupt;
}

signal(S) {
    disable_interrupt();

    S.value++;

    if (S.value <= 0) {
        從 S.list 取出一個 process P;
        wakeup(P);
    }

    enable_interrupt();
}

algorithm 2

wait(S) {
    acquire_internal_lock();   // Test-and-Set 或 CAS

    S.value--;

    if (S.value < 0) {
        將目前 process 加入 S.list;
        release_internal_lock();
        sleep();
    } else {
        release_internal_lock();
    }
}

Entry Section 中仍然有Busy waiting

algorithm 3

wait(S) {
    disable_interrupt();

    while (S <= 0) {
        enable_interrupt();

        do_no_op();       // 繼續等待，占用 CPU

        disable_interrupt();
    }

    S--;
    enable_interrupt();
}

signal(S) {
    disable_interrupt();
    S++;
    enable_interrupt();
}

Busy Waiting 無法完全避免

semaphore 只是將她從定義層次拉到實作層面

POSIX Semaphor

• Semaphore 是 POSIX 標準的一部分 ， 不是 pthread 的一部分
• Semaphore 可以用在：
  • process ↔ process（跨行程同步）
  • thread ↔ thread（同一行程內多執行緒同步）

##　Correctness Properties

• Mutual Exclusion：可以
• Progress：通常可以
• Bounded Waiting：不保證
  • 會不會餓死starvation取決於等待隊列怎麼選人
    • FIFO：比較有 bounded waiting
    • LIFO / priority：可能有人永遠被插隊 → starvation

Advantages and Disadvantages

• 優點:
  • 抽象層更高、可移植、不依賴特定硬體、可用 block 避免 busy waiting
  • 也支援「互斥」+「同步（順序約束）」兩種用途
• 缺點:
  • 容易寫錯
  • 不具結構性
  • 沒有 ownership（所有權）

Cooperation Synchronization（合作式同步：強制順序）

• 需求

  • P1 做 S1
  • P2 做 S2
  • 規定：S2 必須等 S1 做完

• 看到 wait(x)：代表「我需要 x 這個事件先完成」

• 看到 signal(x)：代表「我完成了某個事件，放行後面的人」

Deadlocks and Starvation

• Deadlock

  • 兩個或更多 process 都在等
    • 而「能讓我繼續的事件」只能由「正在等的那些人」造成
      → 形成閉環，永遠沒人能先動

• Starvation

  • 某個 process 一直等不到，但系統其實一直在前進
  • 常見原因：
    • semaphore 等待隊列是 LIFO 或不公平策略
      → 新來的永遠插隊，老的永遠輪不到。

Classical Synchronization Problems

• Purpose

  • Benchmark problems : 把同步問題「標準化」
  • 都要拿來「實戰驗證」
  • 光說「我這個 lock 很棒」不夠，要拿經典問題來測

• 三大經典問題

問題	重點
Producer–Consumer（Bounded Buffer）	容量限制 + 同步
Readers–Writers	讀寫衝突 + 優先權
Dining Philosophers	資源共享 + deadlock / starvation

• Producer–Consumer vs Readers–Writers vs Dining Philosophers

項目	Bounded-Buffer	Readers–Writers	Dining Philosophers
問題類型	生產 / 消費	讀 / 寫	資源競爭
共享資源	有限個 buffer（n 個）	共享資料（DB / file）	筷子（資源）
角色	Producer、Consumer	Reader、Writer	Philosopher
資源數量	有限（n）	1 份資料	每人左右各 1 支
核心限制	有容量上限	Writer 必須獨佔	一次要拿 2 支
允許並行	多個 Producer / Consumer	多個 Reader 可同時	多人思考
不允許並行	同一 buffer 同時使用	Writer 與任何人	同一筷子被兩人拿
主要同步目的	✔ 不超生產 ✔ 不空消費	✔ 保護資料一致性	✔ 避免系統卡死
典型錯誤	生產太多或消費太快	優先權設計錯誤	拿筷子順序錯
Deadlock 可能？	❌（正常設計不會）	❌（除非設計很爛）	✔ 非常典型
Starvation 可能？	❌	✔（Readers 或 Writers）	✔

Monitors

• Motivation of Monitors

  • Semaphore 很有效，但「正確性完全靠程式員」

• Monitor 是更高階的同步結構

• 核心功能：自動互斥（automatic mutual exclusion）

• Monitor 由兩部分構成：

  • 共享資料（variables / state）
  • 操作共享資料的方法（procedures/functions）
    而且外面只能透過方法存取資料。

• 同一時間只允許一個 thread/process 在 monitor 裡執行
  → 這就是 monitor 自帶的 mutual exclusion。優於Semaphore的好處

Similarity to Object-Oriented Classes

• Monitor 很像物件導向 class：

  • 封裝（Encapsulation）：資料 + 操作放一起
  • 資訊隱藏（Data hiding）：內部狀態 private，外面不能直接碰
  • 公開介面（Public interface）：外界只能呼叫方法

• 外部 code 不能直接存取 monitor 內部變數

Condition Variables in Monitor

• Monitor 只保證 mutual exclusion，不保證你要的「條件同步」。

• 很多問題需要「等到條件成立」才繼續，例如 bounded buffer：

  • buffer 滿：producer 不能做 → 要等 notFull
  • buffer 空：consumer 不能拿 → 要等 notEmpty

• monitor 提供 condition variables

  • x.wait()
    • 把自己睡著（suspend）
    • 釋放 monitor lock（不然別人進不來改條件）
    • 等被喚醒後，再回來繼續
  • x.signal()
    • 喚醒 一個 等在 x 的人
    • 若沒人等 → 沒效果（signal lost）

• x的waiting queue可能是 FIFO or FCFS queue

Monitor 種類

1. P等Q全部做完或是Q blocked again (Hoare)
2. Q等P直到P做完或是 P blocked again (BAD)
   • P在這段期間可能又會把condition 改掉，變成Q不一定成立
3. P立即退出Monitor，讓Q先做，P會在下一個進入

類型	P 執行 signal() 後	誰先跑？	Q 等待的 condition	特點
① P waits for Q	P 暫停	Q	✅ 可保證仍成立	Hoare Monitor
② Q waits for P	P 繼續	P	❌ Q 執行時可能已改變	看起來自然，但不保證 condition
③ P exits monitor and Q resumes	P 直接退出 Monitor	Q	✅ 可保證 Q 接著執行	Concurrent C/Pascal

• 1、3 : Signal and Wait
• 2 : Signal and Continue

Implementing a Monitor Using Semaphores

使用 Semaphore 實作 Monitor，需要滿足：

1. Mutual Exclusion

   • 同一時間只能有一個 Process 在 Monitor 裡執行。

2. 符合 Hoare Monitor

   • P 執行 x.signal() 喚醒 Q。
   • P 必須等待，讓 Q 馬上執行。
   • Q 完成或再次 blocked 後，P 才繼續。

3. 實作 Condition Variable：

   • x.wait()
   • x.signal()

Monitor 使用的變數

變數	初始值	用途
mutex	1	保證 Monitor 的 Mutual Exclusion
next	0	讓執行 signal() 後暫停的 Process 等待
next_count	0	記錄有幾個 Process 在 next 等待
x_sem	0	Condition x 的等待 Queue
x_count	0	記錄有幾個 Process 正在等待 Condition x

簡單記：

x_sem = 等 Condition x 的 Queue
x_count = Queue 裡有幾個 Process

Monitor 和 Semaphore 可以互相製作

Monitor Function

每個 external function F：

wait(mutex);

Body of F

if (next_count > 0)
    signal(next);
else
    signal(mutex);

進入 Monitor

wait(mutex);

取得 Monitor 的使用權。

因為 mutex = 1：

• 第一個 Process 可以進入
• 其他 Process 必須等待

離開 Monitor

如果：

next_count > 0

代表有之前執行 signal() 後，讓出執行權的 Process 在 next 等待。

所以：

signal(next);

讓它回來執行。

否則：

signal(mutex);

把 Monitor 開放給其他 Process。

x.wait()

實作：

x_count++;

if (next_count > 0)
    signal(next);
else
    signal(mutex);

wait(x_sem);

x_count--;

x.signal()

實作：

if (x_count > 0) {
    next_count++;
    signal(x_sem);
    wait(next);
    next_count--;
}

這是 Hoare Monitor 的核心。

假設：

• P 正在 Monitor 執行
• Q 正在 x_sem 等待

P 執行：

x.signal();

---

next 和 x_sem 的差別

	x_sem	next
誰在等？	執行 x.wait() 的 Process	執行 x.signal() 後讓出 Monitor 的 Process
等什麼？	等待 Condition x	等被喚醒的 Process 使用完 Monitor
例子	Q	P

簡單記

x_sem = 等 Condition 的 Q
next = signal 後讓 Q 先跑，因此暫停的 P

流程：

Q -- x.wait() --> x_sem 等待

P -- x.signal() --> 喚醒 Q
                     ↓
                  P 去 next 等
                     ↓
                  Q 先執行
                     ↓
                  Q 用完
                     ↓
                  喚醒 next
                     ↓
                  P 繼續

---

Liveness

定義

Liveness

確保 Processes 在 execution life cycle 中能夠持續 make progress。

如果 Process：

wait indefinitely（無限等待）

就是：

Liveness Failure

常見例子：

• Deadlock
• Starvation
• Priority Inversion
• 某些 Infinite Loop / Busy Wait Loop

---

Liveness 保證強度

Deadlock Freedom
       ↓
Starvation Freedom
       ↓
Bounded Waiting

越下面保證越強。

類型	意思
Deadlock-free	至少有某個 Process 最終可以前進
Starvation-free	每個 Process 最終都能前進
Bounded Waiting	每個 Process 不只會前進，而且等待有上限

Deadlock-free

不保證每個 Process 都成功。

只保證：

系統不會全部一起卡死，最終至少有某個 Process 可以前進。

Starvation-free

比 Deadlock-free 更強：

每一個等待的 Process 最終都能取得執行機會。

因此：

Starvation-free ⇒ Deadlock-free

反過來不一定成立。

Bounded Waiting

更強的要求。

如果有 n 個 Processes 競爭 Critical Section：

每個 Process 最多被其他 Processes 超過 n - 1 次，就必須輪到它。

---

Priority Inversion

定義

High-priority Process 被 Low-priority Process 所持有的資源擋住。

假設：

• H = High Priority
• M = Medium Priority
• L = Low Priority

Priority：

H > M > L

首先：

L 取得 Lock
    ↓
H 想取得 Lock
    ↓
H 必須等待 L

問題是 M 出現後：

H：等待 Lock
      ↑
      L：持有 Lock

M 又因 Priority > L
搶走 L 的 CPU

結果：

H 明明 Priority 最高，卻長時間無法執行。

這就是 Priority Inversion。

---

Priority Inheritance Protocol

解決 Priority Inversion。

如果 H 正在等待 L 手上的 Lock：

暫時讓 L 繼承 H 的 Priority。

原本：

H > M > L

H 等待 L：

H
↓ 等待
L 持有 Lock

暫時提高 L：

L Priority = H Priority

因此：

L 快速取得 CPU
    ↓
完成 Critical Section
    ↓
Release Lock
    ↓
H 取得 Lock
    ↓
L 恢復原本 Priority

一句話

誰擋住 High-priority Process，就暫時繼承它的高 Priority。

---

Message Passing IPC

IPC：

Inter-Process Communication

Message Passing 提供一種機制，讓 Processes：

• Communicate
• Synchronize

而且：

不需要共享相同的 Address Space。

基本操作：

send(message)
receive(message)

---

Message Passing 三大分類

問題	類型
Naming	Direct / Indirect
Synchronization	Blocking / Nonblocking
Buffering	Zero / Bounded / Unbounded

---

Naming：Direct Communication

Process 直接指定對方。

分成：

1. Symmetric
2. Asymmetric

---

Symmetric Direct Communication

Sender 和 Receiver：

雙方都必須指定對方。

假設 P 傳給 Q：

P：

send(Q, message)

Q：

receive(P, message)

P 指定 Q。

Q 也指定 P。

因此稱為：

Symmetric Direct Communication

Properties

1. Link 自動建立。
2. 一條 Link 只與 exactly two processes 有關。
3. 每一對 Processes 之間存在 exactly one link。

---

Asymmetric Direct Communication

只有 Sender 必須指定 Receiver。

P：

send(Q, message)

Q：

receive(id, message)

Q 不需要指定：

我要收 P 的 Message。

而是：

任何 Process 傳來的 Message 都可以收。

收到後：

id

用來記錄：

Message 是哪個 Process 傳來的。

---

Symmetric vs Asymmetric

	Symmetric	Asymmetric
Sender 指定 Receiver	✓	✓
Receiver 指定 Sender	✓	✗
Send	send(Q,msg)	send(Q,msg)
Receive	receive(P,msg)	receive(id,msg)

簡單記

Symmetric = 雙方都知道對方是誰
Asymmetric = Sender 知道 Receiver，但 Receiver 不必事先知道 Sender

---

Naming：Indirect Communication

Direct：

P ─────────→ Q

Indirect：

P ──→ Mailbox A ──→ Q

雙方透過：

Mailbox

進行 Communication。

P：

send(A, message)

Q：

receive(A, message)

所以：

P、Q 只需要知道 Mailbox A，不需要直接指定彼此。

---

Direct vs Indirect Communication

	Direct	Indirect
溝通對象	Process	Mailbox
Sender	send(Q,msg)	send(A,msg)
Receiver	receive(P,msg)	receive(A,msg)
Mailbox	✗	✓
Link	通常連接兩個 Process	可以由多個 Process 共用

---

多個 Process 共用 Mailbox

假設：

P1
 ↓
Mailbox A
  ↙  ↘
 P2  P3

P1：

send(A, message)

但是 P2、P3 都：

receive(A, message)

問題：

P2 還是 P3 會收到 Message？

三種可能解法

1. 一條 Link 最多只允許兩個 Processes 使用。
2. 同一時間最多只允許一個 Process 執行 receive()。
3. OS 決定哪個 Process 收到，例如 Round Robin。

重點：

Message 只會被其中一個 Receiver 收到，不是兩個都收到。

---

Mailbox Ownership

Mailbox 可以由：

1. Process 擁有
2. Operating System 擁有

Process-owned Mailbox

可以區分：

• Owner：Receive
• User：Send

因此有唯一 Owner 時：

很清楚誰負責 Receive。

OS-owned Mailbox

Mailbox 由 OS 擁有，不屬於特定 Process。

OS 必須提供 System Calls：

• Create a new mailbox
• Send messages
• Receive messages
• Delete a mailbox

---

Synchronization：Blocking / Nonblocking

Message Passing 可以分成：

• Blocking / Synchronous
• Nonblocking / Asynchronous

重點：

呼叫 send() 或 receive() 後，Process 要不要停下來等待？

---

Blocking Send

Sender：

Block，直到 Message 被 Receiver 或 Mailbox 接收。

流程：

send(message)
    ↓
  等待
    ↓
Message 被接收
    ↓
繼續執行

---

Nonblocking Send

Sender：

Message 傳出後馬上繼續執行。

流程：

send(message)
    ↓
直接繼續

---

Blocking Receive

Receiver：

如果 Message 還沒到，就 Block。

直到：

有有效 Message 可以 Receive。

---

Nonblocking Receive

Receiver 不等待。

如果有 Message：

回傳有效 Message。

如果沒有：

回傳 NULL。

---

Blocking / Nonblocking 比較

Operation	Blocking	Nonblocking
Send	等 Message 被接收	傳完馬上繼續
Receive	沒 Message 就等待	沒 Message 就回傳 NULL

---

Rendezvous

如果同時使用：

• Blocking Send
• Blocking Receive

稱為：

Rendezvous

也就是 Sender 和 Receiver 都需要等待彼此完成 Message Transfer。

記法

Blocking Send + Blocking Receive = Rendezvous

---

Buffering

Buffering 是在討論：

Message Queue 可以存多少個 Message？

分成：

1. Zero Capacity
2. Bounded Capacity
3. Unbounded Capacity

---

Zero Capacity

Queue 大小：

0

沒有空間暫存 Message。

因此：

Sender 必須等待 Receiver 收走 Message。

流程：

Sender
  ↓
send()
  ↓
沒有 Buffer
  ↓
等 Receiver

又稱：

No Buffering

Zero Capacity 也常形成：

Rendezvous

---

Bounded Capacity

Queue 有固定大小 n。

例如：

Queue Size = 3

[m1]
[m2]
[m3]  ← Full

Sender 再送 m4：

Sender 必須 Block。

Receiver 取走 Message：

Receiver 取走 m1

[  ]
[m2]
[m3]

出現空間後，Sender 才能把新的 Message 放進去。

重點

Queue 未滿 → Sender 可以繼續
Queue Full → Sender Block

---

Unbounded Capacity

Queue 理論上沒有容量限制。

因此：

Sender 不會因為 Queue Full 而 Block。

---

Buffering 比較

類型	Queue Size	Sender 何時 Block？
Zero Capacity	0	Receiver 還沒接收時
Bounded Capacity	固定 n	Queue Full
Unbounded Capacity	無限	不會因 Queue Full 而 Block

---

考前總整理

主題	一句話記憶
Monitor	同時間只能一個 Process 在 Monitor
Hoare Monitor	signal() 後 P 等、Q 馬上跑
mutex	保護 Monitor Mutual Exclusion
x_sem	等 Condition x 的 Process
next	Signal 後讓 Q 先跑，因此暫停的 P
x_count	等 Condition x 的人數
next_count	等在 next 的人數
Liveness	Process 必須能持續 make progress
Deadlock	Processes 互相等待
Starvation	某 Process 一直拿不到執行機會
Bounded Waiting	等待次數有上限
Priority Inversion	High Priority 被 Low Priority 擋住
Priority Inheritance	Low 暫時繼承 High 的 Priority
Message Passing	不共享 Address Space 也可以 IPC
Direct	直接指定 Process
Indirect	透過 Mailbox
Symmetric	Sender、Receiver 都指定對方
Asymmetric	只有 Sender 指定 Receiver
Blocking	呼叫後可能停下來等待
Nonblocking	呼叫後不用等待
Rendezvous	Blocking Send + Blocking Receive
Zero Capacity	Queue = 0
Bounded Capacity	Queue 有固定上限
Unbounded Capacity	Queue 理論上無上限

---

最後必背

Monitor

x.wait()
→ Q 等在 x_sem

x.signal()
→ P 喚醒 Q
→ P 去 next 等
→ Q 先執行
→ Q 結束 / Block
→ P 回來

Liveness

Deadlock Freedom
      ↓ 更強
Starvation Freedom
      ↓ 更強
Bounded Waiting

Message Passing

Message Passing
    │
    ├── Naming
    │    ├── Direct
    │    │    ├── Symmetric
    │    │    └── Asymmetric
    │    └── Indirect → Mailbox
    │
    ├── Synchronization
    │    ├── Blocking
    │    └── Nonblocking
    │
    └── Buffering
         ├── Zero
         ├── Bounded
         └── Unbounded

---

作者最後的感想 : 我知道又臭又長，但我真的不知道要怎麼縮減了，可能作業系統就是這樣吧…! <3
因為時間緊急，我下次會記得美化的 可能會請求GPT的支援吧