[Stackless] Scheduling Examples, Problems, Solutions, and Questions

[Andrew Francis]

Hello Colleagues:

Perhaps these should go in a Wiki .....

I have been using channels to implement an order
dependency graph. I have run into problems and I have
found solutions. However I would like to know more
about what is happening.

The following code tries to impose a logical order on
some tasklets.

I expect the following execution trace 

(A | B) C (D | E) F

| - means processes can execute in parallel. 

It is okay to see B finish before A. However it is
wrong to see C finish before B and A finish.

Note, there are no cycles....

In this model, dependencies are implemened through
channels.
Say activity A and activity B share a channel "AtoB."
If channel "AtoB" is a target channel of B, this means
B cannot continue until it receives output. If channel
"AtoB" is a source of A, then A should send input
before finishing.

Here is a programme:

import stackless

class TestActivity(object):

    # sources - hashTable of input  channels
    # targets - hashTable of output channels
    def __init__(self, name, sources, targets):
        self.sources = sources
        self.targets = targets
        self.name = name
            
    def execute(self):
        print self.name, " about to Join"
        for target in self.targets:
            print self.name, "joining ", target
            self.targets[target].receive()
            print self.name, "--joined-- ", target
            
        print self.name, "finished joining"
        
        print self.name, "*** finished Executing ***"
        
        print self.name, "about to update dependents"
        for source in self.sources:
            print self.name, "updating ", source
            self.sources[source].send(True)
        print self.name, "finishing"


class StacklessTests(object):
            
    def TestOne(self):
        
        channelAtoC = stackless.channel()
        channelBtoC = stackless.channel()
        channelCtoD = stackless.channel()
        channelCtoE = stackless.channel()
        channelDtoF = stackless.channel()
        channelEtoF = stackless.channel()
        
        a = TestActivity("A", {"AtoC":channelAtoC},{})
        
        b = TestActivity("B", {"BtoC":channelBtoC},{})
        
        c = TestActivity("C", {"CtoD":channelCtoD,
"CtoE":channelCtoE}, \
                         {"AtoC":channelAtoC,
"BtoC":channelBtoC})
        
        d = TestActivity("D", {"DtoF":channelDtoF},
{"CtoD":channelCtoD})
            
        e = TestActivity("E", {"EtoF":channelEtoF},
{"CtoE":channelCtoE})
        
        f = TestActivity("F", {},
{"EtoF":channelEtoF,"DtoF":channelDtoF})
        
        
        stackless.tasklet(f.execute)()
        stackless.tasklet(e.execute)()
        stackless.tasklet(d.execute)()
        stackless.tasklet(b.execute)()
        stackless.tasklet(c.execute)()
        stackless.tasklet(a.execute)()

        print "--WAITING--"
        stackless.run()
        print "--FINISHED WAITING--"    
    
    
test = StacklessTests()
test.TestOne()

This is the result as I expected. Note I print
"finished" after they finished receiving input and
before activities updating their dependents. This is
okay.

--WAITING--
F  about to Join
F joining  EtoF
E  about to Join
E joining  CtoE
D  about to Join
D joining  CtoD
B  about to Join
B finished joining
B *** finished Executing ***
B about to update dependents
B updating  BtoC
C  about to Join
C joining  AtoC
A  about to Join
A finished joining
A *** finished Executing ***
A about to update dependents
A updating  AtoC
C --joined--  AtoC
C joining  BtoC
C --joined--  BtoC
C finished joining
C *** finished Executing ***
C about to update dependents
C updating  CtoD
D --joined--  CtoD
D finished joining
D *** finished Executing ***
D about to update dependents
D updating  DtoF
A finishing
B finishing
C updating  CtoE
E --joined--  CtoE
E finished joining
E *** finished Executing ***
E about to update dependents
E updating  EtoF
F --joined--  EtoF
F joining  DtoF
F --joined--  DtoF
F finished joining
F *** finished Executing ***
F about to update dependents
F finishing
C finishing
E finishing
D finishing
--FINISHED WAITING--

Now, in the second test, I complicate things by adding
an 
additional channel between B and E

b = TestActivity("B",
{"BtoC":channelBtoC,"BtoE":channelBtoE},\
                {})
        
e = TestActivity("E",
{"EtoF":channelEtoF},{"CtoE":channelCtoE,\
             "BtoE":channelBtoE})

The trace should remain the same. However I get the
following:

--WAITING--
F  about to Join
F joining  EtoF
E  about to Join
E joining  CtoE
D  about to Join
D joining  CtoD
B  about to Join
B finished joining
B *** finished Executing ***
B about to update dependents
B updating  BtoE
C  about to Join
C joining  AtoC
A  about to Join
A finished joining
A *** finished Executing ***
A about to update dependents
A updating  AtoC
C --joined--  AtoC
C joining  BtoC
A finishing
--FINISHED WAITING--

~

This is wrong. I don't understand why the programme
ends while 
tasklets still should be running.

I think what is happening is when Activity B updates
BtoC,
B is scheduled to the end. When C reads "AtoC", it is
rescheduled to the end of the list. However E should
be in a position to re-activate B and C. 

I would like to know what exactly is happening.

~

Now what is interesting is when I change the stackless
channel to Asgeir Ingvarsson's uthread Queue, the
problem disappears. I get the proper trace. Asgeir's
uthread module is a great source of stackless
knowledge.

--WAITING--
F  about to Join
F joining  EtoF
E  about to Join
E joining  CtoE
D  about to Join
D joining  CtoD
B  about to Join
B finished joining
B *** finished Executing ***
B about to update dependents
B updating  BtoE
B updating  BtoC
B finishing
C  about to Join
C joining  AtoC
A  about to Join
A finished joining
A *** finished Executing ***
A about to update dependents
A updating  AtoC
C --joined--  AtoC
C joining  BtoC
C --joined--  BtoC
C finished joining
C *** finished Executing ***
C about to update dependents
C updating  CtoD
D --joined--  CtoD
D finished joining
D *** finished Executing ***
D about to update dependents
D updating  DtoF
D finishing
A finishing
C updating  CtoE
E --joined--  CtoE
E joining  BtoE
E --joined--  BtoE
E finished joining
E *** finished Executing ***
E about to update dependents
E updating  EtoF
F --joined--  EtoF
F joining  DtoF
F --joined--  DtoF
F finished joining
F *** finished Executing ***
F about to update dependents
F finishing
C finishing
E finishing
--FINISHED WAITING--

I am not quite sure why Asgeir's code solves problem.
More
specifically why the pump() method acts allows to the
Queue
to seemingly not block.

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