Subj : Re: Deadlock theorem
To   : comp.programming.threads
From : Uenal Mutlu
Date : Thu May 05 2005 12:13 am

"David Schwartz" wrote
> "Uenal Mutlu" wrote
> > "David Schwartz" wrote
>
> >>     Nope, this code is still illegal by your current rules. There are two
> >> possibilities:
> >>
> >>     1) IsEnd acquires and releases a lock. In this case, your rule 'd' is
> >> violated.
> >
> > Hmm. rule d is there to permit exactly this situation. How can it violate
> > it?
>
>     At this point, I don't think there's any difference between your
> algorithm and just having a lock hierarchy (a specified order in which locks
> must be acquired).
>
>     At times you add additional restrictions, but when they're limitations
> are pointed out, you deny that you actually impose them. At times you grant
> additional abilities, but when it's pointed out that they lead to deadlock,
> you change the rules so they go away.

No, it wasn't so. From the very beginning on of this discussion I knew what
I meant, but formulating the rules was the problem. I'm quite sure that the
4 rules of the theorem now cover all aspects, ie. they describe the algoritm fully.
And: I've this already implemented, it works superb.
Also, as mentioned I've also added routines to programmatically detect
a violation of the theorem, ie. for detecting a deadlock before it happens,
all done inside the Lock() function. It works great.

>     So you are saying nothing more than "all threads must acquire locks in
> the same order".

But we've seen that this alone is not enough for practical use; the locking
method must do some more to lead to a practical, easy-to-use, fast method
by additionally using recursive locking for the same thread.
It's all maybe some small steps only, but IMO it's a simple and mighty method.

Nevertheless I would like to thank all who participated in this discussion, it
has helped me to get to the final formulation of the theorem.

.