茶年 · 中文维基百科

監視器 (程序同步化)

Wikipedia · 2026-06-07 维基百科 👁 2 阅读

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

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

管程是东尼·霍尔与泊·派克·漢森提出的，并由泊·派克·漢森首次在并行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 = 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与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 e队列. 不需要s队列。POSIX线程中的条件变量就是这种非阻塞式：要先显式获得互斥加锁（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因此，应该用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使得期望的条件不再满足，因此被唤醒的线程面临着条件不成立。因此，应该用while循环包围条件变量等待操作.

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

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

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

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

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

参考文献
外部链接

#软件设计模式 #程序架構 #并发控制

评论 (0)

  • 还没有评论，来抢沙发吧。