In the realm of concurrent programming, managing shared resources efficiently and safely is paramount. One crucial technique for achieving this, especially in non-blocking algorithms, is compare-and-set (CAS). Essentially, compare-and-set is an atomic operation that checks if a variable’s value matches an expected value. If they match, it updates the variable with a new value; otherwise, it leaves the variable unchanged. While the concept might initially seem intricate, it becomes remarkably clear with a deeper exploration. Let’s delve into the world of compare-and-set and understand its significance in modern concurrency.
You might also encounter the abbreviation CAS when reading about concurrency. Rest assured, this typically refers to the compare-and-set operation we’re discussing here.
The Check-Then-Act Problem in Concurrent Programming
A common pattern in concurrent algorithms is the “check-then-act” sequence. This pattern arises when code first examines the state of a variable and then performs an action based on that observed state. Consider this simplified, yet problematic, lock implementation as an example:
public class ProblematicLock {
private volatile boolean locked = false;
public void lock() {
while(this.locked) {
// busy wait - until this.locked == false
}
this.locked = true;
}
public void unlock() {
this.locked = false;
}
}This ProblematicLock class, as its name suggests, isn’t a robust, thread-safe lock. It’s intentionally flawed to highlight the challenges that compare-and-set effectively addresses.
The lock() method embodies the “check-then-act” pattern. It checks if the locked variable is false within the while loop. If locked is indeed false, the method exits the loop and proceeds to act by setting locked to true.
However, in a multithreaded environment, this approach is vulnerable. Imagine two threads, Thread A and Thread B, attempting to acquire the lock simultaneously.
If Thread A checks locked and finds it false, it prepares to exit the while loop and set locked to true. Critically, if Thread B also checks locked before Thread A completes its action of setting locked to true, Thread B will also observe locked as false and proceed to exit its own while loop. This scenario leads to a classic race condition. Both threads believe they have acquired the lock, potentially leading to data corruption and unpredictable behavior.
Atomicity: The Solution to Race Conditions
To function correctly in concurrent applications and prevent race conditions, “check-then-act” operations must be atomic. Atomicity implies that the “check” and “act” steps are executed as a single, indivisible unit. Once a thread begins executing an atomic block, it will complete the entire block without interruption from other threads. No other thread can execute the same atomic block concurrently.
In Java, a straightforward way to achieve atomicity for a code block is by using the synchronized keyword. Here’s how we can modify the ProblematicLock to make the lock() method atomic using synchronized:
public class ProblematicLock {
private volatile boolean locked = false;
public **synchronized** void lock() {
while(this.locked) {
// busy wait - until this.locked == false
}
this.locked = true;
}
public void unlock() {
this.locked = false;
}
}By declaring the lock() method as synchronized, we ensure that only one thread can execute it at any given time on the same ProblematicLock instance. The lock() method now operates atomically, effectively preventing the race condition we discussed earlier.
The Cost of Blocking: Synchronization Overhead
While synchronized provides atomicity, it introduces a concept called blocking. When multiple threads attempt to enter a synchronized block simultaneously, only one thread is granted access. The other threads are blocked, waiting for the currently executing thread to exit the synchronized block. Once the executing thread exits, one of the waiting threads is then allowed to proceed.
Entering a synchronized block is relatively inexpensive if access is readily granted. However, the blocking of threads, when contention occurs, can be costly in terms of performance.
Furthermore, there’s no guaranteed order in which blocked threads are unblocked. The operating system or execution platform manages thread unblocking, and while it’s typically fast, there’s still a potential delay where a blocked thread remains idle when it could be processing. This overhead is visualized below:
Hardware-Level Compare-and-Set: A Non-Blocking Approach
Modern CPUs offer built-in support for atomic compare-and-set operations at the hardware level. These operations provide an alternative to synchronized blocks and other blocking mechanisms in certain scenarios. The CPU guarantees that a compare-and-set operation executes atomically, even across multiple CPU cores. We’ll see code examples of this shortly.
Utilizing hardware-level compare-and-set instead of OS or platform-level synchronization eliminates the need for the OS to manage thread blocking and unblocking. This significantly reduces the waiting time for threads attempting to access shared resources, leading to less contention and higher overall throughput. This non-blocking approach is illustrated here:
As depicted, threads using compare-and-set don’t experience full blocking. They continuously attempt the compare-and-set operation until it succeeds, gaining access to the shared resource. This minimizes the delay before a thread can proceed.
It’s worth noting that if a thread repeatedly fails in its compare-and-set attempts due to high contention, it might consume CPU cycles in retries. However, in many practical scenarios, shared resources are not held for extended periods. Therefore, prolonged contention is often not a major issue. In contrast, blocked threads in traditional synchronization remain completely idle, relinquishing CPU time.
Compare-and-Set in Java: The Atomic Classes
Since Java 5, developers have access to CPU-level compare-and-set functionality through the java.util.concurrent.atomic package. This package provides a suite of atomic classes, including:
AtomicIntegerAtomicLongAtomicBooleanAtomicReference
These classes provide methods like compareAndSet(), which leverage the underlying hardware’s compare-and-set instructions.
The key advantage of using Java’s atomic classes is that they directly utilize the CPU’s native compare-and-set capabilities. This results in significantly faster and more efficient concurrent code compared to software-based implementations.
Compare-and-Set as a Lock Guard
Compare-and-set can be effectively employed as a lock guard, preventing multiple threads from entering a critical section simultaneously. Let’s revisit our lock() method and reimplement it using AtomicBoolean and compare-and-set:
public class CompareAndSwapLock {
private AtomicBoolean locked = new AtomicBoolean(false);
public void unlock() {
this.locked.set(false);
}
public void lock() {
while(!this.locked.compareAndSet(false, true)) {
// busy wait - until compareAndSet() succeeds
}
}
}Notice that locked is now an AtomicBoolean instead of a simple boolean. AtomicBoolean offers the crucial compareAndSet() method. This method compares the current value of the AtomicBoolean with an expected value. If they match, it atomically sets the AtomicBoolean to a new value and returns true. If they don’t match, it returns false, indicating the swap did not occur.
In our CompareAndSwapLock example, compareAndSet(false, true) attempts to set locked to true only if its current value is false.
Because the compareAndSet() operation is atomic, only one thread at a time can successfully observe locked as false and swap it to true. Consequently, only one thread can exit the while loop and acquire the “lock” for each unlock() operation that sets locked back to false.
Compare-and-Set for Optimistic Locking
Compare-and-set also forms the foundation for optimistic locking mechanisms. Optimistic locking allows multiple threads to proceed into a critical section concurrently, but only permits one thread to successfully commit its changes at the end.
Consider this concurrent counter implementation using optimistic locking:
public class OptimisticLockCounter{
private AtomicLong count = new AtomicLong();
public void inc() {
boolean incSuccessful = false;
while(!incSuccessful) {
long value = this.count.get();
long newValue = value + 1;
incSuccessful = this.count.compareAndSet(value, newValue);
}
}
public long getCount() {
return this.count.get();
}
}The inc() method retrieves the current count from the AtomicLong count. It then calculates the incremented newValue. The crucial step is compareAndSet(value, newValue).
This compareAndSet() operation checks if the current value of count is still the value that was initially read. If it is, meaning no other thread has modified count in the meantime, the update to newValue is performed atomically, and compareAndSet() returns true, setting incSuccessful to true and exiting the loop.
However, if another thread has incremented count since the initial read, the compareAndSet() will fail because the expected value no longer matches the actual value in AtomicLong. In this case, compareAndSet() returns false, incSuccessful remains false, and the while loop iterates again. The process repeats, reading the updated count, recalculating, and attempting the compare-and-set until it succeeds. This optimistic approach ensures that increments are performed correctly even under concurrency, without resorting to blocking synchronization for every increment operation.
In conclusion, compare-and-set is a fundamental building block for constructing efficient and scalable concurrent algorithms and data structures. Its atomic nature and non-blocking characteristics make it a powerful tool for managing shared state in multithreaded applications, offering performance advantages over traditional blocking synchronization techniques.
