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).
#!/usr/bin/env python
"""
simpleSanta.py
Andrew Francis
October 21th, 2010
The purpose of simpleSanta is as follows:
1) Show a solution to the Santa Claus problem using the select
2) Point out improvements to the select statement
3) Give hints as to why a solution with Join conditions may be easier
for now, we leave out priority to reindeer
"""
import random
import time
import sys
from twisted.internet import reactor
from twisted.internet import defer
from twisted.internet import task
from twisted.python.failure import Failure
import stackless
# we can use ETIME and RTIME to control how long reindeers and elves wait
# before asking questions
RTIME = (10,12)
ETIME = (1,12)
def tick(seconds):
tickCh = stackless.channel()
reactor.callLater(seconds, tickCh.send, None)
tickCh.receive()
def startTwisted():
reactor.run()
def stopTwisted():
reactor.callLater(1, reactor.stop)
print "that's all folks"
def worker(ch, name, theRange):
myChannel = stackless.channel()
while True:
waitTime = random.randint(theRange[0], theRange[1])
tick(waitTime)
ch.send((name, myChannel))
answer = myChannel.receive()
"""
a way of telling the tasklets that Santa is done
"""
def acceptChannels(channels, status):
for name, channel in channels:
channel.send(status)
def deliveryToys(reindeer):
print "All the reindeer have arrived - delivering toys"
acceptChannels(reindeer, True)
def consultWithSanta(elves):
print "Santa consulting with elves"
acceptChannels(elves, True)
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"
def makeWorkers(workers):
for name, ch, waitTime in workers:
stackless.tasklet(worker)(ch, name, waitTime)
return
if __name__ == "__main__":
random.seed()
reindeers = [(reindeer, stackless.channel(), RTIME) for reindeer in \
["DANCER", "PRANCER", "VIXEN", "COMET", "CUPID", "DONER", \
"DASHER", "BLITZEN", "RUDOLPH"]]
elves = [(elf, stackless.channel(), ETIME) for elf in \
['A','B','C','D','E','F','G','H','I','J']]
makeWorkers(reindeers)
makeWorkers(elves)
l = task.LoopingCall(stackless.schedule)
l.start(.001)
stackless.tasklet(startTwisted)()
stackless.tasklet(santa)(reindeers, elves)
stackless.run()
_______________________________________________
Stackless mailing list
[email protected]
http://www.stackless.com/mailman/listinfo/stackless
