Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : David Schwartz
Date : Tue May 03 2005 04:35 pm


"Uenal Mutlu" <520001085531-0001@t-online.de> wrote in message 
news:d58t0h$srf$00$1@news.t-online.com...

>>     I agree that it's valid, just useless and dangerous. Please read my
>> criticism again.

> Hmm. IMO it is by no means useless or dangerous. It is a very important
> feature, because it simplifies object locking very good; you don't need to
> check or unlock whether the object is already locked. In case it is
> "me" (the current thread) who already has it locked then a second
> lock request again by me simply increments the lock counter of the object
> and the lock is (again) granted. Of course one also can do these checkings
> also in the application code, but IMO it doesn't belong therein.

    It doesn't simplify anything. In order to write reliable code, you need 
to know what locks you hold at the current level or at any lower levels. If 
you know what locks you hold, you don't need a recursive lock. Just don't 
acquire the lock again if you know you already hold it.

    As for it being dangerous, consider the following code:

o1.Lock();
while (o1.NotReady())
{
 o1.Unlock();
 Sleep();
 o1.Lock();
}
o1.DoStuff();
o1.Unlock();

    This relies on the object being unlocked after the call to Unlock. With 
recursive locks, this cannot be guaranteed. So recursive locks don't make 
anything easier, you still need to know what locks you hold, and they create 
new risks, the meaning of 'unlock' isn't always clear.

    What is the benefit supposed to be exactly?

>>     How do you guarantee that you don't hold any locks when you need to
>> re-acquire a lock you recently released?

> It is not necessary to check whether other objects are locked.
> The lock request is for the underlying object only.
> Normal behaviour of Lock() is to block until the object can be
> locked (ie. until the other thread releases the lock). There is
> of course also a TryLock() function which tries to lock, and returns
> immediately; the return code says whether it succeeded or not.
> The job of Lock() is not indended to also to check for possible deadlock
> since this (deadlock prevention) happens implicitly when the theorem is 
> applied.

    The problem is that to ensure that your theorem is followed, you need to 
know a lot more information about what locks the thread may hold. This makes 
things very difficult in comparison to other locking hierarchy rules where 
you only need to know about locks held at the current level or lower. Your 
code requires knowledge of locks held above the current hierarchy level, and 
that makes things very, very hard to code.

    For example, suppose I'm writing a hash class. It uses a lower level 
'hash entry' class. It's reasonable to expect the coding of the hash class 
to understand how locks work in the 'hash entry' class. And if I write some 
other class that uses the hash class, it's reasonable to expect it to know 
how locks work in the hash class. However, what is unreasonable, is to 
expect the hash class to understand how lock work in the classes that use 
it.

    For example, suppose a function in the hash class requires two 
lock/unlock cycles on the same hash entry. This is legal under your 
hierarchy if and only if the thread holds no locks.

    Complying with your last rule requires this knowledge. Other ways to 
avoid deadlock don't have this rule. So this makes your rules, while now 
probably correct, not very useful.

    A better way to avoid such deadlocks is a locking hierarchy like the 
following:

    A) Every lock has a place in a strict hierarchy.

    B) No lock lower in the hierarchy may be taken while a lock higher in 
the hierarchy is already held.

    C) Locks may be released in any order.

    D) Separate rules may be used for locks at the same level in the 
hierarchy, and deadlock will not occur among those locks and locks at other 
levels so long as rule B is followed. Deadlock may occur among locks at the 
same level of the hierarchy unless they employ their own deadlock prevention 
scheme (such as this one). In this case, the locks are treated as one lock 
for purpose of other locks in this hierarchy and that lock is considered 
taken when any lock at its level is taken and released when all locks at the 
same level are released.

    This simply allows you to put the "hash entry" lower than the "hash" and 
anything that calls the "hash" higher up. This means that classes need 
knowledge about the classes they call (which is unavoidable anyway) but need 
no knowledge about classes that call them.

    This sounds like it prohibits trees but it really doesn't. Each tree 
branch can be considered as one lock, with the alogorithm applying 
recursively.

    DS

.