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

"Joe Seigh" wrote
> On Sun, 1 May 2005 23:35:10 +0200, Uenal Mutlu 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.

On the net I've seen so many differrent definitions of "hierarchical locking",
but none of them covers what I formulated.
Maybe someone can give a link to the correct definition of hierarchical locking.

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

I've studied the mentioned source, but what they define as
deadlock is just the following case (in pseudo code):

if (TestAndSet(fLocked, 1, 0) == SUCCESS)
  return SUCCESS;
if (GetCurrentThreadId() == ThreadIdOfLockOwner)
  if (lockKind == RECURSIVE_LOCK)
    return SUCCESS;
  else
    return EDEADLCK;
....

That is: it returns EDEADLCK only for the case that when the
caller calls Lock more than once for the same object and the
type of the lock is not RECURSIVE_LOCK. Ie.:
  o1.Lock();
  o1.Lock();
where Lock() is non-recursive (in practice non-recursive locks are useless).

This is IMO far away from practical meaning of a deadlock.
Ie. it cannot detect real deadlocks happening while trying
to lock a group of objects. For example locking o1 and o2:
thread1:
  o1.Lock();
  o2.Lock();
thread2:
  o2.Lock();
  o1.Lock();

Here a deadlock will happen for sure. If I'm not wrong then
Pthreads cannot detect this deadlock scenario.

On the other hand, since in my definition Lock() is always
recursive, applying my method would make the code
deadlock-safe in both cases.
In my definition Lock() is also by default blocking (ie. it waits until it gets the lock).
(In real code I've of course also TryLock() ...)

.