コグノスケ

同期機構

マルチスレッド処理とか調べていると、セマフォ、ミューテックス、モニターといった同期機構達の名前を良く目にします。違いが良くわからぬまま使っているのは良くないと思い立って復習してみたものの…こんがらかってきた。難しい。

以下、そのまとめ。全般的に用語があやしいので正しい用語を知ってたら教えてください。

セマフォとミューテックス

やはりこの二つの違いが難しいです。思いこみが入ってる可能性大なのでご指摘は大歓迎です。

ミューテックス（MUTual EXclusion）はロックまたはアンロックの二状態を持つ同期機構です。ロックされているミューテックスを他の人がロックしようとすると、他の人はロックを拒否されるか、ロックが解除されるまで待ってからロックします。ロック操作にはいくつかの概念があります。

ロックの所有権

AさんがロックしたらAさんが所有者となり、他人のBさんがアンロックすることはできません。Aさんが責任を持ってアンロックしなければなりません。

再帰ロック（リカーシブ・ロック）

ロックした所有者に限って、ロック中のミューテックスをさらに何度もロックできます。これは再帰関数でロックするときに便利です。

弱いロック

条件によってロックに強弱がつくか、または初めから優先順位があります。強いロックが弱いロックを無理矢理アンロックして、ロックを強奪できます。奪われた方は異常な状態になるので、終了させるか、リカバリ処理で元に戻します。これはデッドロックの解消に使えます。

ミューテックスについてはこんなもんでしょうか？次、セマフォいってみよう。

セマフォ（Semaphore）にはロック/アンロックの概念はありません。あるのは P操作（セマフォが0でなければ数字を1減らす、0ならば待つ）と、V操作（セマフォをとにかく1増やす）です。ミューテックスは複雑な型になり得ますが、セマフォは整数値で実装可能でしょう。実装したこと無いけど。

セマフォはある区間（同じセマフォを対象とするP操作とV操作の間）に同時に何人入れるか？だけを制御します。

例えるならば、食堂で料理を載せるトレーでしょうか。食堂の入口で店員（セマフォ）にトレー（セマフォの値）をもらい（P操作）、食事した後、出口でトレーを店員に返す（V操作）というルールです。食堂にトレーが3枚しかなければ、一度に食事できる人は3人（スレッドやプロセス）に制限できるという仕組みです。

チケットの枚数（セマフォの初期値）を変えれば、ミューテックスと等価なセマフォも作れます。二値セマフォ（0か1しか値を取らないセマフォ）と言うそうですが、P操作がロックで、V操作がアンロックに相当します。

しかしセマフォにはミューテックスのような所有権、再帰といった概念はありません。自分のロックが誰かに壊されてしまう可能性（アンロックのときに異常な状態になるので検知はできますが…）や、ロック区間で再帰すればデッドロックに陥って自爆することがある。ってことです。

もちろんセマフォに所有権付けたって、ミューテックスの所有権がなくたって一向に構いません。世の中を見ても、実装によって同期機構の動作はバラバラです。同期機構って何だかわからないー！と感じる主因は単に「実装依存が多すぎる」だけかもなあ…。

その頃Linuxは

ミューテックスとセマフォの実装の例として、Linuxのpthread（POSIX threadの略？）mutexとPOSIXセマフォの説明を見ます。pthread mutexはその名の通りスレッド間のみの同期を取る機構であり、POSIXセマフォはプロセス間共有ができる違いが大きいでしょう。

POSIXセマフォでは名前付きと無名を選べます。名前を付けるとファイルとして見えるのも大きな特徴でしょう。これはあくまでもPOSIXが規定する機能で、セマフォがみんなそうなっているわけではありません。しつこくて申し訳ないです。

一方pthread mutexはというと、基本的には二値セマフォです。しかし所有権チェック＆デッドロックのチェックや、再帰ロックが可能になるオプションを指定できます。しかし 〜NP(non portableかな？) という名前を見るに、恐らくPOSIX準拠じゃない機能です。

一方Javaは

Javaにはセマフォとミューテックスとはまた別にsynchronizedという別の同期機構（モニタというらしい）が備わっていますが、Wikipediaによればモニタはロックで実現できます。奇遇だね俺もそんな気がするよっ、ってことでスルー。

JavaのミューテックスはLockインタフェースの実装クラス（ReentrantLock, ReentrantReadWriteLock）が相当します。どちらも所有権の概念と、再帰ロックの概念を持っています。

他にも公平なロックという概念をオプションとして提供しています。公平なロックは上記の説明で出てませんでしたねえ。あれまー…。簡単に説明します。

公平なロック

ロックしようとした順番にロックを渡す。

不公平なロック

ロックしようとした順番を無視して適当にロックを渡す。

ある一つのミューテックスをロックして仕事してアンロックする、という動きを繰り返しているAさん、Bさん、Cさんの3人がいるとします。3人が常に一つのミューテックスを欲しがっていますが、Aさんが偶然何度もロックを取得してしまうと、BさんやCさんはその間全く動けない状態に陥ります。

このときBさんやCさんは飢餓状態に陥っている、と言います。飢餓状態が起きないことを保証するロックの配り方、それが公平なロックです。

ReadWriteLockは多数の読み出し側（Reader）と少数の書き込み側（Writer）がいるときに有効なロックの戦略です。ReadLock（ReentrantReadWriteLock#getReadLock() で取得する）とWriteLock（ReentrantReadWriteLock#getReadLock() で取得する）のペアで使用します。

ReadLockは特殊なロックで複数人が同時にロックできます。WriteLockはReadLockと他人のWriteLockに対して排他的です。そのためWriteLockはReadLockと同時にかかることはありません。

何言ってんだテメェは！って思ったそこの貴女、表にしまし…たらちょっと見づらかったので、リストにしました。ReadWriteLockは大きく3状態に分けられます。

ロックされていないとき

どちらのロックも成功します。

ReadLockがかかっているとき

ReadLockは成功します。WriteLockは待ちます。

WriteLockがかかっているとき

ReadLockもWriteLockも待ちます。

同期機構においてはPOSIXよりJavaの方が何かと親切ではあります。しかし親切な機能は大概遅いというのもお忘れ無く。