On Tue, 20 Jan 2004 10:45, Dan Sugalski wrote;
> Yes. The recommendation I've always seen for deadlock avoidance is
> to always have all your code grab its mutexes in some fixed order.
Yes; otherwise, you need to back off and start again, if one lock
acquisition fails.
Consider these functions; for the purpose of this example, lexical
lock ordering is implied;
func1($AAAA, $CCCC, $FFFF, $GGGG, $KKKK);
func2($BBBB, $DDDD, $FFFF, $IIII, $KKKK);
func3($FFFF, $KKKK);
So long as the locks are ramped up from the lowest to the highest,
there is no chance of func1 acquiring a lock to be held by func2 (eg,
$KKKK), if that other function already has one of the shared
dependancies (eg, $FFFF).
All well and good. But, what about recursive locks?
ie
sub func1($one is locked, $two is locked, $three is locked) {
for my $x ($one, $two, $three) {
func2($x.property) if $x.property;
}
}
sub func2($eins is locked) {
if ($eins.property) {
func2($eins.property, { });
}
}
$aaa.property = { };
$bbb.property.property = $aaa;
$ccc = { };
if (thork()) { # fork a thread
# thread A
func1($aaa, $bbb, $ccc);
} else {
# thread B
func2($bbb.property);
}
OK, the execution order that causes the deadlock is:
1. Thread B - func2() acquires a lock on the $bbb.property PMC.
2. Thread A - func() acquires a lock on $aaa, $bbb, $ccc.
3. Thread A - func2() acquires a lock on $aaa.property, which
returns quickly
4. Thread A - func2() blocks waiting for a lock on $bbb.property,
held by func2() in thread B
5. Thread B - func2() blocks waiting for a lock on
$bbb.property.property, held by func() in thread A.
So, there are still possibilities for deadlocks, as the non-linear
nature of subroutine calls screws up your nice lock ramping.
In summary, acquiring mutexes in a defined order as a means to avoid
deadlocks only works when you are acquiring them all up front. If you
are acquiring any later, and you detect a deadlock (ie, a loop of
threads blocking on locks held by each other), you *must* be able to
tell one of them to "ramp off" to holding no locks at all. ie,
ROLLBACK :).
The bugger is, winding back execution state automatically to when you
last started acquiring locks is probably an intractable problem from
an interpreter's perspective...
Sounds like a job for an exception to me ;-).
for (1..50) {
eval {
func_that_acquires_first_lock($args);
};
last unless $@ and $@ =~ m/mutex deadlock/i;
}
--
Sam Vilain, [EMAIL PROTECTED]
When I sell liquor, its called bootlegging; when my patrons serve it
on Lake Shore Drive, its called hospitality.
AL CAPONE
