Chapter 15: Nonblocking Synchronization

Back>

Chapter 15: Nonblocking Synchronization

Chapter 15 of Java Concurrency in Practice introduces one of the most powerful tools in modern concurrent programming: nonblocking synchronization. Unlike traditional blocking synchronization (e.g., using synchronized or ReentrantLock), nonblocking synchronization avoids thread suspension and context switching, relying instead on low-level atomic operations such as Compare-And-Swap (CAS).

What is Compare-And-Swap (CAS)?

CAS is an atomic instruction supported by most modern CPUs that updates a memory location only if it matches an expected value. It is the foundation of nonblocking data structures and the java.util.concurrent.atomic package.

boolean compareAndSet(expectedValue, newValue)

If the current value equals expectedValue, CAS atomically replaces it with newValue and returns true. Otherwise, it leaves the value unchanged and returns false.

Why Avoid Blocking and Suspension?

Traditional locking mechanisms rely on thread suspension when a lock is unavailable. While effective in ensuring mutual exclusion, blocking has performance penalties:

• Context switching overhead: Suspending and rescheduling threads requires coordination with the OS and the JVM scheduler, consuming CPU cycles.
• Increased latency: Threads may be delayed arbitrarily due to contention or priority scheduling.
• Risk of deadlock and priority inversion: If thread dependencies form cycles, or lower-priority threads hold locks needed by higher-priority ones.

To address these challenges, nonblocking synchronization uses an optimistic concurrency strategy: assume no contention, proceed with an update, and retry only if contention is detected (via CAS failure). This avoids the costly overhead of blocking by spinning in userspace and ensures system-wide progress.

CAS Support Across the Stack

Layer	CAS Support	Blocking Support
Hardware	Most CPUs provide CAS or LL/SC (Load Linked / Store Conditional)	None — blocking is abstracted by OS or JVM
Operating System	Used in kernel spinlocks and atomic ops	Provides mutexes, semaphores, thread scheduling
Java Virtual Machine	Supported via intrinsics like Unsafe.compareAndSwap	synchronized, monitorenter/exit bytecodes
Java Language	AtomicInteger, AtomicReference, etc.	synchronized, ReentrantLock, wait()

Code Examples

• SimulatedCAS.java: Demonstrates the logic behind CAS using synchronized. While not nonblocking, it helps understand how real CAS behaves internally.
• CasCounter.java: A nonblocking counter using a CAS loop. Threads retry until they successfully increment the value.
• CasNumberRange.java: Uses an AtomicReference to preserve a multivariable invariant (lower <= upper) without locking.
• AtomicPseudoRandom.java: A thread-safe pseudo-random generator that uses CAS for updating the internal seed.
• ReentrantLockPseudoRandom.java: A comparison version that uses traditional locking, illustrating the trade-offs between blocking and nonblocking strategies.
• ConcurrentStack.java: A lock-free stack implementation using Treiber’s algorithm and atomic references, demonstrating how CAS supports scalable data structures.

Advantages of Nonblocking Synchronization

• Improved scalability under contention
• No deadlocks or thread starvation
• Ideal for fine-grained atomic updates
• Works well with modern CPU caches and multi-core systems
• Lower latency by avoiding thread suspension

Limitations and Considerations

• More complex to reason about and debug
• Spin-waiting can consume CPU if not bounded or managed
• ABA problem: solved with AtomicStampedReference or AtomicMarkableReference
• Still relies on underlying hardware instructions — performance varies by CPU architecture

Conclusion

Nonblocking synchronization provides a powerful alternative to traditional locking, particularly in scenarios where high performance, low latency, and scalability are critical. With support at the CPU, OS, JVM, and language levels, Java offers rich tools for building lock-free systems. By using CAS and atomic classes, developers can avoid the penalties of blocking, reduce contention, and build highly concurrent applications that scale with modern hardware.