Dining Philosophers（食事する哲学者問題）

アルゴリズム概要

問題の説明

5人の哲学者が円卓に座り、各自の間にフォークが1本ずつ（計5本）配置されています。各哲学者は「思考」と「食事」を交互に繰り返しますが、食事をするには左右両方のフォークが必要です。各フォークは同時に1人しか使用できません。

入出力例

制約条件

• 1 ≤ n ≤ 60（各哲学者が1〜60回食事）
• 5つのスレッドが並行実行
• デッドロック（全員が永久に待機）を回避
• 飢餓（特定の哲学者が永久に食事できない）を回避

戦略: リソース順序付け

主要ポイント

• 時間計算量: O(1) per call（ロック待機時間を除く）
• 空間計算量: O(1)（固定5個のLock）
• デッドロック回避: Coffmanの循環待機条件を破る
• 飢餓回避: threading.Lockの公平性保証による

ステップバイステップ解説

Python実装

from threading import Lock

class DiningPhilosophers:
    """
    食事する哲学者問題の解決クラス

    リソース順序付け戦略によりデッドロックを完全防止。
    常に小さいフォーク番号→大きいフォーク番号の順でロック取得。

    Time: O(1) per call
    Space: O(1) - 固定5個のLock
    """

    __slots__ = ('_forks',)  # メモリオーバーヘッド削減

    def __init__(self) -> None:
        """5本のフォークに対応するLockを初期化"""
        self._forks = [Lock() for _ in range(5)]

    def wantsToEat(
        self,
        philosopher: int,
        pickLeftFork,
        pickRightFork,
        eat,
        putLeftFork,
        putRightFork
    ) -> None:
        """
        哲学者が食事を行う処理

        Args:
            philosopher: 哲学者ID (0-4)
            pickLeftFork: 左フォーク取得関数
            pickRightFork: 右フォーク取得関数
            eat: 食事関数
            putLeftFork: 左フォーク返却関数
            putRightFork: 右フォーク返却関数
        """
        # 右フォークIDのみ計算（philosopher自身が左フォークID）
        r = (philosopher + 1) % 5

        # リソース順序付け: 小さいID優先でロック
        # 哲学者0-3: philosopher < r (80%のケース)
        # 哲学者4: philosopher > r (20%のケース)
        if philosopher < r:
            # 左(小) → 右(大) の順でロック
            self._forks[philosopher].acquire()
            self._forks[r].acquire()
            try:
                pickLeftFork()
                pickRightFork()
                eat()
                putRightFork()
                putLeftFork()
            finally:
                # ロック解放（取得の逆順）
                self._forks[r].release()
                self._forks[philosopher].release()
        else:
            # 右(小) → 左(大) の順でロック（哲学者4のみ）
            self._forks[r].acquire()
            self._forks[philosopher].acquire()
            try:
                pickLeftFork()
                pickRightFork()
                eat()
                putRightFork()
                putLeftFork()
            finally:
                # ロック解放（取得の逆順）
                self._forks[philosopher].release()
                self._forks[r].release()

フローチャート

フローの説明：
1. フォークIDを計算（右フォーク = (philosopher + 1) % 5）
2. philosopher < r の場合、左→右の順でロック（哲学者0-3）
3. philosopher ≥ r の場合、右→左の順でロック（哲学者4のみ）
4. 両方のフォークを取得（pickLeftFork, pickRightFork）
5. 食事を行う（eat）
6. フォークを返却（putRightFork, putLeftFork）
7. ロックを取得の逆順で解放

計算量分析

時間計算量

空間計算量

代替手法との比較