Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Joe Seigh
Date : Mon May 02 2005 07:50 am

On Mon, 2 May 2005 05:21:25 +0200, Uenal Mutlu <520001085531-0001@t-online.de> wrote:

> "Joe Seigh" wrote
>> It's been around a long as I can remember.  There's no requirement it has
>> to be a tree, just a fixed order.  Releasing a lock doesn't block, so
>> there's no requirement on any release order, though you can't reacquire
>> the lock if you hold locks further down in the hierarchy without
>> releasing those locks first.
>
> On the net I've seen so many differrent definitions of "hierarchical locking",
> but none of them covers what I formulated.
> Maybe someone can give a link to the correct definition of hierarchical locking.

Seems fairly straightforward.  Why do you think your fixed ordering of locks
is significantly different than the others?

The only real difference in the typical solutions is whether you define the
hierarchy as a tree (partially ordered), partially ordered set, or as a
totally ordered list (all directed graphs with no cycles).  The latter is
easier to work with.  The others may give you some more flexibility but
I'm not sure it's worth it given the extra complexity makes it easier to
screw up.

[...]

>> Single UNIX specification.
>
> I've studied the mentioned source, but what they define as
> deadlock is just the following case (in pseudo code):
>
> if (TestAndSet(fLocked, 1, 0) == SUCCESS)
>   return SUCCESS;
> if (GetCurrentThreadId() == ThreadIdOfLockOwner)
>   if (lockKind == RECURSIVE_LOCK)
>     return SUCCESS;
>   else
>     return EDEADLCK;
> ...
>
> That is: it returns EDEADLCK only for the case that when the
> caller calls Lock more than once for the same object and the
> type of the lock is not RECURSIVE_LOCK. Ie.:
>   o1.Lock();
>   o1.Lock();
> where Lock() is non-recursive (in practice non-recursive locks are useless).
>

That's the current implementation.  The spec doesn't restrict it to that.
There's no api to impose a fixed order to locks in Posix so it probably
doesn't do that, though there are probably lock implementations and non
portable Posix extenstions that do.  Also you could do a debug implmentation
that tries to determine a hierarchy on the fly.

If someone doesn't have enough common sense to avoid deadlock then they probably
don't know how to use any of the stack traces to debug it so there's a
market opportunity for this kind of stuff.  Especially since the static
analysis tools won't catch everything.

But if you want to call hierarchical locking Mutlu locking then fine.
We'll figure out what you're talking about.


-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.