[concurrency-interest] santa clause problem solved?

Joe Bowbeer joe.bowbeer at gmail.com
Mon Apr 7 20:45:55 EDT 2008


After a tad more thought I think the problem can be solved using a few
cyclic barriers and a priority queue.

A cyclic barrier of 9 parties serves as the stable for the waiting
reindeer.  When this is released, a high-priority "deliver-toys" task
is queued for santa, and the reindeer wait on a cyclic barrier of 10
parties (the sleigh).  When santa arrives at the sleigh, the whole
gang delivers toys (this is the barrier task) and then the reindeer go
off on separate vacations and santa goes back to sleep (until a new
task arrives).

The elves are harder to deal with.  Arriving elves are given a cyclic
barrier of 4 parties to wait on.  This barrier is a reservation for 3
elves to meet with santa.  A reservation generator hands these out.  A
new reservation is generated after every third elf arrives.  When
three elves have arrived and are waiting on their shared reservation,
a low-priority "meet-with-elves" task is queued for santa.  This task
contains a reference to the barrier those elves are waiting on.  When
santa handles this task, he arrives at that barrier, meets with the
elves (this is the barrier task) and then the elves go back to work
and santa goes back to sleep.

Sound reasonable?  I'd be interested to hear of other solutions.

--Joe

On Mon, Apr 7, 2008 at 1:10 PM, Joe Bowbeer <joe.bowbeer at gmail.com> wrote:
> Does anyone have a nice solution to the Santa Claus Problem using
>  java.util.concurrent?
>
>  I know this is 1/4 turn out of season, but as we all know, Java
>  concurrency is not "real-time" ...
>
>  In Ch. 24 of Beautiful Code, Simon Peyton Jones solves the Santa Claus
>  Problem in Haskell using Software Transactional Memory (STM).  The
>  full source of his solution can be found at:
>
>   http://www.crsr.net/Notes/SantaClausProblem.html
>
>  There's also a full discussion of a "correct" Ada solution in this
>  article Mordechai Ben-Ari:
>
>   http://stwww.weizmann.ac.il/g-cs/benari/articles/santa-claus-problem.pdf
>
>  Ben-Ari, who wrote that Doug Lea invited the readers of Concurrent
>  Programming in Java to develop a full solution, also presents the
>  beginnings of a solution written in ancient BJUC Java.
>  (BJUC=BeforeJavaUtilConcurrent)
>
>  To my eye, a solution in jCSP would look similar to the Haskell and
>  Erlang solutions.
>
>  Has someone written a clean solution with java.util.concurrent?  I'm
>  thinking a custom AbstractQueuedSynchronizer (AQS) may be involved.
>
>  --Joe
>


More information about the Concurrency-interest mailing list