[Stackless] Second Posting - Deadlock Detection Tips Re: Scheduling Examples, Problems, Solutions, and Questions

[Andrew Francis]

Hello Colleagues:

I think this post bounced, so I am reposting. I have
added a few new comments.

--- Christian Tismer <tismer at stackless.com> wrote:
 
> Channels were inspired by the idea of a minimal
> implementation and let people decide what they
> really need. Compatibility to existing stuff
> was never an issue for stackless. Extra things
> should be built on top of it.

As I understand more about channels, Joachim, I like
the minimal implementation approach.  I have to
admit I use channels in a very conservative way. What
I have found is initially the most fustrating is
understanding deadlock in stackless.

Quote from Kristjin:

>If the channels had a buffer, they would be useless
as >a scheduling mechanism.  Implicit in the channel
>semantics is the fact that once your 
>channel.send() has completed, the receiver has
already >read your message.  If there were buffering,
you would >have no such guarantee.

I rely on the blocking nature of channels to implement
synchronizers. Channels can serve many purposes.

I know this is not a resource allocation graph or
banker's algorithm (and I use channels very
conservatively), but I take this simple approach to
see if there is potentially deadlock situations in my
design.

I represent the programme by drawing a directed graph.
Tasklets are vertices. Channels are edges. I put
arrows on both ends of an edge (so I guess I am
dealing with a strongly connected graph). If there is
a cycle, then there is a good chance  you will have a
deadlock situation.

Some gotchas:

1. The execution order of tasklets may occasionally
mask deadlock.

2. A typical stackless construct is 

while stackless.getruncount > 1:
   stackless.schedule()

getruncount() gives you only running tasklets, not
the tasklets blocked (on channels). It is good to
check the number of tasks you have executed after
coming out the loop. 

3. I found that Asgeir's queue helps in situations
where two tasklets communicate via a single channel
(resource allocation is simplified when there is a
single resource). uthread.Queues paves over
hold-and-wait problems with two tasklets sharing a
single resource. Perhaps this is a wrong analysis, but
I think hold-and-wait AND circular wait in stackless
appears as the following:

Tasklet[0](channel1,channel2):
    # tasklet 0 waiting for data
    data = channel1.receive()
    newData = process(data)
    # in reality, tasklet 0 is holding this resource
    # even though it has not actually issued a command
    channel2.send(newData)

Tasklet[1](channel1,channel2):
    # tasklet 0 waiting for data
    data = channel2.receive()
    newData = process(data)
    # in reality, tasklet 1 is holding this resource
    # even though it has not actually issued a command
    channel1.send(newData)


If you are dealing with a complicated graph, this is
sometimes not evident.

I reverse the holding and waiting resources, since the
issuing of the send() and receive() does not exclude
the channel from other tasks, and the command's
execution is of short duration.

> I have lots of examples of buffered channels, they
> can be implemented in different flavors, and you
> should not need more than few lines for this.

It would be nice to see these.

Cheers,
Andrew


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 

_______________________________________________
Stackless mailing list
Stackless at stackless.com
http://www.stackless.com/mailman/listinfo/stackless