わかりやすく デッドロック とは

握って、そして待つ

レースコンディションのレッスンで、よい習慣を一つ身につけました。何かを書き換えるときはまずそれを握り、使い終わるまでほかの人には待ってもらう、というものです。一人用のトイレに並ぶのと同じです。おかげで、二人が重なって結果を台無しにする事故はなくなりました。
今度は、仕事に資源が二つ必要だとします。道具1と道具2と呼び、仕事を終えるには両方がそろっていなければなりません。Aは道具1を先に握って道具2を待ちます。Bは道具2を先に握って道具1を待ちます。どちらもルールどおり一つずつ握っただけなのに、残りの一つはいつまでも手に入りません。
握ったものは放さず、ないものは待つ。この「握って待つ」が、すべての問題の始まりです。

二つのボタンを押して、AとBに一つずつ握らせます。Aは道具1を握って道具2を待ち、Bは道具2を握って道具1を待ちます。どちらも握ったものを放さず、ないものだけを待つので、先へ進めません（赤）。

不思議なことに、どちらも悪いことはしていません。レースコンディションのレッスンで安全だと学んだやり方どおり、順番に一つを握っただけです。それでも二人とも止まってしまいました。
問題は握ること自体ではなく、握ったまま互いを待つという形にあります。この形をもっとはっきり見るには、身近な場面を一つ思い浮かべるとよいでしょう。

狭い橋で向かい合った二人

一人がやっと通れるくらいの狭い橋があります。片方の端から一人が、反対の端からもう一人が、同時に橋に足を踏み入れます。二人は真ん中へ向かって歩き、ばったり出くわします。
先へ進むには、相手によけてもらうしかありません。ところが、二人とも自分の立っている場所を譲りません。自分が先に来たから、自分のほうが急いでいるから。だれも下がらないので、二人は真ん中でいつまでも立ち止まったままです。
橋の一マス一マスが先ほどの道具1と道具2で、二人がAとBです。それぞれ自分の場所を握ったまま相手の場所を待つ、さっき見た形そのものです。

二つのボタンで、AとBを一マスずつ真ん中へ進めます。橋の真ん中で出くわすと、どちらも場所を譲らないので、それ以上進めずに止まります（赤）。

橋の上では、二人が向かい合ったところで止まりました。けれども、詰まるのが二人とはかぎりません。三人、四人、もっと多くの人が一列ではなく輪になって並び、互いを待てば、同じ停止がもっと大きく起こります。
今度は人々を食卓に輪になって座らせ、待ちの輪が閉じる瞬間を自分の手で作ります。

輪が閉じると全員が止まる

食卓に五人が輪になって座っていて、隣り合う人のあいだに箸が一本ずつ置いてあります。食べるには左右両方の箸が必要ですが、全員が同じように、左の箸を先に取って右の箸を待つことにしました。
一人や二人がそうするだけなら問題ありません。だれかが両方を取って食べ、食べ終われば置くからです。ところが全員が同時に左の箸を取ると、全員の右の箸は隣の人の手の中にあります。全員が隣の人を待ち、待ちが食卓をひと回りして自分のところへ戻ってきます。
こうして待ちの矢印が丸い輪になると、輪の上のだれも永遠に動けません。狭い橋の二人が、食卓を囲む大勢に増えたようなものです。

ボタンを押すたびに、次の人が左の箸を取ります。五人目まで取って輪が閉じた瞬間、全員の右の箸が隣の人の手にあるので、すべてが止まります（赤）。

輪が閉じる最後の一歩で、順調に回っていた食卓がまるごと凍りつきました。怖いのは、だれか一人が特に悪いことをしたわけではない点です。全員が同じように、もっともらしく左から取っただけなのに、全体が止まりました。
では、凍りついた食卓はどうやって溶かせばよいのでしょうか。幸い、方法は意外に単純で、道は二つあります。

ほどき方：譲るか、順番を決めるか

一つ目の道は譲ることです。輪の上のだれか一人が、握っていたものをいったん置きます。すると、その人を待っていた隣の人が二本そろえて食べ、食べ終われば置きます。一か所がほどけると次の人がほどけ、詰まりがドミノ倒しのように順にほどけていきます。輪に切れ目が一つでもできれば、もう丸い輪ではないからです。
二つ目の道はもっと賢いやり方です。輪がそもそも閉じないように前もって防ぎます。全員に「だれでも、いつも番号の小さいほうから取る」という同じルールを与えます。そうすれば、道具1を取れなかった人は道具2も取らずに待ちます。全員が同じ順番で取るので、二人が食い違って向かい合うことが起きず、輪はできようがありません。

まず輪を閉じて全員を止め、それから一人に譲らせます。その人が握っていたものを置くと輪が切れ、隣の人から順にほどけて、全員がまた動き出します（緑）。

譲ることはすでに止まった輪をほどく道で、順番を決めることは止まりそのものを起こさない道です。一つは事故が起きたあとの応急手当、もう一つは事故を前もって防ぐ予防といえます。
どちらも、かなめは同じです。丸い待ちの輪を閉じさせないことです。どこか一か所でも切れれば、止まりは再び流れに変わります。

一枚にまとめると

覚えておくことは四つです。
一つ目、それぞれが一つずつ握ったまま相手のものを待つと、「握って待つ」が始まります。二つ目、狭い橋の二人のように、向かい合って譲らなければ、どちらも止まります。
三つ目、その止まりがぐるりと一周して輪が閉じると、輪の上の全員が止まります。これがデッドロックです。四つ目、だれかが握ったものを置いて譲るか、全員が同じ順番で取るように決めておけば、輪が切れるか、そもそもできないので、再び流れられます。

四つのステップを順に押すと、「握って待つ」、橋の上での向かい合い、閉じた輪、譲ることと順番によるほどき方まで、デッドロックの始まりから終わりまでが一枚にまとまります。

レースコンディションのレッスンでは一人ずつ順番にすれば安全だと学びましたが、今回は、その順番に握るやり方がかえって全員を止めてしまうこともあると見ました。同じ道具も使い方しだいというわけです。
安全な行列と、永遠に止まるデッドロックは紙一重です。握る順番を全員でそろえるか、だれかが譲ることを知っているかが、その紙一枚を分けます。
OSの分野に残るレッスンはあと一つです。電源ボタンを押した瞬間から画面がつくまで、コンピューターがどうやって自分で目を覚ますのかを扱います。