2016年10月28日金曜日

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

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

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

「食事する5人の哲学者」のオリジナル説明図

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

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

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

分散デッドロック検出(Chandy-Misra法)された状態!

0 件のコメント:

コメントを投稿