[Stackless] Using Select - The Santa Claus Problem

Andrew Francis andrewfr_ice at yahoo.com
Thu Oct 21 22:08:59 CEST 2010


Hi Guys:

I have started the initial ground work on join-conditions. Join conditions are used for various synchronisation problems ranging from barrier synchronisation, read-writer problems to high level business logic like "contact 10 suppliers and wait for the first four that respond."  I will do the prototyping with stackless.py. 

I encountered the "Santa Claus Problem" in a paper called "Jingle Bells: Solving the Santa Claus Problem with Polyphonic C#."

http://research.microsoft.com/en-us/um/people/nick/santa.pdf

The problem:

"Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves. If awakened by the reindeer, he harnesses each of them to his sleigh, delivers toys with them and finally unharnesses them (allowing them to go off on holiday). If awakened by a group of elves, he shows each of the group into his study, consults with them on toy R&D and finally shows them each out (allowing them to go back to work). Santa should give priority to the reindeer in the case that there is both a group of elves and a group of reindeer waiting."

This problem turns out to be tricky to solve. The book "Beautiful Code" features a Haskell solution.  The Polyphonic C# solution uses join-conditions. Polyphonic C# gets its ideas fro JoCAML. In Polyphonic #C, channels can be synchronous or asynchronous. 

I don't see why a Stackless Python solution could not be elegant as well.... Unlike implementing select where we essentially copied Plan9 - I cannot simply copy Polyphonic C#/JoCAML. 

~

The following is a stab at the problem in Stackless Python with select(). For now, I don't include the section for priority*  However I want to use this example as a springboard for improving select and introducing join-conditions.


def santa(reindeer, elves):
    reindeerChannels = [ch for name, ch, waitTime in reindeer]
    elvesChannels = [ch for name, ch, waitTime in elves]
    reindeerCases = [ch.receiveCase() for ch in reindeerChannels]
    elvesCases = [ch.receiveCase() for ch in elvesChannels]
    reindeerQueue = []
    elvesQueue = []

    cases = reindeerCases + elvesCases

    while True:
        ch, operation, value = stackless.select(cases)
        print value
        if ch in reindeerChannels: 
           reindeerQueue.append(value)
           if len(reindeerQueue) == 9:
              deliveryToys(reindeerQueue)
              reindeerQueue = []
        elif ch in elvesChannels:
           elvesQueue.append(value)
           if len(elvesQueue) == 3:
              consultWithSanta(elvesQueue)
              elvesQueue = []
        else:
           print "WHAT?"

    stopTwisted()
    print "Twisted is dead"
          

if we use callbacks, the solution may be even more tense but harder to follow (I should try this)

Some of the ugliness comes from the need to keep separate data structures for reindeer operations (cases) and reindeer channels. I am thinking of doing the following to solve the aforementioned problem:

theCase = stackless.select(cases)
if theCase in reindeerCases:
   ....

also it makes it removing an unneeded case much easier.

I am hoping a Stackless Python solution with joins would look like

while True:
   case = stackless.select(joinReindeer, joinElves, endSimulationCh)
   if case == reindeerJoin:
      deliveryToys(reindeerJoin)
   elif case == elvesJoin:
      consultWithSanta(elvesJoin)
   elif case == endSimulationCh:
      sys.exit()


I will soon write in more detail in my blog about how join would be done.
Meanwhile any thoughts?

Cheers,
Andrew

* - (running the programme with priority, there was seldom a case where elves and reindeer were ready at the same time - I think this has to do with the non-determinism of select).


      
-------------- next part --------------
A non-text attachment was scrubbed...
Name: simpleSanta.py
Type: text/x-python-script
Size: 3307 bytes
Desc: not available
URL: <http://www.stackless.com/pipermail/stackless/attachments/20101021/571692fb/attachment.bin>


More information about the Stackless mailing list