Non-Blocking Function (Java Concurrency - Part 3)

With regards to java concurrency, when reading some API documentation (e.g. java.util.concurrent),  there's  the term "non-blocking" and "blocking." In computer science, non-blocking means:

• Use low-level atomic hardware primitives (machine instructions) such as compare-and-set instead of intrinsic locks to ensure thread safety (data integrity under concurrent access).

• Performance gain and better scalability. threads does not have to be suspended/waken up by the OS using synchronization.
• Use non-fair locking (which does not guarantee any particular access order), which can have much more system throughput than fair-locking (which grants access to the longest-waiting thread).
  
• It doesn't cause other tasks (threads) to wait until the task is finished.
  
• Deadlock free. The risk of deadlocks is removed. No one thread will wait to get a lock held by another thread "forever". 

With examples, you'll see intrinsic locking is blocking, whereas compare-and-set is non-blocking. Read on.

Intrinsic Locking 

Most common, when more than one thread accesses a mutable variable, all threads must use the synchronized keyword (also known as intrinsic locking or monitor locking) to make our program thread-safe. The synchronized keyword prevent two invocations of synchronized methods on the same object to interleave.

JVMs typically implement blocking by suspending the blocked thread and rescheduling it later, resulting in heavyweight context switches for few instructions protected by the lock. Here's an example of such a blocking algorithm implementation of a counter class:

public class Counter {
    private long value = 0;

    public synchronized long getValue(){  // 1
        return value;
    }

    public synchronized long increment(){ // 2
        return ++value;
    }
}

[1] Synchronization is also needed on the getValue method, to ensure that threads calling getValue see an up-to-date value.
[2] The intrinsic lock is needed because increment involves three separate operations: fetch the value, add one to it, and write the value out.

Compare-and-Set (CAS)

By contrast, the non-blocking counter synchronizes at a finer level of granularity using a hardware primitive instead of the JVM locking code. The finer granularity reduces the chance that there will be contention. If contention happens, the losing threads can retry immediately rather than being suspended and rescheduled. For such a non-blocking counter class, you can use AtomicInteger (since Java 1.5) and rely on its compareAndSet() method.

Here's an example of a non-blocking implementation of the same counter class:

public class Counter {
    private AtomicInteger value = new AtomicInteger();    // 1

    public int getValue() {
        return value.get();
    }

    public int increment(){
        return value.incrementAndGet();
    }

    // alternative explicit implementation
    public int increment() {
        int oldValue 
        do{
          oldValue = value.get();
        } while (!value.compareAndSet(oldValue, oldValue + 1)); // 2
        return oldValue + 1;
    }
}

[1] atomic variable provides fine-grained atomic updates of numbers and object references
[2] Update this variable to this new value, but fail if some other thread changed the value since I last looked.

There's a basic characteristic of all nonblocking algorithms - some algorithmic step is executed speculatively, with the knowledge that it may have to be redone only if the compare-and-set is not successful. Otherwise, it proceed with the optimistic assumption that there will be no contention. If interference is detected, the algorithm back off and retry.

non-blocking stack or non-blocking linked-list example

Similar to using AtomicInteger and its compareAndSet() method to implement a non-blocking counter class, you can use AtomicReference and its compareAndSet() method to implement a non-blocking stack class. See here for the sample code.

conclusion

Under light contention, non-blocking algorithm tends to perform better than blocking implementation in concurrency programming because the unlikely contention cost just a few more iterations of the loop. Only under high contention will the blocking implementation performs better. Non-blocking algorithm, however, can be difficult to design and implement.

what to read next

• ForkJoinPool Example (Java Concurrency - Part 2)
  

references

• What is “non-blocking” concurrency and how is it different than normal concurrency?
  
• Intrinsic Locks and Synchronization
  
• Java theory and practice: Introduction to nonblocking algorithms