Non-Blocking Algorithms

An algorithm is said to be Non-Blocking, if a failure or suspension of any thread cannot cause failure or suspension of another thread. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress.

Why do we need Non-Blocking Algorithms?

When more than one thread working on same data, we need to synchronize the access to the shared data between threads. What I mean is, provide shared data access to at most one thread at any point of time. In addition to atomic access, the changes done by one thread must be visible to other threads. In simple terms, application should maintain following two properties.

a.   Atomicity

b.   Visibility

What is atomicity?

Only one thread can able to access the shared resources at a time. You can achieve this by using synchronization.

What is Visibility?

Shared data updated by one thread is available to other thread when it enters a synchronized block protected by that same monitor (lock).

The traditional approach to maintain above two properties is achieved by using Synchronization. In synchronization, if any thread attempts to acquire a lock that is already held by another thread, the thread will block until the lock is free. While the thread is in blocking state, it don’t perform any useful task, it stays idle, which is not acceptable in all situations.

Disadvantages of Lock Based Approach

a.   Contention: If one thread holds the lock on a resource, then all the other threads that requested for this resource are blocked. If one of the threads holding a lock dies, stalls, blocks, or enters an infinite loop, other threads waiting for the lock may wait forever.

b.   Race Condition: When writing multi-threaded applications, one of the most common problems experienced are race conditions. A race condition occurs when two or more threads can access shared data and they try to change it at the same time.

For Example, Assume two threads T1, T2 tries to update a counter. Assume counter has value 10, initially. Ideally, programmer assumption is that the operations should execute in following sequence.

Thread1	Thread2	Counter Value
		10
Read Counter Value		10
Increment Counter Value by 1		10
Write Back the value		11
	Read Counter Value	11
	Increment Counter Value by 1	11
	Write Back the value	12

If you don’t synchronize the operations correctly, the outcome of the sequence can be wrong. For example, the outcome can be 11, in following sequence.

Thread1	Thread2	Counter Value
		10
Read Counter Value		10
	Read Counter Value	10
Increment Counter Value by 1		10
	Increment Counter Value by 1	10
Write Back the value		11
	Write Back the value	11

c.   Debugging is nightmare: It is very difficult to reproduce the issue in synchronized environment.

d.   Scheduling Overhead: If multiple threads blocked for a resource. Whenever the resource is released, there is a selection overhead required while allocating the resource to one of these threads.

e.   Priority Inversion: A Low-priority thread holding a lock can prevent high-priority threads from proceeding.

f.    Convoying: All other threads have to wait if a thread holding a lock is descheduled due to a time-slice interrupt or page fault.

g.   DeadLock: Incorrect designs can leads to deadlock.

Unlike blocking algorithms, Non-Blocking algorithms don’t suffer from above disadvantages. Many researches claiming that, non-blocking algorithms are efficient than lock based algorithms.

Most of the Non-Blocking algorithms use Compare-and-Swap (CAP) approach to achieve synchronization.

CAP (Compare And Swap)

CAP is an atomic instruction used in multi-threading to achieve synchronization. It compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value. If the value of the variable is updated by another thread in mean time, same procedure is repeated using the updated value, until the operation succeed.

Let’s see an example of incrementing counter, using synchronization first. Later example shows CAP version of the counter.

Counter.java

public class Counter {
 private int value;
 
 public Counter(int value){
  this.value = value;
 }

 public synchronized int getValue() {
  return value;
 }

 public synchronized int increment() {
  return ++value;
 }

 public synchronized int decrement() {
  return --value;
 }
}

You can ask me why the getValue() method is synchronized, it is because, synchronization ensures that the thread accessing the variable value, can see the most updated value.

Now let’s implement the same counter application using CAS approach. Following steps summarize the CAS procedure.

Step 1: Read current value of counter at location ‘V’ and temporarily save it in oldValue.

Step 2: Apply whatever the operations you want to perform on oldValue, compute the new updated value, save it in newValue.

Step 3: Atomically update the location ’V’ to the newValue if the current value at location ‘V’ is matches to oldValue. If the oldValue is not matches to the current value, repeat the steps 1 to 3. If the oldValue matches to the current value at the location ‘V’, then atomically update the oldValue to newValue.

public class CASAtomicUpdate {
 private int value;

 public synchronized int getValue() {
  return value;
 }

 public synchronized boolean casAtomicUpdate(int expectedValue, int newValue) {

  if (value == expectedValue) {
   System.out.println(Thread.currentThread().getName() + " Updated the value to " + newValue);
   value = newValue;
   return true;
  }
  return false;
 }
}

class WorkerThread implements Runnable {
 private CASAtomicUpdate atomicUpdate;

 WorkerThread(CASAtomicUpdate atomicUpdate) {
  this.atomicUpdate = atomicUpdate;
 }

 public void run() {
  try {
   Thread.sleep(1000);
   Thread t1 = Thread.currentThread();

   int oldValue, newValue;

   do {
    oldValue = atomicUpdate.getValue();
    newValue = oldValue + 1;
    System.out
      .println(t1.getName() + " is trying to update the value from " + oldValue + " to " + newValue);
   } while (!atomicUpdate.casAtomicUpdate(oldValue, newValue));

  } catch (Exception e) {
   System.out.println(e);
  }
 }
}

import java.util.concurrent.ExecutorService;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

public class CASAtomicUpdateTest {
 public static void main(String args[]) throws InterruptedException {
  CASAtomicUpdate atomicCounter = new CASAtomicUpdate();
  ExecutorService exec = new ThreadPoolExecutor(10, 10, 0L, TimeUnit.MILLISECONDS,
    new LinkedBlockingQueue<Runnable>());

  WorkerThread tasks[] = new WorkerThread[10];

  for (int i = 0; i < 10; i++) {
   tasks[i] = new WorkerThread(atomicCounter);
   exec.execute(tasks[i]);
  }

 }
}

Sample output

pool-1-thread-2 is trying to update the value from 0 to 1
pool-1-thread-6 is trying to update the value from 0 to 1
pool-1-thread-2 Updated the value to 1
pool-1-thread-8 is trying to update the value from 0 to 1
pool-1-thread-8 is trying to update the value from 1 to 2
pool-1-thread-9 is trying to update the value from 1 to 2
pool-1-thread-7 is trying to update the value from 0 to 1
pool-1-thread-5 is trying to update the value from 0 to 1
pool-1-thread-4 is trying to update the value from 0 to 1
pool-1-thread-1 is trying to update the value from 0 to 1
pool-1-thread-3 is trying to update the value from 0 to 1
pool-1-thread-8 Updated the value to 2
pool-1-thread-10 is trying to update the value from 1 to 2
pool-1-thread-9 is trying to update the value from 2 to 3
pool-1-thread-6 is trying to update the value from 1 to 2
pool-1-thread-9 Updated the value to 3
pool-1-thread-10 is trying to update the value from 2 to 3
pool-1-thread-7 is trying to update the value from 2 to 3
pool-1-thread-5 is trying to update the value from 2 to 3
pool-1-thread-1 is trying to update the value from 2 to 3
pool-1-thread-4 is trying to update the value from 2 to 3
pool-1-thread-3 is trying to update the value from 2 to 3
pool-1-thread-4 is trying to update the value from 3 to 4
pool-1-thread-1 is trying to update the value from 3 to 4
pool-1-thread-5 is trying to update the value from 3 to 4
pool-1-thread-7 is trying to update the value from 3 to 4
pool-1-thread-10 is trying to update the value from 3 to 4
pool-1-thread-6 is trying to update the value from 3 to 4
pool-1-thread-4 Updated the value to 4
pool-1-thread-3 is trying to update the value from 3 to 4
pool-1-thread-5 is trying to update the value from 4 to 5
pool-1-thread-7 is trying to update the value from 4 to 5
pool-1-thread-10 is trying to update the value from 4 to 5
pool-1-thread-6 is trying to update the value from 4 to 5
pool-1-thread-5 Updated the value to 5
pool-1-thread-1 is trying to update the value from 4 to 5
pool-1-thread-7 is trying to update the value from 5 to 6
pool-1-thread-3 is trying to update the value from 4 to 5
pool-1-thread-7 Updated the value to 6
pool-1-thread-1 is trying to update the value from 5 to 6
pool-1-thread-10 is trying to update the value from 5 to 6
pool-1-thread-6 is trying to update the value from 5 to 6
pool-1-thread-10 is trying to update the value from 6 to 7
pool-1-thread-1 is trying to update the value from 6 to 7
pool-1-thread-3 is trying to update the value from 6 to 7
pool-1-thread-10 Updated the value to 7
pool-1-thread-6 is trying to update the value from 6 to 7
pool-1-thread-3 is trying to update the value from 7 to 8
pool-1-thread-1 is trying to update the value from 7 to 8
pool-1-thread-3 Updated the value to 8
pool-1-thread-6 is trying to update the value from 7 to 8
pool-1-thread-1 is trying to update the value from 8 to 9
pool-1-thread-6 is trying to update the value from 8 to 9
pool-1-thread-1 Updated the value to 9
pool-1-thread-6 is trying to update the value from 9 to 10
pool-1-thread-6 Updated the value to 10

In the above example, I created 10 threads, each thread tries ti increment the value of CASAtomicUpdate instance. In worst case, a thread retry at most nine times before the increment is complete. As you observe the output, pool-1-thread-6 attempted 9 times to succeed its incremental operations.

pool-1-thread-6 is trying to update the value from 0 to 1
pool-1-thread-6 is trying to update the value from 1 to 2
pool-1-thread-6 is trying to update the value from 3 to 4
pool-1-thread-6 is trying to update the value from 4 to 5
pool-1-thread-6 is trying to update the value from 5 to 6
pool-1-thread-6 is trying to update the value from 6 to 7
pool-1-thread-6 is trying to update the value from 7 to 8
pool-1-thread-6 is trying to update the value from 8 to 9
pool-1-thread-6 is trying to update the value from 9 to 10
pool-1-thread-6 Updated the value to 10

Non-blocking algorithms are difficult to implement, but they had many advantages like you don’t get any deadlock situation, priority inversion never occur and contention is less expensive.

Reference

https://en.wikipedia.org/wiki/Compare-and-swap

https://en.wikipedia.org/wiki/Non-blocking_algorithm

You may like

Can I customize serialization process?

Restrict a class from serialization, but super class is serialized

Implement Bijective Map

How to resolve Circular Dependency Problem

What is ReentrantLock?