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

"David Schwartz" wrote
> "Uenal Mutlu" wrote
>
>     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.

I tried to explain that this is not true. What you need to know is just
the list of all objects (say listed in a top-down manner), then in any
thread pick any you need, but in the same order as in the list.
Of course the list of the objects cannot be reordered later,
but new objects can be appended.

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

That's the big difference: my motivation was to have a method where
such object dependencies (object hierarchy) aren't required.

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

I try to solve just the case "the same level of the hierarchy", because in my
case the objects are independent (no relationship/hierarchy among them),
ie. a "flat hierarchy".

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

I understand. It's just another method. Maybe a combination of both methods
would result in the ultimate method, though each on its own is complicated enough.
And maybe mine is just a subset of yours (ie. the "same level of the hierarchy" case
of yours above).

.