ShopTalk Blog

We've been busily working on the latest iteration of ShopTalk. Our asynchronous networking library Diesel plays a key role in the application. Recently I got the chance to use Diesel outside of its normal problem domain of network applications.

I have been paging through Beautiful Code for a while now and read the chapter on Beautiful Concurrency the other day. In the chapter, Simon Peyton Jones lays out his solution for "The Santa Problem" using Haskell and Software Transactional Memory (STM). He writes that it is a difficult problem to solve with traditional concurrency primitives (threads, locks) that are provided with procedural programming languages.

The problem goes like this:

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.

Diesel is primarily a library for writing non-blocking network applications but you can also use it to write general concurrent applications using Python generators as coroutines. I thought it would be interesting to use it to write a solution to the Santa Problem.

The solution I came up with uses a combination of shared lists (one each for reindeer and elves) and cooperative events to manage state.

import random
from diesel import Application, Loop, fire, wait, sleep

deer_group = []
elf_group = []

The lists contain the waiting reindeer and elves that eventually cause Santa to wake up when they are full (3 elves, 9 reindeer). The events let Santa communicate with the actors contained in each group. Speaking of the Jolly Old Elf, let's take a look at how he ticks:

def santa():
    while True:
        deer_ready, elves_ready = len(deer_group) == 9, len(elf_group) == 3
        if deer_ready:
            yield work_with_group('deer', deer_group, 'deliver toys')
        if elves_ready:
            yield work_with_group('elf', elf_group, 'meet in my study')
        yield sleep(random.random())

The logic for Santa is quite simple. If a group of deer or elves are ready, he works with them, otherwise he sleeps. The order of operations guarantees that if a group of deer and elves are ready at the same time the deer get priority. That is a requirement of the problem.

The reindeer and elves are created via a generic actor function that returns a generator.

def actor(name, type, group, task, max_group, max_sleep):
    def actor_event_loop():
        while True:
            yield sleep(random.random() * max_sleep)
            if len(group) < max_group:
                group.append(name)
                yield wait('%s-group-started' % type)
                print "%s %s" % (name, task)
                yield wait('%s-group-done' % type)
    return actor_event_loop

The elves and deer each "sleep" for a period of time, which actually represents time spent working (elves) or vacationing (deer). They then wake up and attempt to get into a group. They are only successful if the group isn't at capacity (max_group) already. Once in a group, each actor then waits for an event that signifies the group has been ushered in to see the big man. Elves that aren't lucky enough to gain an audience have to wait - they will continue in their loop and try again later.

Once they are signaled with the *-group-started event they do their task, which amounts to printing it to the screen in this case. They then wait until dismissed by Santa when he fires *-group-done.

While working with a group, Santa does the following:

def work_with_group(name, group, message):
    print "Ho! Ho! Ho! Let's", message
    yield fire('%s-group-started' % name)
    yield sleep(random.random() * 3)
    yield excuse_group(name, group)

def excuse_group(name, group):
    group[:] = []
    yield fire('%s-group-done' % name, True)

Santa prints a greeting to the group, and then signals them to start the task at hand. The sleep call represents the time spent cooperating on the task. Finally, the group is cleared and the actors are signaled that the group activity is done. The reindeer return to their vacations and the elves resume work.

This is all easily coordinated since Python's generators, combined with Diesel, perform cooperative multitasking. Each generator gets processing time to do its own thing and then yields control back to the Diesel core so it can wake another another generator. Any actions performed by a given generator are atomic with regard to the others. This makes working with shared structures easy.

It cuts both ways though. The actions performed by a given generator while it is active block the others. Generators should do what they have to do quickly and then yield control back to the core.

Hopefully this little diversion from the norm here at the ShopTalk blog was educational and entertaining. I know it was for me. The complete code is below. Also see here for Haskell and Erlang versions.

import random
from diesel import Application, Loop, fire, wait, sleep

deer_group = []
elf_group = []

def santa():
    while True:
        deer_ready, elves_ready = len(deer_group) == 9, len(elf_group) == 3
        if deer_ready:
            yield work_with_group('deer', deer_group, 'deliver toys')
        if elves_ready:
            yield work_with_group('elf', elf_group, 'meet in my study')
        yield sleep(random.random())

def actor(name, type, group, task, max_group, max_sleep):
    def actor_event_loop():
        while True:
            yield sleep(random.random() * max_sleep)
            if len(group) < max_group:
                group.append(name)
                yield wait('%s-group-started' % type)
                print "%s %s" % (name, task)
                yield wait('%s-group-done' % type)
    return actor_event_loop

def work_with_group(name, group, message):
    print "Ho! Ho! Ho! Let's", message
    yield fire('%s-group-started' % name)
    yield sleep(random.random() * 3)
    yield excuse_group(name, group)

def excuse_group(name, group):
    group[:] = []
    yield fire('%s-group-done' % name, True)

def main():
    app = Application()
    app.add_loop(Loop(santa))

    elf_do = "meets in study"
    for i in xrange(10):
        app.add_loop(Loop(actor("Elf %d" % i, 'elf', elf_group, elf_do, 3, 3)))

    deer_do = "delivers toys"
    for name in [
            'Dasher', 'Dancer', 'Prancer', 
            'Vixen', 'Comet', 'Cupid', 
            'Donner', 'Blitzen', 'Rudolph',
            ]:
        app.add_loop(Loop(actor(name, 'deer', deer_group, deer_do, 9, 9)))

    app.run()

if __name__ == '__main__':
    main()