Race condition never occurs in a thread-safe program. What is a race condition? When variables are shared by multiple threads, there is a possibility that more than one thread get access to a variable and try to modify its value at the same time. This could lead to a loss of data modification done by a thread and leave the program in an inconsitent state. Such hazards should be avoided by allowing only one thread to access the shared variables when they are being modified. Synchronized methods and synchronized blocks are used to lock an object so that only one thread can access the object’s state and other threads keep waiting for the access until the lock is released.
Java SE 5 has introduced a package java.util.concurrent.atomic which offers lock-free and thread-safe classes. Variables of these class types are called as atomic variables. There are 12 classes within this package. The operations provided by these classes are not only atomic but also volatile. The modifications done to atomic variables by a thread are immediately visible to other threads.
If you need to implement an integer counter in your class as shown in Listing 1 then you can use atomic variables instead of implementing the synchronized methods.
private int count;
public int getCount() {
return count;
}
public synchronized void increment() {
count++;
}
public synchronized void decrement() {
count--;
}
Listing 1. An integer counter
The above counter can be implemented using java.util.concurrent.atomic.AtomicInteger as shown in Listing 2.
private AtomicInteger count = new AtomicInteger(); //initial value is 0
public int getCount() {
return count.get();
}
public void increment() {
count.incrementAndGet();
}
public void decrement() {
count.decrementAndGet();
}
Listing 2. Counter using AtomicInteger
If the piece of code in Listing 1 is just a part of your class or you put this code in a separate class, then the thread executing the increment() or decrement() methods would lock the entire object (instance of your class), thus preventing other threads from accessing the object, leading to thread contention. This way of obtaining exclusive lock by a thread is a pessimistic approach. A high-priority thread can keep waiting to obtain a lock on the object’s monitor, if another thread has locked it, leading to priority inversion. This is a disadvantage of locking.
Compare and Swap (CAS)
Most processors provide a compare-and-swap (CAS) instruction. The CMPXCHG instruction is used in Intel processors to perform CAS. In some processors such as PowerPC, CAS is achieved by load-linked and store-conditional instructions. A CAS is an atomic read-modify-write instruction which checks a memory location for a value and when found replaces it with a new value. Irrespective of whether the value is changed or not, it returns the value in the memory location. The CAS performance of processors will keep increasing in the coming years.
When atomic variables are used, the JVM calls these native compare-and-swap or load-linked/store-conditional instructions of the hardware processor. These classes provide a method compareAndSet(oldValue,newValue).
An alternative way to write the increment() method of Listing 2 using compareAndSet() is given in Listing 3. When multiple threads attempt to update the count only one thread succeeds but the other threads are not blocked. They can retry updating the count. This is an optimistic approach. Such algorithms are called as lock-free because there is no lock obtained by a thread. This is also a nonblocking algorithm since the suspension or failure of one thread does not cause suspension or failure of other thread.
public void increment() {
boolean valueChanged = false;
while(!valueChanged) {
int currentVal = count.get();
int nextVal = currentVal + 1;
if(count.compareAndSet(currentVal,nextVal)) {
valueChanged = true;
}
}
}
Listing 3. Non-blocking CAS approach
In non-blocking CAS approach, the program takes care of contention by retrying. In cases of extreme contention, this non-blocking CAS approach can lead to a livelock. However, non-blocking CAS-based counters using atomic variables have better performance than lock-based counters in low to moderate contention.
When locking is used as in Listing 1, the JVM needs to interact with the operating system to perform thread suspension, context switches and locking. The code in Listing 2 may appear complex but it is executed faster by the JVM since the instructions of the processor are directly used.
AtomicInteger and AtomicLong
The java.util.concurrent.atomic.AtomicInteger and java.util.concurrent.atomic.AtomicLong extend java.lang.Number. They wrap the primitive int and long value respectively. The following methods are provided by these classes:
-
get()– Returns the current value -
set(value)– Sets the given value -
getAndSet(newValue)– Set the new value and return old value -
incrementAndGet()– Increments the value by 1 and returns the new value -
decrementAndGet()– Decrements the value by 1 and returns the new value -
getAndIncrement()– Increments the value by 1 and returns the old value -
getAndDecrement()– Decrements the value by 1 and returns the old value -
addAndGet(value)– Adds the given value to the current value and returns the updated value -
getAndAdd(value)- Adds the given value to the current value and returns the previous value
Unlike java.lang.Integer and java.lang.Long, AtomicInteger and AtomicLong are mutable and hence should not be used as a key in hash based collections.
In my last blog post, I had written about the cache implementation to store the frequently searched programs. One strategy to implement a fixed size cache is to maintain the search frequency of a program in a counter and when the cache size exceeds the maximum allowed size, the programs with least search frequency can be removed from the cache. The ProgramSearchResult class show in Listing 4, encapsulates the program and the search counter.
public class ProgramSearchResult {
private Program program;
private AtomicLong count = new AtomicLong(); //initial value 0
public Program getProgram() {
return program;
}
public void setProgram(Progam program) {
this.program = program;
}
public long getCount() {
return count.get();
}
public void setCount(long value) {
count.set(value);
}
public void incrementCount() {
count.incrementAndGet();
}
}
Listing 4. Class to store searched program and the search count
I will be writing more about the above cache implementation in my next blog post.
