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

Lots here - search for DGC

"Uenal Mutlu" <520001085531-0001@t-online.de> wrote in message 
news:d58at0$b22$04$1@news.t-online.com...
> "doug" wrote
>> '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).
>
> No, you just need to make a list of all your shared objects and
> do the lockings in each thread always in the same sequence
> (the most intuitive would be "top-down"). Example:
>
> List of objects:
>  o1
>  o2
>  o3
>  o4
>  o5
>
> In any of the threads the objects must be locked in the
> same sequence (here using top-down):
>
> thread1: wants to use o2 and o5
>  o2.Lock();
>  o5.Lock();
>
> thread2: wants to use o1 and o5
>  o1.Lock();
>  o5.Lock();
>
> thread3: wants to use all
>  o1.Lock();
>  o2.Lock();
>  o3.Lock();
>  o4.Lock();
>  o5.Lock();
>
> thread4: wants to use o5 and o2
>  o2.Lock();
>  o5.Lock();
>
> thread5: wants to use just o2
>  o2.Lock();
>
> thread6: wants to use o3, o5, o1
>  o1.Lock();
>  o3.Lock();
>  o5.Lock();
>
>
> Following this schema no deadlock will happen ever.
> I wonder why you see this schema to be too complicated.
> It's IMO so simple to follow and apply.
>


DGC:
Dunno mate.  I think you're just describing a hierarchy.  Look at what 
you've done above.  It is nothing more than hierarchical locking. 
o1->o2->o3->o4->o5.  A very simple one (a completely unbalanced tree), but 
still a hierarchy.

It seems to me that *you're* the one complicating things.

>> 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.
>
> Hmm. not true, neither for "higher" nor "lower" in the hierarchy.
> Ie. there is no such requirement. If one can be locked then it
> will be, this is independent of the "hierarchy".
>
> The objects are locked automatically in the most efficent way
> for the least necessary time (ie. no object is locked unnecessarily
> (and by this blocking other threads) compared to other methods
> of locking a group of objects). That is: a group locking is performed
> by locking items in the group individually. IMO this individual locking
> method is faster than to lock just the group container.
>

DGC:
A sema4 hierarchy (or locking hierarchy) in its simplest form is a tree. 
Semaphores in distinct subtrees have no direct relationship with each other, 
and hence are not subject to the locking hierarchy (w.r.t. each other).

You've missed this in your reading/thinking of the concept/pattern.

>> 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.
>
> This might look so but in practice it isn't if Lock() and Unlock() are
> fast implementations (using atomic counter aka fast InterlockedOps).

DGC:
Is this supposed to be portable?  You're making up excuses/reasons now after 
the fact.  Please stop.

>
>> 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.
>
> Thx, I did so. It is definitely not hierarchical locking.
>
>

.