食事する哲学者の問題 with Cizen #Elixir

CizenはElixirでSagaと呼ばれるイベントの購読と配信によって協調動作するプロセス群を使って並列アプリケーションを作るためのライブラリです。本記事ではCizenを使って食事する哲学者の問題を実装してデッドロックを起こした後、解消してみます。

食事する哲学者の問題

まず食事する哲学者の問題について軽く説明します。
まず、円形のテーブルの周りに5人の哲学者が等間隔で座っており、それぞれの正面にある皿で食事をしようとしています。ただし、箸は5枚の皿の間に1本ずつあるだけで全体としては2.5膳しかありません。そして、それぞれの哲学者は自分の皿の両隣の箸しか使えず、会話をしないという制限があるなかで、それぞれの哲学者が箸を2本使って食事を行おうと試みます。

オートマトンとイベント

CizenではSagaを作成する方法がいくつかありますが、本記事ではAutomatonというAPIを使用して各登場人物を作成していきます。

まず作成するオートマトンは以下の2つです。

Philosopher
Chopstick

Philosopherは哲学者、Chopstickは箸を表現するオートマトンです。イベントは以下のものを使います。

BorrowChopstick 箸を要求するイベント
LendChopstick 箸を貸すイベント
ReturnChopstick 箸を返すイベント

それでは実装してみましょう。

プロジェクトの準備

まずは以下のコマンドでプロジェクトを作成します。

mix new cizen_dining_philosophers
cd cizen_dining_philosophers

次にmix.exsを開いて以下のようにdepsにcizenを追加します。

defp deps do
  [
    {:cizen, "~> 0.14.1"}
  ]
end

最後にmix deps.getを実行することでcizenが使える状態になります。

イベントの定義

まずは前述した3つのイベントを定義しましょう。

dining.exsというファイルを作成し以下のコードを挿入してください。

defmodule BorrowChopstick do
  defstruct [:chopstick_id]

  use Cizen.Request # to use defresponse/3
  defresponse LendChopstick, :request_id do
    defstruct [:request_id]
  end
end

defmodule ReturnChopstick do
  defstruct [:chopstick_id]
end

3つのイベントはそれぞれただのstructです。また、LendChopstickを定義するときに使っているdefresponse/3は1対のリクエストとレスポンスになるイベントを定義するときに便利なヘルパです。

箸の定義

次に箸を定義しましょう。

dining.exsに以下のコードを追加します。

defmodule Chopstick do
  use Cizen.Automaton
  defstruct []

  alias Cizen.Effects.{Dispatch, Receive, Subscribe}
  alias Cizen.{Event, Filter}

  @impl true
  def spawn(id, %__MODULE__{}) do
    perform id, %Subscribe{
      event_filter: Filter.any([
        Filter.new(fn %Event{body: %BorrowChopstick{chopstick_id: ^id}} -> true end),
        Filter.new(fn %Event{body: %ReturnChopstick{chopstick_id: ^id}} -> true end)
      ])
    }
    :available
  end

  @impl true
  def yield(id, :available) do
    received = perform id, %Receive{
      event_filter: Filter.new(fn %Event{body: %BorrowChopstick{}} -> true end)
    }

    alias BorrowChopstick.LendChopstick
    perform id, %Dispatch{
      body: %LendChopstick{
        request_id: received.id
      }
    }

    :not_available
  end

  @impl true
  def yield(id, :not_available) do
    perform id, %Receive{
      event_filter: Filter.new(fn %Event{body: %ReturnChopstick{}} -> true end)
    }

    :available
  end
end

状態が:availableのときは箸を誰かに貸し、:not_availableのときは箸が返されるまで待つというだけの動作です。

哲学者の定義

次に哲学者を定義します。

dining.exsに以下のコードを追加します。

defmodule Philosopher do
  use Cizen.Automaton
  defstruct [:name, :left_chopstick, :right_chopstick]

  alias Cizen.Effects.{Request, Dispatch}

  @impl true
  def spawn(_id, struct) do
    {:hungry, struct}
  end

  @impl true
  def yield(id, {:hungry, struct}) do
    %__MODULE__{
      name: name,
      left_chopstick: left_chopstick,
      right_chopstick: right_chopstick
    } = struct

    IO.puts("#{name} is hungry.")

    perform id, %Request{
      body: %BorrowChopstick{
        chopstick_id: left_chopstick
      }
    }

    IO.puts("#{name} has a chopstick in their left hand.")

    perform id, %Request{
      body: %BorrowChopstick{
        chopstick_id: right_chopstick
      }
    }

    IO.puts("#{name} has chopstics in both hands.")

    {:eating, struct}
  end

  @impl true
  def yield(id, {:eating, struct}) do
    %__MODULE__{
      name: name,
      left_chopstick: left_chopstick,
      right_chopstick: right_chopstick
    } = struct

    IO.puts("#{name} is eating.")

    perform id, %Dispatch{
      body: %ReturnChopstick{
        chopstick_id: left_chopstick
      }
    }

    perform id, %Dispatch{
      body: %ReturnChopstick{
        chopstick_id: right_chopstick
      }
    }

    {:hungry, struct}
  end
end

状態が:hungryのとき左手→右手の順に箸を借り、両方借りられた場合は状態が:eatingに遷移
状態が:eatingのとき左手→右手の順に箸を返してから:hungryに遷移

という処理を行います。

デッドロック！

箸と哲学者の用意ができたので早速食事の席を用意しましょう。

dining.exsに以下のコードを追加します。

defmodule Dining do
  use Cizen.Effectful # for handle/1 and perform/2

  alias Cizen.Effects.{All, Start}

  def run do
    handle fn id ->
      chopstick_1 = perform id, %Start{saga: %Chopstick{}}
      chopstick_2 = perform id, %Start{saga: %Chopstick{}}
      chopstick_3 = perform id, %Start{saga: %Chopstick{}}
      chopstick_4 = perform id, %Start{saga: %Chopstick{}}
      chopstick_5 = perform id, %Start{saga: %Chopstick{}}

      philosophers = [
        %Philosopher{
          name: "Plato",
          left_chopstick: chopstick_1,
          right_chopstick: chopstick_2
        },
        %Philosopher{
          name: "Konfuzius",
          left_chopstick: chopstick_2,
          right_chopstick: chopstick_3
        },
        %Philosopher{
          name: "Socrates",
          left_chopstick: chopstick_3,
          right_chopstick: chopstick_4
        },
        %Philosopher{
          name: "Voltaire",
          left_chopstick: chopstick_4,
          right_chopstick: chopstick_5
        },
        %Philosopher{
          name: "Descartes",
          left_chopstick: chopstick_5,
          right_chopstick: chopstick_1
        }
      ]

      perform id, %All{
        effects: Enum.map(philosophers, &(%Start{saga: &1}))
      }

      receive do
        _ -> :ok
      end
    end
  end
end

Dining.run

mix run dining.exsというコマンドで実行すると当然デッドロックが発生します。

実行結果は以下のようになるはずです。

Plato is hungry.
Konfuzius is hungry.
Socrates is hungry.
Voltaire is hungry.
Descartes is hungry.
Plato has a chopstick in their left hand.
Konfuzius has a chopstick in their left hand.
Socrates has a chopstick in their left hand.
Voltaire has a chopstick in their left hand.
Descartes has a chopstick in their left hand.

デカルトは腕をクロスする

さて、どのようにすればデッドロックを解消させることができるでしょうか？

見出しでネタバレしていますが、デカルトが箸を取るときに右手で左側の箸を左手で右側の箸を取るようにすれば解決します。このデッドロックには様々な解消方法がありますが、おそらくこれが一番早いと思います。

dining.exsのDining.run/0のDescartesを定義している部分を以下のように書き換えます。
左手で箸5、右手で箸1を取っていたのを左手で箸1、右手で箸5を取るように変更しました。

%Philosopher{
  name: "Descartes",
  left_chopstick: chopstick_1,
  right_chopstick: chopstick_5
}

これでまたmix run dining.exsで実行すると五人の哲学者が永遠に食事を続けるようになります。

以下は実行結果の例です。

Plato is hungry.
Konfuzius is hungry.
Socrates is hungry.
Voltaire is hungry.
Descartes is hungry.
Plato has a chopstick in their left hand.
Konfuzius has a chopstick in their left hand.
Socrates has a chopstick in their left hand.
Voltaire has a chopstick in their left hand.
Voltaire has chopstics in both hands.
Voltaire is eating.
Voltaire is hungry.
Socrates has chopstics in both hands.
Socrates is eating.
Socrates is hungry.
Konfuzius has chopstics in both hands.
Konfuzius is eating.
Voltaire has a chopstick in their left hand.
Konfuzius is hungry.
Plato has chopstics in both hands.
Plato is eating.
Plato is hungry.
Socrates has a chopstick in their left hand.
Voltaire has chopstics in both hands.
Voltaire is eating.
Voltaire is hungry.
Descartes has a chopstick in their left hand.
Konfuzius has a chopstick in their left hand.
Socrates has chopstics in both hands.
Socrates is eating.
Socrates is hungry.
Descartes has chopstics in both hands.
Descartes is eating.
Descartes is hungry.
.
.
.

さいごに

Cizen、雑に書いてもそれっぽく動くので楽しすぎる……

ソースコード