哲学者たちの食事

哲学者たちの食事

これまで実習したサーブレットは、ロックすべきオブジェクトがひとつの場合であった。開発するアプリケーションが高度になり、ロックの対象が複数になると新たな問題を引き起こす可能性が出てくる。それがデッドロックである。

「哲学者たちの食事(Dining philosophers)」という有名なシナリオある。これにはバリエーションが幾つもあってどれが最初かはっきりしないが、多分次の論文であろう。

Dijkstra, E. W. “Co-operating Sequential Processes”, Programming Languages, Genuys, F.(ed.), Academic Press, 1965

そのバリエーションのひとつを紹介すると、「専ら考えることを生業とする5人の哲学者たちがひとつの丸い食卓に座っている。中央には大きな皿にスパゲッティが盛ってある。５つのフォークが哲学者たちの間に置いてある。また各哲学者の前には取り皿がおいてある。思考中腹がへったことに気がついた哲学者は、やおら自分の左側に置いてあるフォークを左手にもち、更に右手で右側にあったフォークをとり、二つのフォークを使って自分の皿にスパゲッティをとり、食べる。終わったら二つのフォークを元に戻し再び思考を開始する。さてここで、たまたま5人の哲学者たちが同時にスパゲッティを取ろうと自分の左側のフォークをとったらどうなるであろうか？　5人とも右側のフォークが空くまで永久に待ちつづけてしまい、飢餓状態に陥る」

これは哲学者たちという5つのスレッドが、5つの共有オブジェクトをアクセスしようとしたために発生している。ともに左のオブジェクトのロックを確保してから右のオブジェクトのロックを確保しようとしたが、右のオブジェクトのロックはすでに確保されており、その状態が複数のスレッドの膠着を招いている。

一番単純なのは、下図のように、二つのオブジェクトを二つのスレッドがアクセスしようとした場合である。二つのスレッドがともに相手がかけたロックが解除されるのを待ちつづけてしまう。

ロックされる複数のオブジェクトはお互いに独立していたりループ配置されていたり、入れ子になっていたりすることがあるので、ついこの危険性を見落とすことがあるので、注意が必要である。

この問題は今までの手段では解決できず、また発生するとスレッドが永久に存続し、またオブジェクトがロックされたままとなるので深刻な事態を引き起こす。

JavaコンパイラやJava仮想マシンはデッドロックを検出できない。デッドロックの生じないプログラムの作成はプログラマの責任である（検出ツールは存在する。例えばJprobeのThreadalizer）。更には次のような手段も検討されよう。

- 問題が起きてもそれから脱出できるように、危険と思われる個所にはタイムアウトを設定する。絶対に大丈夫と自信をもって開発したプログラムも、稼動させるとしばしばバグが顕在化する。例えば通信制御のソフトウエアは殆ど全ての状態にタイムアウトが設定されており、如何なる想定外の事態が生じてもシステムの停止を防止している。

- 複数の対象オブジェクトをなるべく作らない。例えばサーバにまかせる。「哲学者たちの食事」の場合のサーバとはまさしく給仕である。給仕は各哲学者から食事をとりたいという要求があれば、ふたつのフォークを使ってスパゲッティを取り皿に盛って哲学者に渡す。こうすればデッドロックは発生しない。負荷分散の問題も、給仕がラウンドロビンで各哲学者に聞いて回るなどで解決できる。必要とあらば、仲の良い哲学者に優先度を持たせて、サービスに差をつけることも出来よう。

ここでは、あるオブジェクトがビジーになったときから一定時間が経過しても解除されないときに、警報を発するように機能を追加したEnhancedBusyFlagを紹介しよう。ビジーフラグによるロックの、タイムアウト検出のひとつの見本として参考になろう。このサンプルではタイムアウトを検出したらコンソールに警報を出力するだけだが、更にどのような処置をとらせるかは皆さん次第である。なおこの部分は、多少のスレッドの知識が必要かもしれない。

BusyFlagWatchdogとEnhancedBusyFlag

package basic_servlets;

/**

* BusyFlagが所定の時間を経過しても解除されないときに警報を出す

*/

public class BusyFlagWatchdog extends Thread{

EnhancedBusyFlag enhancedBusyFlag; //どのオブジェクトがビジーをセットしたか

public BusyFlagWatchdog(EnhancedBusyFlag enhancedBusyFlag){

this.enhancedBusyFlag = enhancedBusyFlag;

this.start();

}

public synchronized void run(){

enhancedBusyFlag.waitWatchdog(); //enhancedWatchdogのモニタを取得する

}

}

package basic_servlets;

import java.util.*;

/**

* WatchdogつきBusyFlagのクラス

* 同期ロックを使わないで競合を回避するためのフラグ

*/

public class EnhancedBusyFlag {

private Thread busyflag = null; //フラグとしてスレッドを使用

private int busycount = 0; //同じスレッドが多重獲得したときのカウンタ

private long duration; //このフラグがセットされている最大時間（ミリ秒）

/* コンストラクタ */

public EnhancedBusyFlag(){

duration = Long.MAX_VALUE;

}

public EnhancedBusyFlag(long duration){

this.duration = duration;

}

/* ビジーフラグを開放するメソッド */

public synchronized void freeBusyFlag() {

if (getBusyFlagOwner() == Thread.currentThread()){ //自分がフラグのオーナであれば

busycount--; //カウンタをデクリメント

if (busycount == 0){ //ゼロであれば

busyflag = null; //フラグをクリアして

notifyAll(); //待機中のスレッドに通知する

}

}

}

/* ビジーフラグを取得するメソッド */

public synchronized void getBusyFlag() {

while (tryGetBusyFlag() == false){ //すでにビジーであれば

try{

wait(); //解除を待つ

}catch (Exception e){}

}

//whileループを出たことでビジーフラグがセットされたことになる（詳細は文献参照）

if (duration != Long.MAX_VALUE) //durationが設定されているとタイマー起動

new BusyFlagWatchdog(this); //ウオッチドッグのスレッドが開始

}

/* ビジーフラグのオーナであるスレッドを返すメソッド */

public synchronized Thread getBusyFlagOwner() {

return busyflag;

}

/* ビジーフラグの取得を試みるメソッド */

public synchronized boolean tryGetBusyFlag() {

if (busyflag == null){ //まだセットされていなければ

busyflag = Thread.currentThread(); //自分のスレッドの参照をフラグにセット

busycount = 1; //ビジーカウントを1にセット

return true; //ビジーになったことを返す

}

if (busyflag == Thread.currentThread()){ //自分セットしたフラグを再度セットしようとしている

busycount++; //ビジーカウントをインクリメント

return true; //ビジー状態であることを返す

}

return false; //他のスレッドが使用中であることを返す

}

/* ウオッチドッグの待ち合わせ用メソッド（ウオッチドッグはモニターのオーナでなければならない） */

public synchronized void waitWatchdog(){

if (busyflag != null){ //既にビジーフラグがリセットされていれば監視はしない

try{

wait(duration); //ビジーフラグのリセットのnotifyAllを待つ

if (busyflag != null) //もしまだbusyflagがセットされていたら、タイムアウト!

System.out.println("BusyFlag expired, " + this +", "+ (new Date()).toString());

}catch (Exception e){}

}

}

}

ポイントとなる個所は赤い文字で示してある。このプログラムを理解しやすいように、その構成を下図に示す。

AnotherPocketというサーブレット（シングルトン）には、EnhancedBusyFlagのオブジェクトが定義され、かつそのタイムアウト時間の設定がされる。ポケットの占有権の取得と開放にはlockとunlockのメソッドが用意されている。

EnhancedBusyFlagには3つの同期化されたメソッドがある。これらのいずれかのメソッドを実行しているスレッドがこのオブジェクトのモニタの保持者である。getBusyFlagにはwait()メソッドがあり、ビジー解除まで待ち続ける。スレッドはwait()に入り待機状態になる直前にロックを開放し、このメソッドから出る直前にロックを再度獲得する。従ってwait()内では待機状態になった複数のスレッドが存在し得ることに注意しよう。ビジーを開放するためのfreeBusyFlagにはnotifyAll()のメソッドがあり、このオブジェクトのモニタである待機中のすべてのスレッドを起こす。EnhancedBusyFlagには新たにwaitWatchdogという同期化されたメソッドが追加されている。ここにもwait(duration)というメソッドがあり、スレッドを待機させる。これが時間監視のためのBusyFlagWatchdogという型のスレッドである。このスレッドは、durationで指定された時間が経過するか、notifyメソッドで通知されるまでここで待機する。このスレッドの生成と開始はbusyflagをセットしたスレッドが行う。

BusyFlagWatchdogのオブジェクトが待機する場所は、notify（またはnotifyAll）を発効するメソッドと同じオブジェクト内でなければならないことを理解すれば、このプログラムは簡単に納得できよう。

notifyAllで起こされ、 wait(duration)を抜けたBusyFlagWatchdogスレッドは、その理由がタイムアウトか否かをbusyflagの存在で判断する。ここではコンソールに警報を表示させて終了しているだけだが、一般にはセッションの開放などの処理が必要であろう。

参考までにAnotherPocketクラスのソースコードの最初の個所を以下に示す。新たに追加された部分はやはり赤い文字で示してある。

AnotherPocket

public class AnotherPocket extends HttpServlet{

private int balance; //残高

public static AnotherPocket mother_sPocketMoney; //ロックの対象オブジェクト

private EnhancedBusyFlag flag = new EnhancedBusyFlag(5000); //ローカルなビジーフラグ

// ウオッチドッグつきフラグを、5秒間のタイムアウト時間で生成

// private BusyFlag flag = new BusyFlag(); //上のウオッチドッグつきのフラグを推奨

皆さんこれを使ってAnotherPocketMoneyAgainの動作を確認されたい。AnotherPocketでは処理時間を0から10秒の範囲でランダムな値にしてあり（deductメソッドの中がそうなっていない場合は変更のこと）、他方タイムアウト時間は5秒間に設定されているので、10乃至20回試してみると、約半分の回数で警報がコンソールに出力されよう。

前節　　　　　目次　　　　　次節