死锁管理

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适当按摩结束为：