database-deadlocks - デッドロック管理

Question

私は調査を行っていますが、関連する情報を見つけるのは困難です。私はこの問題に遭遇しました：

次のトランザクション シナリオの待機グラフを生成し、デッドロックが存在するかどうかを判断します。

取引：

T1
T2
T3
T4
T5
T6
T7
T8
T9
T10 

トランザクションによってロックされたデータ項目:

X1,X2,X3
X4,X5,X6
X7,X8
X9,X10
X11,X12
X13,X14
X15
X1111 
X115
X199

トランザクションが待機中のデータ項目:

X4,X5,X6,X7
X7,X8,X9
X1,X10,X111
X7,X11,X12
X5
X6,X1,X2,X3,X11,X12
X5
X1,X115
X1
X11,X12

さて、私がトランザクション管理について見た限りでは、これは非常に難しいことでした。誰かがこの種の問題を解決する方法の説明への参照を提供したり、とにかく助けたりできますか?

Answer 1

よくあることですが、いくつかの問題を解決する鍵は、適切な表現を選択することです。問題を表形式で表す場合:

T1 =>  { locked => [ qw( X1 X2 X3 ) ], waiting => [ qw( X4 X5 X6 X7         ) ] },
T2 =>  { locked => [ qw( X4 X5 X6 ) ], waiting => [ qw( X7 X8 X9            ) ] },
T3 =>  { locked => [ qw( X7 X8    ) ], waiting => [ qw( X1 X10 X111         ) ] },
T4 =>  { locked => [ qw( X9 X10   ) ], waiting => [ qw( X7 X11 X12          ) ] },
T5 =>  { locked => [ qw( X11 X12  ) ], waiting => [ qw( X5                  ) ] },
T6 =>  { locked => [ qw( X13 X14  ) ], waiting => [ qw( X6 X1 X2 X3 X11 X12 ) ] },
T7 =>  { locked => [ qw( X15      ) ], waiting => [ qw( X5                  ) ] },
T8 =>  { locked => [ qw( X1111    ) ], waiting => [ qw( X1 X115             ) ] },
T9 =>  { locked => [ qw( X115     ) ], waiting => [ qw( X1                  ) ] },
T10 => { locked => [ qw( X199     ) ], waiting => [ qw( X11 X12             ) ] },

そうすれば、目の前の問題についてより効果的に推論できます。特定のトランザクションが待機しているリソースを簡単に確認でき、そこからどのトランザクションがそれらのリソースを保持しているかを確認できます。その推論を再帰的に適用します。サイクルに陥った場合は、デッドロックが発生したことになります。

もちろん、表現はさらに良くなる可能性があります。

use strict;
use warnings;

use Data::Dumper;

my %transactions = (
    T1 =>  { locked => [ qw( X1 X2 X3 ) ], waiting => [ qw( X4 X5 X6 X7         ) ] },
    T2 =>  { locked => [ qw( X4 X5 X6 ) ], waiting => [ qw( X7 X8 X9            ) ] },
    T3 =>  { locked => [ qw( X7 X8    ) ], waiting => [ qw( X1 X10 X111         ) ] },
    T4 =>  { locked => [ qw( X9 X10   ) ], waiting => [ qw( X7 X11 X12          ) ] },
    T5 =>  { locked => [ qw( X11 X12  ) ], waiting => [ qw( X5                  ) ] },
    T6 =>  { locked => [ qw( X13 X14  ) ], waiting => [ qw( X6 X1 X2 X3 X11 X12 ) ] },
    T7 =>  { locked => [ qw( X15      ) ], waiting => [ qw( X5                  ) ] },
    T8 =>  { locked => [ qw( X1111    ) ], waiting => [ qw( X1 X115             ) ] },
    T9 =>  { locked => [ qw( X115     ) ], waiting => [ qw( X1                  ) ] },
    T10 => { locked => [ qw( X199     ) ], waiting => [ qw( X11 X12             ) ] },
);

# get a data-item -> transaction mapping
my %items;
for my $transaction (keys %transactions) {
    for my $item (@{$transactions{$transaction}->{locked}}) {
            $items{$item} = $transaction;
    }
}

my @nodes;
my @edges;
for my $transaction (keys %transactions) {
    push @nodes, $transaction;
    for my $item (@{$transactions{$transaction}->{waiting}}) {
            push @edges, { source => $transaction, dest => $items{$item}, item => $item } if $items{$item};
    }
}

print "digraph tx_dependencies {\n";
print "    $_ label=$_;\n" for @nodes;
print "    @{[ $_->{source} ]} -> @{[ $_->{dest} ]} [label=@{[ $_->{item} ]}];\n" for @edges;
print "}\n";

このプログラムは、graphviz ファイルを吐き出します。これを適切に処理すると、次のdotようになります。