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

[Andrew Francis]

Hello Joachim, Christian and Colleagues:

--- 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, I like the
minimal implementation approach. Joachim, 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. 

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. getruncount() gives you only running tasklets, not
the tasklets blocked on channels.

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