互いに譲らないと、デッドロック

握って、そして待つ

前回、私たちは良い習慣を一つ学びました。何かを直すにはまずそれを握り、ほかの人は終わるまで待つ、というものでした。一つしかないトイレに並ぶように。そうすれば、二人が重なって台無しにする事故が消えました。
さて、仕事が二つに増えたとしましょう。資源が二つあります。道具1と道具2と呼びます。ある仕事を終えるには両方の道具が要ります。Aは道具1を先に握って道具2を待ちます。Bは道具2を先に握って道具1を待ちます。それぞれ規則どおり一つ握っただけなのに、どちらももう一つを手に入れられません。
握ったものは放さず、ないものは待つ。この握って待つことが、すべての始まりです。

AとBにそれぞれ一つずつ握らせてみましょう。Aは道具1を握って道具2を待ち（赤）、Bは道具2を握って道具1を待ちます。どちらも握ったものを放さず、ないものを待つので、先へ進めません。

不思議ではありませんか。どちらも悪いことをしたわけではありません。ただ順番に一つ握っただけです。前回、安全だと学んだまさにその方法どおりに。それなのに二人とも止まってしまいました。
問題は握ること自体ではなく、握ったまま互いを待つかたちにあります。このかたちをもっとはっきり見るには、一つの絵を思い浮かべるとよいです。次で、なじみのある場面に変えてみましょう。

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

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

二人を真ん中へ一マスずつ前進させてみましょう。橋の真ん中で出くわすと、どちらも場所を譲らないので、進めず止まります（赤）。

橋では二人が向かい合いました。だから止まりました。でも、行き詰まるのが二人だけとはかぎりません。三人、四人、もっと多くの人が一列ではなく円く並んで互いを待つと、同じ止まりがもっと大きく起きます。
次で、人々を円く座らせてみましょう。輪が閉じるその瞬間を、自分の手で作ってみます。

輪が閉じると、みな止まる

食卓に何人かが円く座っています。人と人の間ごとに、箸が一本ずつ置いてあります。食べるには両側の箸が要るのに、みなが同じように左のを先に取って、右のを待つことにしました。
一人か二人だけならよいのです。だれかが両方を取って食べ、終われば置くからです。ところが、みなが同時に左を取ってしまうと、みなの右の箸は隣の人の手にあります。みなが隣の人を待ちます。待ちがぐるりと一周して、自分自身に戻ってきます。
こうして待ちの矢印が丸い輪をなすと、その輪の上のだれも永遠に動けません。狭い橋の二人が、食卓をぐるりと囲む大勢に増えたわけです。

輪になって座った人たちに、順に左の箸を取らせてみましょう。最後の一人まで取って輪が閉じた瞬間、みなの右が隣の手にあるので、全員が止まります（赤）。

輪が閉じたその最後の一歩で、ちゃんと回っていた食卓が、まるごと凍りつきました。こわいのは、だれか一人がとくに悪いことをしたわけではない、という点です。みなが同じように合理的に左から取っただけなのに、全体が止まりました。
では、この凍った食卓をどう溶かすのでしょう。幸い、やり方は意外と単純です。次で、輪をほどく二つの道を見ましょう。

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

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

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

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

一枚にまとめます

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

各ステップを順に押して、一周をたどってみましょう。握って待つから向かい合いへ、閉じた輪から譲り・順番でほどくまで。デッドロックの一生がひと目で整理できます。

前回は一人ずつやれば安全だと学びましたが、今日はその順番に握ることが、かえってみなを止めうると見ました。同じ道具も使いよう、ということです。安全な行列と、永遠に止まるデッドロックは、紙一重です。握る順番をみな同じにそろえるか、だれかが譲れるか、それがその一重を分けます。