Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : David Holmes
Date : Tue May 03 2005 05:39 pm

"Uenal Mutlu" <520001085531-0001@t-online.de> wrote in message
news:d532nd$kln$03$1@news.t-online.com...
> Theorem:
>    a) "There will be no deadlock if the objects are locked in the same
order."
>    b) "Unlocking can be done in any order."
....
> (If this theorem is new then I would like to give it the name "Mutlu
theorem" :-)

What's the theorem????

deadlock occurs if you have a cyclic dependency in the lock acquisition
order:
  - thread 1: acquire A try to acquire B
 - thread 2: acquire B try to acquire A

This is the defining property of deadlock.

Every text that discusses deadlock discusses the ways to avoid deadlock.
Acquiring your locks in a consistent order is one such technique. This
solution has been known ever since "locking" (or historically it was
probably described in terms of semaphore operations) has existed.

David Holmes

.