FLAGS

筆者おかあつ 大きな区分 記事の区分 記事の一覧 検索 ツイート

2009年7月14日火曜日

(プログラム)哲学者の食事問題 (mixi05-u459989-200907141059)

ミクシ内で書かれた旧おかあつ日記を紹介します。
(プログラム)哲学者の食事問題
2009年07月14日10:59
以下の様なコードを書いた

(※ 下部に添付)

このプログラムは一発でデッドロックに陥る。

この問題は哲学者食事問題と呼ばれる... と僕は思う。

哲学者食事問題
http://en.wikipedia.org/wiki/Dining_philosophers_problem

だけど、僕が書いたプログラムと哲学者食事問題をきちんと関連付けて説明しているドキュメントはとても少ないらしいことがわかった。

これらは本質的に同じ問題だ。 哲学者食事問題というのは、要するに 「二つ以上のスレッドから二つ以上のロックを異なる順番でとってはいけない」という法則だ。

これは要するに、ピコピコハンマーとヘルメットを二人で取り合っているようなものだ。 片方がピコピコハンマー→ヘルメット もう片方がヘルメット→ピコピコハンマーという順番で取ろうとしている。 だから「三すくみ」のようにお互い動けなくなる。

これはきちんと文章にする価値があると思うけど、これをきちんとした文章に起こすのは大変な時間がかかるし、他にもやることいっぱいあるし...。

(※)
public class Philosopher {
  private static final int WAIT = 10;
  private static final int COUNT = 100;
  final Object lock1 = new Object();
  final Object lock2 = new Object();
  final Runnable r1 = new Runnable() {
    @Override
    public void run() {
      try {
        for ( int i=0; i          synchronized ( lock1 ) {
            Thread.sleep( WAIT );
            synchronized ( lock2 ) {
              Thread.sleep( WAIT );
            }
          }
          System.out.println( "ALIVE!1" );
        }
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
      
    }
  };
  final Runnable r2 = new Runnable() {
    @Override
    public void run() {
      try {
        for ( int i=0; i          synchronized ( lock2 ) {
            Thread.sleep( WAIT );
            synchronized ( lock1 ) {
              Thread.sleep( WAIT );
            }
          }
          System.out.println( "ALIVE!2" );
        }
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }
  };
  public void execute() {
    new Thread( r1 ).start();
    new Thread( r2 ).start();
  }

  public static void main( String[] args ) {
    new Philosopher().execute();
  }
}

コメント一覧
おかあつ   2009年07月14日 11:09
そうか... ウェイターソリューションっていうのと、リソースヒエラルキーソリューションっていうのは、きわめて本質的な解決策なんだ。 これはどちらもきわめて簡単なJavaのコードとして表現できる。

だけど、それをきちんと明示的にあらわした記事ってあまり見当たらない。
 
出展 2009年07月14日10:59 『(プログラム)哲学者の食事問題』