Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Joe Seigh
Date : Sun May 01 2005 07:08 pm

On Sun, 1 May 2005 23:35:10 +0200, Uenal Mutlu <520001085531-0001@t-online.de> wrote:

> "Joe Seigh" wrote
>>
>> It's known as hierarchical locking.
>
> Do you have the definition for hierarchical locking, or a link, handy?
> What I've found is the following definition for hierarchical locking:
>   1) Locks are requested from the root to descendents in a hierarchy.
>   2) Locks are released starting at the node locked and moving up the three.

It's been around a long as I can remember.  There's no requirement it has
to be a tree, just a fixed order.  Releasing a lock doesn't block, so
there's no requirement on any release order, though you can't reacquire
the lock if you hold locks further down in the hierarchy without
releasing those locks first.
>
> In my theorem none of these requirements is strictly required: a lock
> request can begin anywhere (at any level of the "hierarchy"), and also
> releasing the lock can happen any time, both independent of the "hierarchy"
> (actually there is no fix relation, or a hierarchy, between the objects;
> objects are usually indepenendent of each other; the point is to lock
> each individually to form a set.
> The only real requirement is to keep the same sequence for the lock
> requests inside all threads.
> Moreover, my theorem implicitly gives a method for quick deadlock
> detection, even as early as in the design phase (ie. on paper).
> It is intended especially for thread-safety requirements.

Lot's of people think you can do that.  You can if knowlege of what
order the locks are acquired is statically known.  That's not always
possible if there's dynamic logic involved.  You have some implementations
out there that check for deadlock at runtime to get around this problem.
See the EDEADLCK return code for pthread_mutex_lock() in the current
Single UNIX specification.



-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.