The Artima Developer Community
Sponsored Link

Weblogs Forum
Too Much Threading

14 replies on 1 page. Most recent reply: Sep 26, 2005 11:45 AM by Bruce Eckel

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 14 replies on 1 page
Bruce Eckel

Posts: 874
Nickname: beckel
Registered: Jun, 2003

Too Much Threading (View in Weblogs)
Posted: Sep 12, 2005 4:35 PM
Reply to this message Reply
Summary
Threading has sucked down a lot of my life in the past few years. Aside from work on earlier versions of Thinking in Java, I clocked 8 months on the threading chapter in "Thinking in C++, Volume 2." I've already spent several months on the "Concurrency" Chapter in "Thinking in Java 4th edition." And now I'm back working on it again.
Advertisement
Because of all the changes in concurrency, the chapter has gotten big. At one point I thought of making it into a separate book. Even with the size that it is, I'm not able to cover all the new library components in java.util.concurrent.

I'm actually having to remove examples. Here's one that I just couldn't make into something appropriate; it was an attempt to use the Exchanger class, which I've decided is just a bit too obscure to include in the book.

However, I think I might get some mileage out of it by posting it here. First, to show you just how far threading has driven me, this example has degenerated into a simulation of a science fiction planet containing mythical creatures with completely questionable reasons for existence. I don't think they could have evolved this way, so perhaps it's an example of "unintelligent design."

More importantly, I'm not sure that I have or haven't synchronized properly or made necessary fields volatile (see the previous posting). At the time I wrote this I had been immersed in threading for long enough that I might have gotten it right -- after all, many of the new components in java.util.concurrent are designed to provide thread safety by themselves. But I figure the eyeballs and feedback will help me ensure that all the rest of the examples in the chapter are correct. I'm hoping that you don't just say "make everything volatile" or "synchronize all methods," but give me the argument for why a particular field or method should be modified, so I can make a clear case for it in the other examples in the book.

Here's the backstory for the example: Red Nibbins and Blue Nibbins try to fool each other into giving up their rample berries, which help them think. Basically, they’re confidence persons, albeit not very smart ones. The rample berries are carried in a special case, and the Nibbins trade cases, unopened, in the hope that the other case will have more berries than the one they have. When a Nibbin is asleep, a Berry Fairy may visit and add more Rample Berries to their case. As a Nibbin's side gains more rample berries than the other, they grow smarter and therefore have more cunning in acquiring more berries. Theoretically, one side should eventually win out over the other.

Note that this example is close to the end of the chapter, so issues such as task termination have already been thoroughly explained.


//: concurrency/Thwonk.java
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
import java.util.*;
import static net.mindview.util.Print.*;

class RampleBerryCase implements Runnable {
  private static Random rand = new Random(47);
  private int berries = 3;
  public void run() {
    try {
      while(!Thread.interrupted()) {
        Thread.sleep(200 + rand.nextInt(1000));
        if(rand.nextInt(10) == 0) // 1 in 10 chance
          berries += 2; // Berry Fairy visits!
      }
    } catch(InterruptedException e) {
      // OK to terminate this way.
    }
  }
  public int numBerries() { return berries; }
}

class Nibbin implements Runnable {
  public enum Color { RED, BLUE };
  private Color color;
  static long counter = 0;
  long id = counter++;
  private static Random rand = new Random(47);
  private RampleBerryCase rampleBerryCase =
    new RampleBerryCase();
  private BerryBrokers berryBrokers ;
  // Construction must be done in steps to prevent
  // null pointers:
  public Nibbin(Color c, BerryBrokers brokers, Executor e){
    color = c;
    berryBrokers = brokers;
    e.execute(rampleBerryCase);
    e.execute(this);
  }
  Color getColor() { return color; }
  public void run() {
    try {
      while(!Thread.interrupted()) {
        int old = rampleBerryCase.numBerries();
        rampleBerryCase = berryBrokers.exchange(this);
        if(rampleBerryCase.numBerries() > old)
          print(this + "Thwonk!"); // (Hooray!)
        else
          print(this + "Blatz!"); // (Darn!)
      }
    } catch(InterruptedException e) {
      // OK to terminate this way.
    }
  }
  public RampleBerryCase getCase() {
    return rampleBerryCase;
  }
  public String toString() {
    return String.format(
      "%1$-4s Nibbin %2$-3d berries: %3$-3d ",
      color, id, rampleBerryCase.numBerries());
  }
}

class BerryBrokers {
  private static class BerryBroker {
    private Exchanger<RampleBerryCase> exchanger =
      new Exchanger<RampleBerryCase>();
    private ReentrantLock
      blueLock = new ReentrantLock(),
      redLock = new ReentrantLock();
    public RampleBerryCase offerBlue(RampleBerryCase old)
    throws InterruptedException {
      return exchanger.exchange(old);
    }
    public RampleBerryCase offerRed(RampleBerryCase old)
    throws InterruptedException {
      return exchanger.exchange(old);
    }
  }
  private ArrayList<BerryBroker> list =
    new ArrayList<BerryBroker>();
  public BerryBrokers(int size) {
    for(int i = 0; i < size; i++)
      list.add(new BerryBroker());
  }
  public RampleBerryCase exchange(Nibbin nibbin)
  throws InterruptedException {
    switch(nibbin.getColor()) {
      case RED:
        for(BerryBroker bb : list) {
          if(bb.redLock.tryLock())
            try {
              return bb.offerRed(nibbin.getCase());
            } finally {
              bb.redLock.unlock();
            }
        }
        // No red locks available. Return the old case:
        return nibbin.getCase();
      case BLUE:
        for(BerryBroker bb : list) {
          if(bb.blueLock.tryLock())
            try {
              return bb.offerBlue(nibbin.getCase());
            } finally {
              bb.blueLock.unlock();
            }
        }
        // No blue locks available. Return the old case:
        return nibbin.getCase();
      default:
        throw new RuntimeException("Not red or blue");
    }
  }
}

public class Thwonk {
  static int size = 100;
  public static void main(String[] args) throws Exception {
    if(args.length > 0) { // Optional argument
      int n = new Integer(args[0]);
      size = n > 0 ? n : size;
    }
    BerryBrokers brokers = new BerryBrokers(size/2);
    ExecutorService e = Executors.newCachedThreadPool();
    for(int i = 0; i < size; i++) {
      new Nibbin(Nibbin.Color.RED, brokers, e);
      new Nibbin(Nibbin.Color.BLUE, brokers, e);
    }
    Thread.sleep(5000);
    e.shutdownNow();
  }
} /* Output: (Sample)
RED  Nibbin 0   berries: 3   Blatz!
RED  Nibbin 0   berries: 3   Blatz!
BLUE Nibbin 1   berries: 3   Blatz!
RED  Nibbin 2   berries: 3   Blatz!
BLUE Nibbin 1   berries: 3   Blatz!
BLUE Nibbin 1   berries: 3   Blatz!
RED  Nibbin 4   berries: 3   Blatz!
...
*///:~

Here's just one issue that I've recently become aware of: in the Nibbin constructor, two tasks are started using the executor e that's passed to the constructor. I've recently learned that creating and starting a thread inside a constructor is problematic, because the constructor doesn't normally release the object lock until construction is complete (thus guaranteeing object consistency when threads are present -- the object is fully constructed before any threads can modify it), but if you start a thread within a constructor, the object lock is then released and the resulting thread can then modify the object before construction is finished. But would the same be true in this case, where a task is handed to an executor? It would be lovely if the executor guards you against such an issue; I already prefer executors to raw threads but this would make the argument for executors far more compelling.

I had made a note to myself to see if this example might be converted into the "beer game" (a business-school simulation of product distribution; see google), but I'm not sure if that's an easy conversion; it's probably a green-fields design instead. As interesting as I think it would be, time constrains will prevent the beer game from making it into the book.

Thanks for any comments.


Frank Zitters

Posts: 5
Nickname: fzitters
Registered: Aug, 2005

Re: Too Much Threading Posted: Sep 12, 2005 8:37 PM
Reply to this message Reply
As their gods, it is our responsibility to make sure poor Nibbins always take notice of Berry Farie's visits. Therefore I suggest to declare RampleBerryCase.berries volatile.

As I see it, there are several reasons for not letting Nibbins start themselves:
- From a design standpoint, a constructor should get an object into valid state but nothing more.
- Lots of bad things can happen if this escapes from a constructor, even if no other threads are involved.
- There are no guarantees as to how and when an Executor will execute it tasks.
- I can't even think of a way for an Executor to find out if a task has already been fully constructed (maybe I should apply for brain upgrade though).
- If we give up our control, Nibbins might lose their faith in God.

I haven't fully caught up with Java 5.0, but I don't believe an object is somehow locked during construction. I can only think of one feasible way for the VM (or rather the compiler) to enforce that an object gets fully constructed before its first use, and that is to prevent this from escaping the constructor.

Hope some of this makes sense to you.

PS: Text formatting doesn't seem to work for me.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Too Much Threading Posted: Sep 13, 2005 5:49 AM
Reply to this message Reply
Why don't you code it like this:
package bruceeckelgame;
 
import java.util.*;
import java.util.concurrent.*;
import static java.lang.System.*;
 
public class Game {
    public static void main( final String[] notUsed ) throws InterruptedException {
        makeCases( Color.BLUE );
        makeCases( Color.RED );
        final ExecutorService pool = Executors.newCachedThreadPool();
        for( int i = 0; i < 20; i++ ) NibbinPair( pool );
        Thread.sleep( 5000 );
        pool.shutdownNow();
        print( Color.BLUE );
        print( Color.RED );
    }
    private static void makeCases( final Color color ) {
        for ( int i = 0; i < 5; i++ ) color.put( new RampleBerryCase() ); // 5 cases each
    }
    private static void NibbinPair( final ExecutorService pool ) {
        final Exchanger< RampleBerryCase > exchanger = new Exchanger< RampleBerryCase >();
        pool.execute( new Nibbin( exchanger, Color.RED ) );
        pool.execute( new Nibbin( exchanger, Color.BLUE ) );
    }
    private static void print( final Color color ) {
        out.println( color + " " + color.cases );
    }
    private static class RampleBerryCase implements Comparable {
        int berries = 3;
        void fairyVisits() { berries += 2; }
        public int compareTo( final Object other ) {
            final RampleBerryCase that = (RampleBerryCase) other;
            return berries - that.berries; // more berries is greater so that casses with less berries are given up first
        }
        public String toString() { return Integer.toString( berries ); }
    }
    private static enum Color {
        RED, BLUE;
        final PriorityBlockingQueue< RampleBerryCase > cases = new PriorityBlockingQueue< RampleBerryCase >() {
            static final long serialVersionUID = 200509131958; // just in case it is serialized!
            public String toString() { // defalut toString doesn't give the sorted order!
                final Object[] sorted = toArray();
                Arrays.sort( sorted );
                return Arrays.toString( sorted );
            }
        };
        void put( final RampleBerryCase caze ) { cases.put( caze ); }
        RampleBerryCase take() throws InterruptedException { return cases.take(); }
    }
    private static enum Result { THWONK, BLATZ }
    private static class Nibbin implements Runnable {
        static long counter = 0;
        long id = counter++;
        final Exchanger< RampleBerryCase > exchanger; // echanger is a meeting point between two Nibbin
        final Color color;
        static final Random rand = new Random( 47 );
        Nibbin( final Exchanger< RampleBerryCase > exchanger, final Color color ) {
            this.exchanger = exchanger; // exchanger for swapping cases (shared with partner)
            this.color = color; // remember which color you are
        }
        public void run() {
            try {
                final RampleBerryCase oldCase = color.take(); // get a case that you don't really want - least valuable
                if( rand.nextInt( 2 ) == 0 ) oldCase.fairyVisits(); // 1 in 2 chance (no prior knowledge - fairy visits after case selected)
                Thread.sleep( 200 + rand.nextInt( 1000 ) ); // random time delay simulating journey to meeting point (exchanger)
                final RampleBerryCase newCase = exchanger.exchange( oldCase ); // exchange cases
                color.put( newCase ); // put the case on the list for a future exchange
                if ( newCase.compareTo( oldCase ) > 0 ) print( Result.THWONK, newCase ); // Hooray! (greater cases have less berries)
                else print( Result.BLATZ, newCase ); // Darn!
            } catch ( InterruptedException notUsed ) { /* OK to terminate */ }
        }
        void print( final Result result, final RampleBerryCase newCase ) {
            out.printf( "%1$-4s Nibbin %2$-3d berries: %3$-3s %4$-6s %5$s\n",
                          color,        id,           newCase, result, color.cases );
        }
    }
}

No need for any volatiles. I added a priority queue to give the Nibbin some intelegence and limited the number of cases to make the output more interesting. On my machine I get:

BLUE Nibbin 5 berries: 3 BLATZ []
RED Nibbin 4 berries: 5 THWONK []
BLUE Nibbin 3 berries: 5 BLATZ []
RED Nibbin 2 berries: 5 BLATZ []
BLUE Nibbin 7 berries: 5 BLATZ []
RED Nibbin 6 berries: 5 BLATZ []
RED Nibbin 10 berries: 3 BLATZ []
BLUE Nibbin 11 berries: 7 THWONK []
RED Nibbin 0 berries: 3 BLATZ []
BLUE Nibbin 1 berries: 5 BLATZ []
BLUE Nibbin 9 berries: 5 BLATZ []
RED Nibbin 8 berries: 5 BLATZ []
BLUE Nibbin 21 berries: 5 BLATZ []
RED Nibbin 20 berries: 5 BLATZ [7]
BLUE Nibbin 13 berries: 5 BLATZ []
RED Nibbin 12 berries: 7 THWONK []
RED Nibbin 14 berries: 7 THWONK []
BLUE Nibbin 15 berries: 5 BLATZ []
BLUE Nibbin 17 berries: 3 BLATZ []
RED Nibbin 16 berries: 9 THWONK []
RED Nibbin 18 berries: 5 BLATZ []
BLUE Nibbin 19 berries: 5 BLATZ []
RED Nibbin 26 berries: 5 BLATZ []
BLUE Nibbin 27 berries: 7 THWONK []
BLUE Nibbin 25 berries: 7 THWONK []
RED Nibbin 24 berries: 7 BLATZ []
RED Nibbin 22 berries: 5 BLATZ []
BLUE Nibbin 23 berries: 5 BLATZ []
RED Nibbin 28 berries: 5 BLATZ []
BLUE Nibbin 29 berries: 11 THWONK []
RED Nibbin 30 berries: 5 BLATZ [5]
BLUE Nibbin 31 berries: 5 BLATZ [5]
BLUE Nibbin 33 berries: 7 BLATZ [5, 7]
RED Nibbin 32 berries: 7 BLATZ [5, 7]
BLUE Nibbin 39 berries: 5 BLATZ [5, 5, 7]
RED Nibbin 38 berries: 11 THWONK [5, 7, 11]
BLUE Nibbin 35 berries: 7 BLATZ [5, 5, 7, 7]
RED Nibbin 34 berries: 9 THWONK [5, 7, 9, 11]
RED Nibbin 36 berries: 5 BLATZ [5, 5, 7, 9, 11]
BLUE Nibbin 37 berries: 5 BLATZ [5, 5, 5, 7, 7]
BLUE [5, 5, 5, 7, 7]
RED [5, 5, 7, 9, 11]

As you can see RED tends to win on my machine (with the random number generator seed given).

Kondwani Mkandawire

Posts: 530
Nickname: spike
Registered: Aug, 2004

Re: Too Much Threading Posted: Sep 13, 2005 7:06 AM
Reply to this message Reply
It puzzles me why people writing introductory/intermediate Java books spend so much
time on threading. All the intermidiate type problems I have come across have always
had an alternative solution. E.g. you want to build a Splash Screen, you use the
Timer class found in Swing (implicit threading which one need not be concerned about),
painting swing components itself has implicit threading (which in most cases the
developer doesn't have to worry about - the EventQueue, SwingUtilities.invokeLater(),
etc). In short, I don't see the need to drag on with a chapter in threading
when Java seems to have already provided a lot of work-arounds, run a survey on
how many students really concentrated on the Threading Chapter for your last book
I doubt there will be that many.

I think concurrent programming is a whole different ball game and should be left
to Books that address advanced programming issues.

Bill Venners

Posts: 2248
Nickname: bv
Registered: Jan, 2002

Re: Too Much Threading Posted: Sep 13, 2005 12:30 PM
Reply to this message Reply
> PS: Text formatting doesn't seem to work for me.

Sorry about that. The code formatting is the one currently not working. We did a fairly major refactor that consisted only of changing package names, and one of the package names we changed was the name of a filter that was doing the text styling. Somewhat long story, but the end result was that I installed the wrong filter afterwords. Once I get that corrected, all the expected text styling will magically start to work again.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Too Much Threading Posted: Sep 13, 2005 8:35 PM
Reply to this message Reply
@Kondwani Mkandawire

I agree with your comments re. using threading and that it is not for begineers/intermediates to use directly, but only via pre-written libraries.

I would probably go further and say that even advanced users should stick with the pre-writen stuff like the swing threading that you suggested and the Concurrent library. My own experiance with threading is that it is much easier to use the Concurrent library or something similar than to get involved with the primitive constructs like synchronized and volatile.

PS code tag doesn't seem to work but other tags do seem to work!

Bill Venners

Posts: 2248
Nickname: bv
Registered: Jan, 2002

Re: Too Much Threading Posted: Sep 14, 2005 12:33 AM
Reply to this message Reply
> PS code tag doesn't seem to work but other tags do seem to
> work!

I put the correct filter back in, so all tags should work as advertised now.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Too Much Threading Posted: Sep 14, 2005 9:50 PM
Reply to this message Reply
For a bit of fun last night I coded the beer game in J5:
package beergame;
 
import java.util.*;
import java.util.concurrent.*;
import static java.lang.System.*;
import static java.lang.Math.*;
 
/**
 * MIT Beer Game simulation. Rules from:
 * <blockquote>
 * http://www.solonline.org/repository/download/instr.html?item_id=456354
 * </blockquote>
 * <p>
 * Except:
 * <ul>
 * <li>I assumed: order delay = shipping delay = production delay = 1 week,
 * the above site doesn't state the delays!
 * <li>The customer buys a random number of cases, between 1 and 10, each week
 * <li>Rest as suggested at above reference
 * </ul>
 * <p>
 * Note: <em>I have never played the game!</em>. Therefore my interpretation
 * of the rules may be wrong!
 *
 * @author Howard Lovatt
 */
public class Play {
    static final int maxOrder = 10; // the maximum order a cistomer can place
    static final int week = 100; // ms, i.e. 1 week takes 0.1 seconds to simulate
    static double runningTotal = 0; // the total cost incurred to date
    static final ExecutorService pool = Executors.newCachedThreadPool();
    public static void main( final String[] notUsed ) throws InterruptedException {
        final Order initialOrder = new Order( maxOrder / 2 ); // establish the initial state
        Queues.rWOrders.put( initialOrder );
        Queues.wDOrders.put( initialOrder );
        Queues.dFOrders.put( initialOrder );
        Production.BEER.orders.put( initialOrder );
        final Beer initialBeer = new Beer( maxOrder / 2 );
        Queues.wRBeers.put( initialBeer );
        Queues.dWBeers.put( initialBeer );
        Queues.fDBeers.put( initialBeer );
        Production.BEER.beers.put( initialBeer );
        Production.BEER.production.put( initialBeer );
        Thread.sleep( week ); // wait a week to allow orders/beers to progress in their queues
        pool.execute( Customer.DEMAND ); // start the game
        pool.execute( Player.RETAILER );
        pool.execute( Player.WHOLESALER );
        pool.execute( Player.DISTRIBUTOR );
        pool.execute( Player.FACTORY );
        pool.execute( Production.BEER );
        Thread.sleep( 3000 ); // game lasts no longer than 3 seconds, to keep output short - but test new strategies for much longer, e.g. 20 seconds, to demonstrate stability!
        pool.shutdownNow();
    }
    private interface Queues { // These static fields are put in an interface so that they are initalized before the static field enums in the Player enum (pain with enums!)
        BlockingQueue< Order > rWOrders = new DelayQueue< Order >();
        BlockingQueue< Order > wDOrders = new DelayQueue< Order >();
        BlockingQueue< Order > dFOrders = new DelayQueue< Order >();
        BlockingQueue< Beer > wRBeers = new DelayQueue< Beer >();
        BlockingQueue< Beer > dWBeers = new DelayQueue< Beer >();
        BlockingQueue< Beer > fDBeers = new DelayQueue< Beer >();
    }
    private static enum Player implements Runnable, Queues {
        RETAILER( Customer.DEMAND.orders, rWOrders, wRBeers, Customer.DEMAND.blackHole ), 
        WHOLESALER( rWOrders, wDOrders, dWBeers, wRBeers ), 
        DISTRIBUTOR( wDOrders, dFOrders, fDBeers, dWBeers ), 
        FACTORY( dFOrders, Production.BEER.orders, Production.BEER.beers, fDBeers );
        static final int targetInventory = 5 * maxOrder; // paramaters for decision method, inventory needs to be large for stability, e.g. 5 * maxOrder, for the simple controller given
        static final float pGain = 1F; // you can play with this! 0 is too low and 2 is too high (the term pGain is from control theory - this is the proportional gain of the controller)
        final BlockingQueue< Order > inOrders; // queues
        final BlockingQueue< Order > outOrders;
        final BlockingQueue< Beer > inBeers;
        final BlockingQueue< Beer > outBeers;
        int backOrder = 0; // start with no backlog
        int inventory = targetInventory; // start with target inventory
        Player( final BlockingQueue< Order > inOrders, final BlockingQueue< Order > outOrders, 
                final BlockingQueue< Beer > inBeers, final BlockingQueue< Beer > outBeers ) {
            this.inOrders = inOrders;
            this.outOrders = outOrders;
            this.inBeers = inBeers;
            this.outBeers = outBeers;
        }
        public void run() {
            try {
                while ( true ) {
                    final int inOrder = inOrders.take().value;
                    final int inBeer = inBeers.take().value; // get beer delivery
                    inventory += inBeer; // add to inventory
                    final int beerRequired = inOrder + backOrder;
                    final int outBeer;
                    if ( inventory >= beerRequired ) {
                        outBeer = beerRequired;
                        backOrder = 0;
                        inventory -= beerRequired;
                    } else {
                        outBeer = inventory;
                        backOrder += beerRequired - inventory;
                        inventory = 0;
                    }
                    outBeers.put( new Beer( outBeer ) );
                    final int inventoryError = targetInventory - inventory + backOrder;
                    final int outOrder = max( 0, round( controller( inventoryError ) ) ); // integer and can't have negative orders
                    outOrders.put( new Order( outOrder ) );
                    out.println( "inOrder = " + inOrder + ", outOrder = " + outOrder + ", inBeer = " + inBeer + ", outBeer = " + outBeer + ", inventory = " + inventory + ", backOrder = " + backOrder + " for " + this);
                }
            } catch ( InterruptedException notUsed ) { /* OK to quit */ }
        }
        float controller( final int error ) { // you can play with different strategies for this simple P controller by setting targetInventory and pGain
            return pGain * error;
        }
        public String toString() { return super.toString() + ":$" + getCost(); }
        double getCost() { return backOrder + 0.5 * inventory; }
    }
    private static enum Customer implements Runnable {
        DEMAND;
        static final Random rand = new Random( 47 );
        static final BlockingQueue< Beer > blackHole = new LinkedBlockingQueue< Beer >() { // disgard beer! - output not needed in simulation
            static final long serialVersionUID = 200509150908; // just in case it is serialized
            public void put( final Beer notUsed ) { /* disgard input - this is a black hole */ }
        };
        final BlockingQueue< Order > orders = new ArrayBlockingQueue< Order >( 1 ); // use a buffer of length 1 so that this task gives way to others - ensures orderly execution
        int weekNumber = 0;
        public void run() {
            try {
                while ( true ) {
                    for ( Player player : Player.values() ) runningTotal += player.getCost(); // Output status
                    out.println( "Week " + (weekNumber++) + ": " + " Running Total = $" + runningTotal + ' ' + Arrays.toString( Player.values() ) );
                    orders.put( new Order( rand.nextInt( maxOrder ) ) ); // place a random order of up to maxOrder beers
                    Thread.sleep( week ); // place next order in a weeks time - lazy programming a scheduled executor would be better!
                }
            } catch ( InterruptedException notUsed ) { /* OK to quit */ }
        }
    }
    private static enum Production implements Runnable {
        BEER;
        final BlockingQueue< Order > orders = new DelayQueue< Order >();
        final BlockingQueue< Beer > production = new DelayQueue< Beer >(); // making beer takes a week
        final BlockingQueue< Beer > beers = new DelayQueue< Beer >();
        public void run() {
            try {
                while ( true ) {
                    final int order = orders.take().value; // get order
                    production.put( new Beer( order ) ); // make beer - it takes a week
                    final int beer = production.take().value; // beer I made earlier
                    beers.put( new Beer( beer ) ); // ship beer
                }
            } catch ( InterruptedException notUsed ) { /* OK to quit */ }
        }
    }
    private static class Order implements Delayed {
        final int value;
        final long endTime = currentTimeMillis() + week; // 1 week delay
        Order( final int value ) {
            if ( value < 0 ) {
                pool.shutdownNow(); // terminate game - numeric overflow!
                throw new IllegalArgumentException( "Negative order or beer - probably a numeric overflow");
            }
            this.value = value;
        }
        public long getDelay( final TimeUnit unit ) { return unit.convert( endTime - currentTimeMillis(), TimeUnit.MILLISECONDS ); }
        public int compareTo( final Delayed notUsed ) { return 0; }
        public String toString() { return Integer.toString( value ); }
    }
    private static class Beer extends Order { // alias for Order, i.e. shipping delay = ordering delay and number of beers >= 0
        Beer( final int value ) { super( value ); }
    }
}

The output is:

Week 0: Running Total = $100.0 [RETAILER:$25.0, WHOLESALER:$25.0, DISTRIBUTOR:$25.0, FACTORY:$25.0]
inOrder = 8, outOrder = 3, inBeer = 5, outBeer = 8, inventory = 47, backOrder = 0 for RETAILER:$23.5
inOrder = 5, outOrder = 0, inBeer = 5, outBeer = 5, inventory = 50, backOrder = 0 for WHOLESALER:$25.0
inOrder = 5, outOrder = 0, inBeer = 5, outBeer = 5, inventory = 50, backOrder = 0 for DISTRIBUTOR:$25.0
inOrder = 5, outOrder = 0, inBeer = 5, outBeer = 5, inventory = 50, backOrder = 0 for FACTORY:$25.0
Week 1: Running Total = $198.5 [RETAILER:$23.5, WHOLESALER:$25.0, DISTRIBUTOR:$25.0, FACTORY:$25.0]
inOrder = 5, outOrder = 3, inBeer = 5, outBeer = 5, inventory = 47, backOrder = 0 for RETAILER:$23.5
inOrder = 3, outOrder = 0, inBeer = 5, outBeer = 3, inventory = 52, backOrder = 0 for WHOLESALER:$26.0
inOrder = 0, outOrder = 0, inBeer = 5, outBeer = 0, inventory = 55, backOrder = 0 for DISTRIBUTOR:$27.5
inOrder = 0, outOrder = 0, inBeer = 5, outBeer = 0, inventory = 55, backOrder = 0 for FACTORY:$27.5
Week 2: Running Total = $303.0 [RETAILER:$23.5, WHOLESALER:$26.0, DISTRIBUTOR:$27.5, FACTORY:$27.5]
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 55, backOrder = 0 for DISTRIBUTOR:$27.5
inOrder = 0, outOrder = 0, inBeer = 5, outBeer = 0, inventory = 60, backOrder = 0 for FACTORY:$30.0
inOrder = 3, outOrder = 1, inBeer = 0, outBeer = 3, inventory = 49, backOrder = 0 for WHOLESALER:$24.5
inOrder = 3, outOrder = 3, inBeer = 3, outBeer = 3, inventory = 47, backOrder = 0 for RETAILER:$23.5
Week 3: Running Total = $408.5 [RETAILER:$23.5, WHOLESALER:$24.5, DISTRIBUTOR:$27.5, FACTORY:$30.0]
inOrder = 3, outOrder = 4, inBeer = 0, outBeer = 3, inventory = 46, backOrder = 0 for WHOLESALER:$23.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 60, backOrder = 0 for FACTORY:$30.0
inOrder = 1, outOrder = 0, inBeer = 0, outBeer = 1, inventory = 54, backOrder = 0 for DISTRIBUTOR:$27.0
inOrder = 1, outOrder = 1, inBeer = 3, outBeer = 1, inventory = 49, backOrder = 0 for RETAILER:$24.5
Week 4: Running Total = $513.0 [RETAILER:$24.5, WHOLESALER:$23.0, DISTRIBUTOR:$27.0, FACTORY:$30.0]
inOrder = 1, outOrder = 0, inBeer = 3, outBeer = 1, inventory = 51, backOrder = 0 for RETAILER:$25.5
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 60, backOrder = 0 for FACTORY:$30.0
inOrder = 4, outOrder = 0, inBeer = 0, outBeer = 4, inventory = 50, backOrder = 0 for DISTRIBUTOR:$25.0
inOrder = 1, outOrder = 4, inBeer = 1, outBeer = 1, inventory = 46, backOrder = 0 for WHOLESALER:$23.0
Week 5: Running Total = $616.5 [RETAILER:$25.5, WHOLESALER:$23.0, DISTRIBUTOR:$25.0, FACTORY:$30.0]
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 60, backOrder = 0 for FACTORY:$30.0
inOrder = 4, outOrder = 4, inBeer = 0, outBeer = 4, inventory = 46, backOrder = 0 for DISTRIBUTOR:$23.0
inOrder = 0, outOrder = 0, inBeer = 4, outBeer = 0, inventory = 50, backOrder = 0 for WHOLESALER:$25.0
inOrder = 9, outOrder = 7, inBeer = 1, outBeer = 9, inventory = 43, backOrder = 0 for RETAILER:$21.5
Week 6: Running Total = $716.0 [RETAILER:$21.5, WHOLESALER:$25.0, DISTRIBUTOR:$23.0, FACTORY:$30.0]
inOrder = 4, outOrder = 0, inBeer = 0, outBeer = 4, inventory = 56, backOrder = 0 for FACTORY:$28.0
inOrder = 0, outOrder = 4, inBeer = 0, outBeer = 0, inventory = 46, backOrder = 0 for DISTRIBUTOR:$23.0
inOrder = 7, outOrder = 3, inBeer = 4, outBeer = 7, inventory = 47, backOrder = 0 for WHOLESALER:$23.5
inOrder = 8, outOrder = 15, inBeer = 0, outBeer = 8, inventory = 35, backOrder = 0 for RETAILER:$17.5
Week 7: Running Total = $808.0 [RETAILER:$17.5, WHOLESALER:$23.5, DISTRIBUTOR:$23.0, FACTORY:$28.0]
inOrder = 3, outOrder = 3, inBeer = 4, outBeer = 3, inventory = 47, backOrder = 0 for DISTRIBUTOR:$23.5
inOrder = 15, outOrder = 18, inBeer = 0, outBeer = 15, inventory = 32, backOrder = 0 for WHOLESALER:$16.0
inOrder = 0, outOrder = 8, inBeer = 7, outBeer = 0, inventory = 42, backOrder = 0 for RETAILER:$21.0
inOrder = 4, outOrder = 0, inBeer = 0, outBeer = 4, inventory = 52, backOrder = 0 for FACTORY:$26.0
Week 8: Running Total = $894.5 [RETAILER:$21.0, WHOLESALER:$16.0, DISTRIBUTOR:$23.5, FACTORY:$26.0]
inOrder = 18, outOrder = 17, inBeer = 4, outBeer = 18, inventory = 33, backOrder = 0 for DISTRIBUTOR:$16.5
inOrder = 8, outOrder = 23, inBeer = 3, outBeer = 8, inventory = 27, backOrder = 0 for WHOLESALER:$13.5
inOrder = 3, outOrder = 1, inBeer = 0, outBeer = 3, inventory = 49, backOrder = 0 for FACTORY:$24.5
inOrder = 2, outOrder = 0, inBeer = 15, outBeer = 2, inventory = 55, backOrder = 0 for RETAILER:$27.5
Week 9: Running Total = $976.5 [RETAILER:$27.5, WHOLESALER:$13.5, DISTRIBUTOR:$16.5, FACTORY:$24.5]
inOrder = 23, outOrder = 37, inBeer = 3, outBeer = 23, inventory = 13, backOrder = 0 for DISTRIBUTOR:$6.5
inOrder = 17, outOrder = 18, inBeer = 0, outBeer = 17, inventory = 32, backOrder = 0 for FACTORY:$16.0
inOrder = 0, outOrder = 5, inBeer = 18, outBeer = 0, inventory = 45, backOrder = 0 for WHOLESALER:$22.5
inOrder = 7, outOrder = 0, inBeer = 8, outBeer = 7, inventory = 56, backOrder = 0 for RETAILER:$28.0
Week 10: Running Total = $1049.5 [RETAILER:$28.0, WHOLESALER:$22.5, DISTRIBUTOR:$6.5, FACTORY:$16.0]
inOrder = 5, outOrder = 25, inBeer = 17, outBeer = 5, inventory = 25, backOrder = 0 for DISTRIBUTOR:$12.5
inOrder = 37, outOrder = 55, inBeer = 0, outBeer = 32, inventory = 0, backOrder = 5 for FACTORY:$5.0
inOrder = 0, outOrder = 0, inBeer = 23, outBeer = 0, inventory = 68, backOrder = 0 for WHOLESALER:$34.0
inOrder = 8, outOrder = 2, inBeer = 0, outBeer = 8, inventory = 48, backOrder = 0 for RETAILER:$24.0
Week 11: Running Total = $1125.0 [RETAILER:$24.0, WHOLESALER:$34.0, DISTRIBUTOR:$12.5, FACTORY:$5.0]
inOrder = 0, outOrder = 0, inBeer = 32, outBeer = 0, inventory = 57, backOrder = 0 for DISTRIBUTOR:$28.5
inOrder = 25, outOrder = 84, inBeer = 1, outBeer = 1, inventory = 0, backOrder = 34 for FACTORY:$34.0
inOrder = 2, outOrder = 0, inBeer = 5, outBeer = 2, inventory = 71, backOrder = 0 for WHOLESALER:$35.5
inOrder = 8, outOrder = 10, inBeer = 0, outBeer = 8, inventory = 40, backOrder = 0 for RETAILER:$20.0
Week 12: Running Total = $1243.0 [RETAILER:$20.0, WHOLESALER:$35.5, DISTRIBUTOR:$28.5, FACTORY:$34.0]
Week 13: Running Total = $1361.0 [RETAILER:$20.0, WHOLESALER:$35.5, DISTRIBUTOR:$28.5, FACTORY:$34.0]
inOrder = 0, outOrder = 0, inBeer = 1, outBeer = 0, inventory = 58, backOrder = 0 for DISTRIBUTOR:$29.0
inOrder = 0, outOrder = 100, inBeer = 18, outBeer = 18, inventory = 0, backOrder = 50 for FACTORY:$50.0
inOrder = 10, outOrder = 0, inBeer = 0, outBeer = 10, inventory = 61, backOrder = 0 for WHOLESALER:$30.5
inOrder = 1, outOrder = 9, inBeer = 2, outBeer = 1, inventory = 41, backOrder = 0 for RETAILER:$20.5
Week 14: Running Total = $1491.0 [RETAILER:$20.5, WHOLESALER:$30.5, DISTRIBUTOR:$29.0, FACTORY:$50.0]
inOrder = 0, outOrder = 0, inBeer = 18, outBeer = 0, inventory = 76, backOrder = 0 for DISTRIBUTOR:$38.0
inOrder = 0, outOrder = 45, inBeer = 55, outBeer = 50, inventory = 5, backOrder = 0 for FACTORY:$2.5
inOrder = 9, outOrder = 0, inBeer = 0, outBeer = 9, inventory = 52, backOrder = 0 for WHOLESALER:$26.0
inOrder = 9, outOrder = 8, inBeer = 10, outBeer = 9, inventory = 42, backOrder = 0 for RETAILER:$21.0
Week 15: Running Total = $1578.5 [RETAILER:$21.0, WHOLESALER:$26.0, DISTRIBUTOR:$38.0, FACTORY:$2.5]
inOrder = 0, outOrder = 0, inBeer = 50, outBeer = 0, inventory = 126, backOrder = 0 for DISTRIBUTOR:$63.0
inOrder = 0, outOrder = 0, inBeer = 84, outBeer = 0, inventory = 89, backOrder = 0 for FACTORY:$44.5
inOrder = 8, outOrder = 6, inBeer = 0, outBeer = 8, inventory = 44, backOrder = 0 for WHOLESALER:$22.0
inOrder = 9, outOrder = 8, inBeer = 9, outBeer = 9, inventory = 42, backOrder = 0 for RETAILER:$21.0
Week 16: Running Total = $1729.0 [RETAILER:$21.0, WHOLESALER:$22.0, DISTRIBUTOR:$63.0, FACTORY:$44.5]
inOrder = 6, outOrder = 0, inBeer = 0, outBeer = 6, inventory = 120, backOrder = 0 for DISTRIBUTOR:$60.0
inOrder = 0, outOrder = 0, inBeer = 100, outBeer = 0, inventory = 189, backOrder = 0 for FACTORY:$94.5
inOrder = 8, outOrder = 14, inBeer = 0, outBeer = 8, inventory = 36, backOrder = 0 for WHOLESALER:$18.0
inOrder = 8, outOrder = 8, inBeer = 8, outBeer = 8, inventory = 42, backOrder = 0 for RETAILER:$21.0
Week 17: Running Total = $1922.5 [RETAILER:$21.0, WHOLESALER:$18.0, DISTRIBUTOR:$60.0, FACTORY:$94.5]
inOrder = 14, outOrder = 0, inBeer = 0, outBeer = 14, inventory = 106, backOrder = 0 for DISTRIBUTOR:$53.0
inOrder = 0, outOrder = 0, inBeer = 45, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 8, outOrder = 16, inBeer = 6, outBeer = 8, inventory = 34, backOrder = 0 for WHOLESALER:$17.0
inOrder = 8, outOrder = 8, inBeer = 8, outBeer = 8, inventory = 42, backOrder = 0 for RETAILER:$21.0
Week 18: Running Total = $2130.5 [RETAILER:$21.0, WHOLESALER:$17.0, DISTRIBUTOR:$53.0, FACTORY:$117.0]
inOrder = 16, outOrder = 0, inBeer = 0, outBeer = 16, inventory = 90, backOrder = 0 for DISTRIBUTOR:$45.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 8, outOrder = 10, inBeer = 14, outBeer = 8, inventory = 40, backOrder = 0 for WHOLESALER:$20.0
inOrder = 1, outOrder = 1, inBeer = 8, outBeer = 1, inventory = 49, backOrder = 0 for RETAILER:$24.5
Week 19: Running Total = $2337.0 [RETAILER:$24.5, WHOLESALER:$20.0, DISTRIBUTOR:$45.0, FACTORY:$117.0]
inOrder = 10, outOrder = 0, inBeer = 0, outBeer = 10, inventory = 80, backOrder = 0 for DISTRIBUTOR:$40.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 1, outOrder = 0, inBeer = 16, outBeer = 1, inventory = 55, backOrder = 0 for WHOLESALER:$27.5
inOrder = 0, outOrder = 0, inBeer = 8, outBeer = 0, inventory = 57, backOrder = 0 for RETAILER:$28.5
Week 20: Running Total = $2550.0 [RETAILER:$28.5, WHOLESALER:$27.5, DISTRIBUTOR:$40.0, FACTORY:$117.0]
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 0, outOrder = 0, inBeer = 10, outBeer = 0, inventory = 65, backOrder = 0 for WHOLESALER:$32.5
inOrder = 8, outOrder = 0, inBeer = 1, outBeer = 8, inventory = 50, backOrder = 0 for RETAILER:$25.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 80, backOrder = 0 for DISTRIBUTOR:$40.0
Week 21: Running Total = $2764.5 [RETAILER:$25.0, WHOLESALER:$32.5, DISTRIBUTOR:$40.0, FACTORY:$117.0]
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 65, backOrder = 0 for WHOLESALER:$32.5
inOrder = 6, outOrder = 6, inBeer = 0, outBeer = 6, inventory = 44, backOrder = 0 for RETAILER:$22.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 80, backOrder = 0 for DISTRIBUTOR:$40.0
Week 22: Running Total = $2976.0 [RETAILER:$22.0, WHOLESALER:$32.5, DISTRIBUTOR:$40.0, FACTORY:$117.0]
Week 23: Running Total = $3187.5 [RETAILER:$22.0, WHOLESALER:$32.5, DISTRIBUTOR:$40.0, FACTORY:$117.0]
inOrder = 6, outOrder = 0, inBeer = 0, outBeer = 6, inventory = 59, backOrder = 0 for WHOLESALER:$29.5
inOrder = 0, outOrder = 6, inBeer = 0, outBeer = 0, inventory = 44, backOrder = 0 for RETAILER:$22.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 80, backOrder = 0 for DISTRIBUTOR:$40.0
Week 24: Running Total = $3396.0 [RETAILER:$22.0, WHOLESALER:$29.5, DISTRIBUTOR:$40.0, FACTORY:$117.0]
inOrder = 6, outOrder = 0, inBeer = 0, outBeer = 6, inventory = 53, backOrder = 0 for WHOLESALER:$26.5
inOrder = 1, outOrder = 1, inBeer = 6, outBeer = 1, inventory = 49, backOrder = 0 for RETAILER:$24.5
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 80, backOrder = 0 for DISTRIBUTOR:$40.0
Week 25: Running Total = $3604.0 [RETAILER:$24.5, WHOLESALER:$26.5, DISTRIBUTOR:$40.0, FACTORY:$117.0]
inOrder = 1, outOrder = 0, inBeer = 0, outBeer = 1, inventory = 52, backOrder = 0 for WHOLESALER:$26.0
inOrder = 2, outOrder = 0, inBeer = 6, outBeer = 2, inventory = 53, backOrder = 0 for RETAILER:$26.5
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 80, backOrder = 0 for DISTRIBUTOR:$40.0
Week 26: Running Total = $3813.5 [RETAILER:$26.5, WHOLESALER:$26.0, DISTRIBUTOR:$40.0, FACTORY:$117.0]
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 52, backOrder = 0 for WHOLESALER:$26.0
inOrder = 4, outOrder = 0, inBeer = 1, outBeer = 4, inventory = 50, backOrder = 0 for RETAILER:$25.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 80, backOrder = 0 for DISTRIBUTOR:$40.0
Week 27: Running Total = $4021.5 [RETAILER:$25.0, WHOLESALER:$26.0, DISTRIBUTOR:$40.0, FACTORY:$117.0]
inOrder = 3, outOrder = 3, inBeer = 0, outBeer = 3, inventory = 47, backOrder = 0 for RETAILER:$23.5
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 80, backOrder = 0 for DISTRIBUTOR:$40.0
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 52, backOrder = 0 for WHOLESALER:$26.0
Week 28: Running Total = $4228.0 [RETAILER:$23.5, WHOLESALER:$26.0, DISTRIBUTOR:$40.0, FACTORY:$117.0]
inOrder = 3, outOrder = 1, inBeer = 0, outBeer = 3, inventory = 49, backOrder = 0 for WHOLESALER:$24.5
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 6, outOrder = 9, inBeer = 0, outBeer = 6, inventory = 41, backOrder = 0 for RETAILER:$20.5
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 80, backOrder = 0 for DISTRIBUTOR:$40.0
Week 29: Running Total = $4430.0 [RETAILER:$20.5, WHOLESALER:$24.5, DISTRIBUTOR:$40.0, FACTORY:$117.0]
inOrder = 0, outOrder = 0, inBeer = 0, outBeer = 0, inventory = 234, backOrder = 0 for FACTORY:$117.0
inOrder = 5, outOrder = 11, inBeer = 3, outBeer = 5, inventory = 39, backOrder = 0 for RETAILER:$19.5
inOrder = 1, outOrder = 0, inBeer = 0, outBeer = 1, inventory = 79, backOrder = 0 for DISTRIBUTOR:$39.5
inOrder = 9, outOrder = 10, inBeer = 0, outBeer = 9, inventory = 40, backOrder = 0 for WHOLESALER:$20.0

What do you think? - other than that I should have something better to do with my evenings :)

Kondwani Mkandawire

Posts: 530
Nickname: spike
Registered: Aug, 2004

Re: Too Much Threading Posted: Sep 15, 2005 2:16 AM
Reply to this message Reply
> What do you think? - other than that I should have
> something better to do with my evenings :)

Lol! You should, no I'm just playing. The snippet
caught my attention coz of the word *beer*.

Anyways, great code - has drawn my attention to parts of
the API I never knew existed. The concurrent package
will definitely be an asset in future programming projects.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Too Much Threading Posted: Sep 15, 2005 7:03 PM
Reply to this message Reply
@Kondwani Mkandawire,

Glad you enjoyed playing the game and that you like the concurrent API. I read some more on the beer game and it should have a two week delay, the original code had a one week delay. When I fixed the delay I also found a bug in the original, compareTo in Order was wrong. The new code is below.

When reading up on the beer game I see that the suggested strategy is to simply parrot the in orders to out orders. This works better than my controller, so I added this also.

Have you found a better controller?

package beergame;
 
import java.util.*;
import java.util.concurrent.*;
import static java.lang.System.*;
import static java.lang.Math.*;
 
/**
 * MIT Beer Game simulation. Rules from:
 * <blockquote>
 * http://www.solonline.org/repository/download/instr.html?item_id=456354
 * </blockquote>
 * <p>
 * Except:
 * <ul>
 * <li>I assumed: order delay = shipping delay = production delay = 2 weeks,
 * the above site doesn't state the delays! Other sites indicate 2 weeks.
 * <li>The customer buys a random number of cases, between 1 and 10, each week.
 * The above site suggests 4 cases for 5 weeks and then 8 cases thereafter.
 * <li>Rest as suggested at above reference
 * </ul>
 * <p>
 * Note: <em>I have never played the game!</em>. Therefore my interpretation
 * of the rules may be wrong!
 *
 * @author Howard Lovatt
 */
public class Play {
    static final int maxOrder = 10; // the maximum order a customer can place
    static final int week = 100; // ms, i.e. 1 week takes 0.1 seconds to simulate
    static float runningTotal = 0F; // the total cost incurred to date
    static final ExecutorService pool = Executors.newCachedThreadPool();
    public static void main( final String[] notUsed ) throws InterruptedException {
        preLoad(); // pre-load all the queues except the customer queues (which aren't delayed) with maxOrder / 2 orders or beers
        preLoad(); // pre-load the queues with a second order/beer, the queues have a two week delay
        pool.execute( Customer.DEMAND ); // start the game
        pool.execute( Player.RETAILER );
        pool.execute( Player.WHOLESALER );
        pool.execute( Player.DISTRIBUTOR );
        pool.execute( Player.FACTORY );
        pool.execute( Production.BEER );
        Thread.sleep( 30 * week ); // game lasts *about* 30 weeks (to keep output short), but test new strategies for much longer, e.g. 200 weeks, to demonstrate stability!
        pool.shutdownNow();
    }
    private static void preLoad() throws InterruptedException { // establish the initial state
        final Order initialOrder = new Order( maxOrder / 2 );
        Queues.rWOrders.put( initialOrder );
        Queues.wDOrders.put( initialOrder );
        Queues.dFOrders.put( initialOrder );
        Production.BEER.orders.put( initialOrder );
        final Beer initialBeer = new Beer( maxOrder / 2 );
        Queues.wRBeers.put( initialBeer );
        Queues.dWBeers.put( initialBeer );
        Queues.fDBeers.put( initialBeer );
        Production.BEER.beers.put( initialBeer );
        Production.BEER.production.put( initialBeer );
        Thread.sleep( week ); // wait a week to allow orders/beers to progress in their queues
    }
    private interface Queues { // These static fields are put in an interface so that they are initalized before the static field enums in the Player enum (pain with enums!)
        BlockingQueue< Order > rWOrders = new DelayQueue< Order >();
        BlockingQueue< Order > wDOrders = new DelayQueue< Order >();
        BlockingQueue< Order > dFOrders = new DelayQueue< Order >();
        BlockingQueue< Beer > wRBeers = new DelayQueue< Beer >();
        BlockingQueue< Beer > dWBeers = new DelayQueue< Beer >();
        BlockingQueue< Beer > fDBeers = new DelayQueue< Beer >();
    }
    private static enum Player implements Runnable, Queues {
        RETAILER( Customer.DEMAND.orders, rWOrders, wRBeers, Customer.DEMAND.blackHole ), 
        WHOLESALER( rWOrders, wDOrders, dWBeers, wRBeers ), 
        DISTRIBUTOR( wDOrders, dFOrders, fDBeers, dWBeers ), 
        FACTORY( dFOrders, Production.BEER.orders, Production.BEER.beers, fDBeers );
        static final int targetInventory = 2 * maxOrder; // paramaters for controller: inventory needs to be large, e.g. 5 * maxOrder, for stability with pGain > 0 (runaway occures with back orders because you have to supply back orders *and* new orders)
        static final float pGain = 0F; // you can play with this! Best controller I have found with pGain is inGain = 0, targetInventory = 5 * maxOrder and pGain = 0.125 (but inGain controller is better). The term pGain is from control theory - this is the proportional gain of the controller relative to the inventory error (difference from traget inventory)
        static final float inGain = 1F; // you can play with this. Web sites suggest that pGain = 0, targetInventory = 2 * maxOrder, and inGain = 1 is optimal (this is the best I can find also)
        final BlockingQueue< Order > inOrders; // queues
        final BlockingQueue< Order > outOrders;
        final BlockingQueue< Beer > inBeers;
        final BlockingQueue< Beer > outBeers;
        int backOrder = 0; // start with no backlog
        int inventory = targetInventory; // start with target inventory
        Player( final BlockingQueue< Order > inOrders, final BlockingQueue< Order > outOrders, 
                final BlockingQueue< Beer > inBeers, final BlockingQueue< Beer > outBeers ) {
            this.inOrders = inOrders;
            this.outOrders = outOrders;
            this.inBeers = inBeers;
            this.outBeers = outBeers;
        }
        public void run() {
            try {
                while ( true ) {
                    final int inOrder = inOrders.take().value;
                    final int inBeer = inBeers.take().value; // get beer delivery
                    inventory += inBeer; // add to inventory
                    final int beerRequired = inOrder + backOrder;
                    final int outBeer;
                    if ( inventory >= beerRequired ) {
                        outBeer = beerRequired;
                        backOrder = 0;
                        inventory -= beerRequired;
                    } else {
                        outBeer = inventory;
                        backOrder += beerRequired - inventory;
                        inventory = 0;
                    }
                    outBeers.put( new Beer( outBeer ) );
                    final int inventoryError = targetInventory - inventory + backOrder;
                    final int outOrder = max( 0, round( controller( inOrder, inventoryError ) ) ); // integer and can't have negative orders
                    outOrders.put( new Order( outOrder ) );
                    out.println( "inOrder = " + inOrder + ", outOrder = " + outOrder + ", inBeer = " + inBeer + ", outBeer = " + outBeer + ", inventory = " + inventory + ", backOrder = " + backOrder + " for " + this);
                }
            } catch ( InterruptedException notUsed ) { /* OK to quit */ }
        }
        float controller( final int inOrder, final int error ) { // you can play with different strategies, see above
            return inGain * inOrder + pGain * error;
        }
        public String toString() { return super.toString() + ":$" + getCost(); }
        float getCost() { return backOrder + 0.5F * inventory; }
    }
    private static enum Customer implements Runnable {
        DEMAND;
        static final Random rand = new Random( 47 );
        static final BlockingQueue< Beer > blackHole = new LinkedBlockingQueue< Beer >() { // disgard beer! - output not needed in simulation
            static final long serialVersionUID = 200509150908; // just in case it is serialized
            public void put( final Beer notUsed ) { /* disgard input - this is a black hole */ }
        };
        final BlockingQueue< Order > orders = new ArrayBlockingQueue< Order >( 1 ); // use a buffer of length 1 so that this task gives way to others - ensures orderly execution
        int weekNumber = 0;
        public void run() {
            try {
                while ( true ) {
                    for ( Player player : Player.values() ) runningTotal += player.getCost(); // Output status
                    out.println( "Week " + (weekNumber++) + ": " + " Running Total = $" + runningTotal + ' ' + Arrays.toString( Player.values() ) );
                    orders.put( new Order( rand.nextInt( maxOrder ) ) ); // place a random order of up to maxOrder beers
                    Thread.sleep( week ); // place next order in a weeks time - lazy programming a scheduled executor would be better!
                }
            } catch ( InterruptedException notUsed ) { /* OK to quit */ }
        }
    }
    private static enum Production implements Runnable {
        BEER;
        final BlockingQueue< Order > orders = new DelayQueue< Order >();
        final BlockingQueue< Beer > production = new DelayQueue< Beer >(); // making beer takes a week
        final BlockingQueue< Beer > beers = new DelayQueue< Beer >();
        public void run() {
            try {
                while ( true ) {
                    final int order = orders.take().value; // get order
                    production.put( new Beer( order ) ); // make beer - it takes a week
                    final int beer = production.take().value; // beer I made earlier
                    beers.put( new Beer( beer ) ); // ship beer
                }
            } catch ( InterruptedException notUsed ) { /* OK to quit */ }
        }
    }
    private static class Order implements Delayed {
        final int value;
        final long endTime = currentTimeMillis() + 2 * week; // 2 week delay
        Order( final int value ) {
            if ( value < 0 ) {
                pool.shutdownNow(); // terminate game - numeric overflow!
                throw new IllegalArgumentException( "Negative order or beer - probably a numeric overflow");
            }
            this.value = value;
        }
        public long getDelay( final TimeUnit unit ) { return unit.convert( endTime - currentTimeMillis(), TimeUnit.MILLISECONDS ); }
        public int compareTo( final Delayed other ) {
            final Order that = (Order) other;
            final long diff = endTime - that.endTime; // note: long and result int
            if ( diff == 0 ) return 0;
            return diff > 0 ? 1 : -1;
        }
        public String toString() { return Integer.toString( value ); }
    }
    private static class Beer extends Order { // alias for Order, i.e. shipping delay = ordering delay and number of beers >= 0
        Beer( final int value ) { super( value ); }
    }
}

Chris Dailey

Posts: 56
Nickname: mouse
Registered: Dec, 2002

Re: Too Much Threading Posted: Sep 16, 2005 12:09 PM
Reply to this message Reply
Why am I thinking of the line "Too many notes" from the movie Amadeus?

John Atwood

Posts: 1
Nickname: johnatwood
Registered: Sep, 2005

Re: Too Much Threading Posted: Sep 16, 2005 7:06 PM
Reply to this message Reply
rather than invent yet another example concurrency problem, you might use the Santa Claus Problem (description from paper [1] below).

Santa Claus sleeps at the North pole until awakened by either all of the nine reindeer, or by a group of three out of ten elves. He performs one of two indivisible actions:
- If awakened by the group of reindeer, Santa harnesses them to a sleigh, delivers toys, and ¬nally unharnesses the reindeer who then go on vacation.
- If awakened by a group of elves, Santa shows them into his offce, consults with them on toy R&D, and finally shows them out so they can return to work constructing toys.

A waiting group of reindeer must be served by Santa before a waiting group of elves. Since Santa's time is extremely valuable, marshalling the reindeer or elves into a group must not be done by Santa.

paper [3] below comments:
The errors which are easy to make in an attempt to solve this problem include extra elves being able to sneak into a group once Santa has started showing elves into his office, or Santa being able to go off delivering toys whilst the reindeer are still waiting in the stable. Ben-Ari [1] points out a bug (of the second kind) in Trono’s initial semaphore-based solution, shows how the problem may be
solved fairly neatly using Ada’s concurrency primitives and compares this with a much less elegant and less efficient solution in Java.


Have you looked at JoinJava? http://joinjava.unisa.edu.au/

[1] Here's a 1997 solution ,in Java: http://citeseer.ist.psu.edu/ben-ari97how.html
[3] Here's a solution in an extension of C#, which is based on concepts somewhat similar to JoinJava: http://citeseer.ist.psu.edu/572685.html


John

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Too Much Threading Posted: Sep 19, 2005 2:25 AM
Reply to this message Reply
@John Atwood

The Santa Claus problem is another easy one for J5:
package santa;
 
import java.util.*;
import java.util.concurrent.*;
import static java.util.concurrent.TimeUnit.*;
import static java.lang.System.*;
import static java.lang.Math.*;
 
/**
 * Santa Claus Problem based on:
 * <blockQuote>
 * <a href="http://citeseer.ist.psu.edu/ben-ari97how.html">
 * Mordechai Ben-Ari, "How to solve the Santa Claus problem",
 * Concurrency: Practice and Experience, vol. 10, num. 6,
 * pages 485-496, 1998
 * </a>
 * </blockQuote>
 *
 * @author Howard Lovatt
 */
public class Main {
    private static final long year = 100; // ms, i.e. simulate 1 year in 0.1 s
    private static final ExecutorService threads = Executors.newCachedThreadPool();
    public static void main( final String[] notUsed ) throws InterruptedException {
        execute( Santas.values() ); // start threads
        execute( WaitingRooms.values() );
        execute( Elves.values() );
        execute( Reindeers.values() );
        Thread.sleep( 3 * year ); // run simulation for a fixed time
        threads.shutdownNow();
    }
    private static void execute( final Runnable[] helpers ) {
        for ( final Runnable helper : helpers ) threads.execute( helper );
    }
    private static enum Santas implements Runnable {
        THE_MAN;
        final BlockingQueue< HelperList > helperListQueue = new PriorityBlockingQueue< HelperList >(); // queue of unlimited length so that reindeers always get priority
        public void run() {
            try {
                while ( true ) {
                    final HelperList helperList = helperListQueue.take();
                    helperList.get( 0 ).santaActions( helperList ); // visitor like call! The receiver is purely for dispatching, it isn't used
                }
            } catch ( InterruptedException notUsed ) { /* OK to exit */ }
        }
    }
    private static enum WaitingRooms implements Runnable, Comparable< WaitingRooms > {
        ELVES( 3 ), REINDEERS( 9 );
        final int size;
        final BlockingQueue< Helper > helpersQueue;
        WaitingRooms( final int size ) {
            this.size = size;
            helpersQueue = new LinkedBlockingQueue< Helper >( size ); // note: queue limited in length, this will block a thread if the queue is already full
        }
        public void run() {
            try {
                while ( true ) {
                    final HelperList helpers = new HelperList( size );
                    for ( int index = 0; index < size; index++ ) { helpers.set( index, helpersQueue.take() ); } // wait untill waiting room is full
                    Santas.THE_MAN.helperListQueue.put( helpers ); // wake up Santa
                }
            } catch ( InterruptedException notUsed ) { /* OK to exit */ }
        }
    }
    private static enum Elves implements Runnable, Helper {
        ELF1, ELF2, ELF3, ELF4, ELF5, ELF6, ELF7, ELF8, ELF9, ELF10;
        public void run() { helperRun( this, WaitingRooms.ELVES.helpersQueue ); }
        public void santaActions( HelperList helpers ) { // Elves consult with Santa
            out.println( "Enter Santa's office: " + helpers );
            out.println( "Consult with Santa:   " + helpers );
            out.println( "Exit Santa's office:  " + helpers );
        }
    }
    private static enum Reindeers implements Runnable, Helper {
        REINDEER1, REINDEER2, REINDEER3, REINDEER4, REINDEER5, REINDEER6, REINDEER7, REINDEER8, REINDEER9;
        public void run() { helperRun( this, WaitingRooms.REINDEERS.helpersQueue ); }
        public void santaActions( HelperList helpers ) { // Reindeer deliver toys
            out.println( "Harnesses reindeer:   " + helpers );
            out.println( "Deliver toys:         " + helpers );
            out.println( "Unharnesses reindeer: " + helpers );
        }
    }
    private static void helperRun( final Helper helper, final BlockingQueue< Helper > waitingRoomQueue ) {
        try {
            while ( true ) {
                while ( waitingRoomQueue.contains( helper ) ) Thread.sleep( year / 10 ); // catch a scheduler that keeps scheduling the same thread to run
                waitingRoomQueue.put( helper ); // enter Santa's waiting room
                Thread.sleep( year - round( (year / 10) * random() ) ); // go to sleep until next year, minus random delay to make things interesting!
            }
        } catch ( InterruptedException notUsed ) { /* OK to exit */ }
    }
    private interface Helper { void santaActions( HelperList helpers ); } // the things Santa does with this type of helper
    private static class HelperList extends AbstractList< Helper > implements Comparable< HelperList > { // special list that implements Comparable so that it can be used in a PriorityQueue
        final int size;
        final Helper[] helpers;
        HelperList( final int size ) {
            this.size = size;
            this.helpers = new Helper[ size ];
        }
        public Helper get( final int index ) { return helpers[ index ]; }
        public Helper set( final int index, final Helper element ) {
            final Helper old = helpers[ index ];
            helpers[ index ] = element;
            return old;
        }
        public int size() { return size; }
        public int compareTo( final HelperList that ) {
            final boolean isThisElves = get( 0 ) instanceof Elves; // get dynamic type of elements
            final boolean isThatElves = that.get( 0 ) instanceof Elves;
            return isThisElves == isThatElves ? 0 : (isThisElves ? -1 : 1); // Reindeer > Elves
        }
        public boolean equals( final Object that ) { // make equals consistent with compareTo, hashCode OK
            if ( !(that instanceof HelperList) ) return false; // also catches null
            return compareTo( (HelperList)that ) == 0;
        }
    }
}

To me this codes better than either Ada or using Join Calculus.

What do you think?

Tim Peierls

Posts: 3
Nickname: tpeierls
Registered: Sep, 2005

Re: Too Much Threading Posted: Sep 24, 2005 12:24 AM
Reply to this message Reply
> It puzzles me why people writing introductory/intermediate
> Java books spend so much time on threading. ...
> I think concurrent programming is a whole different ball
> game and should be left to Books that address advanced
> programming issues.

I couldn't disagree more. The time to start learning about concurrency is when you first learn the language. Treating it as an advanced topic makes it seem optional. But it isn't optional, not even if you stick to Swing client apps.

It isn't that hard to do things right, but if you don't acknowledge that there is a right way, you will produce broken code that will appear to work just fine on one machine and then fail mysteriously (and possibly silently) on another.

The real problem is that introductory books, at least until recently, haven't presented the rules effectively and simply. So it's important that Bruce include this chapter.

Bruce Eckel

Posts: 874
Nickname: beckel
Registered: Jun, 2003

Re: Too Much Threading Posted: Sep 26, 2005 11:45 AM
Reply to this message Reply
What Tim just said.

But I think it's useful to know that one of the (many) illusions about threading is that "it's just an advanced topic that beginners can ignore." Personally, I think that even to use the threading idioms in Swing properly you have to understand what the issues are. You can't ignore threading and build robust Java programs.

That said, I suspect I'm going a bit too far in the Concurrency chapter in TIJ4; I haven't been able to throw out examples that I think are particularly illuminating, partly because I haven't seen similar examples elsewhere. But at least it's relatively "inverted pyramid", so you can read as far as you want to in the chapter and stop when the material becomes more advanced than what you need.

Flat View: This topic has 14 replies on 1 page
Topic: XML down a slippery slope Previous Topic   Next Topic Topic: The Relationship Between HeronFront and HeronScript


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us