Non-blocking, Lock-free operations

1. Overview

In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. 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.

1.1 DealLocks

• Deadlocks are generally unrecoverable
• Can bring the application to a complete halt
• The more locks in the application, the higher the chances for a deadlock

1.2 Slow Critical Section

• Multiple threads using the same lock
• One thread holds the lock for very long
• That thread will slow down all the other threads
• All threads become as slow as the slowest thread

1.3 Priority Inversion

• Two threads sharing a lock
  • Low priority thread (document server)
  • Hight priority thread (UI)
• Low priority thread acquires the lock and is preempted (scheduled out)
• High priority thread cannot progress because of the low priority thread is not scheduled to release the lock

1.4 Thread not Releasing a lock (Kill Tolerance)

• Thread dies, gets interrupted or forget to release a lock
• Leaves all thread hanging forever
• Unrecoverable, Just like a deadlock
• To avoid, developers need to write more complex code

1.5 Performance

• Performance overhead in having contention over a lock
  • Thread A acquires a lock
  • Thread B tries to acquire a lock and gets blocked
  • Thread B is scheduled out (context switch)
  • Thread B is scheduled back (context switch)
• Additional overhead may not be noticeable for most applications
• But for latency-sensitive applications, this overhead can be significant

1.6 Why did we need locks?

• Multiple threads accessing shared resources
• At least one thread is modifying the shared resources
• Operations are not atomic
• A single Java operation turns into one or more hardware operations
• Example: counter++ turns into 3 hardware instructions:
  • Read count
  • Calculate new value
  • Store a new value to count

2. Description

2.1 Lock Free solution

2.1.1 Breakdown

• Utilize operations which are guaranteed to be one hardware operation
• A single hardware operation is
  • Atomic by definition
  • Thread-safe

2.1.2 Atomic instructions

• Read/Assignment on all primitive types except for long and double
• Read/Assignment on all references
• Read/Assignment on volatile long and double

2.1.3 Avoiding Data Races

• Read/Assignment on all volatile primitive types and references

2.1.4 AtomicX Classes

• Class located in the java.util.concurrent.atomic package
• Internally uses the Unsafe Class which provides access to a low level, native methods
• Utilize platform-specific implementation of atomic operations

Atomic packages available in Java 10

3. Example

3.1 Stack

3.1.1 With synchronized keyword

public static class StandardStack<T> {
        private StackNode<T> head;
        private int counter = 0;

        public synchronized void push(T value) {
            StackNode<T> newHead = new StackNode<>(value);
            newHead.next = head;
            head = newHead;
            counter++;
        }

        public synchronized T pop() {
            if(head == null) {
                counter++;
                return null;
            }
            T value = head.value;
            head = head.next; // previous head is garbage collected automatically by GC
            counter++;
            return value;
        }

        public int getCounter() {return counter;}
    }
    private static class StackNode<T> {
        public T value;
        public StackNode<T> next;

        public StackNode(T value) {
            this.value = value;
            this.next = next;
        }
    }

3.1.2 With the atomic package

public static class LockFreeStack<T> {
        private AtomicReference<StackNode<T>> head = new AtomicReference<StackNode<T>>();
        private AtomicInteger counter = new AtomicInteger(0);
        public void push(T value) {
            StackNode<T> newHeadNode = new StackNode<>(value);
            while (true) {
                StackNode<T> currentHeadNode = head.get();
                newHeadNode.next = currentHeadNode;
                if(head.compareAndSet(currentHeadNode, newHeadNode)) {
                    break;
                } else {
                    LockSupport.parkNanos(1);
                }
            }
            counter.incrementAndGet();
        }
        public T pop() {
            StackNode<T> currentHeadNode = (StackNode<T>) head.get();
            StackNode<T> newHeadNode;
            while(currentHeadNode != null) {
                newHeadNode = currentHeadNode.next;
                if(head.compareAndSet(currentHeadNode, newHeadNode)) {
                    break;
                } else {
                    LockSupport.parkNanos(1);
                    currentHeadNode = (StackNode<T>) head.get();
                }
            }
            counter.incrementAndGet();
            return currentHeadNode != null ? currentHeadNode.value : null;
        }
        public int getCounter() {
            return counter.get();
        }
    }

// synchronized
190,568,501 operations were performed in 10 seconds
// atomic
743,488,968 operations were performed in 10 seconds

3.2 Arithmetic

3.2.1 Using AtomicReference wrapping primitive

private static class Metric {
        private static class InternalMetric{
            public long count;
            public long sum;
        }
        
        AtomicReference<InternalMetric> internalMetric = new AtomicReference<>(new InternalMetric());
 
        public void addSample(long sample) {
            InternalMetric currentState;
            InternalMetric newState;
            do {
                currentState = internalMetric.get();
                newState = new InternalMetric();
                newState.sum = currentState.sum + sample;
                newState.count = currentState.count + 1;
            } while (!internalMetric.compareAndSet(currentState, newState));
        }
 
        public double getAverage() {
            InternalMetric newResetState = new InternalMetric();
            InternalMetric currentState;    
            double average;
            do {
                currentState = internalMetric.get();            
                average = (double)currentState.sum / currentState.count;
            } while (!internalMetric.compareAndSet(currentState,  newResetState));
            
            return average;
        }        
    }

4. Reference

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

https://www.justsoftwaresolutions.co.uk/threading/non_blocking_lock_free_and_wait_free.html