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

"Peter Koch Larsen" wrote
> "Uenal Mutlu" skrev
> > "Peter Koch Larsen" wrote
> >> "Uenal Mutlu" skrev
> >> > "Joe Seigh" wrote
> >> >>
> >> >> 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.
> >> >
> >> > Do you mean that the following case is not possible with hierarchical
> >> > locking?
> >> > o1.Lock();
> >> > o2.Lock();
> >> > o3.Lock();
> >> > o1.Unlock()
> >> > o2.Unlock();
> >> > o1.Lock();
> >> >
> >> > With my method this is possible. And this also shows that the
> >> > methods indeed aren't the same.
> >> >
> >> >
> >> What do you mean? Let us test your solution:
> >> Thread 1:
> >> o1.Lock();
> >> o2.Lock();
> >> o3.Lock();
> >> o1.Unlock()
> >> o2.Unlock();
> >> >>  context switch
> >>
> >> Thread 2:
> >> o1.Lock();
> >> o2.Lock();
> >> o3.Lock(); => waits for unlock by thread 1
> >>
> >> Thread 1 resumes:
> >> o1.Lock(); => waits for unlock by thread 2
> >>
> >> A nice and simple deadlock.
> >
> > Of course you are right. I'm aware of the deadlock when there
> > is more than 1 thread. The purpose of the code was just to
> > show one of the differences between the definition of hierarchical
> > locking and my method.
> >
> >
> Quoting from your original post:
>
> 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" :-)
> [end quote]
>
> I must admit you've lost me. I do not understand

Please take a look at the example I'd posted (reposting it below).
Especially what happens inside thread5 (But: it is by no means
said that the deadlock actually will happen inside thread5! It only
says that deadlock will happen for sure if not followed the theorem,
or inversing this: no deadlock will happen for sure if the theorem is applied.

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

---

.