食事する哲学者の問題(Dining Philosophers Problem) Semaphore で遊ぶ その2

Java NetBeans

食事する哲学者の問題(Dining Philosophers Problem)を J2SE5.0 で追加された java.util.concurrent.Semaphore を使ってプログラムを組んでみます。

Semaphore については前回のエントリーでざっくり説明し、シンプルなプログラムも紹介しています。

Semaphore で遊ぶ

それでは、食事する哲学者の問題(Dining Philosophers Problem)とは何か調べてみます。

WikiPedia によると、食事する哲学者の問題(Dining Philosophers Problem)とは、並列処理に関する問題を一般化した例である。古典的なマルチプロセスの同期(排他制御)問題である。とされています。

もともとは、1965年、エドガー・ダイクストラは5台のコンピュータが5台のテープ装置に競合アクセスするという同期問題を提示した。

間もなく、この問題はアントニー・ホーアによって「食事する哲学者の問題」に変形して語られることとなった。

どうして食事する哲学者にすり替わったかは置いといて・・・

【問題】

5人の哲学者が食事したり、考え事をしたりしている。

かれらの前には、真ん中にスパゲッティの入った大きなボールが置かれた丸い食卓がある。

その食卓には5枚の皿が置かれ、皿と皿の間にフォークが1本ずつ置かれている。

スパゲッティをボールから取って自分の皿によそうには2本のフォークを必要とし、哲学者は一度に1本のフォークしかテーブルから取ることができない。

(左右の手で同時に両側にある2本のフォークを取ることはできない、という意味。まずどちらかの側のフォークを取ってから、逆の側のフォークを取る。)

哲学者同士は決して会話をしない。

このため、5人が左のフォークを手にとって右のフォークが食卓に置かれるのを待つという危険なデッドロック状態が発生する可能性がある。

スパゲッティではないけどこういう状況ですね。

cake1

【解説】

本来、デッドロック問題の解説手段として使われた。このシステムがデッドロックに到るのは「満たされない要求の円環」が存在する場合である。

例えば、哲学者 P1 が哲学者 P2 の手にしているフォークを待っていて、P2 は哲学者 P3 のものを……といったように円環形に要求が連鎖する。

例えば、それぞれの哲学者が次のように振る舞うとする。

1.左のフォークが得られるまで思索して待ち、フォークを取り上げる。

2.右のフォークが得られるまで思索して待ち、フォークを取り上げる。

3.食事する。

4.右のフォークを置く。

5.左のフォークを置く。

6.最初にもどって繰り返す。

この解法は正しくない。

このやりかたではデッドロックが発生し、全哲学者が左のフォークを持ち、右のフォークが持てるようになるのを待つという状況が発生しうる。

その場合、右のフォークは決して得られない (>_<。)

今回はこの方法でデッドロックを起こさないように Semaphore を使ってリソースへのアクセスを制限し対処するプログラムを組んでみることにします。

これって少し考えてみれば食事をしている両隣の哲学者はフォークをとれない状況ができるので同時に食事出来る哲学者の最大数は5人の場合は二人となります。

つまり、使われるフォークの数は4本となります。

これを利用すれば比較的簡単に Semaphore を利用してプログラムを組むことができますね。

それではプログラムを組んでみることにしますが、素直に哲学者に登場していただくより綺麗な女性を食事にお誘いしました。

今回デッドロックを避けるために使う Semaphore はウェイターの役割をはたします。

つまり、スパゲッティを食べる権利( パーミット取得 )があることを許可してくれます。

綺麗な女性は左のフォーク、そして右のフォークと使うことができればスパゲッティを食べることができます。

ただし、隣の女性がフォークを使っていたら( ロックがかかっていたら )フォークがあくのを待たなければ( ロックが解放される )いけません。

ウエイターは綺麗な女性がスパゲッティを食べ終わり左右のフォークを置いたなら、

その綺麗な女性のスパゲッティを食べる権利( パーミット )を戻してもらい、

次に待機している綺麗な女性がいれば「どうぞ、お食べください」とスパゲッティを食べる権利( パーミット )を与えます。。

そして綺麗な女性はフォークが空いていれば手に取りスパゲッティを食べられます。

フォークが空いていなければ待ちます。

これの繰り返しです。

最大二人の綺麗な女性がスパゲッティを同時に食べることがこれで可能となります。

左右のフォークの使用状況( ロックの状態 )によりフォーク待ち時間が発生してしまいますがこれでデッドロックは解消されます。

きっと綺麗な女性達は美味しいスパゲッティをお腹いっぱい食べて満足してお帰りになられたでしょう。

これをプログラムにすると次のようになりました。

プログラムを実行させてデッドロックが発生せず動作するか確認します。

桐谷美玲 左のフォークをとりあげる思索した時間は、0秒7838E-5
北川景子 左のフォークをとりあげる思索した時間は、0秒8168E-5
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒313E-6
桐谷美玲 1回目の食事
桐谷美玲 1回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、1秒3359217400000001
北川景子 1回目の食事
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
北川景子 1回目食事終了
剛力彩芽 右のフォークをとりあげる思索した時間は、1秒3721449000000001
剛力彩芽 1回目の食事
堀北真希 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
堀北真希 1回目の食事
剛力彩芽 1回目食事終了
堀北真希 1回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒375070565
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒652E-6
桐谷美玲 2回目の食事
新垣結衣 1回目の食事
新垣結衣 1回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒652E-6
桐谷美玲 2回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、0秒08200188600000001
北川景子 2回目の食事
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒652E-6
北川景子 2回目食事終了
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒583391387
堀北真希 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒652E-6
堀北真希 2回目の食事
剛力彩芽 2回目の食事
堀北真希 2回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒652E-6
剛力彩芽 2回目食事終了
新垣結衣 右のフォークをとりあげる思索した時間は、0秒436658855
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒652E-6
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒652E-6
新垣結衣 2回目の食事
桐谷美玲 3回目の食事
新垣結衣 2回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒294E-6
桐谷美玲 3回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、0秒23805942200000002
北川景子 3回目の食事
堀北真希 左のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
堀北真希 3回目の食事
北川景子 3回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒312E-6
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
剛力彩芽 3回目の食事
堀北真希 3回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒652E-6
剛力彩芽 3回目食事終了
新垣結衣 右のフォークをとりあげる思索した時間は、0秒18132323900000002
新垣結衣 3回目の食事
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒652E-6
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 4回目の食事
新垣結衣 3回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 4回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、0秒39374600600000004
北川景子 4回目の食事
堀北真希 左のフォークをとりあげる思索した時間は、0秒652E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒312E-6
堀北真希 4回目の食事
堀北真希 4回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒9640000000000005E-6
北川景子 4回目食事終了
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒023616073
剛力彩芽 4回目の食事
新垣結衣 左のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
剛力彩芽 4回目食事終了
新垣結衣 右のフォークをとりあげる思索した時間は、0秒7176410350000001
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒312E-6
新垣結衣 4回目の食事
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 5回目の食事
桐谷美玲 5回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
新垣結衣 4回目食事終了
堀北真希 右のフォークをとりあげる思索した時間は、0秒718831517
堀北真希 5回目の食事
北川景子 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
北川景子 右のフォークをとりあげる思索した時間は、0秒3543E-5
北川景子 5回目の食事
堀北真希 5回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒6430000000000004E-6
北川景子 5回目食事終了
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒140569047
剛力彩芽 5回目の食事
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒981E-6
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 6回目の食事
桐谷美玲 6回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒6420000000000003E-6
剛力彩芽 5回目食事終了
新垣結衣 右のフォークをとりあげる思索した時間は、0秒256017732
新垣結衣 5回目の食事
堀北真希 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
新垣結衣 5回目食事終了
堀北真希 右のフォークをとりあげる思索した時間は、0秒908995176
堀北真希 6回目の食事
北川景子 左のフォークをとりあげる思索した時間は、0秒973E-6
北川景子 右のフォークをとりあげる思索した時間は、0秒313E-6
北川景子 6回目の食事
堀北真希 6回目食事終了
北川景子 6回目食事終了
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒156232277
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒652E-6
桐谷美玲 7回目の食事
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
剛力彩芽 6回目の食事
桐谷美玲 7回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒312E-6
剛力彩芽 6回目食事終了
新垣結衣 右のフォークをとりあげる思索した時間は、0秒200991297
新垣結衣 6回目の食事
堀北真希 左のフォークをとりあげる思索した時間は、0秒652E-6
新垣結衣 6回目食事終了
堀北真希 右のフォークをとりあげる思索した時間は、1秒3822943870000002
堀北真希 7回目の食事
北川景子 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
北川景子 右のフォークをとりあげる思索した時間は、0秒3030000000000004E-6
北川景子 7回目の食事
堀北真希 7回目食事終了
北川景子 7回目食事終了
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒089658099
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 8回目の食事
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒625000000000001E-6
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒313E-6
剛力彩芽 7回目の食事
剛力彩芽 7回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒955E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒652E-6
新垣結衣 7回目の食事
桐谷美玲 8回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
新垣結衣 7回目食事終了
堀北真希 右のフォークをとりあげる思索した時間は、0秒8264462760000001
北川景子 左のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
堀北真希 8回目の食事
北川景子 右のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
北川景子 8回目の食事
堀北真希 8回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒6420000000000003E-6
北川景子 8回目食事終了
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒217371327
剛力彩芽 8回目の食事
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒312E-6
桐谷美玲 9回目の食事
剛力彩芽 8回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
新垣結衣 8回目の食事
桐谷美玲 9回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
新垣結衣 8回目食事終了
堀北真希 右のフォークをとりあげる思索した時間は、1秒21894861600000004
北川景子 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
堀北真希 9回目の食事
北川景子 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
北川景子 9回目の食事
堀北真希 9回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒652E-6
北川景子 9回目食事終了
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒780406594
剛力彩芽 9回目の食事
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒294E-6
桐谷美玲 10回目の食事
剛力彩芽 9回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒973E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒652E-6
新垣結衣 9回目の食事
桐谷美玲 10回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
新垣結衣 9回目食事終了
堀北真希 右のフォークをとりあげる思索した時間は、0秒475458529
堀北真希 10回目の食事
北川景子 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
北川景子 右のフォークをとりあげる思索した時間は、0秒312E-6
北川景子 10回目の食事
堀北真希 10回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒652E-6
北川景子 10回目食事終了
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒34860347900000005
新垣結衣 左のフォークをとりあげる思索した時間は、0秒652E-6
剛力彩芽 10回目の食事
剛力彩芽 10回目食事終了
新垣結衣 右のフォークをとりあげる思索した時間は、1秒0036094330000000507
新垣結衣 10回目の食事
新垣結衣 10回目食事終了

堀北真希 が 10回食事するのに要した時間は、28秒6504769030000013でした。
新垣結衣 が 10回食事するのに要した時間は、30秒9585105100000035でした。
剛力彩芽 が 10回食事するのに要した時間は、30秒0028747960000004014でした。
北川景子 が 10回食事するのに要した時間は、28秒998852129000003でした。
桐谷美玲 が 10回食事するのに要した時間は、27秒3586783140000023でした。

(○・ω・)ノ——– I eat delicious spaghetti and am stuffed. ——–(^_^)

ちゃんと動きました。(^_^)

このプログラムでは Semaphore インスタンス生成時のコンストラクタ引数に哲学者の人数を割り当てました。

また、公平性も設定しました。

パーミット数の設定は同時アクセスは 2 スレッドまでなので 2 と設定して、acquire()、release() とパーミット取得数とパーミット解放数を 1 してもいいでしょう。

今回は、パーミット数の設定を 5 , acquire(2)、release(2) とパーミット取得数とパーミット解放数を 2 としました。

同時アクセス可能なのが 2 スレッドで左右のフォークをロックするのでこの問題の鍵となるフォークの数を考慮にいれました。(あまり意味の無いこだわり)

final Semaphore semaphore = new Semaphore(PHILOSOPHERS_NUMBER, true);

NetBeans のプロファイラでスレッドの状態を確認してみましょう。

1

5 個の ForkJoinPool.commonPool-worker-29 とかのスレッドが最大で二つ同時アクセスされているのが確認できます。

スレッド終了後にフォークのロック解放待ちが無い場合はすぐに新たなスレッドが実行されているのも確認できます。

Semaphore って本当に便利ですね!

さて、ここでちょっとしたことを試してみよう。

Semaphore の公平性の設定をしなかったらどうなるのか?

final Semaphore semaphore = new Semaphore(PHILOSOPHERS_NUMBER); // 公平性無し

では、プログラムを実行させてみます。

剛力彩芽 左のフォークをとりあげる思索した時間は、0秒0810000000000002E-5
堀北真希 左のフォークをとりあげる思索した時間は、0秒0810000000000002E-5
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
剛力彩芽 1回目の食事
堀北真希 1回目の食事
堀北真希 1回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒313E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒652E-6
堀北真希 2回目の食事
剛力彩芽 1回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒312E-6
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒652E-6
剛力彩芽 2回目の食事
堀北真希 2回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒312E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒652E-6
堀北真希 3回目の食事
剛力彩芽 2回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒910000000000001E-7
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
剛力彩芽 3回目の食事
堀北真希 3回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
堀北真希 4回目の食事
剛力彩芽 3回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒910000000000001E-7
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
剛力彩芽 4回目の食事
堀北真希 4回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒652E-6
堀北真希 5回目の食事
剛力彩芽 4回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒6420000000000003E-6
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
剛力彩芽 5回目の食事
堀北真希 5回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒312E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
堀北真希 6回目の食事
剛力彩芽 5回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒910000000000001E-7
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒652E-6
剛力彩芽 6回目の食事
剛力彩芽 6回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒312E-6
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
剛力彩芽 7回目の食事
堀北真希 6回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒910000000000001E-7
堀北真希 右のフォークをとりあげる思索した時間は、0秒652E-6
堀北真希 7回目の食事
剛力彩芽 7回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
剛力彩芽 8回目の食事
堀北真希 7回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒910000000000001E-7
堀北真希 右のフォークをとりあげる思索した時間は、0秒652E-6
堀北真希 8回目の食事
剛力彩芽 8回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒973E-6
剛力彩芽 9回目の食事
堀北真希 8回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒6430000000000004E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
堀北真希 9回目の食事
剛力彩芽 9回目食事終了
剛力彩芽 左のフォークをとりあげる思索した時間は、0秒652E-6
剛力彩芽 右のフォークをとりあげる思索した時間は、0秒652E-6
剛力彩芽 10回目の食事
堀北真希 9回目食事終了
堀北真希 左のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
堀北真希 右のフォークをとりあげる思索した時間は、0秒652E-6
堀北真希 10回目の食事
剛力彩芽 10回目食事終了
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒312E-6
堀北真希 10回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒616E-6
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒830071894
桐谷美玲 1回目の食事
桐谷美玲 1回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、0秒888391644
北川景子 1回目の食事
北川景子 1回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒6420000000000003E-6
桐谷美玲 左のフォークをとりあげる思索した時間は、1秒44702734600000005
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒652E-6
桐谷美玲 2回目の食事
桐谷美玲 2回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、1秒2932113780000001
北川景子 2回目の食事
北川景子 2回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒3030000000000004E-6
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒6195947270000001
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒312E-6
桐谷美玲 3回目の食事
桐谷美玲 3回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、1秒23741232
北川景子 3回目の食事
北川景子 3回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒6420000000000003E-6
桐谷美玲 左のフォークをとりあげる思索した時間は、1秒2788060170000002
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒652E-6
桐谷美玲 4回目の食事
桐谷美玲 4回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、0秒9319671190000001
北川景子 4回目の食事
北川景子 4回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒633E-6
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒55758825
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒3543E-5
桐谷美玲 5回目の食事
桐谷美玲 5回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、0秒7469512070000001
北川景子 5回目の食事
北川景子 5回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒910000000000001E-7
桐谷美玲 左のフォークをとりあげる思索した時間は、1秒08432603500000013
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒973E-6
桐谷美玲 6回目の食事
桐谷美玲 6回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、0秒733817256
北川景子 6回目の食事
北川景子 6回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 左のフォークをとりあげる思索した時間は、1秒1698336330000001
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒312E-6
桐谷美玲 7回目の食事
桐谷美玲 7回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、1秒4533695360000001
北川景子 7回目の食事
北川景子 7回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒322E-6
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒8525430700000001
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒652E-6
桐谷美玲 8回目の食事
桐谷美玲 8回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、0秒669598278
北川景子 8回目の食事
北川景子 8回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 左のフォークをとりあげる思索した時間は、1秒3454052980000002
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
桐谷美玲 9回目の食事
桐谷美玲 9回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、1秒25630280000000005
北川景子 9回目の食事
北川景子 9回目食事終了
北川景子 左のフォークをとりあげる思索した時間は、0秒652E-6
桐谷美玲 左のフォークをとりあげる思索した時間は、0秒598060677
桐谷美玲 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
桐谷美玲 10回目の食事
桐谷美玲 10回目食事終了
北川景子 右のフォークをとりあげる思索した時間は、1秒09184714699999996
北川景子 10回目の食事
新垣結衣 左のフォークをとりあげる思索した時間は、0秒946E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒312E-6
新垣結衣 1回目の食事
北川景子 10回目食事終了
新垣結衣 1回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒973E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
新垣結衣 2回目の食事
新垣結衣 2回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒6430000000000004E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
新垣結衣 3回目の食事
新垣結衣 3回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒312E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒652E-6
新垣結衣 4回目の食事
新垣結衣 4回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒322E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
新垣結衣 5回目の食事
新垣結衣 5回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒024E-5
新垣結衣 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
新垣結衣 6回目の食事
新垣結衣 6回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒973E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
新垣結衣 7回目の食事
新垣結衣 7回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒6430000000000004E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒9820000000000003E-6
新垣結衣 8回目の食事
新垣結衣 8回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒652E-6
新垣結衣 右のフォークをとりあげる思索した時間は、0秒3210000000000001E-6
新垣結衣 9回目の食事
新垣結衣 9回目食事終了
新垣結衣 左のフォークをとりあげる思索した時間は、0秒910000000000001E-7
新垣結衣 右のフォークをとりあげる思索した時間は、0秒6510000000000002E-6
新垣結衣 10回目の食事
新垣結衣 10回目食事終了

堀北真希 が 10回食事するのに要した時間は、10秒9469584730000005でした。
新垣結衣 が 10回食事するのに要した時間は、40秒20581136300000225でした。
剛力彩芽 が 10回食事するのに要した時間は、10秒11629695400000095でした。
北川景子 が 10回食事するのに要した時間は、31秒21609595200000342でした。
桐谷美玲 が 10回食事するのに要した時間は、30秒20136357100000168でした。

(○・ω・)ノ——– I eat delicious spaghetti and am stuffed. ——–(^_^)

うわぁぁぁ・・・ 思いっきり不公平じゃないですか!

NetBeans のプロファイラでスレッドの状態を確認してみます。

2

今回のようなフォークのロック解放待ちがあるような場合はまずいような・・・

こんなとこもあるよね。

3

プログラムの処理時間が大幅に増えてます。

公平性の設定はよく考えないと思わぬ結果をもたらすかもしれませんね。

CompletableFuture を使えば楽に並行処理を記述できるし、Java って世に出たときはマルチスレッド対応だぜ!って誇らしげに売りにしていた。

あれから20年、確実に進化しています。

どんどん進化していく並行処理を日本語で優しく解説しているサイトはあまり無いのが残念です。

便利なものほど正しく使わないと痛い目をみますからね。

もっと正しい知識を優しい日本語の解説で入手したい今日この頃です。

今月の私は健康診断でコレステロールと中性脂肪の値が高いと指摘されたにもかかわらずこういった美味しいケーキをたくさん食べてしまいました。

c4

c3

c2

c5

美味しさそのままで中性脂肪とコレステロールの値をさげるケーキって無いものか。

お終い!

Hatena タグ:

Semaphore で遊ぶ

Java NetBeans

早いもので今日は五月五日 こどもの日です。

祝日法2条によれば、「こどもの人格を重んじ、こどもの幸福をはかるとともに、母に感謝する」となっています。

5月5日は古来から端午の節句として日本では男子の健やかな成長を祈願し各種の行事を行う風習があります。

ということで、私も男子の健やかな成長を祈願するプログラムを組むことにしました。

今さらですが、J2SE5.0 で追加された java.util.concurrent.Semaphore をつかってふざけた 夢のようなプログラム組みました。

男子の健やかな成長には素敵な女性との出会いは必要不可欠です。

だから4人の素敵な女性にデートに誘われると言う内容です。

しかし、体は一つしかありませんので一度に4人では収集付かなくなります。

そこで恭平さんにヘルプをお願いしました。(^_^;)

これでも、素敵な女性4人に対して男子は二人です。

これでなんとかするために Semaphore を使って二組のカップルまでがデートに出かけられるとします。

残りの二人の女性は先に出かけた二組のカップルのどちらか片方が帰ってきたらデートに出かけるという設定です。

つまり、男子二人というリソースに同時アクセス出来るのは素敵な女性スレッド二つまでということになります。

それが Semaphore を使えば実現できてしまうのです。

Semaphore はざっくり説明するとリソースに対するアクセスが可能か不可能かのいずれかの値をとる Binary Semaphore と

アクセス可能なリソース数を任意に設定することが出来る Counting Semaphore があります。

Java で採用された Semaphore は Counting Semaphore にあたります。

有限リソースに対して並行アクセス可能なスレッド数を自由に設定できます。

今回組むプログラムにうってつけの優れものとなっています。(^_^)

17 行目で Semaphore を生成しています。

コンストラクタの引数はパーミット数と公平性を設定します。

今回のプログラムではパーミット数はリソース数と同じ 2 となっています。

公平性は API ドキュメントを見ると今回のプログラムの場合は優しい私はパフォーマンスより平等性を重視して true と設定しました。

ちなみに API ドキュメントによると

このクラスのコンストラクタは、オプションで公平性パラメータを受け入れます。
falseに設定すると、このクラスはスレッドがパーミットを取得する順序について保証しません。
特に、バージ(barging)が許可されています。
つまり、acquire()を呼び出すスレッドに、待機していたスレッドより先にパーミットを割り当てることができます。
論理的には、新しいスレッドが、待機中のスレッドのキューの先頭に配置されます。
公平性がtrueに設定されると、セマフォは、acquireメソッドのいずれかを呼び出すスレッドが、これらのメソッドの呼出しが処理された順序(先入れ先出し、FIFO)でパーミットを取得するように選択されることを保証します。
FIFO順序付けは、必然的にこれらのメソッド内の特定の内部実行ポイントに適用されます。
そのため、あるスレッドが別のスレッドより前にacquireを呼び出しても、そのスレッドよりあとに順序付けポイントに到達する可能性があります。
また、メソッドからの復帰時も同様です。また、時間指定のないtryAcquireメソッドは公平性の設定に従いませんが、利用可能なパーミットをすべて取得することにも注意してください。

となっています。

実は今回のプログラムではこの公平性の設定の違いというのは解りにくいのですが

食事する哲学者の問題Dining Philosophers Problem)を Semaphore を使った簡易的なプログラムを組んでみるとよく解ります。

次に Semaphore からパーミットを取得するために acquire() メソッドを使います。

このプログラムでは 23 行目で使っています。

public void acquire() throws InterruptedException は API ドキュメントによると次のようになっています。

このセマフォからパーミットを取得します。パーミットが利用可能になるか、またはスレッドが割り込みされるまでブロックします。
パーミットが利用可能な場合はパーミットを取得してすぐに復帰するため、利用可能なパーミットの数は1つずつ減ります。

パーミットが利用可能でない場合、現在のスレッドはスレッドのスケジューリングに関して無効になり、次の2つのいずれかが起きるまで待機します。
•ほかのスレッドがこのセマフォに対してrelease()メソッドを呼び出し、現在のスレッドが次にパーミットを割り当てられるスレッドになる。
•ほかのスレッドが現在のスレッドに割り込みを行う。

現在のスレッドで、
•このメソッドへのエントリ上で設定された割込みステータスが保持されるか、
•パーミットの待機中に割り込みが発生した場合、
InterruptedExceptionがスローされ、現在のスレッドの割込みステータスがクリアされます。例外:InterruptedException – 現在のスレッドで割込みが発生した場合

これとは別に引数で取得するパーミット数を設定できるメソッドもあります。

次は取得したパーミットを解放する release() メソッドを調べてみます。

33 行目で使っています。

デートが終了したらパーミットを保持する必要はないので解放します。

public void release() は API ドキュメントによると次のように書かれています。

パーミットを解放し、セマフォに戻します。
パーミットを解放すると、利用可能なパーミットの数が1つずつ増えます。
いくつかのスレッドがパーミットを取得しようと試みている場合は、その中の1つのスレッドが選択され、解放されたばかりのパーミットが与えられます。
そのスレッドは、スレッドのスケジューリングに関して(ふたたび)有効になります。

パーミットを解放するスレッドは、acquire()の呼出しでそのパーミットを取得している必要はありません。
セマフォの適切な使用法は、アプリケーションでのプログラミング規約で確立されます。

たったこれだけでリソースにアクセスできる並行スレッド数を制限できてしまうんですねぇ・・・

このプログラムの実行結果は次のようになります。

待っているのは、堀北真希
待っているのは、北川景子
待っているのは、新垣結衣
待っているのは、剛力彩芽
今からデートに行くのは、北川景子
今からデートに行くのは、堀北真希
北川景子 は ゆっち とデートに行きました。
堀北真希 は 恭平 とデートに行きました。
北川景子 は ゆっち とデートから帰ってきました。
今からデートに行くのは、新垣結衣
新垣結衣 は ゆっち とデートに行きました。
新垣結衣 は ゆっち とデートから帰ってきました。
今からデートに行くのは、剛力彩芽
剛力彩芽 は ゆっち とデートに行きました。
剛力彩芽 は ゆっち とデートから帰ってきました。
堀北真希 は 恭平 とデートから帰ってきました。
(○・ω・)ノ——– Are you happy? ——–

さて、疑い深い私は NetBeans のプロファイラでスレッドの状態を確認してみました。( 注意:先ほどの実行結果とはことなります。)

1a

期待通りの動きをしてくれてます。(^_^) NetBeans のプロファイア手軽に使えて便利だね。

Semaphore 使える良い娘じゃないか!

もし、あなたが 恭平さん に素敵な女性とデートさせずに全ての女性を独り占めしたいとしたらこのプログラムをどのように変更したらいいでしょうか?

答えは簡単ですね!

私はヘルプを頼んだ 恭平さん に悪いのでプログラムの変更はいたしません。

どうしてもというかたはご自由に。(^_^;)

ちなみに今回のプログラムでは

CompletableFuture<Void> lovers1 = CompletableFuture.runAsync(() -> maki.play(), executor);

として ExecutorService を使いましたが

CompletableFuture<Void> lovers1 = CompletableFuture.runAsync(() -> maki.play());

として Fork/Join Framework を使うのもありです。

こどもの日の休日スペシャルはこれでお終いです。

食事する哲学者の問題Dining Philosophers Problem)に続く かも?

Hatena タグ: ,