Wikipedia

モニタ (同期)

モニタ（Monitor）は、リソース（何らかのハードウェア機器や変数群）を共有する複数のタスクの同期を実現する手法である。

パー・ブリンチ＝ハンセン（英語版）が発明し、Concurrent Pascal（英語版） 言語に最初に実装され、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 はアントニー・ホーアのアイデアに基づいて最初にモニタを考案し実装した。その後ホーアが論理的フレームワークを構築し、本来のセマフォと能力的に等価であることを示した。

モニタを言語レベルでサポートする例を以下に示す:

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

外部リンク編集

「https://ja.wikipedia.org/w/index.php?title=モニタ_(同期)&oldid=87220765」から取得