条件变量

**監視器** (英語：Monitors，也稱為**管程**) 是一種程式結構，結構內的多個子程式（物件或模組）形成的多個工作執行緒互斥存取共享資源。這些共享資源一般是硬體或一群變數。監視器實現了在一個時間點，最多只有一個執行緒在執行監視器的某個子程式。與那些通過修改資料結構實現互斥存取的並行程式設計相比，監視器實現很大程度上簡化了程式設計。

監視器提供了一種機制，執行緒可以臨時放棄互斥存取，等待某些條件得到滿足後，重新獲得執行權恢復它的互斥存取。

監視器是東尼・霍爾

與泊・派克・漢森
提出的，並由泊・派克・漢森首次在並列 Pascal 中實現。東尼・霍爾證明了這與號誌是等價的。監視器在當時也被用於單作業系統環境中的行程間通訊。

在程式語言 Concurrent Pascal，Pascal-Plus，Modula-2，Modula-3，Mesa 以及 Java 中都提供這個功能。

## 監視器實現對共享資源的互斥存取

一個監視器包含:

* 多個彼此可以互動並共享資源的執行緒
* 多個與資源使用有關的變數
* 一個互斥鎖
* 一個用來避免競態條件的不變數

一個監視器的程式在執行一個執行緒前會先取得互斥鎖，直到完成執行緒或是執行緒等待某個條件被滿足才會放棄互斥鎖。若每個執行中的執行緒在放棄互斥鎖之前都能保證不變數成立，則所有執行緒皆不會導致競態條件成立。

以下這個銀行帳戶的提款／存款事務的監視器是個簡單的例子：

```
**monitor class** _Account_ {
  **private** _int_ balance := 0
  **invariant** balance >= 0

  **public method** _boolean_ withdraw(_int_ amount)
     **precondition** amount >= 0
  {
    **if** balance < amount **then** **return false**
    **else** { balance := balance - amount ; **return true** }
  }

  **public method** deposit(_int_ amount)
     **precondition** amount >= 0
  {
    balance := balance + amount
  }
}
```

當一個執行緒執行監視器中的一個子程式時，稱為占用 (occupy) 該監視器。監視器的實現確保了在一個時間點，最多只有一個執行緒占用了該監視器。這是監視器的互斥鎖存取性質。

當執行緒要呼叫一個定義在監視器中的子程式時，必須等到已經沒有其它執行緒在執行監視器中的某個子程式。

在監視器的簡單實現中，編譯器為每個監視器物件自動加入一把私有的互斥鎖。該互斥鎖初始狀態為解鎖，在監視器的每個公共子程式的入口給該互斥鎖加鎖，在監視器的每個公共子程式的出口給該互斥鎖解鎖。

這個例子中的不變數是「任何操作執行前 balance 變數必須反映正確的餘額」。一般而言，不變數的條件不被寫在程式中，而在註解中有相關說明，然而 Eiffel 程式設計語言顯式檢查不變數。

## 條件變數 (Condition Variable)

對於許多應用場合，互斥操作是不夠用的。執行緒可能需要等待某個條件 $P$ 為真，才能繼續執行。在一個忙碌等待迴圈中

```
   **while** **not**( $P$ ) **do** **skip**
```

將會導致所有其它行程都無法進入臨界區使得該條件 $P$ 為真，該監視器發生死結.

解決辦法是**條件變數**(condition variables). 概念上，一個條件變數就是一個執行緒佇列 (queue), 其中的執行緒正等待某個條件變為真。每個條件變數 $c$ 關聯著一個斷言 $P_{c}$ . 當一個執行緒等待一個條件變數，該執行緒不算作占用了該監視器，因而其它執行緒可以進入該監視器執行，改變監視器的狀態，通知條件變數 $c$ 其關聯的斷言 $P_{c}$ 在當前狀態下為真.

因此對條件變數存在兩種主要操作:

* `**wait** c` 被一個執行緒呼叫，以等待斷言 $P_{c}$ 被滿足後該執行緒可恢復執行。執行緒掛在該條件變數上等待時，不被認為是占用了監視器.
* `**signal** c` (有時寫作 `**notify** c`) 被一個執行緒呼叫，以指出斷言 $P_{c}$ 現在為真.

在下述例子中，用監視器實現了一個號誌。一個私有整型變數 `s` 需要被互斥存取。監視器中定義了子程式「增加」(V) 與子程式「減少」(P)，整型變數 `s` 不能被減少到小於 0; 因此子程式「減少」必須等到該整型變數是正數時才可執行。使用條件變數 `sIsPositive` 與相關聯的斷言 $P_{sIsPositive}=(s>0)$ .

```
**monitor class** _Semaphore_
{
  **private** _int_ s := 0
  **invariant** s >= 0
  **private** _Condition_ sIsPositive /* **associated with** s > 0 */

  **public method** P()
  {
    **if** s = 0 **then** **wait** sIsPositive
    **assert** s > 0
    s := s - 1
  }

  **public method** V()
  {
    s := s + 1
    **assert** s > 0
    **signal** sIsPositive
  }
}
```

當一個通知 (signal) 發給了一個有執行緒處於等待中的條件變數，則有至少兩個執行緒將要占用該監視器：發出通知的執行緒與等待該通知的某個執行緒。只能有一個執行緒占用該監視器，因此必須做出選擇。兩種理論體系導致了兩種不同的條件變數的實現:

* 阻塞式條件變數 (Blocking condition variables)，把優先級給了被通知的執行緒.
* 非阻塞式條件變數 (Nonblocking condition variables)，把優先級給了發出通知的執行緒.

### 阻塞式條件變數

東尼・霍爾與泊・派克・漢森最早提出的是阻塞式條件變數。發出通知 (signaling) 的執行緒必須等待被通知 (signaled) 的執行緒放棄占用監視器（或者離開監視器，或者等待某個條件變數）。使用阻塞式條件變數的監視器被稱為_霍爾風格_(Hoare-style) 監視器或_通知且急迫等待_(signal-and-urgent-wait) 監視器.

設每個監視器物件有兩個執行緒佇列

* `e` 是入口佇列
* `s` 是已經發出通知的執行緒佇列.

設對於每個條件變數 $c$ , 有一個執行緒佇列

 * `$c$.q`, 所有等待 $c$ 的執行緒的佇列

這些佇列會公平 (fair) 排程，甚至實現為先進先出.

各個環節實現如下 (規定各個環節彼此是互斥的。因此 restart 一個執行緒，並不會立即執行，直到當前環節完成)

```
 enter the monitor:
    enter the method
    if the monitor is locked
        add this thread to e
        block this thread
    else
        lock the monitor
```

```
 leave the monitor:
    schedule
    return from the method
```

```
 **wait** $c$ :
    add this thread to $c$.q
    schedule
    block this thread
```

```
 **signal** $c$ :
    if there is a thread waiting on $c$.q
        select and remove one such thread t from $c$.q
        (t is called "the signaled thread")
        add this thread to s
        restart t
        (so t will occupy the monitor next)
        block this thread
```

```
  schedule :
    if there is a thread on s
      select and remove one thread from s and restart it
      (this thread will occupy the monitor next)
    else if there is a thread on e
      select and remove one thread from e and restart it
      (this thread will occupy the monitor next)
    else
      unlock the monitor
      (the monitor will become unoccupied)
```

`schedule` 子程式選擇下一個執行緒占用監視器，如果沒有候選的執行緒則解鎖監視器.

發出通知的執行緒轉入等待，但會比線上程入口的佇列有更高優先權被排程，這稱為 _"通知且急迫等待"_。另一種方案是 _"通知且等待"_，不設 `s` 佇列，發出通知的執行緒進入 `e` 佇列等待.

某些實現提供了 **signal and return** 操作.

```
 **signal** $c$ **and return** :
    if there is a thread waiting on $c$.q
        select and remove one such thread t from $c$.q
        (t is called "the signaled thread")
        restart t
        (so t will occupy the monitor next)
    else
        schedule
    return from the method
```

如果在每個 **signal** $c$ 的開始處， $P_{c}$ 為真，那麼在 **wait** $c$ 的結尾處 $P_{c}$ 也應為真。 這可由契約式設計來表達。在這些契約中， $I$ 是監視器的不變數.

```
 enter the monitor:
    **postcondition** $I$
```

```
 leave the monitor:
    **precondition** $I$
```

```
 **wait** $c$ :
    **precondition** $I$
    **modifies** the state of the monitor
    **postcondition** $P_{c}$ and $I$
```

```
 **signal** $c$ :
    **precondition** $P_{c}$ and $I$
    **modifies** the state of the monitor
    **postcondition** $I$
```

```
 **signal** $c$ **and return** :
    **precondition** $P_{c}$ and $I$
```

在上述契約中，設定 $I$ and $P_{c}$ 不依賴於任何佇列長度.

如果可以查詢條件變數所關聯的佇列上處於等待的執行緒的數量，可以使用更為複雜的契約。例如，一個有用的契約對，無需不變數就允許監視器的占用被傳遞

```
 **wait** $c$ :
    **precondition** $I$
    **modifies** the state of the monitor
    **postcondition** $P_{c}$
```

```
 **signal** $c$
    **precondition** (**not** empty($c$) **and** $P_{c}$) **or** (empty($c$) **and** $I$)
    **modifies** the state of the monitor
    **postcondition** $I$
```

參見
Howard
and
Buhr _et al.,_ 有更多資訊。

 
特別需要注意，斷言 $P_{c}$ 完全是由編程者負責，編程者需要在頭腦中保持對斷言有一致的 (consistent) 定義。

下例是用阻塞式監視器實現一個有界的、執行緒安全的棧。即多執行緒並行存取這個棧時，在任意時刻最多只有一個執行緒執行 push 或 pop 操作。

```
**monitor class** _SharedStack_ {
  **private const** capacity := 10
  **private** _int_[capacity] A
  **private** _int_ size := 0
  **invariant** 0 <= size **and** size <= capacity
  **private** _BlockingCondition_ theStackIsNotEmpty /* **associated with** 0 < size **and** size <= capacity */
  **private** _BlockingCondition_ theStackIsNotFull /* **associated with** 0 <= size **and** size < capacity */
```

```
  **public method** push(_int_ value)
  {
    **if** size = capacity **then** **wait** theStackIsNotFull
    **assert** 0 <= size **and** size < capacity
    A[size] := value ; size := size + 1
    **assert** 0 < size **and** size <= capacity
    **signal** theStackIsNotEmpty **and return**
  }
```

```
  **public method** _int_ pop()
  {
    **if** size = 0 **then** **wait** theStackIsNotEmpty
    **assert** 0 < size **and** size <= capacity
    size := size - 1 ;
    **assert** 0 <= size **and** size < capacity
    **signal** theStackIsNotFull  **and return** A[size]
  }
}
```

### 非阻塞式條件變數

_非阻塞式條件變數_ (也稱作 _"Mesa 風格"_ 條件變數或 _"通知且繼續"_(signal and continue) 條件變數), 發出通知的執行緒並不會失去監視器的占用權。被通知的執行緒將會被移入監視器入口的 `e` 佇列。不需要 `s` 佇列。pthread 中的條件變數就是這種非阻塞式：要先顯式獲得互斥加鎖（pthread\_mutex\_lock），呼叫 pthread\_cond\_wait 時隱式對互斥鎖解鎖並進入阻塞睡眠，被喚醒後還要再顯式獲得互斥加鎖。

非阻塞式條件變數經常把 **signal** 操作稱作 **notify** — . 也常用 **notify all** 操作把該條件變數關聯的佇列上所有的執行緒移入 `e` 佇列.

各種操作定義如下. (規定各種操作都是互斥的，執行緒被 restart 並不會立即執行，直到發起的操作完成)

```
 enter the monitor:
    enter the method
    if the monitor is locked
      add this thread to e
      block this thread
    else
      lock the monitor
```

```
 leave the monitor:
    schedule
    return from the method
```

```
 **wait** $c$ :
    add this thread to $c$.q
    schedule
    block this thread
```

```
 **notify** $c$ :
    if there is a thread waiting on $c$.q
        select and remove one thread t from $c$.q
        (t is called "the notified thread")
        move t to e
```

```
 **notify all** $c$ :
    move all threads waiting on $c$.q to e
```

```
  schedule :
    if there is a thread on e
      select and remove one thread from e and restart it
    else
      unlock the monitor
```

一個變種實現，把被通知的 (notified) 執行緒移入佇列 `w`, 具有比 `e` 更高的優先級。參見
Howard
and
Buhr _et al._。

可以把斷言 $P_{c}$ 關聯於條件變數 $c$ ，因而 $P_{c}$ `**wait** $c$` 返回時期望為真。但是，這必須確保發出通知的執行緒結束到被通知的執行緒恢復執行這一時間段內， $P_{c}$ 保持為真。這一時間段內可能會有其它執行緒占用過監視器。因此通常必須把每個 **wait** 操作用一個迴圈包裹起來：

```
  **while** **not**( $P$ ) **do** **wait** c
```

其中 $P$ 是一個條件，強於 $P_{c}$ . 操作 `**notify** $c$` 與 `**notify all** $c$` 被視為 "提示"(hints) 某個等待佇列的 $P$ 可能為真.
上述迴圈的每一次迭代，表示失去了一次通知。

一個銀行帳戶的例子，取款執行緒將等待資金已經完成注入帳戶之後再執行。

```
**monitor class** _Account_ {
  **private** _int_ balance := 0
  **invariant** balance >= 0
  **private** _NonblockingCondition_ balanceMayBeBigEnough
```

```
  **public method** withdraw(_int_ amount)
     **precondition** amount >= 0
  {
    **while** balance < amount **do** **wait** balanceMayBeBigEnough
    **assert** balance >= amount
    balance := balance - amount
  }
```

```
  **public method** deposit(_int_ amount)
     **precondition** amount >= 0
  {
    balance := balance + amount
    **notify all** balanceMayBeBigEnough
  }
}
```

在這個例子中，被等待的條件是取款金額大於存款餘額，存款執行緒不可能知道取款金額，因此存款執行緒發出的通知的意涵是提示所有等待中的取款執行緒檢查它自身的斷言是否為真。

### 隱式條件變數監視器

Java 程式設計語言中，每個物件都可以作為一個監視器。需要互斥使用的方法必須明確標示關鍵字 **synchronized**。 代碼塊也可以標示關鍵字 **synchronized**。

不使用明確的條件變數，Java 的這種監視器在入口佇列之外，使用單獨的條件等待佇列。所有等待的執行緒進入這個佇列，所有的 **notify** 與 **notify all** 操作也施加於這個佇列。這種方法已經被其它程式設計語言使用，如 C#。

### 隱式通知

另一種實現方法是忽略 **signal** 操作。當一個執行緒交出監視器占用權 (returning 或者 waiting)，所有處於等待狀態的執行緒的斷言都被檢查，直到發現某個執行緒的斷言為真。在這種系統中，不需要條件變數，但是斷言必須明確編碼。 wait 操作的契約：

```
 **wait** $P$:
    **precondition** $I$
    **modifies** the state of the monitor
    **postcondition** $P$ and $I$
```

### Posix Thread 中的條件變數

pthread 中，條件變數實際上是一個阻塞執行緒處於睡眠狀態的執行緒佇列。每個條件變數都必須與一個（且建議只能是一個）互斥鎖配套使用。一個執行緒首先獲得互斥鎖，然後檢查或者修改「條件」；如果條件不成立，則呼叫 pthread\_cond\_wait ()，依次實施 3 個操作：

1. 對當前互斥鎖解鎖（以便其它執行緒可以存取或者修改「條件」）
2. 把執行緒自身阻塞掛起到互斥鎖的執行緒佇列中
3. 被其它執行緒的訊號從互斥鎖的執行緒佇列喚醒後，對當前配套的互斥鎖申請加鎖，如果加鎖未能成功，則阻塞掛起到當前互斥鎖上。pthread\_cond\_wait () 函式將不返回直到執行緒獲得配套的互斥鎖。

執行緒離開「條件」的臨界區時，必須對當前互斥鎖執行解鎖。

### Windows Thread 中的條件變數

從 Windows Vista 開始，Windows Thread 用 critical section 與條件變數配合，二者均為使用者態同步物件，不能跨行程使用。使用 API 函式 InitializeConditionVariable 建立條件變數；函式 SleepConditionVariableCS 用於釋放臨界區並阻塞在條件變數上；函式 WakeConditionVariable 或 WakeAllConditionVariable 喚醒掛在條件變數上的執行緒。

也可配套使用讀寫鎖（Slim Reader/Writer (SRW) Locks）。

### Spurious wakeup

假喚醒是 POSIX Threads 與 Windows API 使用條件變數時可能發生的複雜情形。一個掛在條件變數上的執行緒被 signaled，正在等待的條件仍有可能不成立。假喚醒（Spurious wakeup）是指即使沒有執行緒 signaled 該條件變數，掛在該條件變數上的執行緒卻被喚醒。因此，應該用 while 迴圈包圍條件變數等待操作：

### stolen wakeups

被偷走的喚醒是 POSIX Threads 與 Windows API 使用條件變數時，執行緒呼叫 g\_cond\_signal 時，另一個執行緒已經取得了 mutex 使得期望的條件不再滿足，因此被喚醒的執行緒面臨著條件不成立。因此，應該用 while 迴圈包圍條件變數等待操作.

## 歷史

東尼・霍爾與泊・派克・漢森在 1972 年形成了監視器的構思，根據他們自己更早的想法與艾茲赫爾・戴克斯特拉的工作.

泊・派克・漢森第一個實現了監視器。 東尼・霍爾發展了理論框架並證明了與號誌等價。

監視器不久用於單任務作業系統的行程間通訊.

已經支援監視器的程式設計語言：

* Ada (從 Ada 95 (作為 protected objects) 開始)
* C# (以及其它使用.NET Framework 的程式設計語言)
* C++ (從 C++11 開始，詳見 b:C++/STL/ConditionVariable)
* Concurrent Euclid
* Concurrent Pascal
* D
* Delphi (Delphi 2009 及更高版本，使用 TObject.Monitor)
* Java (使用 wait 與 notify methods)
* Mesa
* Modula-3
* Python (通過 threading.Condition （頁面存檔備份，存於網際網路檔案館） object)
* Ruby
* Squeak Smalltalk
* Turing, Turing+ 與 Object-Oriented Turing
* μC++

許多庫已經允許在程式設計語言沒有本地支援時構建監視器。當庫呼叫時，編程者負責明確表示互斥執行的代碼塊的開始與結尾. Pthreads 就是這樣一個庫.

## 參考文獻

## 外部連結

* "Monitors: An Operating System Structuring Concept （頁面存檔備份，存於網際網路檔案館）" by Charles Antony Richard Hoare
* "Signalling in Monitors" by John H. Howard
* "Experience with Processes and Monitors in Mesa （頁面存檔備份，存於網際網路檔案館）" by Butler W. Lampson and David D. Redell
* pthread\_cond\_wait （頁面存檔備份，存於網際網路檔案館） - description from the Open Group Base Specifications Issue 6, IEEE Std 1003.1
* "Block on a Condition Variable" by Dave Marshall
* "Strategies for Implementing POSIX Condition Variables on Win32" by Douglas C. Schmidt and Irfan Pyarali
* Condition Variable Routines （頁面存檔備份，存於網際網路檔案館） from the Apache Portable Runtime Library
* wxCondition description （頁面存檔備份，存於網際網路檔案館）
* boost::condition class description
* ZThread Condition Class Reference （頁面存檔備份，存於網際網路檔案館）
* Wefts::Condition Class Reference （頁面存檔備份，存於網際網路檔案館）
* ACE\_Condition Class Template Reference
* QWaitCondition Class Reference
* Common C++ Conditional Class Reference （頁面存檔備份，存於網際網路檔案館）
* at::ConditionalMutex Class Reference （頁面存檔備份，存於網際網路檔案館）
* threads::shared （頁面存檔備份，存於網際網路檔案館） - Perl extension for sharing data structures between threads