Member-only story
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…