監視器 (程序同步化)

監視器 (英語：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]