Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Uenal Mutlu
Date : Sun May 01 2005 08:52 pm

"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" :-)

Here's an example (proof):

LockableSharedObject o1, o2, o3;

  // inside thread1:
      //...
      {
      o1.Lock();
      o2.Lock();
      // process
      // unlock (in any order)
      }
      //...

  // inside thread2:
      //...
      {
      o1.Lock();
      o3.Lock();
      // process
      // unlock (in any order)
      }
      //...

  // inside thread3:
      //...
      {
      o2.Lock();
      o3.Lock();
      // process
      // unlock (in any order)
      }
      //...

  // inside thread4:
      //...
      {
      o1.Lock();
      // process
      // unlock
      }
      //...

  // inside thread5:
      //...
      { // THIS DOES NOT FOLLOW THE THEOREM, THEREFORE DEADLOCK WILL HAPPEN
      o2.Lock();
      o1.Lock();
      // process
      // unlock
      }
      //...

.