Using Lock free algorithms

In this article we will look into Atomic Variables which can help us to write lock free and wait free algorithms which were not possible prior to Java 5.0.

Two main points about Atomic Variables are:

Help to write lock free and wait free algorithm

Under high contention ( lots of thread are fighting for lock ), JVM spends more time with scheduling of threads, managing contention, queues of waiting threads and less time in doing the real work.
This dramatically reduces the throughput of the process.
Problem with locking:
-Thread in block state cannot do anything else.
-If the blocked thread is high priority, then its a big disaster.
-Can cause Dead lock
-Managing a Block thread is a heavy weight process, so throughput decreases.

Soon we will see how can we write lock free algorithms using atomic variables.

Implement very light weight process like CAS

CAS is compares and swap. Let’s take an example to understand the concept of CAS. Suppose we have once variable “i” and we are doing some calculation over “I” and storing the result back into “i”. In a nutshell-
        i = someComplicateComputation( i )
for “i” = 1,
        someComplicatedComputation(i) è 1234

In CAS Process following happens-
        A memory location V will be defined.
        A local variable A will be defined.
        A local variable B will be defined.

V will hold the initial value of “i”. So
V = i =1
A = V = 1
B = result of that computation = 1234
compare ( V , A )
if
         both values are same --> replace V with B's value.
else
        this means in the mean while someone has changed the value of V, so repeat the whole process again. Lets someone changes the value of “i”, hence V to 2.
       
             V = 2;
             A = V = 2
             B = result = 3246;
              compare ( V , A )
                        and so on...!!
       
This is very light weight process. This CAS technique is implemented by atomic package classes.

Example – Lets write a simple program which first increase the number by 1, then decrease the number by 1, and then increase again by 1. So overall effect is increase the number by 1. Lets run 4 threads concurrently access the method and compare the performance of AtomicInteger Vs Integer.

package com.vaani.threads.atomic;

import java.util.concurrent.atomic.*;
public class AtomicVariableExample implements Runnable {
    AtomicInteger atomic_int_1 = new AtomicInteger();
    AtomicInteger atomic_int_2 = new AtomicInteger();
    int int_1;
    int int_2;
    private static int count = 0;


    public static void main(String[] args) {
        AtomicVariableExample pr = new AtomicVariableExample();
        new Thread(pr).start();// 1 0 1
        new Thread(pr).start();// 2 1 2
        new Thread(pr).start(); // 3 2 3
        new Thread(pr).start(); // 4 3 4
        while (true) {
            if (count == 4) {
                System.out.println(pr.atomic_int_1.get());
                System.out.println(pr.int_1);
                break;
            }


        }
    }



    public void run() {
        System.out.println("Inside run method...");
        doCalc();

    }

    private void doCalc() {
        try {
            atomic_int_2 = atomic_int_1;
            int_2 = int_1;
            atomic_int_2.incrementAndGet();
            int_2 = int_2 + 1;
            Thread.sleep(1000);
            atomic_int_2.decrementAndGet();
            int_2 = int_2-1;
            Thread.sleep(1000);
            atomic_int_2.incrementAndGet();
            int_2 = int_2 + 1;
            Thread.sleep(1000);
            atomic_int_1 = atomic_int_2;
            int_1 = int_2;
            synchronized (this) {
                count++;
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

}

Atomic variables

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. We discussed about atomic operations in java earlier.
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.

Atomic operations

An atomic operation is an operation which is performed as a single unit of work without the possibility of interference from other operations.
In Java the language specification guarantees that that reading or writing a variable is atomic (unless the variable is of type long or double). Long and double are only atomic if they declared as volatile.
The operation i++ it not atomic in Java for the standard variables (int, long, etc).
Here i++ is not a single instructions its basically 3 instructions :
i.) Read i
ii.) Increment i
iii.) Set i
These 3 instructions may not happen atomically.

It first reads the value which is currently stored in i (atomic operations) and then it adds one to it (atomic operation). But between the read and the write the value of i might have changed. Java

Since Java 1.5 the java language provides atomic variables, e.g. AtomicInteger or AtomicLong which provide methods like getAndDecrement(), getAndIncrement() and getAndSet() which are atomic.

How to synchronize a static variable of a class ?

There are some ways(3 to my knowledge, but may be more), by which a static variable can be synchronized in java.

1) Use a synchronized static method. This synchronizes on the class object.

public class Counter {
    private static int count = 0;

    public static synchronized void incrementCount() {
        count++;
    }
} 

2) Explicitly synchronize on the class object, using synchronize on ClassName.class

public class Counter {
    private static int count = 0;

    public void incrementCount() {
        synchronize (Test.class) {
            count++;
        }
    }
} 

3) Synchronize on some other static object.

public class Counter {
    private static int count = 0;
    private static final Object countLockHelper = new Object();

    public void incrementCount() {
        synchronize (countLockHelper) {
            count++;
        }
    }
} 

Method 3 is best in many cases because the lock object is not exposed outside of your class. So if you create instance of these class, they will be synchronized on the same static object.

But if you just using some basic type like integer here in case of counter, consider using an AtomicInteger or another suitable class from the java.util.concurrent.atomic package:

public class Counter {

    private final static AtomicInteger count = new AtomicInteger(0); 

    public void incrementCount() {  
        count.incrementAndGet();
    }  
}