JUC Review (Part 2): Understanding Locks

Locks are unavoidable in concurrent programming. This post runs through the common lock concepts in one place, from fair locks and read-write locks to CAS and AQS, as the second part of my JUC review.

The Basic Idea of Locking

A lock mechanism guarantees that in a multithreaded environment, only one thread can enter a critical section at any given moment, ensuring the consistency of the data manipulated inside it.

Common Locks

1) Fair Lock

Prevents thread starvation — that is, prevents a thread from never getting a CPU time slice and being unable to make progress. Guaranteeing fairness requires extra bookkeeping of thread state and more context switches, so the overhead is higher and throughput drops somewhat. ReentrantLock can be made fair via a constructor parameter; Synchronized is non-fair by default and cannot be made fair.

2) Non-Fair Lock

Threads compete directly for compute resources, which can lead to starvation. But throughput is higher and thread switching less frequent — whoever grabs the CPU time slice first gets to run.

3) Reentrant Lock

Also called a recursive lock: a thread can re-acquire a lock it already holds, which helps avoid certain deadlock scenarios. Both ReentrantLock and Synchronized are reentrant.

4) Non-Reentrant Lock

If a thread that holds the lock tries to acquire it again inside the synchronized block, it deadlocks — a non-reentrant lock may only be acquired once within the block.

5) Mutex Lock

While one thread holds the resource, other threads are suspended and consume no CPU; when the lock is released, the CPU schedules the suspended threads. Suitable for resources that aren't accessed at high frequency — otherwise the constant thread scheduling becomes inefficient.

6) Read-Write Lock

ReentrantReadWriteLock consists of a read lock and a write lock, which are mutually exclusive. Use the read lock for read-only access to the shared resource and the write lock when modifying it — a good fit for read-heavy, write-light workloads. When no thread holds the write lock, multiple threads can hold the read lock concurrently; but once a thread holds the write lock, all other attempts to acquire either lock block.

Write priority: if write threads keep acquiring the write lock, read threads can be starved.

Read priority: if read threads keep acquiring the read lock, write threads may never get in — starving the writers.

7) Fair Read-Write Lock

A simple approach to a fair read-write lock: queue up the threads requesting the lock and grant it first-in, first-out regardless of whether they're readers or writers. Readers can still run concurrently, and starvation is alleviated to a degree.

8) Stamped Lock

StampedLock is a faster lock than ReentrantReadWriteLock, supporting optimistic reads, pessimistic read locks, and write locks. Unlike ReentrantReadWriteLock, StampedLock allows one thread to acquire the write lock even while multiple threads are performing optimistic reads.

Perspectives on Concurrent Synchronization

The "locks" below are not concrete lock implementations; they're more like perspectives on concurrent synchronization, or states a lock can be in.

1) Optimistic Locking

Implemented with version numbers or the CAS algorithm, assuming conflicts are rare. It works like this: when modifying a resource, assume you're the only one modifying it; after the modification, verify — and if the check fails, redo it. Despite the name, optimistic locking never actually takes a lock, which is why it's also called lock-free programming.

2) Pessimistic Locking

Assumes multiple threads will modify the resource, so every modification takes a lock. Database locking mechanisms are generally built on pessimistic locking.

3) Segmented Locking

Segmented locking exists to make locking finer-grained: when an operation doesn't need to update the whole array but only a single element, we lock just that element. In JDK 1.7, ConcurrentHashMap used segmented locking for concurrent access, locking individual Segments for higher concurrency — but in JDK 1.8 this was replaced by the CAS algorithm.

4) Biased Locking

When a synchronized block is only ever accessed by one thread, that thread acquires the lock automatically, lowering the cost of lock acquisition.

5) Lightweight Lock

When a biased lock is accessed by a second thread, it upgrades to a lightweight lock; other threads then try to acquire it by spinning, without blocking.

6) Heavyweight Lock

When a lightweight lock is spun on by another thread past a certain number of attempts without success, it upgrades to a heavyweight lock, which blocks the other threads.

7) Spin Lock

A thread trying to acquire the lock doesn't block immediately; instead it loops, retrying the acquisition. This burns more CPU — the thread is essentially idling. Usually a spin limit is set, after which the thread is suspended.

8) Deadlock

Deadlock isn't a kind of lock but a phenomenon: two running threads each need a lock the other already holds in order to proceed, so the program freezes and can't move forward. Deadlocks can be diagnosed with jstack: first get the application's pid with jps -l, then run jstack <pid> to inspect for deadlocks. You can also open the UI tool via the jconsole command to view deadlock information.

What Is the CAS Algorithm

CAS stands for Compare And Swap — exactly what the name says. It's a lock-free algorithm that guarantees thread safety without taking any locks: variables are synchronized without any thread blocking, which puts it in the category of non-blocking synchronization.

CAS involves three operands: the memory value V, the expected value A, and the new value B. The operation is: if and only if V equals A, CAS atomically replaces V with B; otherwise it does nothing. In general, CAS is a spin operation — it keeps retrying until it succeeds.

CAS has the following characteristics: the ABA problem, spin overhead, and atomicity for only a single shared variable.

• The ABA problem. If variable V reads as A initially and still checks out as A when we're about to assign, that doesn't prove no other thread modified it — in the meantime it could have been changed to something else and then back to A, and CAS would wrongly conclude it was never touched. This is CAS's ABA problem. In practice, judge the actual scenario: if ABA doesn't matter much for your use case, you can leave it alone; otherwise, attach a version number to every modification, or just fall back to pessimistic locking.
• Spin overhead. As mentioned, CAS is a spin operation with a head-through-the-wall persistence — on failure it retries until it succeeds. If the spinning goes on for a long time, it puts a heavy load on the CPU; that's the spin overhead.
• Atomicity for only one shared variable. CAS works on a single shared variable; when an operation spans multiple shared variables, CAS can't guarantee synchronization. One fix is to wrap those variables into a single object and apply CAS to that.

The underlying assembly instruction is lock cmpxchgl, where the lock prefix is especially important. What it does:

1. Ensures the read-modify-write operation on memory executes atomically. On Pentium and earlier processors, an instruction with the lock prefix locked the bus for the duration of its execution, temporarily preventing other processors from accessing memory over the bus — obviously an expensive proposition. Starting with the Pentium 4, Intel Xeon, and P6 processors, Intel added a meaningful optimization on top of bus locking: if the area of memory being accessed is already locked in the processor's internal cache during the lock-prefixed instruction (i.e. the cache line containing it is in the exclusive or modified state) and the memory area fits entirely within a single cache line, the processor executes the instruction directly. Because the cache line stays locked for the duration, other processors can't read or write the memory area the instruction touches, so atomicity is preserved. This is called cache locking, and it dramatically reduces the cost of lock-prefixed instructions — though under heavy contention between processors, or when the accessed memory address is misaligned, the bus still gets locked.

2. Forbids reordering of this instruction with the reads and writes before and after it.

3. Flushes all data in the write buffer to memory.

What Is AQS

Abstract Queued Synchronizer. Every implementation of the Lock interface in JUC is built on the AQS abstract class.

Wrapping Up

This post gathered the common lock concepts in one pass: fair vs. non-fair and reentrant vs. non-reentrant describe a lock's behavior; read-write locks and StampedLock target read-heavy workloads; and the progression from optimistic and pessimistic locking through biased, lightweight, and heavyweight locks is more about perspectives on synchronization and lock states. CAS is the cornerstone of lock-free programming in JUC, and understanding its three operands and the ABA problem is well worth the effort. As for AQS, it's the common skeleton behind every Lock implementation in JUC — its internals deserve a post of their own.