Deadlock management

Question

I am doing a research but any relevant information is hard to find. I stumbled upon this problem:

Produce a wait-for-graph for the following transaction scenario and determine whether deadlock exists.

Transaction:

T1
T2
T3
T4
T5
T6
T7
T8
T9
T10 

Data items locked by transaction:

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

Data items transaction is waiting for:

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

Now, as far as I've seen on transaction management, this striked me as quite hard. Can someone provide reference to explanation how to solve this type of problem, or help anyhow?

Answer 1

As is quite common, the key to resolving some problems is choosing a good representation. If you represent your problem in tabular form:

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             ) ] },

then you can reason more effectively about the problem at hand. It's easy to see what resources a certain transaction is waiting for, and from there you can see which transactions holds those resources. Apply that reasoning recursively. If you end up in a cycle, you've just found a deadlock.

'Course, the representation can even be better:

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";

This program spews a graphviz file, which when massaged appropriately with dot ends up as: