From Passion to Profession
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use
  • Home
  • Notes
  • Projects
  • Resources
    • Discovery Log
    • Books I Read
    • Blogs I Visit
    • Tools I Use

Non-Blocking Function (Java Concurrency - Part 3)

7/11/2013

0 Comments

 
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 
0 Comments



Leave a Reply.

    Categories

    All
    Algorithm
    Concurrency
    CQ
    Data Structure
    Design Pattern
    Developer Tool
    Dynamic Programming
    Entrepreneur
    Functional Programming
    IDE
    Java
    JMX
    Marketing
    Marklogic
    Memory
    OSGI
    Performance
    Product
    Product Management
    Security
    Services
    Sling
    Social Media Programming
    Software Development

    Feed Widget

    Archives

    May 2020
    March 2020
    April 2018
    March 2018
    February 2018
    December 2017
    March 2017
    November 2016
    June 2016
    May 2016
    April 2016
    October 2015
    September 2015
    August 2015
    September 2014
    July 2014
    June 2014
    May 2014
    March 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013
    August 2013
    July 2013
    June 2013

    RSS Feed

in loving memory of my mother  and my 4th aunt
Photos used under Creative Commons from net_efekt, schani, visnup, Dan Zen, gadl, bobbigmac, Susana López-Urrutia, jwalsh, Philippe Put, michael pollak, oskay, Creative Tools, Violentz, Kyknoord, mobilyazilar