応用情報技術者 2017年秋期午前2 問29

問題文

トランザクションA〜Gの待ちグラフにおいて、永久待ちの状態になっているトランザクション全てを列挙したものはどれか。ここで、待ちグラフのX→Yは、トランザクションXはトランザクションYがロックしている資源のアンロックを待っていることを表す。

🖊️ 解答を隠して解いてみる

選択肢

ア：A, B, C, D

イ：B, C, D

ウ：B, C, D, F（正解）

エ：C, D, E, F, G

🔒 解説は解答すると表示されます

待ちグラフと永久待ち【午前2解説】

正解の理由

待ちグラフの矢印は、C→A、C→B、B→D、D→C、D→E、E→G、F→D、F→E の8本です。B→D→C→B が循環しているので、B、C、D は互いに相手のアンロックを待ち続け、永久待ち（デッドロック）になります。さらに F は D のアンロックを待っていますが、D は永久に処理を終えないので、F も永久に先へ進めません。一方、A と G は何も待っておらず、E は G を待つだけなので、G の終了後に処理を続けられます。よって永久待ちは B、C、D、F で、ウが正解です。

解法ステップ

矢印を書き出す。C→A、C→B、B→D、D→C、D→E、E→G、F→D、F→E
循環（有向サイクル）を探す。B→D→C→B が循環しているので、B、C、D は永久待ち。
循環しているトランザクションを待っているトランザクションを探す。F→D があるので、F も永久待ち。
残りを確認する。
- A：出ていく矢印がない（何も待っていない）ので、処理を続けられる。
- G：同じく何も待っていない。
- E：G だけを待っている。G が終われば処理を続けられる。

選択肢別の誤答解説

ア: A, B, C, D
A は C から待たれているだけで、A 自身は何も待っていません。永久待ちではありません。また、F が抜けています。
イ: B, C, D
循環している3つだけを挙げていますが、循環中の D を待っている F が抜けています。
ウ: B, C, D, F
循環している B、C、D と、D を待つ F で、正しい組合せです。
エ: C, D, E, F, G
E と G は永久待ちではなく、循環している B が抜けています。

よくある誤解

循環の中のトランザクションだけを永久待ちと考えること。循環の中のトランザクションを待っているトランザクションも、待ち続けるしかないので永久待ちになります。
矢印の向きを逆に読むこと。X→Y は「X が Y を待つ」なので、待たれている側（矢印の先）が何も待っていなければ、その先は処理を続けられます。

補足コラム

待ちグラフで永久待ちになるのは、「循環の中にあるトランザクション」と「矢印をたどると循環に行き着くトランザクション」です。矢印をたどった先が、何も待っていないトランザクションで終わるなら、そのトランザクションは時間がたてば処理を続けられます。

FAQ

Q. D は E も待っていますが、E は永久待ちになりませんか？
A. 待っているのは D の側です。E 自身は G だけを待っているので、G の処理が終われば E も処理を続けられます。

Q. デッドロックはどう解消しますか？
A. 循環中のトランザクションの一つ（例えば B）をロールバックしてロックを解放させます。すると循環が解け、C、D、F も順に処理を続けられます。

関連キーワード: 待ちグラフ、デッドロック、永久待ち、ロック、トランザクション

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！