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