[concurrency-interest] santa clause problem solved?

David Holmes dcholmes at optusnet.com.au
Mon Apr 7 21:39:07 EDT 2008


Hi Joe,

Sounds fairly reasonable. :) I'd never heard of this "problem". There are
three main concurrency issues to deal with that I can see:

1.  To have Santa wait for either the elves or the reindeer - different
languages/systems will make that easier than others. In j.u.c the easiest
way to wait for multiple things is as you suggest: wait on a queue (priority
if needed as in this case) and have the other actions post events to the
queue.

2. To give priority to reindeer over elves. This is actually harder in many
languages, but with a priority queue it's quite straight-forward.

3. Having the elves/reindeer wait for each other and then Santa.

The two barriers for the reindeer seems straight-forward enough.

The elves is a little trickier and I didn't quite see how your solution
worked. If the elves wait on a barrier with four parties, what triggers the
event when 3 arrive? Does your "reservation generator" keep track of
requests and post the event after every third request? That seems to work,
but there's a potential delay between an elf requesting the cyclic barrier
and actually waiting on it, so you might wait for thousands of elves to
block before the initial group of three all arrive at the barrier.

Another possibility is for all elves to try and grab a Semaphore with 3
permits. When they have that they wait on a barrier-3, the barrier task for
which posts the event to the queue together with a barrier-4, and then
signals the semaphore so the next 3 elves can get through. The elves then
wait on the barrier-4 until Santa arrives. I'm not sure how to manage the
references to the barrier-4 and it has the same delay problem :) Maybe delay
is unavoidable if all the elves rush to Santa at once :-)

Now back to real work for me!

Cheers,
David

> -----Original Message-----
> From: concurrency-interest-bounces at cs.oswego.edu
> [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Joe
> Bowbeer
> Sent: Tuesday, 8 April 2008 10:46 AM
> To: concurrency-interest
> Subject: Re: [concurrency-interest] santa clause problem solved?
>
>
> 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
>
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest at altair.cs.oswego.edu
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest



More information about the Concurrency-interest mailing list