Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Uenal Mutlu
Date : Wed May 04 2005 07:27 am

Theorem (update-2):
   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.)
   d) It is ok if the owning thread of a lock calls Lock() again for any of its
       locked objects provided that Lock() can handle such recursive locking.

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.
Lock() in these examples means recursive locking to prevent deadlocking
the calling thread when it calls Lock() more than once for the same object,
and it also means blocking (waits until it gets the lock), though both is optional.

Rationale behind rule d:
A well known real-world example for recursive locking is the CriticalSection
method of Win32 (citation: "After a thread has ownership of a critical section,
it can make additional calls to EnterCriticalSection or TryEnterCriticalSection
without blocking its execution. This prevents a thread from deadlocking itself
while waiting for a critical section that it already owns.")

.