监视器

一个管程包含:

多个彼此可以交互并共用资源的线程

多个与资源使用有关的变量

一个互斥锁

一个用来避免竞态条件的不变量

一个管程的程序在运行一个线程前会先获取互斥锁，直到完成线程或是线程等待某个条件被满足才会放弃互斥锁。若每个执行中的线程在放弃互斥锁之前都能保证不变量成立，则所有线程皆不会导致竞态条件成立。

以下这个银行账户的提款／存款事务的管程是个简单的例子：

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程序设计语言显式检查不变量。

对于许多应用场合，互斥操作是不够用的。线程可能需要等待某个条件为真，才能继续执行。在一个忙碌等待循环中

while not( ) do skip

将会导致所有其它进程都无法进入临界区使得该条件为真，该管程发生死锁.

解决办法是条件变量(condition variables). 概念上，一个条件变量就是一个线程队列(queue), 其中的线程正等待某个条件变为真。每个条件变量关联着一个断言. 当一个线程等待一个条件变量，该线程不算作占用了该管程，因而其它线程可以进入该管程执行，改变管程的状态，通知条件变量其关联的断言在当前状态下为真.

因此对条件变量存在两种主要操作:

wait被一个线程调用，以等待断言被满足后该线程可恢复执行. 线程挂在该条件变量上等待时，不被认为是占用了管程.

signal (有时写作notify)被一个线程调用，以指出断言现在为真.

在下述例子中, 用管程实现了一个信号量. 一个私有整型变量需要被互斥访问。管程中定义了子程序“增加”(V)与子程序“减少”(P)，整型变量不能被减少到小于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)管程.

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

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

是入口队列

是已经发出通知的线程队列.

设对于每个条件变量, 有一个线程队列

, 所有等待的线程的队列

这些队列会公平(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 : add this thread to .q schedule block this thread signal : if there is a thread waiting on .q select and remove one such thread t from .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)

子程序选择下一个线程占用管程，如果没有候选的线程则解锁管程.

发出通知的线程转入等待，但会比在线程入口的队列有更高优先权被调度，这称为"通知且急迫等待"。另一种方案是"通知且等待"，不设队列，发出通知的线程进入队列等待.

某些实现提供了signal and return操作.

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

如果在每个signal 的开始处，为真, 那么在wait 的结尾处也应为真。 这可由契约式设计来表达. 在这些契约中, 是管程的不变量.

enter the monitor: postcondition leave the monitor: precondition wait : precondition modifies the state of the monitor postcondition and signal : precondition and modifies the state of the monitor postcondition signal and return : precondition and

在上述契约中，设定 and 不依赖于任何队列长度.

如果可以查询条件变量所关联的队列上处于等待的线程的数量，可以使用更为复杂的契约。例如，一个有用的契约对，无需不变量就允许管程的占用被传递

wait : precondition modifies the state of the monitor postcondition signal precondition ( not empty( ) and ) or (empty( ) and ) modifies the state of the monitor postcondition

参见HowardandBuhr et al.,有更多信息。

特别需要注意，断言完全是由编程者负责，编程者需要在头脑中保持对断言有一致的(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)条件变量), 发出通知的线程并不会失去管程的占用权. 被通知的线程将会被移入管程入口的队列. 不需要队列。pthread中的条件变量就是这种非阻塞式：要先显式获得互斥加锁（pthread_mutex_lock），调用pthread_cond_wait时隐式对互斥锁解锁并进入阻塞睡眠，被唤醒后还要再显式获得互斥加锁。

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

非阻塞式条件变量经常把signal操作称作notify — . 也常用notify all操作把该条件变量关联的队列上所有的线程移入队列.

各种操作定义如下. (规定各种操作都是互斥的，线程被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 : add this thread to .q schedule block this thread notify : if there is a thread waiting on .q select and remove one thread t from .q (t is called "the notified thread") move t to e notify all : move all threads waiting on .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)线程移入队列, 具有比更高的优先级. 参见HowardandBuhr et al.。

可以把断言关联于条件变量，因而wait返回时期望为真. 但是，这必须确保发出通知的线程结束到被通知的线程恢复执行这一时间段内，保持为真. 这一时间段内可能会有其它线程占用过管程。因此通常必须把每个wait操作用一个循环包裹起来：

while not( ) do wait c

其中是一个条件，强于. 操作notify与notify all被视为"提示"(hints)某个等待队列的可能为真.上述循环的每一次迭代，表示失去了一次通知。

一个银行账户的例子，取款线程将等待资金已经完成注入账户之后再执行。

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 : precondition modifies the state of the monitor postcondition and

pthread中，条件变量实际上是一个阻塞线程处于睡眠状态的线程队列。每个条件变量都必须与一个（且建议只能是一个）互斥锁配套使用。一个线程首先获得互斥锁，然后检查或者修改“条件”；如果条件不成立，则调用pthread_cond_wait()，依次实施3个操作：

1. 对当前互斥锁解锁（以便其它线程可以访问或者修改“条件”）

   把线程自身阻塞挂起到互斥锁的线程队列中

   被其它线程的信号从互斥锁的线程队列唤醒后，对当前配套的互斥锁申请加锁，如果加锁未能成功，则阻塞挂起到当前互斥锁上。pthread_cond_wait() 函数将不返回直到线程获得配套的互斥锁。

线程离开“条件”的临界区时，必须对当前互斥锁执行解锁。

从Windows Vista开始，Windows Thread用critical section与条件变量配合，二者均为用户态同步对象，不能跨进程使用。使用API函数InitializeConditionVariable创建条件变量；函数SleepConditionVariableCS用于释放临界区并阻塞在条件变量上；函数WakeConditionVariable或 WakeAllConditionVariable唤醒挂在条件变量上的线程。

也可配套使用读写锁（Slim Reader/Writer (SRW) Locks）。

假唤醒是POSIX Threads与Windows API使用条件变量时可能发生的复杂情形。一个挂在条件变量上的线程被signaled，正在等待的条件仍有可能不成立。假唤醒（Spurious wakeup）是指即使没有线程signaled该条件变量，挂在该条件变量上的线程却被唤醒。因此，应该用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);}

被偷走的唤醒是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)

en:Concurrent Euclid

en:Concurrent Pascal

D

Delphi (Delphi 2009及更高版本，使用TObject.Monitor)

Java (使用wait与notify methods)

Mesa

en:Modula-3

Python (通过 object)

Ruby

Squeak Smalltalk

Turing, en:Turing+与en:Object-Oriented Turing

en:μC++

许多库已经允许在程序设计语言没有本地支持时构建管程。当库调用时，编程者负责明确表示互斥执行的代码块的开始与结尾. Pthreads就是这样一个库.