平成23年度 秋期 午前 問20

✓ これが正解イC，D

解説

取る順序が食い違う相手とだけ輪ができます。

表に並んでいる数値は、そのプロセスが資源を何番目に占有するかを表しています。ですからまず、表を取りに行く順番の並びに直します。プロセス A は資源 X、資源 Y、資源 Z の順です。プロセス B も同じ並びです。プロセス C は資源 Z、資源 X、資源 Y の順で、プロセス D は資源 Z、資源 Y、資源 X の順です。デッドロックは、互いに相手が握っているものを待ち合って、どちらも先へ進めなくなる状態です。つまり待ちの関係が輪になったときに起こります。ここで要になるのは、並びがそろっているかどうかです。同じ並びで取りに行く相手どうしでは、先に始めたほうが順に握っていき、後から来たほうは一つ目の入口で止まったまま待ちます。追い越しが起こらないので、握ったまま相手を待つ形にならず、輪はできません。並びが食い違う相手とは、一方が先頭のものを握り、もう一方が別のものを握った状態で、互いに相手の持ち分を待つ場面を作れます。排他制御では占有の順番を全体でそろえておくのが定石ですが、この設問はその定石を裏返し、そろっていない相手を探させる形になっています。

ほかの選択肢はなぜ違うのか

• アB，C，D：B を含めた三つを挙げていますが、B は A とまったく同じ並びで取りに行くので追い越しが起きようがなく、待ち合いの輪にはなりません。一つ多い答えです。
• ウC だけ：C だけを挙げていますが、D も A と並びが食い違います。D が最後に求める資源 X は A が最初に握るものなので、両者が互いを待つ場面を作れます。一つ取りこぼしています。
• エD だけ：D だけを挙げていますが、C も A と並びが食い違います。C が最初に求める資源 Z は A が最後に握るものなので、ここでも互いを待つ場面が成り立ちます。こちらも一つ足りません。