並列プログラミングにおいて、各プロセスの協調をどうやって取るか、という問題に関する比喩。

並行処理の研究題材としてエドガー・ダイクストラ(Edsger Wybe D〓kstra)が提唱した。

目次 問題 検討課題

問題

中央にスパゲッティが盛られた円卓の回りに5人の哲学者が座っており、それぞれの前に皿が1枚置かれ、その右側にフォークが1本置かれる。

各哲学者から見ると、左右に1本ずつフォークが置かれているように見えるが、テーブル全体では5本しかフォークはない。哲学者は普段は考え事をしているが、空腹になると、まず自分の右側にあるフォークを取り、次に自分の左にあるフォークを取ってスパゲティを自分の皿に盛り、左のフォークを元の場所に戻して右のフォークで食事し、食事が終わると右のフォークを置いてまた考え事に戻る。

もし自分の使いたいフォークを他の人が使っている場合には、それが空くまで待っている。

検討課題

普段はこれで問題がないが、ある瞬間に哲学者が5人とも食事をしたいと思った場合を想定する。

全員が右のフォークを手に取り、左隣の哲学者が使用中の左のフォークが空くのを待つが、その左の哲学者も同じ状況になるので、結果としていつまでも食事ができなくなってしまう。これは「デッドロック」と呼ばれる。

これを避ける方法を考えるのが、哲学者の食事問題である。

リンク

用語の所属
並列処理
関連する用語
プロセス
デッドロック
リソースの競合
ストール
エドガー・ダイクストラ

[再検索] [戻る]