Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Uenal Mutlu
Date : Tue May 03 2005 04:57 am

"David Schwartz" wrote
> "Uenal Mutlu" wrote
>
> > The theorem works.
> > The example you are referring to was a (theoretical) example
> > where the following happens inside a single thread:
> > o1.Lock();
> > o2.Lock();
> > o3.Lock();
> > o1.Unlock()
> > o2.Unlock();
> > o1.Lock();
> >
> > The reason was just to show that the methods (mine vs. hierarhical
> > locking)
> > are really different at least in such a case.  Ie. in my method the o3
> > lock
> > does not need to be unlocked before being able to lock o1 again, whereas
> > in hierarchical locking it is necessary to unlock all objects deeper in
> > the hierarchy.
>
>     Then your theorem is simply false. Consider the example above. When the
> thread goes to lock 'o1' for the second time, it could deadlock with another
> thread that holds the 'o1' lock and is waiting for the 'o3' lock.

What the above example shows is a special case for singlethreading only.

I've extended the theorem as follows to make it clear:

-------
Theorem (updated):
   a) There will be no deadlock if the objects are locked in the same order.
   b) Unlocking can be done in any order.
   c) If there are multiple threads then the set of objects to lock within
       a thread must not contain the same object more than once.
       (Unlocking all in the set and starting over again (either the same or a
       different set of objects), either in the same block or in a different block, is ok.)

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.
For demonstation purposes Lock() in these examples means recursive
locking to prevent deadlocking himself, and it also means blocking (waits
until it gets the lock), but both is optional.

Example to demonstrate the meaning of rule c:

thread1:
  o3.Lock();    // Lock order is important (see rule a); all threads must use "the same direction"
  o2.Lock();
  o1.Lock();
  o2.Unlock();    // Unlock order is irrelevant (see rule b)
  o3.Unlock();
  o1.Unlock()

thread2:
  o2.Lock();
  o1.Lock();
  o2.Unlock();
  o1.Unlock();
  // another block (scope or func); see rule c
  o2.Lock();
  o1.Lock();
  o2.Unlock();
  o1.Unlock();
  // another block (scope or func); see rule c
  o3.Lock();
  o2.Lock();
  o3.Unlock();
  o2.Unlock();

------

.