监视器 (程序同步化)

互斥

一个监视器包含:

• 许多的会彼此交互并共用资源的
• 许多与资源使用有关的变量
• 一个
• 一个用来避免的

一个监视器的程序在运行工作前会先关上互斥锁，直到完成工作或是等待其他条件时才会解锁。若每个程序在解开互斥锁之前都能保证不变量成立，则所有工 作皆不会导致条件竞争发生。

以下这个提款／存款的银行监视器是个简单的例子：

monitor account {
  int balance := 0
  
  function withdraw(int amount) {
    if amount < 0 then 錯誤 "提款金額不能為負數"
    else if balance < amount then 錯誤 "餘額不足"
    else balance := balance - amount
  }
  
  function deposit(int amount) {
    if amount < 0 then 錯誤 "存款金額不能為負數"
    else balance := balance + amount
  }
}

这个例子中的是“任何操作运行前 balance 变量必须反映正确的余额”。一般而言，不变量的条件不被写在程序中，而在中有相关说明，然而有些像(Eiffe) 的函数编程语言会检查不变量。互斥锁由自动加入，使得监视器较为可靠。

[] 条件变量 (Condition Variable)

为了避免程序进入状态(busy waiting state)，程序必须能彼此告知对方关注的事件。监视器通过条件变量提供这项功能。当某个程序运行前需要某些先决条件时，它会等待相关的 条件变量备妥。在等待期间它会放开互斥锁并从运行程序清单中被除名。后续其他运行的程序会通过条件变量通知等待中的程序。程序接获通知后会取得互斥锁并准 备运行。

以下的监视器使用条件变量实现一个程序间的通信，使得同时只有一个整数值能被存储。

monitor channel {
  int contents
  boolean full := false
  condition snd
  condition rcv

  function send(int sent) {
    if full then wait(rcv)
    contents := sent
    full := true
    notify(snd)
  }

  function receive() {
    var int received

    if not full then wait(snd)
    received := contents
    full := false
    notify(rcv)
    return received
  }
}

由于程序在等待条件时会立即失去互斥锁，所以等待者必须在进入等待状态前确定监视器的不变量没被破坏。在上述的例子中通知者也是如此。

在监视器早期的实现中，条件变量通知后会导致等待程序获得互斥锁并立即开始运行(称为 Hoare sematics)，因此可以保证它所等待的条件保持成立。该功能的实现既复杂又耗时，且随时有可能在期间打断程序的运行，故研究人员发展了其其它的替代方 法。

在现今的实现中，事件通知并不会让运行中的程序失去运行的权利(称为 Mesa sematics)，而会让等待中的程序进入运行就绪的状态。发出通知的程序会继续持有互斥锁，直到退出为止。此方法的副作用是程序发出通知前并不需要维 护监视器的不变量，所以当被通知的程序恢复运行时必须再次确认它所等待的条件是否遭到更动。

例如监视器一个的程序包含以下叙述：if test then wait(cv)则 另一个程序有可能在test成立后进入监视器，并且在等候条件的程序接获通知并继续运行前使test不成立。因此这个叙述应该改写为while test do wait(cv)使程序在继续运行前再次确认条件是否成立。

在实际上有 "notifyAll" 或 "broadcast" 操作，用以通知所有等待某条件的程序。这项操作很实用，例如许多程序都在等待各自需要的存储空间时，一旦有空间被释放后这些程序都会获得通知并继续运行。

以下是条件变量的实现示例：

conditionVariable{
  int queueSize = 0;
  semaphore lock;
  semaphore waiting;
  
  wait(){
     lock.acquire();
     queueSize++;
     lock.release();
     waiting.down();
  }
  
  signal(){
     lock.acquire();
     if (queueSize > 0){
        waiting.up();
     }
     lock.release();
  }
}