監視器 (程序同步化)

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

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

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

在程式語言Concurrent 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^[3] and Buhr et al.,^[4]有更多資訊。

特別需要注意，斷言 $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^[3] and Buhr et al.^[4]。

可以把斷言 $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個操作：

對當前互斥鎖解鎖（以便其它線程可以訪問或者修改「條件」）
把線程自身阻塞掛起到互斥鎖的線程佇列中
被其它線程的訊號從互斥鎖的線程佇列喚醒後，對當前配套的互斥鎖申請加鎖，如果加鎖未能成功，則阻塞掛起到當前互斥鎖上。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該條件變數，掛在該條件變數上的線程卻被喚醒。^[5]因此，應該用while迴圈包圍條件變數等待操作：

/* In any waiting thread: */
while(!buf->full)
	wait(&buf->cond, &buf->lock);

/* In any other thread: */
if(buf->n >= buf->size){
	buf->full = 1;
	signal(&buf->cond);
}

stolen wakeups[編輯]

被偷走的喚醒是POSIX Threads與Windows API使用條件變數時，線程呼叫g_cond_signal時，另一個線程已經取得了mutex使得期望的條件不再滿足，因此被喚醒的線程面臨着條件不成立。^[6]^[7]因此，應該用while迴圈包圍條件變數等待操作.

歷史[編輯]

東尼·霍爾與泊·派克·漢森在1972年形成了監視器的構思, 根據他們自己更早的想法與艾茲赫爾·戴克斯特拉的工作. ^[8] 泊·派克·漢森第一個實現了監視器。東尼·霍爾發展了理論框架並證明了與訊號量等價。

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

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

Ada (從 Ada 95 (作為protected objects) 開始)
C# (以及其它使用.NET Framework的程式語言)
C++ (從 C++11 開始，詳見b:C++/STL/ConditionVariable)
Concurrent Euclid（英語：Concurrent Euclid）
Concurrent Pascal（英語：Concurrent Pascal）
D
Delphi (Delphi 2009及更高版本，使用TObject.Monitor)
Java (使用wait與notify methods)
Mesa
Modula-3
Python（通過threading.Condition^[9]對象）
Ruby
Squeak Smalltalk
Turing（英語：Turing (programming language)）, Turing+（英語：Turing+）與Object-Oriented Turing（英語：Object-Oriented Turing）
μC++（英語：μC++）

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

參考文獻[編輯]

^ Hoare, C. A. R. (1974), "Monitors: an operating system structuring concept". Comm. A.C.M. 17(10), 549–57. [1]
^ Brinch Hansen, P. (1975). "The programming language Concurrent Pascal". IEEE Trans. Softw. Eng. 2 (June), 199–206.
^ ^3.0 ^3.1 John Howard (1976), "Signaling in monitors". Proceedings of the 2nd International Conference on Software Engineering, 47–52
^ ^4.0 ^4.1 Buhr, P.H; Fortier, M., Coffin, M.H. (1995). "Monitor classification". ACM Computing Surveys (CSUR) 27(1). 63–107. [2]
^ David R. Butenhof《Programming with POSIX Threads》 ISBN 0-201-63392-2: "This means that when you wait on a condition variable, the wait may (occasionally) return when no thread specifically broadcast or signaled that condition variable. Spurious wakeups may sound strange, but on some multiprocessor systems, making condition wakeup completely predictable might substantially slow all condition variable operations. The race conditions that cause spurious wakeups should be considered rare."
^ MSDN:SleepConditionVariableCS function. [2017-02-16]. （原始內容存檔於2017-02-16）.
^ GNOME DEVELOPER: Threads Functions. [2017-02-16]. （原始內容存檔於2020-08-14）.
^ Brinch Hansen, P. (1993). "Monitors and concurrent Pascal: a personal history", The second ACM SIGPLAN conference on History of programming languages 1–35. Also published in ACM SIGPLAN Notices 28(3), March 1993. [3]
^ threading.Condition （頁面存檔備份，存於互聯網檔案館）

外部連結[編輯]

"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

[1] Hoare, C. A. R. (1974), "Monitors: an operating system structuring concept". Comm. A.C.M. 17(10), 549–57. [1]

[2] Brinch Hansen, P. (1975). "The programming language Concurrent Pascal". IEEE Trans. Softw. Eng. 2 (June), 199–206.

[Howard76-3] 3.0 ^3.1 John Howard (1976), "Signaling in monitors". Proceedings of the 2nd International Conference on Software Engineering, 47–52

[Buhr95-4] 4.0 ^4.1 Buhr, P.H; Fortier, M., Coffin, M.H. (1995). "Monitor classification". ACM Computing Surveys (CSUR) 27(1). 63–107. [2]

[5] David R. Butenhof《Programming with POSIX Threads》 ISBN 0-201-63392-2: "This means that when you wait on a condition variable, the wait may (occasionally) return when no thread specifically broadcast or signaled that condition variable. Spurious wakeups may sound strange, but on some multiprocessor systems, making condition wakeup completely predictable might substantially slow all condition variable operations. The race conditions that cause spurious wakeups should be considered rare."

[6] MSDN:SleepConditionVariableCS function. [2017-02-16]. （原始內容存檔於2017-02-16）.

[7] GNOME DEVELOPER: Threads Functions. [2017-02-16]. （原始內容存檔於2020-08-14）.

[8] Brinch Hansen, P. (1993). "Monitors and concurrent Pascal: a personal history", The second ACM SIGPLAN conference on History of programming languages 1–35. Also published in ACM SIGPLAN Notices 28(3), March 1993. [3]

[9] threading.Condition （頁面存檔備份，存於互聯網檔案館）

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]