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();
        }
    }

}