link もっと前
   2008年 2月 20日 -
      2008年 2月 20日  
link もっと後

link 未来から過去へ表示(*)
link 過去から未来へ表示

日々

link permalink

同期機構

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

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

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

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

ミューテックス(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 の方が何かと親切ではあります。しかし親切な機能は大概遅いというのもお忘れ無く。

[編集者: すずき]
[更新: 2008年 2月 21日 02:37]
link 編集する

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
   2008年 2月 20日 -
      2008年 2月 20日  
link もっと後

管理用メニュー

link 記事を新規作成

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDF ファイル RSS 1.0
QR コード QR コード

最終更新: 7/22 04:22

カレンダー

<2008>
<<<02>>>
-----12
3456789
10111213141516
17181920212223
242526272829-

最近のコメント 5件

  • link 18年07月04日
    すずき 「NEON にも対応してみましたが、やはり...」
    (更新:07/11 21:26)
  • link 18年05月30日
    すずき 「情報ありがとうございます。PT2 2枚差...」
    (更新:06/02 17:27)
  • link 18年05月30日
    通りすがりですみませ... 「私のPC(Win10)ではB−CAS1枚...」
    (更新:06/02 16:42)
  • link 18年05月20日
    すずき 「数えたことはありませんが Windows...」
    (更新:05/22 22:26)
  • link 18年05月20日
    hdk 「Linux も、先日の Meltdown...」
    (更新:05/21 22:55)

最近の記事 3件

link もっとみる
  • link 18年07月21日
    すずき 「[Bluetooth UART 変換] UART を Blueto...」
    (更新:07/22 04:22)
  • link 18年07月17日
    すずき 「[エアコンが臭い] 「エアコンの嫌なニオイが完全に消えた」 "窓全...」
    (更新:07/17 22:53)
  • link 18年07月16日
    すずき 「[AArch64 向け Linux 開発環境の構築 その 2] そ...」
    (更新:07/17 22:46)

こんてんつ

open/close wiki
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報