食事する哲学者の問題
2008年07月07日09:56
http://en.wikipedia.org/wiki/Dining_philosophers_problem
http://ja.wikipedia.org/wiki/%E9%A3%9F%E4%BA%8B%E3%81%99%E3%82%8B%E5%93%B2%E5%AD%A6%E8%80%85%E3%81%AE%E5%95%8F%E9%A1%8C
こういう問題があるという話しを聞いた。 ややこしいのだが、５人の哲学者が円卓を囲んで食事をしているというのだ。 ５人の哲学者それぞれの間にはフォークがおいてある。 しかし、円卓の中央においてあるのはスパゲティーで、自分の皿にスパゲティーを取るためには、二本のフォークが必要だ。 しかし、フォークの数は限られている。
このとき、あるタイミングで哲学者がフォークを取ろうとすると、いつまでたってもフォークを取る事が出来なくなってしまうことがある。 例えば、全員の哲学者がいっせいに右にあるフォークを取ったとする。その後、左のフォークを取ろうとすると、そのフォークは必ず使用中ということになる。 そのフォークが未使用になるのを待つ。 しかし、全員が未使用になるのを待っているので、いつまでたってもそのフォークは未使用にならない。 こうして夜は深けて行く。 このような全員が右のフォークを取るというパターン以外にも、このようにお互いがお互いを待ってしまう事でいつまでも待ち続けてしまうパターンはたくさんある。
これは、並列処理のデッドロックが起こる原因を比喩で説明したものだ。
僕もずいぶん並列処理については経験をつんだが、なんだかわかりづらい例えだと思った。
なんかもっといい例えがないかなと考え始めた。
で思ったのだけど、世の中に人間が引き起こすデッドロックっていっぱいあるのではないだろうか。 特に日本人なんていつもデッドロックしっぱなしだ。
＝＝＝
並列処理でのプロセスやスレッドというのは、ある意味人と同じ様なもので、だから、人の世界で起こることは、並列処理の世界でも起こるし、並列処理の世界で起こることは人の世界でも起こる。 例えば...
例１） お見合い
お見合いの席上、相手の人がとても魅力的で嫌われたくないと思っている。 だから相手の人が言う事を聞いてから、それにあわせて話をしようと思っている。 席上の二人はお互いそう思って相手が何かを言い始めるのを待っているため、いつまでたっても会話が始まらない。
これはある意味、人間関係のデッドロックだ。 これと同じことが並列処理でも起こる。
例２） 正面衝突
商店街を歩いていたら、向こうからオバチャンが自転車で走ってきた。 こちらが右によけようとしたら、自転車も右によけた。 「あっ」と思って左によけたら自転車も同時に左によけてしまった。 びっくりして右によけたら自転車も右によけた。 そうこうしているうちに激突。
これと同じことは並列処理でも起こる。
例３－１） 交差点
道路の幅がほぼ同じくらいの見通しのよい交差点がある。 Ａさんは、交差点に差し掛かった。 向こうから車が来るのが見える。 ま、こちらが優先だから向こうが止まるだろう。 Ｂさんも同じ交差点に差し掛かった。 こちらが優先だから向こうが止まるだろう...。 かくして交通事故は発生する。
例３－２） 交差点２
道路の幅がほぼ同じくらいの見通しのよい交差点がある。 道路の幅が同じくらいの交差点では右側に見える車が優先だ。 ところが、ここに全ての方向から車が来たとすると、全ての車は右側の車が行過ぎるのを待つため、全ての車は動かない。
例４） 図書館
Ａさんは、図書館でAKIRAの１巻を読んでいた。 初めて読んだけど、すごい面白い！ これは全シリーズまとめて借りて帰ろうと思う。 しかし、同じ図書館に、AKIRAの２巻を読んでいるＢさんが居た。 初めて読んだけどすごい面白い！ これは全シリーズまとめて借りて帰ろうと思う。 Ａさんが２巻を待つ傍ら、Ｂさんは１巻を待っている。 Ａさんは職員に２巻が貸し出し中か聞いてみた。 貸し出し中でないことを知る。 同様にＢさんも職員に聞いた。１巻は貸し出し中ではなかった。 こうしてＡさんもＢさんも図書館が閉館の時間になるまで、待ち続ける。
例５） Visual Source Saver
VSSというマイクロソフトのファイルバージョン管理ソフトがある。 古いチェックアウト式の管理方法を採用しているソフトで、ファイルを更新するときは、チェックアウトといってロックをかけてから、更新し始める。 更新が終わったら、チェックインといって、ロックを解除するという仕掛けになっている。 ファイルがロック中の間は、他の人はチェックアウトする事は出来ない。
VSSを使っているプロジェクトで、ある日、Ａさんが ファイルＡとファイルＢを同時に更新しようとファイルをチェックアウトしようとしたら、ファイルＢが使用中だったので、ファイルＡをロックしたままファイルＢの解放を待った。
その頃違うフロアで働いているＢさんは、ファイルＢとファイルＡを同時に更新しようとした。 ファイルＢはチェックアウトできたのだが、ファイルＡは使用中だったので、そのままファイルＡの解放を待った。
ＡさんもＢさんも、お互い欲しいファイルが解放されず、残業。
＝＝
考えてみれば当たり前なのだけど、実際対等な相手同士と生活していると、こういう衝突や齟齬というのはよく起こる。
これを解決する一番いい方法は、仲介人を立てることだ。 お見合いなら仲人を立てる。 商店街には交通整理のおじさんを配置する。 交差点には信号を配置する。 図書館も、最近は職員に頼んで本を持ってくる方式の図書館がある。 並列処理もこれと同じ様に「メッセージキュー」というものを介して処理を行ったりすることで、問題の多くは解決できる。
あるいは発想自体を転換して衝突しないようにしてしまう方法もある。 たとえば、独り占めを禁止することなどがそれにあたる。 ファイルバージョン管理ソフトも最近ではロックが不要なファイル管理が一般的になってきた。
wikiには「Chandy / Misra の解法」というのが 紹介されている。 だけど、経験的にいって、こういう風な相談の上で順番を決めるという方法を取るのは、キナ臭い感じがする。
数学的に見れば可能なのかもしれないけど、実際に応用する時は非常に困難だからだ。 多くの場合、例１）や例２）の様な問題が発生して、問題の追跡に甚大な手間を取られたりする。 処理が上手くいっているときはいいが、ひとたびバグが発生するともうほとんど追跡が不可能なのだ。 また、プロセス間の処理が前後する事（レースコンディション）で、処理のケース分岐がとんでもない数になってしまったりもする。 現実では理論のようにきれいに割り切れないことが多い。
更に実際に起こる問題は もっと複雑なことも多い。 こういう複雑な問題を相手にする時は、問題に対処する方法を考えるのではなくて、そもそも問題自体が発生しない方法を考えることがとても大切ではないかと思う。
P.S.
ボツになった例 ＮＧ集 ：
話の流れにふさわしくないので、カットされたものの、折角書いたので公開するもの。
例・番外編：KY系－１）
飲み会で妙にハイテンションなＡさんが騒いでいる。 色々とギャグを飛ばすのだがいまいち面白くない。 心無く笑っていると「なんだ！ 空気読めよ！ 」と責められるので、仕方なく声を
あげて笑う。 あなたは 「空気が読めないのはおめぇだ...」と心の中で叫ぶが、言葉には出せない。 実に精神的につらい飲み会だが、席を立つわけにも行かず、こうして空気を読みあいのうち、夜は深けて行く。
並列処理での各処理は、能動的処理と受動的処理の二種類に分類できる。 受動的処理のプロセスが組み合わさってしまうとデッドロックに陥る。 日本人は、国民全員受動的なので、人間関係が常にデッドロックに陥っている。
例・番外編：KY系－２）
ＡさんとＢさんはある問題について話し合っているのだが、どうも話がかみ合わない。 Ａさん、痺れを切らして「あああああ、なんでわからないですか！」と叫ぶ。 Ｂさんは「何を！ わかっとらんのはお前じゃ！」と叫ぶ。
並列処理での各処理は、能動的処理と受動的処理の二種類に分類できる。 能動的処理のプロセスが組み合わさってしまうと処理が予期しない結果を招くようになる。 日本人は話を聞かない人が多いので、コミュニケーションが常にデッドロックみたいなものだ。
P.S.1
※ ところで、Wikiは、英語の記事と比べて日本語の記事はおかしい事が多いと思うけど、この記事は翻訳された方がとても優秀で非常に読みやすい。 しかし英語版の方に書いてある箸の例、書いたヤツ誰だよ。 わけわかんねーこと書きやがって。 わかってねーなら、すっこんでろといいたい。
P.S.2
はっ... これってよく考えたら、データベースで複数のレコードをロックするときに発生するデッドロックのことじゃん！ これって思ったよりぜんぜん常識的なことじゃん！ 正に今僕が作っているプログラムの問題じゃん！ ぜんぜん人事じゃないよ！ そうか！
http://ja.wikipedia.org/wiki/%E9%A3%9F%E4%BA%8B%E3%81%99%E3%82%8B%E5%93%B2%E5%AD%A6%E8%80%85%E3%81%AE%E5%95%8F%E9%A1%8C
こういう問題があるという話しを聞いた。 ややこしいのだが、５人の哲学者が円卓を囲んで食事をしているというのだ。 ５人の哲学者それぞれの間にはフォークがおいてある。 しかし、円卓の中央においてあるのはスパゲティーで、自分の皿にスパゲティーを取るためには、二本のフォークが必要だ。 しかし、フォークの数は限られている。
このとき、あるタイミングで哲学者がフォークを取ろうとすると、いつまでたってもフォークを取る事が出来なくなってしまうことがある。 例えば、全員の哲学者がいっせいに右にあるフォークを取ったとする。その後、左のフォークを取ろうとすると、そのフォークは必ず使用中ということになる。 そのフォークが未使用になるのを待つ。 しかし、全員が未使用になるのを待っているので、いつまでたってもそのフォークは未使用にならない。 こうして夜は深けて行く。 このような全員が右のフォークを取るというパターン以外にも、このようにお互いがお互いを待ってしまう事でいつまでも待ち続けてしまうパターンはたくさんある。
これは、並列処理のデッドロックが起こる原因を比喩で説明したものだ。
僕もずいぶん並列処理については経験をつんだが、なんだかわかりづらい例えだと思った。
なんかもっといい例えがないかなと考え始めた。
で思ったのだけど、世の中に人間が引き起こすデッドロックっていっぱいあるのではないだろうか。 特に日本人なんていつもデッドロックしっぱなしだ。
＝＝＝
並列処理でのプロセスやスレッドというのは、ある意味人と同じ様なもので、だから、人の世界で起こることは、並列処理の世界でも起こるし、並列処理の世界で起こることは人の世界でも起こる。 例えば...
例１） お見合い
お見合いの席上、相手の人がとても魅力的で嫌われたくないと思っている。 だから相手の人が言う事を聞いてから、それにあわせて話をしようと思っている。 席上の二人はお互いそう思って相手が何かを言い始めるのを待っているため、いつまでたっても会話が始まらない。
これはある意味、人間関係のデッドロックだ。 これと同じことが並列処理でも起こる。
例２） 正面衝突
商店街を歩いていたら、向こうからオバチャンが自転車で走ってきた。 こちらが右によけようとしたら、自転車も右によけた。 「あっ」と思って左によけたら自転車も同時に左によけてしまった。 びっくりして右によけたら自転車も右によけた。 そうこうしているうちに激突。
これと同じことは並列処理でも起こる。
例３－１） 交差点
道路の幅がほぼ同じくらいの見通しのよい交差点がある。 Ａさんは、交差点に差し掛かった。 向こうから車が来るのが見える。 ま、こちらが優先だから向こうが止まるだろう。 Ｂさんも同じ交差点に差し掛かった。 こちらが優先だから向こうが止まるだろう...。 かくして交通事故は発生する。
例３－２） 交差点２
道路の幅がほぼ同じくらいの見通しのよい交差点がある。 道路の幅が同じくらいの交差点では右側に見える車が優先だ。 ところが、ここに全ての方向から車が来たとすると、全ての車は右側の車が行過ぎるのを待つため、全ての車は動かない。
例４） 図書館
Ａさんは、図書館でAKIRAの１巻を読んでいた。 初めて読んだけど、すごい面白い！ これは全シリーズまとめて借りて帰ろうと思う。 しかし、同じ図書館に、AKIRAの２巻を読んでいるＢさんが居た。 初めて読んだけどすごい面白い！ これは全シリーズまとめて借りて帰ろうと思う。 Ａさんが２巻を待つ傍ら、Ｂさんは１巻を待っている。 Ａさんは職員に２巻が貸し出し中か聞いてみた。 貸し出し中でないことを知る。 同様にＢさんも職員に聞いた。１巻は貸し出し中ではなかった。 こうしてＡさんもＢさんも図書館が閉館の時間になるまで、待ち続ける。
例５） Visual Source Saver
VSSというマイクロソフトのファイルバージョン管理ソフトがある。 古いチェックアウト式の管理方法を採用しているソフトで、ファイルを更新するときは、チェックアウトといってロックをかけてから、更新し始める。 更新が終わったら、チェックインといって、ロックを解除するという仕掛けになっている。 ファイルがロック中の間は、他の人はチェックアウトする事は出来ない。
VSSを使っているプロジェクトで、ある日、Ａさんが ファイルＡとファイルＢを同時に更新しようとファイルをチェックアウトしようとしたら、ファイルＢが使用中だったので、ファイルＡをロックしたままファイルＢの解放を待った。
その頃違うフロアで働いているＢさんは、ファイルＢとファイルＡを同時に更新しようとした。 ファイルＢはチェックアウトできたのだが、ファイルＡは使用中だったので、そのままファイルＡの解放を待った。
ＡさんもＢさんも、お互い欲しいファイルが解放されず、残業。
＝＝
考えてみれば当たり前なのだけど、実際対等な相手同士と生活していると、こういう衝突や齟齬というのはよく起こる。
これを解決する一番いい方法は、仲介人を立てることだ。 お見合いなら仲人を立てる。 商店街には交通整理のおじさんを配置する。 交差点には信号を配置する。 図書館も、最近は職員に頼んで本を持ってくる方式の図書館がある。 並列処理もこれと同じ様に「メッセージキュー」というものを介して処理を行ったりすることで、問題の多くは解決できる。
あるいは発想自体を転換して衝突しないようにしてしまう方法もある。 たとえば、独り占めを禁止することなどがそれにあたる。 ファイルバージョン管理ソフトも最近ではロックが不要なファイル管理が一般的になってきた。
wikiには「Chandy / Misra の解法」というのが 紹介されている。 だけど、経験的にいって、こういう風な相談の上で順番を決めるという方法を取るのは、キナ臭い感じがする。
数学的に見れば可能なのかもしれないけど、実際に応用する時は非常に困難だからだ。 多くの場合、例１）や例２）の様な問題が発生して、問題の追跡に甚大な手間を取られたりする。 処理が上手くいっているときはいいが、ひとたびバグが発生するともうほとんど追跡が不可能なのだ。 また、プロセス間の処理が前後する事（レースコンディション）で、処理のケース分岐がとんでもない数になってしまったりもする。 現実では理論のようにきれいに割り切れないことが多い。
更に実際に起こる問題は もっと複雑なことも多い。 こういう複雑な問題を相手にする時は、問題に対処する方法を考えるのではなくて、そもそも問題自体が発生しない方法を考えることがとても大切ではないかと思う。
P.S.
ボツになった例 ＮＧ集 ：
話の流れにふさわしくないので、カットされたものの、折角書いたので公開するもの。
例・番外編：KY系－１）
飲み会で妙にハイテンションなＡさんが騒いでいる。 色々とギャグを飛ばすのだがいまいち面白くない。 心無く笑っていると「なんだ！ 空気読めよ！ 」と責められるので、仕方なく声を
あげて笑う。 あなたは 「空気が読めないのはおめぇだ...」と心の中で叫ぶが、言葉には出せない。 実に精神的につらい飲み会だが、席を立つわけにも行かず、こうして空気を読みあいのうち、夜は深けて行く。
並列処理での各処理は、能動的処理と受動的処理の二種類に分類できる。 受動的処理のプロセスが組み合わさってしまうとデッドロックに陥る。 日本人は、国民全員受動的なので、人間関係が常にデッドロックに陥っている。
例・番外編：KY系－２）
ＡさんとＢさんはある問題について話し合っているのだが、どうも話がかみ合わない。 Ａさん、痺れを切らして「あああああ、なんでわからないですか！」と叫ぶ。 Ｂさんは「何を！ わかっとらんのはお前じゃ！」と叫ぶ。
並列処理での各処理は、能動的処理と受動的処理の二種類に分類できる。 能動的処理のプロセスが組み合わさってしまうと処理が予期しない結果を招くようになる。 日本人は話を聞かない人が多いので、コミュニケーションが常にデッドロックみたいなものだ。
P.S.1
※ ところで、Wikiは、英語の記事と比べて日本語の記事はおかしい事が多いと思うけど、この記事は翻訳された方がとても優秀で非常に読みやすい。 しかし英語版の方に書いてある箸の例、書いたヤツ誰だよ。 わけわかんねーこと書きやがって。 わかってねーなら、すっこんでろといいたい。
P.S.2
はっ... これってよく考えたら、データベースで複数のレコードをロックするときに発生するデッドロックのことじゃん！ これって思ったよりぜんぜん常識的なことじゃん！ 正に今僕が作っているプログラムの問題じゃん！ ぜんぜん人事じゃないよ！ そうか！
コメント一覧
まはヴぃーら 2008年07月07日 12:09
空気読むのもほどほどにしとけってことですね。
ところで「人事」って「他人事」のことですよね？
ところで「人事」って「他人事」のことですよね？
