モニタ (同期)

並行計算の領域でモニタ（）とは、複数のスレッドの同期を実現するための構成であり、コンピュータのリソースを排他的に使用することを可能にしたり、スレッド同士が競合状態に陥るのを防ぐためのものである。モニタは、スレッドの状況に関するシグナルを他のスレッドに伝えるメカニズムを備える。

が発明し、に最初に実装され、Solo Operating System でのプロセス間通信方式として使われた。

相互排他
モニタは以下のものから構成される:
 共有リソースを操作するプロシージャ群（モニタプロシージャ、モニタ関数）
 ミューテックスロック
 リソースと結び付けられた変数
 競合状態を防ぐために仮定されるモニタ不変条件

モニタ・プロシージャは何かをする前にロックをかけ、処理が完了するか、ある条件を待つことになるまでそれをかけておく（条件については後述）。各プロシージャがロックを解放する際に不変条件が真であることを保証するなら、競合状態となるようなリソースの状態は各タスクからは見えないということになる。

単純な例として、銀行口座のトランザクションのためのモニタを考える。

 monitor account {
   int balance := 0
   
   function withdraw(int amount) {
     if amount < 0 then error "Amount may not be negative"
     else if balance < amount then error "Insufficient funds"
     else balance := balance - amount
   }
   
   function deposit(int amount) {
     if amount < 0 then error "Amount may not be negative"
     else balance := balance + amount
   }
 }

この場合のモニタ不変条件は、簡単に言えば「新たな操作を行う際にそれ以前の全操作が balance に反映されていなければならない」ということになる。これはコード自身には書かれていないが、通常コメントに記載されるだろう。例えばEiffelのような言語は不変条件のチェックを取り入れており、ロックはコンパイラによって追加される。これはプログラマがロックとアンロックをいちいち書かなければならない言語よりも安全で信頼性が高い。

条件変数

ビジーウェイト状態となるのを防ぐため、プロセスは互いにそのイベントを通知する手段を持っている必要がある。モニタはこれを条件変数（condition variable）で実現する。モニタが処理を進める際にある条件が真になっていなければならないとしたとき、対応する条件変数上で待つ。待つにあたってロックを解放し、そのプロセスは実行可能な状態ではなくなる。別のプロセスがその後その条件を真にした場合、条件変数を使ってその条件を待っているプロセスに通知する。通知されたプロセスは再度実行可能状態となってロックを獲得し、処理を続行できる。

以下のモニタは条件変数を使ってプロセス間通信チャンネルを実装している。この通信チャンネルは一度に1つの整数しか格納できない。

 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
   }
 }

ある条件上で待ち状態となる際にロックを解放させられるため、待とうとするプロセス（スレッド）は実際に待ち状態となる前にモニタ不変条件が真であることを保証しなければならない。上の例では通知する側にも同じことが言える。

初期のモニタの実装では、条件変数が真となったことを通知された待ち状態のプロセスは即座にロックを獲得して処理を再開するため、条件変数は真であり続けることが保証されていた。このような実装は非常に複雑でオーバーヘッドも大きい。また、任意のプロセスを中断できる一般的なスケジューリング方式とも相容れない。そのため、条件変数の実装や意味論が研究されてきた。

最近の実装では、通知してもいきなり制御が奪われることはなく、待ち状態のプロセスを単に実行可能状態にする。通知を行ったプロセスはロックを保持し続け、モニタ関数を抜けるときにロックを解放する。この方式の副作用として、通知を行う際にモニタ不変条件が真であることを保証する必要がなく（ロックを保持しており、他のプロセスは動けないため）、待っていたプロセスは再度条件が真であるかチェックしなければならない。特にモニタ関数に if test then wait(cv) という文があったとき、この wait(cv) から戻ってくるまでに別のプロセスが動作して条件変数を再び偽にする可能性がある。そのため、この文を while test do wait(cv) のように書き直して処理を続行する前に再度条件変数をチェックしなければならない。

ある条件変数で待っているプロセス群全てを実行可能状態にする実装もある。例えば、複数のプロセスが何らかの記憶装置に空きができるのを待っている場合などに有効である。というのも記憶装置上の領域を解放した場合、その解放したサイズと待っているサイズがどう対応するかはスケジューラにはわからないため、とりあえず全部を実行可能とする必要があるためである。

条件変数の実装例を以下に示す:

 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();
   }
 }

歴史
Per Brinch Hansen はアントニー・ホーアのアイデアに基づいて最初にモニタを考案し実装した。その後ホーアが論理的フレームワークを構築し、本来のセマフォと能力的に等価であることを示した。

モニタを言語レベルで実装した例を以下に示す:

Java
Mesa

モニタをライブラリレベルでサポートした例を以下に示す:
.NET Framework を使用する言語
Squeak Smalltalk
その他、多数の言語およびライブラリ

脚注

外部リンク

"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 - 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 Variables - Windows applications | Microsoft Docs - Microsoft Windows Vista以降でサポート
Condition Variable Routines - Apache Portable Runtime ライブラリより
wxCondition description
Synchronization - 1.69.0 - Boost C++ライブラリ
Condition Variables - 1.69.0 - Boost.Fiber
std::condition_variable - cppreference.com - C++11以降の標準C++ライブラリ
ZThread Condition Class Reference
Wefts::Condition Class Reference
ACE: ACE_Condition< MUTEX > Class Template Reference - 
QWaitCondition Class | Qt Core 5.12 - Qt
Common C++ Conditional Class Reference
at::ConditionalMutex Class Reference
threads::shared - スレッド間でデータ構造を共有するための Perl 拡張

プログラミング言語の構文
排他制御