モニタ (同期)

並行計算におけるモニタの詳細解説

並行計算において、複数のスレッドが共有リソースに同時にアクセスすると、データの不整合や競合状態が発生する可能性があります。これを防ぐための同期機構の一つがモニタです。モニタは、共有オブジェクトの状態へのアクセスを排他的に制御し、特定の条件が満たされるまでスレッドを待機させるための構成概念です。

モニタの基本構成

モニタは、以下の要素で構成されています。

ミューテックス（ロック）: 共有リソースへのアクセスを排他的に制御します。あるスレッドがミューテックスを獲得すると、他のスレッドはロックが解放されるまで待機します。
条件変数: スレッドが特定の条件が満たされるまで待機するためのメカニズムです。条件変数は、オブジェクトの状態が変化したときに明示的に通知（シグナル）されます。

モニタは、スレッドが排他アクセス権を一時的に手放し、特定の条件が満たされるまで待機することを可能にします。条件が満たされたら、排他アクセス権を再度獲得して処理を再開します。

モニタの動作原理

1. 相互排他: モニタ内のプロシージャ（関数）は、処理を開始する前にミューテックスロックを獲得します。これにより、複数のスレッドが同時に同じプロシージャを実行することを防ぎます。
2. 条件待機: ある条件が満たされない場合、スレッドは条件変数上で待機します。このとき、スレッドはロックを解放し、実行可能な状態ではなくなります。
3. 条件通知: 別のスレッドが条件を満たした場合、条件変数を介して待機中のスレッドに通知します。通知されたスレッドは実行可能状態になり、ロックを獲得して処理を再開します。

モニタの具体例

銀行口座の例

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` が共有リソースであり、`withdraw` と `deposit` がモニタプロシージャです。モニタ不変条件は、「操作前のすべての操作が `balance` に反映されている」ことです。これにより、競合状態を防ぎ、データの一貫性を保ちます。

通信チャネルの例

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


この例では、`contents` が共有リソースで、`send` と `receive` がモニタプロシージャです。条件変数 `snd` と `rcv` を使用して、送信側と受信側のスレッドを同期させています。

条件変数の実装と課題

初期のモニタの実装では、条件が満たされたことを通知されたスレッドは即座にロックを獲得し処理を再開していました。しかし、これは複雑でオーバーヘッドが大きく、一般的なスケジューリング方式とも相容れません。そのため、現在では通知されたスレッドは単に実行可能状態になり、ロックを獲得して処理を再開する前に再度条件を確認する方式が一般的です。

条件変数の実装例

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


この例では、セマフォを使って条件変数を実装しています。`wait()` でスレッドを待ち状態にし、`signal()` で待ち状態のスレッドを解除します。

モニタの歴史と採用言語

モニタの概念は、パー・ブリンチ＝ハンセンによって発明され、Concurrent Pascal で最初に実装されました。その後、アントニー・ホーアが論理的フレームワークを構築しました。

モニタは、以下のプログラミング言語でサポートされています。

.NET言語（C#、VB.NET）：`System.Threading.Monitor` クラス
C++ (C++11以降): `std::mutex` と `std::condition_variable` の組み合わせ
Java: `Object.wait()` と `Object.notify()` 、Java 1.5以降は `Lock` と `Condition` も利用可能
その他：Delphi, Mesa, Python, Ruby, Squeak Smalltalk など

POSIXスレッドライブラリ (Pthreads) では、ミューテックスと条件変数を表現する抽象オブジェクト `pthread_mutex_t` と `pthread_cond_t` が用意されています。

まとめ

モニタは、並行プログラミングにおいて重要な同期機構であり、複数のスレッドが共有リソースを安全に操作するための基盤を提供します。ミューテックスと条件変数を組み合わせることで、競合状態を防ぎ、効率的なスレッド同期を実現します。モニタの仕組みを理解することは、堅牢で効率的な並行プログラムを開発するために不可欠です。

もう一度検索