AOJ 1604 - デッドロック検出
解法
まずは、すでにロックを獲得した資源と、次に獲得する資源を対にした頂点を作成していきます。
10個程度しか資源は存在しないので、ビットで情報を持たせることができます。
その後、2つの頂点を選んだときのパターンを見ると、今回は3パターンします。
2つの頂点どちらも既にロックを獲得した資源が存在しているパターン
2つの頂点が同時に存在することはないので、無視してかまいません。2つの頂点どちらも既にロックを獲得した資源が存在せず、片方の頂点が所有している資源をもう片方の頂点が次に獲得するパターン
片方(青い方)はこれ以降資源を獲得することはできませんが、もう片方(黄色)は次の資源を獲得することができます。この2つの頂点は、和集合の資源を獲得した状態で、次に黄色のNEXTの部分の資源を獲得しにいく1つの頂点とみなすことができます。2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いの頂点が、相手が所有している資源を次に獲得するパターン
言うまでもなくデッドロックが発生します。2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いが次に獲得する資源はどちらも所有していない資源のパターン
お互いが影響しあうことはないので、無視できます。
全てのパターンについて、tps://onlinejudge.u-aizu.ac.jp/problems/1604)
提出コード
解法
まずは、すでにロックを獲得した資源と、次に獲得する資源を対にした頂点を作成していきます。
10個程度しか資源は存在しないので、ビットで情報を持たせることができます。
その後、2つの頂点を選んだときのパターンを見ると、今回は3パターンします。
2つの頂点どちらも既にロックを獲得した資源が存在しているパターン
2つの頂点が同時に存在することはないので、無視してかまいません。2つの頂点どちらも既にロックを獲得した資源が存在せず、片方の頂点が所有している資源をもう片方の頂点が次に獲得するパターン
片方(青い方)はこれ以降資源を獲得することはできませんが、もう片方(黄色)は次の資源を獲得することができます。この2つの頂点は、和集合の資源を獲得した状態で、次に黄色のNEXTの部分の資源を獲得しにいく1つの頂点とみなすことができます。2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いの頂点が、相手が所有している資源を次に獲得するパターン
言うまでもなくデッドロックが発生します。2つの頂点どちらも既にロックを獲得した資源が存在せず、お互いが次に獲得する資源はどちらも所有していない資源のパターン
お互いが影響しあうことはないので、無視できます。
全てのパターンについての判定がこれで網羅できるようになるので、あとは複数頂点が1つの頂点にまとめられる回数、つまり10回程度、任意の2頂点について操作を行うということを繰り返せば、デッドロックが起こるかどうかを判定できます。
感想
資源数が少ないので状態を頂点にするという発想まではよかったのですが、それ以降どうすればいいかわかりませんでした…
