Monday, March 17, 2008

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+moreWater, beans)) {
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.

9 comments:

Thomas Edwin Santosa said...

your code is hard to read

tobe said...

Thanks, Thomas, do you have a suggestion for how it could be clearer?

aberrant said...

I think maybe Thomas might be unhappy with the code being cut off by your page theme. Also lot of people are used to looking at code with blank lines between methods. And your one line method implementations are not what people tend to see in the average blog code snippet. Please understand I'm not putting you down for your style, just trying to make it more blog friendly. I tend to use Eclipse auto-format on my code before posting it. If only just to get it in some format others are used to seeing.

On the actual topic, if the boolean was volatile in your first example there would be no issue right? Volatile guarantees that all threads will see the same value.

Thomas Edwin Santosa said...

Hi. Sorry for not being clear. Yes, the hard part is the right margin.

tobe said...

Thanks, guys. Yes, aberrant, a volatile solves it.

Janne said...

Thanks for the interesting blog entry. In the last example I'm left wondering: do we really need the AtomicReference, or would a plain volatile Lamp-reference be enough? All the code dealing with changing the reference and checking it is synchronized already with Lamp.this.

tobe said...

Janne, first I was thinking you are right, but on second thoughts I don't think so. Consider two threads hitting the synchronized block at the same time. One will go in and change the state while the other will be waiting to get a lock, but when it gets the lock the code it is about to execute is no longer valid because the previous thread changed the state.

Janne said...

Hmm, I still think this would work without atomic reference. First, change this:

private AtomicReference<Lamp> state = new AtomicReference<Lamp>(new Off());

to this:

private volatile Lamp state = new Off();

Then change this line from On and Off-states:

if (state.compareAndSet(this, guard) {

to these two lines:

if (state == this) {
state = guard;

Both of these replacements are still synchronized with Lamp.this

The argument: "One will go in and change the state while the other will be waiting to get a lock, but when it gets the lock the code it is about to execute is no longer valid because the previous thread changed the state." IMHO is wrong because we have the same check whether the current object is itself the state.

What do you think?

tobe said...

Janne, I see what you mean. The lines:

if (state == this) {
state = guard;

require that all state changes happen under synchronization of the same monitor, which happens to be true in my given example, so you are right.

However, I really wanted to avoid synchronization and put it in as a trick in only those transitions needing a guard, just to be able to put other threads in a waiting state. I have discovered a better way now:
private class TransitionGuard extends Lamp {
CountDownLatch latch = new CountDownLatch(1);
public boolean isOn() {
latch.await();
return state.get().isOn();
}
public void setOn(boolean on) {
latch.await();
state.get().setOn(on);
}
}
and then you just countDown the latch at the end of the transition, no synchronization required.