[concurrency-interest] santa clause problem solved?

Joe Bowbeer joe.bowbeer at gmail.com
Wed Apr 9 02:20:38 EDT 2008


On Mon, Apr 7, 2008 at 6:39 PM, David Holmes wrote:
>
>  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 :-)
>

I simplified the code quite a bit and added a semaphore to control
access to the barriers.

There are now only three classes:

1. Santa
2. GroupActivity (for "delivering toys" and "meeting with elves")
3. Worker (for reindeer and elves)

Note that I'm using separate barriers for starting and stopping the
group activity, whereas one barrier can often be reused for both
purposes.  Using two barriers allows new permits to be released as
soon as the current activity has started.  This way, a new team can
form while the current activity is in progress -- as you suggest.

By the way, the code now uses a Deque instead of a PriorityQueue.  The
single high-priority reindeer task is added at the head, while the
low-priority elf tasks are added at the tail.

The code:

/*
 *  SantaClausProblem.java
 */

import java.util.Deque;
import java.util.Random;
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;

/**
 * A simulation of the Santa Claus Problem using java.util.concurrent.
 *
 * <p>See <a href="http://www.crsr.net/Notes/SantaClausProblem.html">
 * http://www.crsr.net/Notes/SantaClausProblem.html</a> for a
 * solution using Haskell and Software Transactional Memory (STM).
 * See <a href="http://research.microsoft.com/~nick/santa.pdf">
 * http://research.microsoft.com/~nick/santa.pdf</a> for a solution
 * written in Polyphonic C#.
 *
 * @author Joe Bowbeer
 */
public class SantaClausProblem {

    static final int ELF_QUORAM = 3;
    static final int NUM_ELVES = 10;
    static final int NUM_REINDEER = 9;

    /** Santa sleeps, meets with elves and delivers toys with reindeer. */
    static class Santa implements Runnable {
        private final BlockingQueue<Runnable> queue;
        Santa(BlockingQueue<Runnable> queue) {
            this.queue = queue;
        }
        public void run() {
            try {
                while (true) {
                    System.out.println("Santa is sleeping");
                    queue.take().run();
                }
            } catch (InterruptedException ex) {
                // quit
            }
            System.out.println("Santa is done");
        }
    }

    /** An activity performed by Santa with a team of helpers. */
    static class GroupActivity {

        private final String name;
        private final Semaphore permit;
        private final CyclicBarrier groupBarrier;
        private final CyclicBarrier entryBarrier;
        private final CyclicBarrier exitBarrier;

        GroupActivity(String name,
                final int size,
                final Deque<Runnable> deque,
                final boolean prepend, // addFirst if high-priority
                final Runnable action) {

            this.name = name;
            permit = new Semaphore(size, true); // fair
            entryBarrier = new CyclicBarrier(size + 1);
            exitBarrier = new CyclicBarrier(size + 1);

            // Wake up Santa when a sufficiently large group has formed
            groupBarrier = new CyclicBarrier(size, new Runnable() {
                public void run() {
                    Runnable task = new Runnable() {
                        public void run() {
                            try {
                                entryBarrier.await(); // hitch
                                permit.release(size); // form new team
                                System.out.println("Santa is " + action);
                                action.run();
                                exitBarrier.await();  // unhitch
                            } catch (InterruptedException ex) {
                                Thread.currentThread().interrupt();
                            } catch (BrokenBarrierException ex) {
                                Thread.currentThread().interrupt();
                            }
                        }
                    };
                    if (prepend) {
                        deque.addFirst(task);
                    } else {
                        deque.addLast(task);
                    }
                }
            });
        }

        void arrive() throws InterruptedException, BrokenBarrierException {
            permit.acquire();       // join team
            groupBarrier.await();   // wakeup Santa
            entryBarrier.await();   // hitch and go
        }

        void leave() throws InterruptedException, BrokenBarrierException {
            exitBarrier.await();    // unhitch
        }

        @Override public String toString() {
            return name;
        }
    }

    /** Alternates between group activity with Santa and a solo task. */
    static class Worker implements Runnable {
        private final String name;
        private final GroupActivity group;
        private final Runnable soloTask;
        Worker(String name, GroupActivity group, Runnable soloTask) {
            this.name = name;
            this.group = group;
            this.soloTask = soloTask;
        }
        public void run() {
            System.out.println(name + " starting");
            try {
                while (true) {
                    System.out.println(name + " is waiting for Santa");
                    group.arrive();
                    System.out.println(name + " at " + group);
                    group.leave();
                    System.out.println(name + " is " + soloTask);
                    soloTask.run();
                }
            } catch (InterruptedException ex) {
                // quit
            } catch (BrokenBarrierException ex) {
                // quit
            }
            System.out.println(name + " quitting");
        }
    }

    static final Random RAND = new Random();

    /** Represents a time-consuming activity. */
    static Runnable makeRandomDelay(final int delay, final String name) {
        return new Runnable() {
            public void run() {
                try {
                    Thread.sleep(RAND.nextInt(delay));
                } catch (InterruptedException ex) {
                    Thread.currentThread().interrupt(); // propagate
                }
            }
            @Override public String toString() {
                return name;
            }
        };
    }

    /** Simulates the Santa Claus Problem. */
    public static void main(String[] unused) throws InterruptedException {

        ExecutorService executor = Executors.newCachedThreadPool();

        BlockingDeque<Runnable> deque = new LinkedBlockingDeque<Runnable>();

        Runnable deliverToys = makeRandomDelay(1000, "delivering toys");
        Runnable onHoliday = makeRandomDelay(2000, "on holiday");
        Runnable designToys = makeRandomDelay(500, "designing toys");
        Runnable makeToys = makeRandomDelay(1000, "making toys");

        GroupActivity sleigh = new GroupActivity(
                "sleigh", NUM_REINDEER, deque, true, deliverToys);

        for (int i = 0; i < NUM_REINDEER; i++)
            executor.execute(new Worker("reindeer-"+(i+1), sleigh, onHoliday));

        GroupActivity meeting = new GroupActivity(
                "meeting", ELF_QUORAM, deque, false, designToys);

        for (int i = 0; i < NUM_ELVES; i++)
            executor.execute(new Worker("elf-"+(i+1), meeting, makeToys));

        executor.execute(new Santa(deque));

        // Run simulation for 30 seconds and then shut it down.
        Thread.sleep(30000);
        executor.shutdownNow();
        executor.awaitTermination(2, TimeUnit.SECONDS);
    }
}

Generates output like:

...
Santa is sleeping
elf-6 is waiting for Santa
elf-9 is waiting for Santa
elf-6 at meeting
elf-9 at meeting
Santa is designing toys
elf-3 at meeting
elf-1 is waiting for Santa
elf-10 is waiting for Santa
Santa is sleeping
elf-9 is making toys
elf-3 is making toys
elf-6 is making toys
elf-5 is waiting for Santa
elf-10 at meeting
Santa is designing toys
elf-5 at meeting
elf-1 at meeting
elf-9 is waiting for Santa
elf-4 is waiting for Santa
reindeer-2 is waiting for Santa
elf-2 is waiting for Santa
...


More information about the Concurrency-interest mailing list