管程

管程 (英语：Moniters，也称为监视器) 是对多个工作线程实现互斥访问共享資源的对象或模块。這些共享資源一般是硬體裝置或一群變數。管程实现了在一个时间点，最多只有一个线程在执行它的某个子程序。与那些通过修改数据结构实现互斥访问的并发程序设计相比，管程实现很大程度上简化了程序设计。

管程提供了一种机制，线程可以临时放弃互斥访问，等待某些条件得到满足后，重新获得执行权恢复它的互斥访问。

管程是东尼·霍尔 与泊·派克·漢森 提出的，并由泊·派克·漢森首次在并行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$为真，才能继续执行。在一个忙等待(busy waiting)循环中

   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$现在为真.

下属例子, 用管程实现了一个信号量. 管程定义了子程序“增加”(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)，把优先级给了发出通知的线程.

阻塞式条件变量

东尼·霍尔与Per Brinch Hansen最早提出的是阻塞式条件变量. 发出通知(signaling)的线程必须等待被通知(signaled)的线程放弃占用管程（或者离开管程，或者等待某个条件变量）。使用阻塞式条件变量的管程被称为霍尔风格(Hoare-style)管程或通知且急迫等待(signal-and-urgent-wait)管程.

霍尔风格管程，有两个条件变量a与b. 根据Buhr et al.

设每个管程对象有两个线程队列

• 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., for more

特别需要注意，断言$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队列.

Mesa风格的管程，有两个条件变量a与b

非阻塞式条件变量经常把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. for further discussion.

可以把断言$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风格管程

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$

历史

C. A. R. 霍尔与Per Brinch Hansen在1972年形成了管程的构思, 根据他们自己更早的想法与艾兹赫尔·戴克斯特拉的工作. Brinch Hansen第一个实现了管程. 霍尔发展了理论框架并证明了与信号量等价.

管程不久用于单任务操作系统的进程间通信.

已经支持管程的程序设计语言：

• Ada 从Ada 95 (作为protected objects)
• C# (以及其它使用.NET Framework的程序设计语言)
• en:Concurrent Euclid
• en:Concurrent Pascal
• D
• Delphi (Delphi 2009及更高版本，使用TObject.Monitor)
• Java (使用wait与notify methods)
• Mesa
• en:Modula-3
• Python (通过threading.Condition object)
• Ruby
• Squeak Smalltalk
• Turing, en:Turing+与en:Object-Oriented Turing
• en:μ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