监视器 (程序同步化)

监视器 (Monitors，也称为监视器) 是一种程序结构，结构内的多个子程序（对象或模块）形成的多个工作线程互斥访问共享资源。这些共享资源一般是硬件或一群变数。管程实现了在一个时间点，最多只有一个线程在执行管程的某个子程序。与那些通过修改数据结构实现互斥访问的并发程序设计相比，管程实现很大程度上简化了程序设计。

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

管程是东尼·霍尔与泊·派克·汉森提出的，并由泊·派克·汉森首次在并行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'''( <math>P</math> ) '''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)管程.

<image>

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

- `e`是入口队列
- `s`是已经发出通知的线程队列.

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

- `<math>c</math>.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''' <math>c</math> :
    add this thread to <math>c</math>.q
    schedule
    block this thread

 '''signal''' <math>c</math> :
    if there is a thread waiting on <math>c</math>.q
        select and remove one such thread t from <math>c</math>.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''' <math>c</math> '''and return''' :
    if there is a thread waiting on <math>c</math>.q
        select and remove one such thread t from <math>c</math>.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''' <math>I</math>

 leave the monitor:
    '''precondition''' <math>I</math>

 '''wait''' <math>c</math> :
    '''precondition''' <math>I</math>
    '''modifies''' the state of the monitor
    '''postcondition''' <math>P_c</math> and <math>I</math>

 '''signal''' <math>c</math> :
    '''precondition''' <math>P_c</math> and <math>I</math>
    '''modifies''' the state of the monitor
    '''postcondition''' <math>I</math>

 '''signal''' <math>c</math> '''and return''' :
    '''precondition''' <math>P_c</math> and <math>I</math>
```

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

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

```
 '''wait''' <math>c</math> :
    '''precondition''' <math>I</math>
    '''modifies''' the state of the monitor
    '''postcondition''' <math>P_c</math>

 '''signal''' <math>c</math>
    '''precondition''' ('''not''' empty(<math>c</math>) '''and''' <math>P_c</math>) '''or''' (empty(<math>c</math>) '''and''' <math>I</math>)
    '''modifies''' the state of the monitor
    '''postcondition''' <math>I</math>
```

参见Howard与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`队列。POSIX线程中的条件变量就是这种非阻塞式：要先显式获得互斥加锁（pthread_mutex_lock），调用pthread_cond_wait时隐式对互斥锁解锁并进入阻塞睡眠，被唤醒后还要再显式获得互斥加锁。

<image>

非阻塞式条件变量经常把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''' <math>c</math> :
    add this thread to <math>c</math>.q
    schedule
    block this thread

 '''notify''' <math>c</math> :
    if there is a thread waiting on <math>c</math>.q
        select and remove one thread t from <math>c</math>.q
        (t is called "the notified thread")
        move t to e

 '''notify all''' <math>c</math> :
    move all threads waiting on <math>c</math>.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与Buhr et al.。

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

```
  '''while''' '''not'''( <math>P</math> ) '''do''' '''wait''' c
```

其中$P$是一个条件，强于$P_c$. 操作`'''notify''' <math>c</math>`与`'''notify all''' <math>c</math>`被视为"提示"(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
  }
}
```

在这个例子中，被等待的条件是取款金额大于存款余额，存款线程不可能知道取款金额，因此存款线程发出的通知的意涵是提示所有等待中的取款线程检查它自身的断言是否为真。

### 隐式条件变量管程

<image>

Java程序设计语言中，每个对象都可以作为一个管程。需要互斥使用的方法必须明确标示关键字synchronized。代码块也可以标示关键字synchronized。

不使用明确的条件变量, Java的这种管程在入口队列之外，使用单独的条件等待队列. 所有等待的线程进入这个队列，所有的notify与notify all操作也施加于这个队列。这种方法已经被其它程序设计语言使用，如C#。

### 隐式通知

另一种实现方法是忽略signal操作。当一个线程交出管程占用权(returning或者waiting)，所有处于等待状态的线程的断言都被检查，直到发现某个线程的断言为真。在这种系统中，不需要条件变量，但是断言必须明确编码。wait操作的契约：

```
 '''wait''' <math>P</math>:
    '''precondition''' <math>I</math>
    '''modifies''' the state of the monitor
    '''postcondition''' <math>P</math> and <math>I</math>
```

### Posix Thread中的条件变量

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

- 对当前互斥锁解锁（以便其它线程可以访问或者修改“条件”）
- 把线程自身阻塞挂起到互斥锁的线程队列中
- 被其它线程的信号从互斥锁的线程队列唤醒后，对当前配套的互斥锁申请加锁，如果加锁未能成功，则阻塞挂起到当前互斥锁上。pthread_cond_wait 函数将不返回直到线程获得配套的互斥锁。

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

### Windows Thread中的条件变量

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

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

### Spurious wakeup

假唤醒是POSIX Threads与Windows API使用条件变量时可能发生的复杂情形。一个挂在条件变量上的线程被signaled，正在等待的条件仍有可能不成立。假唤醒（Spurious wakeup）是指即使没有线程signaled该条件变量，挂在该条件变量上的线程却被唤醒。因此，应该用while循环包围条件变量等待操作：

```c
/* 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使得期望的条件不再满足，因此被唤醒的线程面临着条件不成立。因此，应该用while循环包围条件变量等待操作.

## 历史

东尼·霍尔与泊·派克·汉森在1972年形成了管程的构思, 根据他们自己更早的想法与艾兹赫尔·戴克斯特拉的工作。泊·派克·汉森第一个实现了管程。东尼·霍尔发展了理论框架并证明了与信号量等价。

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

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

- Ada (从 Ada 95 (作为protected objects) 开始)
- C# (以及其它使用.NET Framework的程序设计语言)
- C++ (从 C++11 开始，详见b:C++/STL/ConditionVariable)
- D
- Delphi (Delphi 2009及更高版本，使用TObject.Monitor)
- Java (使用wait与notify methods)
- Mesa
- Modula-3
- Python（通过threading.Condition对象）
- Ruby
- Squeak Smalltalk
- Turing, 与

许多库已经允许在程序设计语言没有本地支持时构建管程。当库调用时，编程者负责明确表示互斥执行的代码块的开始与结尾. 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