Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Uenal Mutlu
Date : Mon May 02 2005 12:35 am

"Joe Seigh" wrote
> On Sun, 1 May 2005 19:18:11 +0200, 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" :-)
> >
>
> 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.

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.

Maybe someone can point to the right link to check whether hierarchical
locking and what my theorem says are both the same.

.