Deadlock

デッドロックの定義

計算機科学の内の最重要タームの一つのデッドロック．今一度デッドロックの定義を確認しておきたい．端的に言えば，デッドロックとは

• “二つ以上”のリソースのロックをめぐって
• 複数のプロセスが互いに待ち合う

事象を指す．
デッドロックが発生すればデッドロック検知・処理機構が実装されていない限り，アプリケーションはクラッシュもせず処理もしない，プロセスは正常実行中のまま，という保守の観点から厄介な状態に陥る．

ここでは，デッドロックを意図的に発生させてみる．

デッドロックを意図的に発生

いざ，デッドロックを意図的に発生させるコードというのは実は思った以上に難しい．有名な４賢人の箸が最も有名だが，ここではウィキペディアのデッドロック中での原因の項で示されている例を実装してみた．

以下上記ページからの引用

ここに変数Aと変数Bの二つのデータと、BにAの値を加算し、Aを0にする処理AとAにBの値を加算し、Bを0にする処理Bの二つの処理があったとする。マルチスレッドで処理をするため変数Aと変数BにアクセスするためのクリティカルセクションA（以下CSA）とクリティカルセクションB（以下CSB）の二つのクリティカルセクションを用意する。

処理Aは以下の手順であるとする。

1. CSAに入る
2. CSBに入る
3. BにAの値を加算
4. Aに0を代入
5. CSBから出る
6. CSAから出る

また同様に処理Bは以下の手順であるとする。

1. CSBに入る
2. CSAに入る
3. AにBの値を加算
4. Bに0を代入
5. CSAから出る
6. CSBから出る

この場合は以下のようにプログラムが動作するとデッドロックが発生する。

以下のコードは上記ステップをJavaで実装してみた例である．

public class Deadlock {
 
 Object critA = new Object();
 Object critB = new Object();
 int a;
 int b;
 
 public void start() throws Exception {
  
  a = 100;
  b = 50;
  Thread a = new Thread( new CriticalSectionLogic(), "A" );
  Thread b = new Thread( new CriticalSectionLogic(), "B" );
  a.start();
  Thread.sleep( 100 );
  b.start();
 }

 /**
  * @param args
  */
 public static void main(String[] args) throws Exception {
  
  Deadlock d = new Deadlock();
  d.start();

 }
 
 public void criticalSectionA( String name ) throws Exception {
  
  synchronized( critA ) {
   System.out.printf( "%s entering into CSA\n", name );
   synchronized( critB ) {
    Thread.sleep( 100 );
    b += a;
   }
   a = 0;
  
   System.out.printf( "%s exitting into CSA\n", name );
  }
  
 }
 
 public void criticalSectionB( String name ) throws Exception {
  
  synchronized( critB ) {
   System.out.printf( "%s entering into CSB\n", name );
   synchronized( critA ) {
    a += b;
   }
   b = 0;
   System.out.printf( "%s exitting into CSB\n", name );
  }
  
 }
 
 class CriticalSectionLogic implements Runnable {

  public void run() {
   
   String name = Thread.currentThread().getName();
   System.out.printf( "Thread %s starting..\n", name );
   try {
    if( name.equals( "A" ) ) {
     criticalSectionA( name );
     criticalSectionB( name );
    }
    else {
     criticalSectionB( name );
     criticalSectionA( name );
    }
   } catch ( Exception e ) {
    e.printStackTrace();
   }
    
  }

 }

}

criticalSectionAでsleep()を読んでいるのはthreadAをwaitさせる為．

実行結果は何度実行しても以下の通りとなり，このプログラムは永遠に終了しない．

Thread A starting..
A entering into CSA
Thread B starting..
A exitting into CSA
B entering into CSB
B exitting into CSB
B entering into CSA
A entering into CSB