Thread-safe state handling

In my previous post I noted that handling mutable state in multi-threaded programs is a problem that should preferably be avoided. Sometimes it may be too complicated to avoid mutate state and I will in this post look into some ways of handling it, including how the classic State design pattern can help, with a little twist. A good, if old, introduction to threading issues in Java can be found here.

Consider the following code:

public class Lamp {
  private boolean on;
  public boolean isOn() {return on;}
  public void setOn(boolean on) {this.on = on;}
}

No threading problems, right?

Wrong! I had read about it but learnt it again the hard way when one of my unit tests started failing spuriously. I could tell from other measuring points that there was no way that assert could fail, yet it did, sometimes. The issue is that, especially on a multi-core machine, there is no guarantee that other threads will ever get to see changes. To guarantee that, either the same synchronization monitor must be used for both reads and writes, or the variable needs to be volatile.

With that lesson in mind, let's look at another example:

public class WaterDispenser {
  private volatile int water;
  public void fill(int amount) { water += amount; }
  public void get(int amount) throws InsufficientWaterException {
    if (water >= amount) water -= amount;
    else throw new InsufficientWaterException();
  }
}

Unfortunately, += and -= are not atomic operations so two threads filling up at the same time may result in only the one fill being effective. Also there is a gap between the check and the decrement so the class may end up in an invalid state if two threads get water at the same time.

It is always an option just to synchronize the methods and it may well be the best option in this case. It is when you have frequently used methods that just query the state that you want to avoid synchronization because it will give an overhead on every query.

Just for illustration, let's use an AtomicInteger here, which has the same memory consistency guarantees as volatile and a bit of extra functionality. The addition in fill is now atomic, but in the get we also check that we have enough water so it's not good enough to just do an atomic subtraction after the check since that precondition may not be valid when we get to the subtraction, we have to atomically check that the value didn't change with a compareAndSet or redo.

public class WaterDispenser {
private AtomicInteger water;
public void fill(int amount) { water.addAndGet(amount); }
public void get(int amount) throws InsufficientWaterException {
  int currentWater;
  int nextWater;
  do {
    currentWater = water.get();
    nextWater = currentWater - amount;
    if (nextWater < 0) throw new InsufficientWaterException();
  } while (!water.compareAndSet(currentWater, nextWater));
}

It becomes more and more complex to analyze and avoid race conditions the more you need to do, consider for example extending the WaterDispenser to become a CoffeeMachine, when you have to use coffee beans as well as water.

The State pattern is used to make it easier to analyze and express state-dependent behaviour. Not surprisingly, I suppose, it can also be used to simplify concurrent state-handling, although perhaps with a stricter interpretation of "state-dependent behaviour".

public class CoffeeMachine {
  private AtomicReference<CoffeeMachineState> state = new AtomicReference<CoffeeMachineState>(new CoffeeMachineState(0,0));

  public void fillBeans(int beans) {
    state.get().fillBeans(beans);
  }
  public void fillWater(int water) {
    state.get().fillWater(water);
  }
  public Coffee makeCoffee(int water, int beans) throws OutOfWaterException, OutOfBeansException {
    return state.get().makeCoffee();
  }

  private class CoffeeMachineState {
    private final int water;
    private final int beans;
    CoffeeMachineState(w, b) {
      water = w;
      beans = b;
    }
    void fillBeans(int moreBeans) {
      if (!state.compareAndSet(this, new CoffeeMachineState(water, beans+moreBeans)) {
        state.get().fillBeans(moreBeans);
      }
    }
    void fillWater(int moreWater) {
      if (!state.compareAndSet(this, new CoffeeMachineState(water+moreWater, beans)) {
        state.get().fillWater(moreWater);
      }
    }
    Coffee makeCoffee(int w, int b) throws OutOfWaterException, OutOfBeansException {
      if (water < w) throw new OutOfWaterException();
      if (beans < b) throw new OutOfBeansException();
      if (!state.compareAndSet(this, new CoffeeMachineState(water-w, beans-b)) {
        return state.get().makeCoffee(w,b);
      }
      return new Coffee(w,b);
    }
  }
}

Again it would probably be better to just sychronize the methods in this case, but it serves to illustrate the pattern: delegate calls to the current state, which either manages to change the state or delegates to the new state if another thread got in first.

Back to the lamp example, which is a classic for the state pattern, but we'll add some functionality. The lamp is placed in a room and when we turn it on we should illuminate the room and when we turn it off we should darken the room. Now we have a gap between the state change and the room operation, a gap where another thread can come in and wreak havoc. The solution is to introduce a transitional state that holds other threads at bay while you complete the transition.

class Lamp {
 private AtomicReference<Lamp> state = new AtomicReference<Lamp>(new Off());
 private final Room room;
 public Lamp(Room room) {this.room = room;}
 public boolean isOn() {return state.get().isOn();}
 public void setOn(boolean on) {state.get().setOn(on);}

 private class On extends Lamp {
   public boolean isOn() {return true;}
   public void setOn(boolean on) {
     if (on) return;
     synchronized (Lamp.this) {
       TransitionGuard guard = new TransitionGuard();
       if (state.compareAndSet(this, guard) {
         room.darken();
         state.set(new Off());
       } else {
         state.get().setOn(on);
       }
     }
   }
 }

 private class Off extends Lamp {
   public boolean isOn() {return false;}
   public void setOn(boolean on) {
     if (!on) return;
     synchronized (Lamp.this) {
       TransitionGuard guard = new TransitionGuard();
       if (state.compareAndSet(this, guard) {
         room.illuminate();
         state.set(new On());
       } else {
         state.get().setOn(on);
       }
     }
   }
 }

  private class TransitionGuard extends Lamp {
    public boolean isOn() {
      synchronized (Lamp.this) {
        return state.get().isOn();
      }
    }
    public void setOn(boolean on) {
      synchronized (Lamp.this) {
        state.get().setOn(on);
      }
    }
  }    
}

Synchronizing would be easier, but with this pattern we only pay the synchronization cost during complex state transitions, although we do get a certain cost for object creations, but this is generally very low.

One final word of caution: if using an object involves querying more than one of its stateful values, that is also a potential race and you should consider returning an immutable object representing a snapshot of all the queryable state instead.