Solving the Santa Claus Problem with Barriers

There are already many solutions to the “Santa Claus Problem” by John Trono¹. It’s a “problem simple to understand and yet far from easy to solve”; the author’s original solution (based on semaphores) was only partly correct. The probably most known analysis of the problem was written by Mordechai Ben-Ari², who also provided solutions in Ada95 and Java. This is the original problem description:

Santa Claus sleeps in his shop up at the North Pole, and can only be wakened by either all nine reindeer being back from their year long vacation on the beaches of some tropical island in the South Pacific, or by some elves who are having some difficulties making the toys. One elf’s problem is never serious enough to wake up Santa (otherwise, he may never get any sleep), so, the elves visit Santa in a group of three. When three elves are having their problems solved, any other elves wishing to visit Santa must wait for those elves to return. If Santa wakes up to find three elves waiting at his shop’s door, along with the last reindeer having come back from the tropics, Santa has decided that the elves can wait until after Christmas, because it is more important to get his sleigh ready as soon as possible. (It is assumed that the reindeer don’t want to leave the tropics, and therefore they stay there until the last possible moment. They might not even come back, but since Santa is footing the bill for their year in paradise… This could also explain the quickness in their delivering of presents, since the reindeer can’t wait to get back to where it is warm.) The penalty for the last reindeer to arrive is that it must get Santa while the others wait in a warming hut before being harnessed to the sleigh.

As an exercise to learn the java.util.concurrent package of Java J2SE 5.0 I implemented another solution using barriers (CyclicBarrier objects). As either three elves or all nine reindeer must assemble before they are allowed to wake Santa, this seems to me an obvious choice.

The solution consists mainly of an outer class SantaClaus, that sets up all needed synchronisation variables and controls the program termination, and two inner classes Elf and Reindeer, that are instantiated on a separate thread for each individual elf and reindeer behaviour. The source code is also available as syntax coloured HTML; an earlier version without the harnessing part can be found here.

The barrier that manages the grouping of the elves is protected by a Semaphore queueElves with three permits. This implements the requirement “any other elves wishing to visit Santa must wait for those elves to return” in a rather defensive manner: there is some virtual waiting room for the elves to wait before waking Santa that has room for only three elves.

This defensive approach makes the priority requirement (if nine reindeer and three elves are waiting, Santa must deliver toys first) simple to fulfill; a fair semaphore (semaphore with a FIFO queue) is enough:

As no more than one group of elves can sit in the virtual waiting room and access to the waiting room is blocked until the first group of elves have got back to the toy manufacture, the ninth reindeer will never encounter more than two elves in the waiting room³. It is therefore enough to guarantee that the reindeer are serviced first if they are the first to try the semaphore that protects Santa’s office.

Using a fair semaphore also for queueElves guarantees that no elf is starved when he would like to consult with Santa.

If we would want the get rid of the queueElves semaphore or expand the problem (eg. Santa could start answering the letters from kids), we had to replace the semaphore santasAttention with an advanced mechanism like a PriorityBlockingQueue to guarantee priority for the reindeer.