[Stackless] Requesting Comments for a Deadlock Detection Module

[Christian Tismer]

Hi Andrew,

here comes a little input from me about deadlock detection.

On 2/27/09 8:28 PM, Andrew Francis wrote:

> I envision the deadlock detector used as follows: a developer believes
> they have deadlock. They include the detection module and use the
> register() method to tell the detector which channels a tasklet uses.
> The programme is executed.

Yes.
This is what I would do pretty differently.
Not using a register method to be called by hand.
Instead, I would overwrite the definition of channels
and modify the channel methods to do the deadlock detection.

> When stackless.run() prematurely returns, the detector goes through the
> graph, looking for cycles, returning a list of tuples, describing the
> tasklets and channels in question.

I believe this would be more helpful if done during a channel
action, because you then know exactly, which action caused
the deadlock, in the end.

...

> To help detect hold-and-wait and circular wait, I create a wait-for
> graph. Wait-for graphs are described in section 16.6 of Silberschatz's
> "Database System Concepts."

Got no time to look this up, but I believe you know what you are saying.

...

> Once the graph is completed, I use a variation of the graph traversal
> algorithm in Sedgewick. If a cycle is found, the detector stops and the
> path is returned. I imagine something like pygraph(?) could be used to
> visual the deadlocked tasklets and channels.

Would it be possible to do that traversal incrementally, updating
on every channel action?

> Anyhow I have included the code and a simple example. I suspect the
> detector is naive to catch every case (i know it won't case the of a
> single tasklet waiting on a single channel). Still I think the detection
> module would be useful to a new Stackless programmer. Maybe I could use
> stuff like class decorators to make the module easier to use. Anyhow
> comments could be appreciated. Enjoy!

Well, isn't that simple approach sufficient: tracking all actions
until the deadlock occours, and that's about it?
Maybe I was too quick with something :-)

Just my 2 cent - chris
-- 
Christian Tismer             :^)   <mailto:tismer at stackless.com>
tismerysoft GmbH             :     Have a break! Take a ride on Python's
Johannes-Niemeyer-Weg 9A     :    *Starship* http://starship.python.net/
14109 Berlin                 :     PGP key -> http://wwwkeys.pgp.net/
work +49 30 802 86 56  mobile +49 173 24 18 776  fax +49 30 80 90 57 05
PGP 0x57F3BF04       9064 F4E1 D754 C2FF 1619  305B C09C 5A3B 57F3 BF04
       whom do you want to sponsor today?   http://www.stackless.com/