Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : doug
Date : Tue May 03 2005 09:25 am

'fraid not, it was something I was taught at Uni.

You've had a long conversation above with David and Joe, and I won't repeat 
any of it, but I'm afraid I agree with them.  Your solution may work, but 
it's too complicated for general use.  As David points out, you have to know 
the entire history of a thread and the locks it has obtained and released. 
This is simply impossible in real life (one of the projects I work on has a 
few hundred threads, three milion lines of code, and several thousand 
semaphores - we use a runtime 'semaphore hierarchy checker' (in debug 
builds) to ensure acquires follow the hierarchy).

Your addition of rule C doesn't change anything for me.  I see it an 
unnecessary, when it would be covered by rule a) - i.e. always grab in the 
same order.  This implies releasing anything any sema4 higher in the 
hierarchy.  Your rule (c) would have us discard all semaphores.
To my mind, the result will be less efficient (due to more releases and 
acquires) and more complicated (due to having to fit the program locking to 
your artificial constraints) than the well known method.

Don't mean to rain on your parade - it's good you're thinking about how to 
extend/change/enhance existing ideas.  But you should also be totally 
familiar with existing concepts.  Grep for "hierarchical locking" on google 
and have a scan of a few links.

"Uenal Mutlu" <520001085531-0001@t-online.de> wrote in message 
news:d53i2n$mkt$03$1@news.t-online.com...
> "doug" wrote
>> 'fraid this is just standard 'semaphore hierarchy'.
>
> Really? Do you have a link to the definition of "semaphore hierarchy" ?
>
>
>> "Uenal Mutlu" wrote
>>
>> > Theorem:
>> >   a) "There will be no deadlock if the objects are locked in the same
>> > order."
>> >   b) "Unlocking can be done in any order."
>> >
>> > Some explanation:
>> > "Order" in this context means sequence.
>> > The theorem applies equally well to both sequential and parallel
>> > processing
>> > (ie. threads, tasks, processes, coroutines etc.), and regardless of the
>> > number
>> > of objects one wishes to lock in any of the parallel running units (aka
>> > threads).
>> > That is: the objects designated for locking, and the number of them, 
>> > can
>> > be
>> > different in each thread; only the locking sequence (order) must be the
>> > same in all threads.
>> >
>> > (If this theorem is new then I would like to give it the name "Mutlu
>> > theorem" :-)
>
>

.