When a data (typically a variable) can be accessed by several threads, you must synchronize the access to the data to ensure visibility and correctness.
By example, if you have a simple counter (yes, once again) :
public class Counter {
private int value;
public int getValue(){
return value;
}
public int getNextValue(){
return value++;
}
public int getPreviousValue(){
return value--;
}
}
This class works really well in single-threaded environment, but don't work at all when several threads access the same Counter instance. If you don't know why, read this post about synchronization. You can solve the problem using synchronized at method level :
public class SynchronizedCounter {
private int value;
public synchronized int getValue(){
return value;
}
public synchronized int getNextValue(){
return value++;
}
public synchronized int getPreviousValue(){
return value--;
}
}
This class now works well. But locking is not a lightweight mechanism and have several disadvantages. When several threads try to acquire the same lock, one or more threads will be suspended and they will be resumed later. When the critical section is little, the overhead is really heavy especially when the lock is often acquired and there is a lot of contention. Another disadvantage is that the other threads waiting of the lock cannot do something else during waiting and if the thread who has the lock is delayed (due to a page fault or the end of the time quanta by example), the others threads cannot take their turn.
So how to do to avoid this disadvantages ? We must use non-blocking algorithms. This algorithms don't use blocking mechanisms and by that fact are more scalable and performing. These algorithms use low-level machine instructions which are atomic to ensure the atomicity of higher-level operations. While locking is a pessimistic approach, we can also use optimistic technique to develop algorithms. This time, we'll detect collisions between threads in which case, the operation fails and we do something else (often retrying the same operation).
The actual processors provide several instructions that simplify greatly the implementation of these non-blocking algorithms, the most-used operation today is the compare-and-swap operation (CAS). This operation takes three parameters, the memory address, the expected current value and the new value. It atomically update the value at the given memory address if the current value is the expected, otherwise it do nothing. In both cases, the operation return the value at the address after the operation execution. So when several threads try to execute the CAS operation, one thread wins and the others do nothing. So the caller can choose to retry or to do something else. We often use this operation to implement another operation, the compare-and-set. This method makes exactly the same things as CAS but return a boolean indicating if the operation succeeded or not.
Before Java 5.0, this operation was not available directly to developer, but in Java 5.0 several atomic variables (for int, long, boolean and reference values) were added. The int and long versions also supports numeric operations. The JVM compiles these classes with the better operations provided by the hardware machine, CAS or a Java implementation of the operation using a lock. Here are the classes :
- AtomicInteger
- AtomicLong
- AtomicBoolean
- AtomicReference
All these classes supports compare-and-set (via the compareAndSet() method) and other operations (get(), set() and getAndSet()). The setters operations are implemented using compareAndSet. These classes supports multi-threaded access and have a better scalability than synchronizing all the operations.
Here is how we can rewrite our counter using an AtomicInteger :
public class AtomicCounter {
private final AtomicInteger value = new AtomicInteger(0);
public int getValue(){
return value.get();
}
public int getNextValue(){
return value.incrementAndGet();
}
public int getPreviousValue(){
return value.decrementAndGet();
}
}
The incrementAndGet() and decrementAndGet() methods are two of the numeric operations provided by the AtomicLong and AtomicInteger classes. You also have getAndDecrement(), getAndIncrement(), getAndAdd(int i) and addAndGet().
This version is faster than the synchronized one and is also thread safe.
If you only have the compareAndSet(), here is how we can implement increment() method using it :
public void increment(AtomicInteger integer){
while(true){
int current = integer.get();
int next = current + 1;
if(integer.compareAndSet(current, next)){
return;
}
}
}
This seems to be complicated, but this is the cost of non-blocking algorithms. When we detect collision, we retry until the operation succeeded. This is the common schema for non-blocking algorithms.
Here is a thread-safe Stack implemented using AtomicReference :
public class Stack {
private final AtomicReference<Element> head = new AtomicReference<Element>(null);
public void push(String value){
Element newElement = new Element(value);
while(true){
Element oldHead = head.get();
newElement.next = oldHead;
//Trying to set the new element as the head
if(head.compareAndSet(oldHead, newElement)){
return;
}
}
}
public String pop(){
while(true){
Element oldHead = head.get();
//The stack is empty
if(oldHead == null){
return null;
}
Element newHead = oldHead.next;
//Trying to set the new element as the head
if(head.compareAndSet(oldHead, newHead)){
return oldHead.value;
}
}
}
private static final class Element {
private final String value;
private Element next;
private Element(String value) {
this.value = value;
}
}
}
It's really more complicated than using synchronized on the two methods but also more performing if there is contention (and often even if there is no contention).
So this ends this post. To conclude, atomic variables classes are a really good way to implement non-blocking algorithms and moreover are also a very good alternative to volatile variables, because they can provide atomicity and visibility.
