分散デッドロック検出のデモ

　12月10日に、本学で｢KAITシンポジウム｣というイベントがあります。
http://www.sympo2016.cs.kanagawa-it.ac.jp

　そこではポスター（デモ）展示も行われます。その一つとして、以下の展示デモを予定しています。｢食事する５人の哲学者｣という有名な問題を扱います。これは、｢共有資源への競合問題｣です。問題の説明は、Wikiペデイアなどをご覧下さい。ここでは、５人の哲学者が食事をしようとしても、誰も先へ進めなくなる｢デッドロック｣状態の検出を主に問題としています。

｢食事する５人の哲学者｣のオリジナル説明図

　全体を見渡すことができれば、その検出は容易です。しかし、各哲学者は、他人の情報を知ろうとはしません。自分だけの世界にいますので、ひたすら待つだけです。もしかすると、他の哲学者が食事中であり、それが終わるのを待てば全体は動きだすのかもしれません。

　この問題は、以前、｢i-Androidの会｣でもプレゼンしたことがあります。その際も、各哲学者を１台のAndroidスマホに割り当てるという、真に現実感のあるエージェントで実現しようとしました。その際、フォークの取得に関する情報を、何とクラウド経由で交換していました。実装を簡単にするためでした。それに対して、今回は、５台のスマホ間の完全なローカルネットワークだけで実現したところが新しいです。

動作は停止状態にあるがデッドロックではない！

分散デッドロック検出（Chandy-Misra法）された状態！