Ractorで「食事する哲学者の問題」を解く

Posted on November 21, 2020 , Tags: Ruby, Ractor, STM, Ractor::TVar

Ruby に Software Transactional Memory (STM) を入れようと思った話 を読んで、そういえば STM で 「食事する哲学者の問題」 を解ける、という話を見たなと思い、やってみた。

食事する哲学者の問題

「食事する哲学者の問題」について軽く説明をする。N 人の哲学者が円卓に座り、食事をとる。それぞれの哲学者の間にはフォークが置かれており(N 人なら N 個になる)、自分の両側のフォークを手に持つことができれば食事ができる。詳しくは上記 Wikipedia を見るとよい。

まずはデッドロックを発生させてみる

素直に悲観的ロックでこの問題を解くとデッドロックが発生する。Ractor を使って書くと以下のようになる。

Mutex を包んだ Ractor を左と右のフォークとして哲学者に渡し、それぞれのロックが獲得できたなら、食事をする。という動きになっている。
これを実行すると以下のようにデッドロックが発生する。

STM を使って解く

STM で解く「食事する哲学者の問題」 - あどけない話 にあるように STM を使うと、デッドロックを回避できるようだ。
ractor-tvar を使えば同じように実装できるのかやってみる。
まずは Gemfile を作って、ractor-tvar をインストールしておく

この後、手元で ractor-tvar のサンプルコードを動かしたところ cannot load such file -- ractor/tvar/ractor_tvar.so (LoadError) というエラーがでた。そのため ractor_tvar.so の場所を手動で変更して回避した。自分の手元環境だけかもしれないが一応issue を起票しておいた(2020/11/24 追記) この問題は 0.2.0 で修正された。

STM での実装だが、今回は以下のように実装した。

Ractor::TVar に自分の名前を入れることでロックの代わりとした。
これを実行してみると以下のように、デッドロックになることなく進むことが確認できた。

(2020/11/27 追記) Ractor::RetryTransaction を使えばループいらないのではという指摘をいただいたのでそのように修正した。感謝。

まとめ

STM を使うことで、食事する哲学者の問題のデッドロックを回避できた。 今回作ったコードは yoshitsugu/dining_philosophers_problem_ractor として GitHub に公開してある。