前回の記事に引き続き、今回は「哲学者の食事問題」におけるデッドロック について書いていきます。

並行処理では、複数のスレッドが同じメモリや共有資源にアクセスするため、データ競合(data race) が起こる危険があります。
そのため、同時に触られては困る部分、クリティカルセクション を mutex で保護する必要があることを学びました。

しかし、mutex を使えばすべて解決するわけではありません。
共有資源を守るためにロックを導入すると、今度はお互いが相手の資源を待ってしまい、誰も先に進めなくなる状態 が発生することがあります。
これが デッドロック(deadlock) です。

デッドロックとは？

たとえば哲学者の食事問題では、各哲学者は食事をするために2本のフォークを必要とします。
もし全員が同じタイミングで左のフォークを取って、そのまま右のフォークを待ったとすると、全員が「1本は持っているけれど、もう1本が手に入らない」状態になります。

このとき、

哲学者1は右のフォークを待つ
哲学者2も右のフォークを待つ
哲学者3も右のフォークを待つ
…
最後の哲学者も右のフォークを待つ

という状態になり、誰も食事を始められません。
このように、複数のスレッドやプロセスが互いに待ち合い、処理が止まってしまう状態 をデッドロックと呼びます。

並行処理では、スレッドがどの順番で実行されるかは固定ではありません。
そのため、「普段は問題なく動いているように見えるけれど、ある実行順序になったときだけ止まる」ということが起こります。
これが並行処理の特徴というか難しいところだなと思います。

デッドロックが発生する4条件

デッドロックは、次の4つの条件がすべてそろったときに発生します。

1. Mutual Exclusion（相互排他）
ある資源を同時に1つのスレッドしか使えないことです。
哲学者の問題では、1本のフォークを同時に2人で使うことはできません。

2. Hold and Wait（保持して待つ）
すでに1つの資源を持っているスレッドが、さらに別の資源を待っている状態です。
左のフォークを持ったまま右のフォークを待つ、という状況がこれに当たります。

3. No Preemption（強制的に奪えない）
いったん獲得した資源を、他のスレッドが無理やり取り上げることができないことです。
フォークは、それを持っている哲学者が手放すまで使えません。

4. Circular Wait（循環待ち）
待ち関係が輪になっている状態です。
AはBの資源を待ち、BはCの資源を待ち、最後はAの資源を待つ、というように循環していると、全体が止まります。

これら4つの条件がすべてそろったときにデッドロックが発生する、ということなので、1つでも成立しないようにできればデッドロックは防げます。

デッドロックへの対処法

大きく分けて３つの手法があるようです。

1. Prevention（予防）
デッドロック成立に必要な4条件のうち、少なくとも1つを成立しないように設計する方法です。

2. Avoidance（回避）
資源要求のたびに、その割り当てを許しても安全かを判断し、危険な状態に入らないようにする方法です。
代表例がBanker’s Algorithmで、これは各プロセスが必要とする最大資源量をあらかじめ把握しておき、要求が来るたびに「この割り当てを行ってもシステムが安全状態を保てるか?」を確認するものです。
もし割り当て後に安全状態を維持できるなら資源を与え、そうでなければ待たせます。
つまり、デッドロックが起きそうな状態そのものに入らないよう制御する考え方です。

3. Detect and Recover（検出と回復）
デッドロックの発生自体は許容し、発生後に検出して回復する方法です。

哲学者の食事問題では何を採用するのか？

哲学者の食事問題では、通常はprevention の考え方が用いられます。
最初からデッドロックが起きないように設計するということです。

特にデッドロックの４条件のうちの１つであるCircular Wait（循環待ち） を壊す方法がよく使われます。
哲学者の食事問題はダイクストラによる古典的な同期問題ですが、参考にしたOSTEPの本には、この問題に対する最も単純な解法として「少なくとも1人の哲学者だけ、他の哲学者と異なる順番でフォークを取る方法」が紹介されています。これはダイクストラ自身が用いた解法でもあるようです。
たとえば5人の哲学者がいる場合、1人だけ他の哲学者と逆の順番でフォークを取るようにすると、全員が同じ向きに待つ状況を崩すことができます。

ただし、この説明だけだと「最後の1人だけ逆順にすればよい」という個別のテクニックに見えてしまいます。

そこで、より一般的な考え方としてtotal orderingがあります。
これは、すべての共有資源に一意の順序を与え、常に小さい番号の資源から先に取得する いうルールを設ける方法です。
哲学者の食事問題で言えば、各フォークに番号を振って「常に番号の小さいフォークから取る」と決めることにあたります。

見た目の結果としては、「最後の哲学者だけフォークを取る順番が逆になる」ように見える場合があります。
しかし本質はそこではなく、リソース全体に順序を与えて、待ち関係に循環が生じないようにしている という点にあります。
これにより、待ち関係が輪にならなくなるため、デッドロックを防ぐことができます。

補足：total ordering と partial ordering

total orderingは非常に分かりやすく、哲学者の食事問題のような比較的単純な状況では有効です。
一方で、実際のシステムはもっと複雑で、すべてのリソースに単純な1本の順序を与えるだけでは扱いにくい場合があります。

そのような場合には、より柔軟なpartial orderingという考え方が使われるようです。
これは、必要な範囲で部分的に順序関係を定める方法です。
すべてを一直線に並べるのではなく、「この種類のロックはこの種類より先に取る」といった制約を設けるイメージです。

Linux のメモリ管理コードにも、そのような順序付けの考え方を見ることができるようです。
参考例: https://elixir.bootlin.com/linux/v5.2/source/mm/filemap.c

まとめ

どの手法を取るにせよ、単にmutex を使えば安全という話ではない、ということがわかりました。
共有資源を守るためのロックも、使い方を誤ると別のバグを生みます。

並行処理では、排他制御そのものだけでなく、ロックの取り方、取得順序、状態更新の設計 まで考える必要があります。

哲学者の食事問題はデッドロックさえ避ければ良いような単純な題材に見えます。
実際にはatomicity-violation bugs, order-violation bugsといったデッドロック以外のバグも意識しなければならず、並行処理における重要な落とし穴が凝縮されている問題だと感じました。

次回は、デッドロック以外のバグのatomicity-violation bugs, order-violation bugsについてもう少し理解を深めたいと思います。

参照図書:

https://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf
https://pages.cs.wisc.edu/~remzi/OSTEP/threads-bugs.pdf
※PDFで公開されています：
日本語訳はこちら
https://github.com/syarochan/Operating-Systems-Three-Easy-Pieces-in-japanese/blob/master/31/31.md
https://github.com/syarochan/Operating-Systems-Three-Easy-Pieces-in-japanese/blob/master/32/32.md