<<PREV | ToC | NEXT>>

The Dining Philosophers Problem
食事をする哲学者の問題

Revised: May/3rd/2002

ここでは資源共有問題として有名な「食事をする哲学者の問題」 (The Dining Philosophers Problem, 1965, Dijiksra) を実現するサンプルを紹介します。

本稿ではテキストベースのアプリケーションとして作成しますが、 Sun Microsystems の Tutorial では GUI アプレットとしてサンプルが公開されています。コードを読む力のある方は参照すると良いでしょう。

シナリオ

５人の哲学者が円卓についている。各々の哲学者にはスパゲッティーを盛った皿が出されている。スパゲッティ−はとても絡まっているので、二本のフォークを使わないと食べられない。お皿の間に一本のフォークが置いてあるので、五人の哲学者に対して五本のフォークが用意されていることになる。哲学者は思索と食事を交互に繰り返している。空腹を覚えると、左右のフォークを手に取ろうと試み、首尾よく二本のフォークを手にできればしばし食事をし、しばらくするとフォークを置いて思索に戻る。隣の哲学者が食事中でフォークが手に取れない場合は、そのままフォークが空くのを待って飢えてしまう。

全員の哲学者が同時に左手のフォークに手を伸ばすと、円卓上に空いたフォークがなくなってしまうので、フォークが空くのを待ったままだれも食事ができずに飢え続けてしまう。

クラス概要

同期指定されたコードを持つ五つの共有オブジェクトと、それを利用する五つのスレッドの問題として考えます。

共有オブジェクト: Fork

int id

どの哲学者の左手にあるのかを識別する番号。

boolean eating

哲学者の手にとられているか。

void pick(int i)

同期指定して２つ以上のスレッドにアクセスされないようにしておく。メソッド引数はフォークを取った哲学者の識別番号。eating が true の間は他の哲学者の手にとられていることになるので wait()。false ならば true をセット。

void down()

同期指定したコードで、 eating に false をセット。

スレッド: Phylosopher

int id

哲学者を識別する番号。

int eatTime

食事に費やす時間。

int thinkTime

思索に費やす時間。

int left

左手にとるフォークの番号。 id を代入。

int right

右手にとるフォークの番号。 id - 1 を代入。但し、id が 0 の哲学者は 4。

Fork[] forks

共有オブジェクト。要素数は 5。

void setProperties

以上の変数に値をセット。

void feelHungry()

Fork 型オブジェクトで id が left, right のものを呼ぶ。両方の処理が終了したらメッセージを出力して eatTime だけ sleep() したあと左右のフォークを down()。

void think()

メッセージを出力して thinkTime だけ sleep()。

void run()

feelHungry() と think() を繰り返し呼ぶ。

サンプル

// 共有オブジェクト
class Fork {
	// どの哲学者の左手にあるか識別する番号
	private int id;
	// いずれかの哲学者の手にとられているかどうか
	private boolean eating = false;
	
	// コンストラクタ
	Fork(int i) {
		// メソッド引数の哲学者の左手に置かれている
		id = i;
	}
	
	// 手にとられる
	public synchronized void pick(int i) {
		while (eating == true) {
		// 隣の哲学者の手に取られている間は繰り返し
			try {
				System.out.println(i + " is starving.");
				// 待機プールへ
				wait();
			} catch (InterruptedException e) {
				System.out.println(e);
			}
		}
		// 手に取れたら true をセット
		eating = true;
	}
	
	// 手から離される
	public synchronized void down() {
		// 食事が済んだら false をセット
		eating = false;
		// 待機プールのスレッドをロック探索状態に
		notifyAll();
	}
}

class Philosopher implements Runnable {
	int id;       	// 哲学者の識別番号
	int eatTime;	// 食事時間
	int thinkTime;	// 思索時間
	int left;     	// 左手のフォークの番号
	int right;    	// 右手のフォークの番号
	Fork[] forks = new Fork[4];	// 共有オブジェクト
	
	// コンストラクタ
	Philosopher(int i) {
		id = i;
	}
	
	// 哲学者のプロパティのセット
	public void setProperties(int eating, int thinking, Fork[] objs) {
		left = id;
		if (id != 0) { 
			right = id - 1;
		} else {
			right = 4;
		}
		eatTime = eating;
		thinkTime = thinking;
		forks = objs;
	}
	
	// 空腹を感じるとフォークを手に取る
	public void feelHungry() {
		// 左手のフォークを手に取る
		forks[left].pick(id);
		
		// ここの待機時間が長いとデッドロック発生
		try {
			Thread.sleep(500);
		} catch (InterruptedException e) {
			System.out.println(e);
		}
		
		// 右手のフォークを手に取る
		forks[right].pick(id);
		
		System.out.println(id + " is eating.");
		try {
			// 食事中
			Thread.sleep(eatTime);
		} catch (InterruptedException e) {
			System.out.println(e);
		}
		// 食事終了
		// 左手のフォークを離す
		forks[left].down();
		// 右手のフォークを離す
		forks[right].down();
	}
	
	// 思索
	public void think() {
		try {
			// 思索中
			Thread.sleep(thinkTime);
		} catch (InterruptedException e) {
			System.out.println(e);
		}
	}
	
	// スレッドの run() メソッド
	public void run() {
		while (true) {
			// 思索中
			System.out.println(id + " is thinking.");
			think();
			// 空腹を感じる
			System.out.println(id + " feels hungry.");
			feelHungry();
		}
	}
}

これらのクラスを利用するコントロールクラスは次のように書けます：

class Dining {
	public static void main(String[] args) {
		// 共有オブジェクト
		Fork[] forks = new Fork[5];
		// 哲学者
		Philosopher[] phils = new Philosopher[5];
		
		// インスタンス化
		for (int i=0; i<5; i++) {
			forks[i] = new Fork(i);
			phils[i] = new Philosopher(i);
		}
		
		// 哲学者のプロパティ
		//                     eating, thinking, shared object
		phils[0].setProperties(2000,   1000,     forks);
		phils[1].setProperties(1900,   1100,     forks);
		phils[2].setProperties(1800,   1200,     forks);
		phils[3].setProperties(1700,   1300,     forks);
		phils[4].setProperties(1600,   1400,     forks);
		
		// スレッド
		Thread[] thres = new Thread[5];
		for (int i=0; i<5; i++) {
			// 哲学者をスレッドに委譲
			thres[i] = new Thread(phils[i]);
		}
		
		// スレッドの開始
		for (int i=0; i<5; i++) {
			thres[i].start();
		}
	}
}

全ての哲学者が左手にフォークを持ってしまうとデッドロックになる。上の例の場合は、思索から覚めた哲学者０から順番に左手のフォークを取っていき、最初にフォークを手にした哲学者０が右手にフォークを取ろうとしたときには右隣の哲学者４が左手でフォークを取ってしまっているため、哲学者０はそのフォークが空くのを待ち続ける。以下１、２、３、４も同じように右隣の哲学者がフォークを離すのを待ち続ける。

Philosopher クラスの feelHunger() メソッドで、左手のフォークを手にとってから右手のフォークを手にとるまでの時間を sleep() で 500 に指定している。この値を小さくすればデッドロックは起こらない。哲学者４が左手でフォークを握る前に哲学者０は右手でそのフォークを握って首尾よく食事を済ませて、フォークを置いて思索に戻るので、待たされていた哲学者４は左手にフォークを握ることができ、哲学者１は右手でフォークが握れて食事にありつける。こうして順番に一人ずつ全員の哲学者が食事にありつくことができる。

Deadlock が発生した実行例：

C:\java\thread>javac Dining.java
C:\java\thread>java Dining
0 is thinking.
1 is thinking.
2 is thinking.
3 is thinking.
4 is thinking.
0 feels hungry.
1 feels hungry.
2 feels hungry.
3 feels hungry.
4 feels hungry.
0 is starving.
1 is starving.
2 is starving.
3 is starving.
4 is starving.

強制終了は [Ctrl + C] です。

<<PREV | ToC | NEXT>>