Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Uenal Mutlu
Date : Tue May 03 2005 07:14 pm

"David Schwartz" wrote
> "Uenal Mutlu" wrote
>
> >>     Consider code like this, where the 'FooFinder' lock protects creation
> >> and destruction of 'Foo' objects so that we don't have two by the same
> >> name
> >> and can safely find them by name.
> >>
> >> FooFinder::Lock();
> >> Foo *j=FooFinder->FindFooByName("foo");
> >> if(j!=NULL)
> >> {
> >>  j->X(); // internally locks this particular foo
> >>  j->Y(); // internally locks this particular foo
> >> }
> >> FooFinder::Unlock();
> >>
> >>     If the 'X' and 'Y' functions internally lock 'foo', you have a
> >> problem
> >> since you had to release the FooFinder lock before you could lock the
> >> lock
> >> built into the 'j' object again.
>
> > Hmm. I don't see any problem, though it is not the kind how I
> > use object locking b/c in my code j->X() would lock the objects
> > it needs to access, do its job, and then release them, so would
> > j->Y() and any other function.
>
>     Well that's the problem. You see, j->Y() would lock the same lock j->X()
> just released. Your hierarchy specifically prohibits that.

Sorry, this is not true. More below.

> > If you don't use a recursive Lock() and/or do Lock() in one function
> > and Unlock() in a different function then things will become
> > very complex. I would recommend a method like my above Locker
> > helper class and a recursive Lock(). There is virtually no overhead
> > in recursive locking. It just checks whether the lock request is from
> > the same thread like the current lock owner and increments a counter
> > and returns true to indicate success. Ie.
> > o1.Lock()
> > o1.Lock()
> > called from the same thread is harmless regardless where each
> > of them is called. See also example above.
>
>     But your hierarchy doesn't allow that. Consider:
>
> SomeFunction()
> {
>  o1.Lock();
>  o2.SomeFunctionWhichLocksAndThenUnlocks();
>  o2.SomeFunctionWhichLocksAndThenUnlocks();
>  o1.Unlock();
> }
>
>     Your hierarchy does not allow you to relock o2 while you still hold the
> o1 lock. So this is not legal.

No, Sir. This scenario I'm using so often that it is "natural" for me.
That is: the theorem covers this and it is heavily used in how I use
locking in applications.
I wonder why you think this should not be possible? I'd suggest
to take a look again at the f1() and f2() functions of my prev posting.
It is exactly the same scenario like yours above, and it works.

>     And recursive locks are just plain wrong. You cannot write sane code
> unless you know what locks you hold (at the same or lower levels in a
> hierarchy), and recursive locking is only helpful if you don't know what
> locks you hold (at the same or lower levels in a hierarchy). The worst part
> about recursive locking is it sets you up for problems because you don't
> know what 'unlock' is actually going to do.

Hmm. maybe we have different meanings of recursive locking.
In my definition it is a locking mechanism where the same owner (thread)
can lock an object multiple times in series without the need of first
unlocking it.
o1.Lock();
o1.Lock();
o1.Lock();
Obviously there must be 3 Unlock() calls to release the objects.
As said in my prev. posting this kind of recursive locking is valid
for the _current lock owner_ (thread) only, and there is virtually no
overhead (just an incrementing of a counter; if it becomes 0 (due to Unlock() calls)
then the object is released). And: for recursive locking there is no
need to know what other objects are locked or not; recursive locking
is applied on the same one object for the same one thread only.

> > The theorem is mainly intended for deadlock-free locking of
> > groups of usually independent/hierarchyless objects inside
> > multiple threads for the purpose of accessing them as a set.
> > And I would say this kind of resource aquisition leads to better
> > performace than to lock the same group in just one lock (maybe
> > this sounds weird but it's not).
>
>     Perhaps, but since the theorem imposes needless requirements, it just
> restricts what you can do for no benefit.

Hmm. I personally don't feel it has needless requirements or restrictions,
It is designed for and applied in real-world apps, ie. not only in theory.
For me it is simple, intuitive, and very fast.

I'm currently extending it for detecting violations of the theorem (ie. an
automatic deadlock detector conditionally compiled only in debug build.
IMO it even could be used in release build since the overhead seems not that much).

.