Java Multithreading, Concurrency, and Parallelism — Part 17.2

Introduction to non-blocking — Compare and Swap

We have seen the CopyOnWriteArrayList in the previous part. In this part, we will look at ConcurrentHashMap which is yet another beast in terms of understanding what is happening behind the scenes. But before that, we need to understand what CAS(Compare-And-Swap) is. We will dedicate this article solely to CASing. In the next part, we will have an in-depth understanding of putVal() method which is commonly used by all the put variants: put, putIfAbsent, putAll and etc.

Compare-And-Swap

compare-and-swap is a technique or a tool used in multithreading to provide non-blocking thread safety. So far what we have seen with synchronized and ReentrantLock, are the blocking mechanisms. This CAS technique is even implemented at the hardware level right into the machine’s Instruction Set. For example, in the Intel x-86, it is implemented as CMPXCHG (compare-and-exchange) instruction. All the modern multiprocessor architectures support CAS in their instruction set. It is the most popular primitive for implementing non-blocking concurrent collections. Most of the concurrent collections in Java use CAS in combination with minimal locking(Lock Striping) to achieve a higher degree of concurrency.

To understand how CAS works, consider our Counter scenario, where we have two threads T1 and T2 and both are trying to increment the value of the Counter object. We know that the increment…