条件変数

ウィキペディア

モニタ (同期)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/17 20:15 UTC 版)

この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。（2019年3月）

並行計算の分野におけるモニタ（英: monitor）とは、共有オブジェクトの状態が複数のスレッドから同時にアクセスされることを防ぎ、かつ状態が変化するまで待機させるような、同期のための構成概念である。モニタはスレッドに、排他アクセス権を再取得してタスク（英語版）を再開する前に、特定の条件が満たされるまで待機するために、排他アクセス権を一時的にあきらめさせるメカニズムを提供する。モニタはミューテックス（ロック）と、少なくとも1つの条件変数（英: condition variable）から成る。条件変数は、オブジェクトの状態が変化したときに明示的にシグナルされ、このときミューテックスは条件変数を待機している別のスレッドに一時的に明け渡されている。

モニタの別の定義として、ミューテックスをラップするスレッドセーフなクラスまたはオブジェクトのことを指す。

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

以下のようなプログラミング言語でモニタがサポートされている。

• Concurrent Pascal
• C#やVB.NETなどの.NET言語（System.Threading.Monitorクラス^{[1][注釈 1]}）
• C++（C++11以降の標準C++ライブラリにおけるstd::mutexとstd::condition_variable^[3]の組み合わせなど^[4]）
• Java（Object.wait()とObject.notify()を経由したサポートのほか、Java 1.5以降はLockとConditionも用意されている）
• Delphi（System.SyncObjs.TConditionVariableMutexクラス^[5]）
• Mesa
• Python
• Ruby
• Squeak Smalltalk

その他、多数の言語およびライブラリによってサポートされている。POSIXスレッドライブラリ (Pthreads) ではミューテックスと条件変数を表現する抽象オブジェクトpthread_mutex_tとpthread_cond_tおよびそれらを操作する関数群^[6]が用意されている。Boost C++ライブラリのboost::mutexとboost::condition_variable^[7]の実装には、POSIX環境ではPthreadsが利用されている。これらの設計は、前述のC++11で標準化されたスレッドライブラリの原型にもなった。なお、Windows APIには条件変数の直接的なサポートが長らく存在しなかったため、BoostのWin32実装では匿名セマフォが使われている^[8]。Microsoft Windows VistaおよびMicrosoft Windows Server 2008以降で条件変数のネイティブAPIサポートが追加された^[9]。

脚注

注釈

1. ^ .NETのMonitorは単純なミューテックスを実現するためのクラスでもあり、C#やVB.NETなどのlockステートメントは、コンパイラによって内部的にはMonitorクラスを使用したコードに展開される^[2]。

出典

1. ^ Monitor Class (System.Threading) | Microsoft Learn
2. ^ lock ステートメント - 共有リソースへのスレッド アクセスを同期します - C# | Microsoft Learn
3. ^ std::condition_variable - cppreference.com
4. ^ 条件変数の利用方法 - cpprefjp C++日本語リファレンス
5. ^ System.SyncObjs.TConditionVariableMutex - RAD Studio API Documentation
6. ^ pthread_cond_timedwait, pthread_cond_wait - wait on a condition | The Open Group Base Specifications Issue 6 / IEEE Std 1003.1, 2004 Edition
7. ^ Synchronization - 1.84.0 / §Condition Variables
8. ^ thread/include/boost/thread/win32/condition_variable.hpp at boost-1.84.0 · boostorg/thread · GitHub
9. ^ Condition Variables - Win32 apps | Microsoft Learn

外部リンク

この節に雑多な内容が羅列されています。事項を箇条書きで列挙しただけの節は、本文として組み入れるか、または整理・除去する必要があります。（2019年3月）

• "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
• "Block on a Condition Variable" by Dave Marshall
• "Strategies for Implementing POSIX Condition Variables on Win32" by Douglas C. Schmidt and Irfan Pyarali
• Condition Variable Routines - Apache Portable Runtime ライブラリより
• wxCondition description
• Condition Variables - 1.69.0 - Boost.Fiber
• ZThread Condition Class Reference
• Wefts::Condition Class Reference
• ACE: ACE_Condition< MUTEX > Class Template Reference - ACE（英語版）
• QWaitCondition Class | Qt Core 5.12 - Qt
• Common C++ Conditional Class Reference
• at::ConditionalMutex Class Reference
• threads::shared - スレッド間でデータ構造を共有するための Perl 拡張

ウィキペディア小見出し辞書

条件変数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/10/06 10:10 UTC 版)

「モニタ (同期)」の記事における「条件変数」の解説

ビジーウェイト状態となるのを防ぐため、プロセスは互いにそのイベントを通知する手段を持っている必要がある。モニタはこれを条件変数（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(); }}