デッドロック — お互いの一足を待ち続ける2人

2人のランナーが、それぞれ片方ずつスニーカーを握っています。Aさんは右足、Bさんは左足。走るには左右ペアが必要なのに、お互い「君がそっちを離してくれたら走れるのに」と相手の1足を待ち続け、永遠に動けません。これがデッドロックです。

プログラムでも、複数の処理が複数の資源(ロック)を取り合うとき、まったく同じことが起こります。下の図1で、2つのスレッドにロックを取らせて、どうすれば膠着するのか・どうすれば防げるのかを自分の手で再現してみてください。

デッドロックが成立する「4つの条件」

デッドロックは気まぐれに起きるのではなく、4つの条件がすべて揃ったときだけ発生します(コフマンの条件)。図1で起きたのは、まさにこの4つが同時に成り立った瞬間です。

裏を返せば、この4つのうち1つでも崩せばデッドロックは起きません。実務でいちばんよく使われるのが④「循環待ち」を壊す方法です。

やり方は驚くほど単純で、「全員が必ず同じ順番でロックを取る」と決めるだけ。たとえば「必ずA→Bの順で取る」と統一すれば、スレッド①がAを持っているとき、スレッド②はそもそもBより先にAを取りに来るので、Aの前で待つことになります。①→②→①という待ちの輪(サイクル)ができなくなるのです。図1で②にも「Aを取得」から始めさせると、デッドロックにならないことを確かめてみてください。

まとめ

デッドロックは「お互いが、相手の持っているものを待ち続ける輪」。発生には4条件が揃う必要があり、逆に1つ崩せば防げます。実務では「ロックを取る順番を全員で統一する」のが王道。並行処理のバグで処理が固まったら、まず「どこかに待ちの輪ができていないか」を疑ってみてください。