[Stackless] Requesting Comments for a Deadlock Detection Module

[Andrew Francis]

Hi Folks:

Last week, I wrote my first rough cut of a deadlock detection module. I haven't had a chance to thoroughly test it. Still, I would like comments. Many of the ideas come from previous posts on deadlock:

http://www.stackless.com/pipermail/stackless/2005-December/000290.html

and the "Adventures in Stackless Python Twisted Integration" Pycon 2008 talk. 

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.

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 make the assumption that cooperative scheduling automatically gives one no-premption  and mutual exclusion off the bat. So we have to look for hold and wait and circular wait. For hold-and-wait, I believe hold-and-wait looks as follows:

tasklet A:
     a.receive()
     b.send()

tasklet B
     b.send()
     a.receive()


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

I treat send/receive's as transactions. A channel with a balance of zero is assumed to be either a completed transaction or a transaction that never started. Consequently it is ignored. 

The register() creates the holding table (as in Hold-and-wait). This insight comes from Asgeir Ingvarsson's insight in the December 2005 thread.

When detect() is invoked, the detector goes though the holding table. If the balance is non-zero (this is the wait), tasklets associated with that channel are added to the graph.

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.

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!

Cheers,
Andrew




 












      
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DeadlockDetection2.py
Type: text/x-python
Size: 2902 bytes
Desc: not available
URL: <http://www.stackless.com/pipermail/stackless/attachments/20090227/eeafe883/attachment.py>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: deadlockTest.py
Type: text/x-python
Size: 812 bytes
Desc: not available
URL: <http://www.stackless.com/pipermail/stackless/attachments/20090227/eeafe883/attachment-0001.py>