モニタ (同期)

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

パー・ブリンチ＝ハンセンが発明し、Concurrent Pascalに最初に実装され、Solo Operating System でのプロセス間通信方式として使われた。

1. 相互排他
-------

モニタは以下のものから構成される:

共有リソースを操作するプロシージャ群
ミューテックスロック
リソースと結び付けられた変数
競合状態を防ぐために仮定されるモニタ不変条件モニタ・プロシージャは何かをする前にロックをかけ、処理が完了するか、ある条件を待つことになるまでそれをかけておく。各プロシージャがロックを解放する際に不変条件が真であることを保証するなら、競合状態となるようなリソースの状態は各タスクからは見えないということになる。

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

monitor account {//int// balance := 0

function withdraw {if amount < 0 then error "Amount may not be negative"else if balance < amount then error "Insufficient funds"else balance := balance - amount }

function deposit {if amount < 0 then error "Amount may not be negative"else balance := balance + amount } }

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

2. 条件変数
-------

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

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

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

function send {if full then wait contents := sent full := true notify }

function receive {var //int// received

if not full then wait received := contents full := false notify return received } }

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

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

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

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

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

conditionVariable{ int queueSize = 0; semaphore lock; semaphore waiting;

wait{ lock.acquire; queueSize++; lock.release; waiting.down; }

signal{ lock.acquire; if { waiting.up; } lock.release; } }

3. 歴史
-----

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

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

Java
Mesaモニタをライブラリレベルでサポートした例を以下に示す:

.NET Framework を使用する言語
Squeak Smalltalk
その他、多数の言語およびライブラリ

4. 脚注
-----

5. 外部リンク
--------

section=1

"[1]" by Charles Antony Richard Hoare
"[2]" by John H. Howard
"[3]" by Butler W. Lampson and David D. Redell
[4] - the Open Group Base Specifications Issue 6, IEEE Std 1003.1 より
"[5]" by Dave Marshall
"[6]" by Douglas C. Schmidt and Irfan Pyarali
[7] - Microsoft Windows Vista以降でサポート
[8] - Apache Portable Runtime ライブラリより
[9]
[10] - Boost C++ライブラリ
[11] - Boost.Fiber
[12] - C++11以降の標準C++ライブラリ
[13]
[14]
[15] -
[16] - Qt
[17]
[18]
[19] - スレッド間でデータ構造を共有するための Perl 拡張