Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Uenal Mutlu
Date : Tue May 03 2005 08:06 pm

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

> 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.

> 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).

> 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.

.