12b6
Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Uenal Mutlu
Date : Tue May 03 2005 07:54 am

"David Schwartz" wrote
> "Uenal Mutlu" wrote
>
> > Theorem (updated):
> >   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.)
>
>     While now probably true, this would result in a very crippled locking
> hierarchy. Any thread that wanted to acquire a lock would need to know the
> full history of the thread's locking since the first lock it acquired.

Regardless whether the objects are known in advance (ie. while
writing the program) or only at run-time, you need to follow
the same sequence. It's IMO simple and also intuitive to follow
(apply) the rules of the theorem.

> Even calling two functions from the same class would be problemmatic if each
> function locked the object.

IMO it's not the case. Normally a lock should be kept as
short as possible. I'm using a helper class (stack object) to
perform the locking and it unlocks the object automatically
in its dtor when the scope goes out of view. By using this
method "forgetting" to unlock an object cannot happen.
Since Lock() is "recursive for the lock owner (= thread)", it does
not deadlock if the same thread tries to lock an object multiple
times (ie. by calling other functions). For example:

void X::f2()
{ // Locker is a helper class.  In its ctor it locks the passed object reference
  // and in its dtor unlocks it. Locker is blocking.
  Locker L1(o1.LV);    // LV is lock internal data (for example a CritialSection object)
  Locker L2(o2.LV);
  //...
}

void X::f1()
{
  Locker L1(o1.LV);
  Locker L2(o2.LV);
  //...
  f2();
  //...
}

Here, although o1 and o2 are locked, f2() will not deadlock because
it is the same thread. Alternatively one can use following method
(also in case Lock() should be missing the "recursive" feature):

void X::f1()
{
  {
  Locker L1(o1.LV);
  Locker L2(o2.LV);
  //...
  }
  f2();
  //...
}

>     Many of the most common patterns can't be used under this rule. For
> example, you can't have one lock that controls the existence of objects of a
> class and an individual lock for each object to protect that particular
> object. Without this, reference counting is nearly impossible.

For something like reference counting I wouldn't use this. I would
use it to get access to shared objects (for example vector, map etc).
My locks are usually for a short time only, ie. not lasting.
Otherwise I would recommend to use a flag (but modifying such
a shared objects must of course be done in a "locked state").

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

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.

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).

.

0