Java Concurrency Bugs #3 – atomic + atomic != atomic

4

Background: Poll#1#2

This installment of Java concurrency bugs is a simple thing but one that still shows up too frequently, particularly in those new to concurrency. It is tempting to believe that given a “thread-safe” class that you can use that correctly in all situations. This is not true. The problem is that composing two atomic thread-safe operations seems safe, but has several potential pitfalls.

The most obvious pitfall is assuming that performing two (or more) atomic operations yields a new atomic operation, which is definitely not the case. For example, consider this operation on a Hashtable (in which all methods are synchronized and thread-safe):

/**
* If the key already exists, get its value. Otherwise add the key-value pair.
*/
public Object putIfAbsent(Hashtable table, Object key, Object value) {
if(table.containsKey(key)) {
// already present, return existing value
return table.get(key);
} else {
// doesn’t exist, create and return new value
table.put(key, value);
return value;
}
}

Since the Hashtable is thread-safe, this method is thread-safe too right? Well, kind of. It’s not going to cause visibility problems in the table or deadlocks. But there is a race condition here if multiple threads are executing putIfAbsent(). After the first if check, it’s possible for anything to happen. Another thread could remove the key from the table or add the key to the table, invalidating the result of the if check. Similarly, after the put call, another thread could similarly add, remove, or modify the entry, thus causing this thread to return a wrong value.

To fix this code, you must either participate in the same lock that governs the existing atomic operations OR wrap those calls in a new layer of locking. I picked Hashtable quite intentionally as it locks on its instance, allowing external users to participate in the same lock used internally:

public Object putIfAbsent(Hashtable table, Object key, Object value) {
synchronized(table) {
if(table.containsKey(key)) {
// already present, return existing value
return table.get(key);
} else {
// doesn’t exist, create and return new value
table.put(key, value);
return value;
}
}
}

Or you could encapsulate access to this Hashtable in a full wrapper object that completely hides the Hashtable and provides a single composite putIfAbsent. In the case of a Map that didn’t use itself as the internal lock object, this would be your only choice. In a wrapper object, it would not suffice to just lock this one method in a new lock; you need to lock ALL operations in the new lock to properly synchronize individual get(), put(), remove(), etc calls against the putIfAbsent() call.

The ConcurrentMap interface added in JDK 1.5 defines composite operations so they can be implemented efficiently. For example, the ConcurrentHashMap implementation can efficiently implement this internally as it would be a performance disaster to implement it in a wrapper.

Another perhaps simpler example of this can be seen with volatiles. A simple volatile counter will appear to be safe to those first encountering concurrency:

// This is broken!
public class VolatileCounter {
private volatile int count;

public int next() {
return count++;
}
}

The key here is that “count++” is not one atomic operation; it’s three operations. Read – Increment – Write. And the Read and Write parts are atomic but composing these three operations together does not yield an atomic composite. You really need to protect this counter with some form of synchronization or other mechanism of performing this increment atomically.

One good option in Java is the AtomicInteger (and its cousins) that let you perform this operation safely (and likely more cheaply) than with synchronization:

public class AtomicCounter {
private AtomicInteger count = new AtomicInteger();

public int next() {
return count.incrementAndGet();
}
}

Here we see how AtomicInteger defines a new method incrementAndGet() that is a safe (fast) composite operation of two otherwise atomic operations. But this happens only be merging them in an encapsulation, not by calling separate increment() and get() operations.

This seems like a simple thing but when it occurs in a bug it’s usually far more subtle. This problem with composing concurrent code based on locks is one of the biggest issues with producing reusable concurrent code and of composing large systems in Java.

Comments

4 Responses to “Java Concurrency Bugs #3 – atomic + atomic != atomic”
  1. Even worse, the following is not atomic either:

    private long value;
    // later…
    value = 64;

    Because longs are 64 bit, if you run this on a 32-bit chip then the assignment can happen as two separate 32 bit operations. To fix this you need to make the field volatile.

  2. Hi Alex,

    nice and useful ‘Trap-Collection’ – enjoyed reading so far!

    When i first read the title of this post, i thought you’ll speak about having two or more atomic fields which are related to each other in the sense that they participate within a ‘combined’ invariant.
    As pointed out in Goetz’ brilliant Book, of course you also have to make all operations atomic that will manipulate both of those atomic fields in order to hold the invariant.

    I think you will elaborate on that specific topic on a further post … :o)

    Greetings

    Mario

  3. Raoul Duke says:

    “issues with producing reusable concurrent code and of composing large systems in Java”

    here’s hoping somebody comes up with a viable alternative some day (e.g. STM).

  4. Alex says:

    @Neil: Yep, thanks for another good point to keep in mind.

    @Mario: That does sound like another good topic! In some ways, it’s the same point I’m making here, although more at the data level than at the method level. Thanks for the thought.

    @Raoul: STM is one option (although that brings its own set of questions). The model used in Clojure is the most useful implementation of it that I’ve seen – you can mostly rely on functional programming and immutability but drop into mutable refs and an STM when needed. Actor concurrency is another model getting some play lately (Erlang, Scala, etc). And I think some of the CCR, F#, and other stuff coming out of Microsoft is really interesting as well.