整理 同步機制 (Synchronization) 的基礎概念，基本上就是作業系統概念的第六章內容。

Operating System Concepts，俗稱恐龍書，整理筆記時最新是第十版 (2018)。

名詞

• Synchronization (同步機制)
  • SpinLock（自旋鎖）
  • Mutex 互斥鎖 (Linux)
  • Semaphore: 信號燈, 旗號. (Linux)
• Condition Variable (Solaris, PThread)
  • readers–writer locks (Solaris, PThread)
• Patterns
  • Read-Write Lock Pattern（讀寫鎖）
  • Before/After Pattern
  • Reactive
• Race Condition: 競爭條件，又稱 Race Hazard (種族危險)
• Context Switch: 上下文切換。
  • Context 中文翻譯成 上下文、情境、背景、脈絡、框架，計算機科學裡常用 上下文，指的是不同程序之間主控權交換的過程。
  • Context Switch 用在人身上指的就是一心多用，或者頻繁切換主軸、焦點，相關參閱 Cost in Context Switch
• Critical Section: 臨界區段，縮寫成 CS。有時候也用 Critical Region.
• Atomic Instructions
  • Compare-And-Swap (CAS)
  • Test and Set (TAS)

Context 可以想像一個人到新環境時，一開始感覺到的氛圍

問題與概念

Lock (鎖)

• 同步機制最主要要解決的問題是 鎖 (Lock) 的管理。
• 在各種單處理器、多處理器 (Multiprocessers)
• 減少 Race Condition (競爭條件) 的增加

Java 的實踐： synchronized

Race Condition

很多 Process 同時存取操作同一份資料，因為執行次序不同，導致結果不一樣的現象，此現象稱為 Race Condition，中文翻譯成 競爭條件。

作業系統概念書中原文的描述如下：

A situation like this, where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place, is called a race condition

Race Condition 這樣的現象衍生出資料不一致的問題，通常需要透過一些機制來保證同時間，資料不會被同時修改。

除了軟體的多執行緒常出現此問題，硬體的數位邏輯電路也會出現此問題。

The Critical Section Problem

一個系統由 n 個 Process 組成。而每個 Process 都有一段叫做 Critical Section (以下縮寫 CS) 的區間，這段時間 process 正在存取 (accessing)、更新 (updating) 與其他至少一個 process 共享的資料，也就是 shared data。

Critical Section 的概念如下 pseudo code：

1
2
3
4
5
6
7
8

while (true) {
  // ENTRY SECTION
    // critical section
  // EXIT SECTION

    // remainder section
}

Critical Section Problem 主要目的是：

設計一個協議、方法，讓多個 process 在執行任務的時候，可以協作、並同步 (synchronize) 共享資料。

滿足解決 CS 問題有三個必要條件：

1. Mutual Exclusion (互斥鎖)
2. Progress (有進展)
3. Bounded waiting (有限等待)

作業系統通常透過兩種方法處理 CS:

1. preemptive kernels (搶佔)
2. nonpreemptive kernels (非搶佔)

Synchronization

Mutex

全名是 Mutual Exclusion，縮寫成 Mutex，中文稱為 互斥鎖。是一種 同步控制 (Concurrency Control)，用於多執行緒中，防止兩個執行緒同時對一個公共資源進行讀寫的機制。

透過一個變數或物件確保 Critical Section 內的資料同一時間，只會有單一存取。

• In linux, 二進位號誌（binary semaphore）又稱互斥鎖（Mutex）
  • Mutex = Binary Semaphore

MSDN 的分類 如下三大類：

• (Interrupt / Queued) Spinlock
• (Fast/Kernel/Unsafe Fase) Mutex
• Synchronization Event

特性：

• Blocking

實作方式：

• VxWorks Version 5.4
• POSIX Threads (pThreads) – IEEE Std 1003.1, 2004 Edition
• Microsoft Windows Win32 – Not .NET

Semaphore

Semaphore 中文翻譯成旗號、信號，相關論文：

• 1962: Dekker’s Algorithm
  • Dijkstra (1962 or 1963)
  • Busy waiting
• 1965: Binary Semaphore
  • Dijkstra - P(S) & V(S)
  • Prolagen (try, and lower), Verhogen (raise, to increase)
  • Solution of a problem in concurrent programming control
• 1965: Counting Semaphore
  • Dr. Carel S. Scholten
  • Initial value

種類：

• binary semaphore (二進位信號)
  • binary semaphore 值只能是 0 或 1
  • 邏輯上相當於一個 Mutex (互斥鎖)，但是 Mutex 具備擁有者 (Owner) 的概念，只有所著 Mutex 的 Process，才具有解鎖的權限。semaphore 則無此限制。
• Counting Semaphore (技術信號)
  • 也稱為 General Semaphore，通用的 Semaphore
  • Reentrant Mutex, 可重入互斥鎖，又稱 recursive mutex, recursive lock

運作原理：

P 和 V 的意義來自荷蘭文 ( Edsger W. Dijkstr 為荷蘭人)

1. V operation：V() 會將 semaphore 的值加 1，signal 函數或是 sem_post()
   • V 代表 verhogen (荷蘭文)，意思是增加
2. P operation：P() 會將 semaphore 的值減 1，wait 函數或是 sem_wait()
   • P 代表 portmanteau prolaag (荷蘭文)，其意思是嘗試減小。

每個 P 或 V operation 必須具備 atomic operation，該 operation 是不可分割的 (all or nothing)。

註：Dijkstra 是荷蘭人，所以均以荷蘭文為代號

特性：

• Semaphore 可以設定 Acquire 的次數
• 如果 CS 允許被兩個以上的 Thread 執行，通常會採用 Semaphore，副作用就是 Deadlock
• Mutex 只能被 Acquire 的 Thread 釋放，Semaphore 則無此限制

衍伸問題：

1. Accidental release
2. Deadlock
   1. Recursive Deadlock
   2. Deadlock through Task Death
   3. Priority Inversion
   4. Semaphore as a Signal

實作：

• java.util.concurrent.Semaphore
• .NET Core: Semaphore 類別
• 用 Semaphore 實作 Rate Limit

相關資料

• semaphore (信號)
• Java Semaphore: Coordinating Threads
• 主題分享: 淺談 Semaphore 與 Mutex, 簡報
• Linux 核心設計: 淺談同步機制
• Mutex, Semaphore, the difference, and Linux kernel
• java:高效的解決死鎖問題的執行緒通訊方式：Semaphore 和 BlockingQueue
  • Package java.util.concurrent
• Little Book Of Semaphores

SpinLock（自旋鎖）

• Spinlock 的產生背景
  • 多處理器的環境中
  • 特性
  • Non-Blocking
  • 作業系統核心：僅供自己內部使用的特權機制
• 實作的時候 利用 spinlock sleeping semaphore preempt_RT
• 適用場景：自旋锁比较适用于锁使用者保持锁时间比较短的情况。
  • 作業系統核心：僅供自己內部使用的特權機制
  • 大多不會給 AP 開發者使用
• 實作：
  • Java 1.5 package: java.util.concurrent.atomic
    • AtomicBoolean，AtomicInteger，AtomicLong，AtomicReference
    • AtomicIntegerArray，AtomicLongArray
    • AtomicLongFieldUpdater，AtomicIntegerFieldUpdater，AtomicReferenceFieldUpdater
    • AtomicMarkableReference，AtomicStampedReference，AtomicReferenceArray
  • TAS: test-and-set
• Spinlock 衍生的問題：
  • 遞迴死鎖
  • 過多佔用 CPU 資源
• 相關詞彙：
  • CAS: Compare And Set

相關資料：

• Linux 核心設計: 多核處理器和 spinlock
• Locks, Deadlocks, and Synchronization

比較

• Mutex:
  • 一間可以容納 1 個人的房間，有一把鑰匙。
  • 只有一個人，和一把鑰匙。拿了鑰匙可以進去房間。
  • A mutex is really a semaphore with value 1.
• Semaphore:
  • 一間可以容納 N 個人的房間，沒有鑰匙。
  • 如果房間還沒滿，人就可以進去。
  • 如果房間滿了，就要等待有人出來。
  • N = 1，稱為 Binary Semaphore，用來限制對某一個資源的同時間訪問。
• Spinlock:
  • 內核態 (CPU Mode) 的概念
  • Spinlock 是 busy waiting，Semaphore 是 sleep

要搶資源時用 mutex；要互相通知時用 semaphore

延伸閱讀

站內延伸

• Study Notes - I/O Models
• Cost in Context Switch

參考資料

• Synchronization (computer science) (Wikipedia)
• Threading objects and features (Microsoft)
• Mutex vs. Semaphores – Part 1: Semaphores
• 管理設計篇之“分佈式鎖”
• 概念性、宏觀視野的程序/執行緒同步機制總覽 - 洪朝貴 教授
• Read-Write Lock Pattern
• spinlock & mutex & semaphore 的作用和區別

Open Course

• Taiwan Linux Kernel Hackers
  • 淺談 Semaphore 與 Mutex
• Linux 核心設計 by 黃敬群
  • 淺談同步機制, Youtube
  • 多核處理器和 spinlock
• 清華大學開放式課程：周志遠教授 作業系統
  • 第18D講 Critical Section
  • 第20C講 Semaphore