ruby で "哲学者の食事"

http://www2.ruby-lang.org/ja/20020315.html
にある "哲学者の食事" で、 デッドロックについて少し実験した。

上ページにあるコードは すでに デッドロック を回避するようになっている。
そこで、わざと デッドロック がおこるように編集した。

    $forks[(n+1)%N].lock   # cause deadlock　　<--  追加
#    if not $forks[(n+1)%N].try_lock                  <-- 元のコードをコメントに
#      $forks[n].unlock    # avoid deadlock
#      next
#    end

これで デッドロック がおこるはずだが、実際に走らせても なかなか デッドロックにならない。

そこで次の様に 食事時間の調整、２番目のフォークを取るまえに sleep を入れるなどして、
デッドロックを起こりやすくしてみた。

$ cat DiningPhilosophers.rb

# See http://www2.ruby-lang.org/ja/20020315.html
#
# The Dining Philosophers - thread example
#
# o: thinking, *: eating
# -: free. |: using

require "thread"

N = 5    # number of philosophers

def wait(n = 20)
  sleep rand(n) / 10.0
end

def think
  wait(10)
end

def eat
  wait(10)
end

def philosopher(n)
  while true
    think
    $forks[n].lock

    wait(20)

    $forks[(n+1)%N].lock   # cause deadlock
#    if not $forks[(n+1)%N].try_lock
#      $forks[n].unlock    # avoid deadlock
#      next
#    end

    $state[n*2] = ?|;
    $state[(n+1)%N*2] = ?|;
    $state[n*2+1] = ?*;

    print $state, "\n"
    eat

    $state[n*2] = ?-;
    $state[(n+1)%N*2] = ?-;
    $state[n*2+1] = ?o;
    print $state, "\n"

    $forks[(n+1)%N].unlock
    $forks[n].unlock

  end
end

$forks = []
for i in 0..N-1
  $forks[i] = Mutex.new
end
$state = "-o"*N
print $state, "\n"

for i in 0..N-1
  Thread.start{ philosopher(i) }
  sleep 0.3
end
sleep

これで デッドロックが起こるタイミングはまちまちだが、確実に デッドロック が起こるようになった。
その上で、もとのコードにあったデッドロック回避コードに戻すと、デッドロックが起こらなくなった。

でも、ほんとうに完全に デッドロック回避できているかの確信は持てない。
なぜなら、最初の デッドロックを起こすように書き換えただけでも、デッドロックを起こさせることはできなかったのだ。
デッドロックの発生回避を確実に確認するよい方法はないのだろうか？

# この実験は ruby 1.8.6, jruby 1.1.1 で行った