応用情報技術者試験 応用情報技術者試験 平成29年度秋期 午前 問29: トランザクション A〜G の待ちグラフにおいて，永久待ちの状態になっているトランザクション全てを列挙したものはどれか。ここで，待ちグラフの X→Y は，トランザ

問題本文

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

選択肢

• ア.A, B, C, D
• イ.B, C, D
• ウ.B, C, D, F
• エ.C, D, E, F, G

正解

ウ. B, C, D, F

解説

待ちグラフでは X→Y は『X が Y のアンロックを待つ』ことを表し，矢印をたどって閉路(サイクル)ができると互いに永久に待ち合うデッドロック(永久待ち)になる。このグラフでは B→D→C→B という閉路があり，B・C・D は循環待ちで永久待ちになる。さらに F→D の矢印があり，F は永久待ちの D を待っているので F も永久にアンロックされず永久待ちになる。よって永久待ちは B, C, D, F で，ウが正しい。

選択肢ごとの解説

• ア.誤り。A は他から待たれているだけで，A 自身は何も待っていない(出ていく矢印がない)ため永久待ちではない。F が抜けている点も誤り。
• イ.誤り。閉路 B→D→C→B の B・C・D は正しいが，その D を待っている F も永久待ちになるため，F が抜けている。
• ウ.正しい。閉路を成す B・C・D に加え，永久待ちの D を待つ F も永久にアンロックされず永久待ちになる。
• エ.誤り。E は G を待ち，G は何も待たずいずれ完了できるため E・G とも永久待ちではない。閉路に入らない E,G を含む点が誤りで，閉路の B も欠けている。