Synchronization Tool Evaluation
Introduction
Synchronization tool 的選擇不只看 correctness，也看 contention 下的成本：等待者是 spin / retry、sleep、進 queue，還是由 higher-level abstraction 管理。
CAS-Based Synchronization
CAS-based approach 是 optimistic synchronization：先假設衝突少，直接嘗試更新；若發現值被別人改過，再 retry。
- Uncontended / moderate contention：overhead 低
- High contention：大量 retry 會浪費 CPU，甚至比 lock 慢
Lock-Based Synchronization
Mutex lock / semaphore 是 pessimistic strategy：進 critical section 前先 acquire lock，避免同時修改。
- High contention：可把等待者 block 到 queue，避免所有人一直 retry
- Contended lock：可能需要 sleep、wait queue、context switch，成本較重
General Guidelines
| Situation | Usually better choice | Intuition |
|---|---|---|
| Uncontended | CAS / atomic variable | 沒競爭時成本最低 |
| Moderate contention | CAS | retry 通常很快成功 |
| High contention | Traditional lock / semaphore | 避免大量 thread spin / retry |
| Single counter update | atomic variable | 只需保護單一變數 |
| Short critical section on multicore | spinlock | 省下 context switch |
| Finite identical resources | counting semaphore | value 表示剩餘數量 |
| Complex condition synchronization | condition variable | protocol 藏進 ADT，較不易寫錯 |
Tradeoff
Low-level tools（CAS、memory barrier）效能彈性高，但正確性難；higher-level tools（semaphore、monitor）較好用，但 overhead 與 scalability 取決於 implementation。
實務上通常由 OS / library 用 low-level primitive 實作可靠 abstraction，再讓 application 使用較高階的 tool。