待ちグラフと永久待ち
出典: 平成29年度 秋期 応用情報技術者試験 午前 問29 (IPA)
トランザクション A～G の待ちグラフにおいて，永久待ちの状態になっているトランザクション全てを列挙したものはどれか。ここで，待ちグラフの X→Y は，トランザクション X はトランザクション Y がロックしている資源のアンロックを待っていることを表す。
〔トランザクション A～G の待ちグラフ〕
- ア A, B, C, D
- イ B, C, D
- ウ B, C, D, F
- エ C, D, E, F, G
正解と解説を見る
正解: ウ
- ア: A は誰も待っていないので、永久待ちにはなりません。また F が抜けています。
- イ: B，C，D は閉路でデッドロックしていますが、D を待っている F も永久待ちになるので抜けています。
- ウ: 閉路の B，C，D と、D を待ち続ける F が永久待ちになるので正しい答えです。
- エ: B が抜けているうえ、E と G は G が何も待っていないので、いずれ処理が進みます。
ポイント
- 矢印をたどると B → D → C → B と輪になっています (閉路)。B，C，D はお互いを待っていて、永久に進めません (デッドロック)。
- F は D を待っています。D は永久に資源を解放しないので、F も永久に待つことになります。
- A，E，G は輪の外の、待っていないトランザクションや、待ちが解消されるトランザクションです。C は A も待っていますが、A は何も待っていません。E は G を待っていますが、G は何も待っていないのでいずれ進めます。