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
"""
DeadlockDetection.py
The purpose of this programme is to experiment with
deadlock detection in Stackless Python
February 14th, 2009
<song>Swimming - Martha and the Muffins </song>
"""
import stackless
class Detector(object):
def __init__(self):
self.visits = {}
self.graph = {}
self.holding = {}
return
def __buildGraph__(self):
for channel in self.holding:
a,b,(balance, flag, queue) = channel.__reduce__()
for task in queue:
if channel.balance == 0:
continue
for t in self.holding[channel]:
if t == task:
continue
else:
self.add(task, t)
self.visits[task] = 0
def add(self, vertex1, vertex2):
if vertex1 not in self.graph:
self.graph[vertex1] = []
self.graph[vertex1].append(vertex2)
def dumpGraph(self):
for i in self.graph:
print i, '->', self.graph[i]
def dumpHoldings(self):
for i in self.holding:
print i, self.holding[i]
def registerResources(self,channels):
t = stackless.getcurrent()
for c in channels:
if c not in self.holding.keys():
self.holding[c] = []
self.holding[c].append(t)
def __visit__(self, list, parent):
result = None
for edge in list:
if self.visits[edge] == 1:
result = [edge]
break
elif self.visits[edge] == 0:
self.visits[edge] += 1
result = self.__visit__(self.graph[edge], edge)
if result != None:
result.append(edge)
return result
def printCycle(self, root, cycle):
last = root
while (len(cycle) != 0):
node = cycle.pop()
print last,'->',node
last = node
def detect(self):
for key in self.graph.keys():
if self.visits[key] == 0:
self.visits[key] += 1
result = self.__visit__(self.graph[key], key)
if result != None:
self.printCycle(key, result)
break
def T(name, receiving, sending):
global detector
detector.registerResources([receiving, sending])
print name, "about to receive"
receiving.receive()
print name,"about to receive"
sending.send()
print "done"
if __name__ == "__main__":
global detector
detector = Detector()
c1 = stackless.channel()
c2 = stackless.channel()
c3 = stackless.channel()
channels = [c1, c2, c3]
stackless.tasklet(T)("T1",c1,c3)
stackless.tasklet(T)("T2",c2,c1)
stackless.tasklet(T)("T3",c3,c2)
stackless.run()
detector.__buildGraph__()
detector.detect()
"""
DeadlockTest.py
The purpose of this programme is to experiment with
deadlock detection in Stackless Python
February 18th, 2009
<song>Plug in Baby - Muse </song>
"""
import stackless
from DeadlockDetector import DeadlockDetector
global detector
def T(name, receiving, sending):
detector.registerResources(stackless.getcurrent(), [receiving, sending])
receiving.receive()
sending.send()
print "done"
if __name__ == "__main__":
detector = DeadlockDetector()
c1 = stackless.channel()
c2 = stackless.channel()
c3 = stackless.channel()
channels = [c1, c2, c3]
stackless.tasklet(T)("T1",c1,c3)
stackless.tasklet(T)("T2",c2,c1)
stackless.tasklet(T)("T3",c3,c2)
stackless.run()
detector.detect()
detector.__dumpGraph__()
detector.__dumpHoldings__()
_______________________________________________
Stackless mailing list
[email protected]
http://www.stackless.com/mailman/listinfo/stackless
