Reentrant Locks & CAS (Compare-And-Swap)

In concurrent programming, synchronization generally falls into two categories: Pessimistic Locking (blocking threads using mutual exclusion locks) and Optimistic Locking (allowing threads to proceed without locking, using hardware-level atomic instructions to detect and resolve conflicts). We will explore the leading implementations of both strategies: Reentrant Locks and Compare-And-Swap (CAS).

1. Learning Objectives

• Understand the mechanics of Reentrant Locks, lock fairness, and timed lock acquisition.
• Master hardware-level Compare-And-Swap (CAS) atomic instructions.
• Differentiate between pessimistic locking (blocking) and optimistic locking (non-blocking).
• Identify and solve the ABA Problem using versioning and stamped references.
• Analyze performance under low vs. high thread contention.

2. Problem & Naive Solution

Suppose you are building a metric tracker for a financial trading platform. The tracker must count millions of transaction requests per second across dozens of concurrent threads. If a thread blocks, it can introduce unacceptable latency.

The Naive Solution (Pessimistic Synchronized Locking)

A developer implements the counter using standard synchronized blocks:

3. Issues with the Naive Approach

• High Thread Blocking and Context-Switching Latency: Under high contention, threads are repeatedly suspended and resumed by the OS scheduler. The CPU spends more time performing context switches than incrementing the counter.
• No Way to Avoid Blocking: If a thread fails to acquire the lock, it is suspended. It cannot check the lock status and perform alternative work instead of blocking.

4. CAS Validation Flow

Below is a diagram of the CAS loop. If the memory value matches the expected value, the CPU updates it atomically; if not, the thread retries the operation in a loop.

5. Theory: Reentrant Locks vs. CAS

Let's explore the concepts behind pessimistic locking and optimistic locking:

A. Reentrant Locks

A Reentrant Lock is a pessimistic lock that allows a thread to re-acquire the same lock if it already holds it, preventing deadlocks when calling nested synchronized methods.

• Reentrancy Count: Tracks how many times the lock holder thread has acquired the lock. It releases the lock once the count reaches 0.
• Fairness: Optional configuration where the lock is granted to the longest-waiting thread (FIFO queue), reducing thread starvation at the cost of throughput.
• Acquisition Options: * tryLock(): Non-blocking check. Attempts to acquire the lock immediately and returns a boolean status. * lockInterruptibly(): Allows waiting threads to be interrupted, preventing threads from hanging indefinitely.

B. Compare-And-Swap (CAS)

CAS is a hardware-level atomic instruction (like cmpxchg on x86 processors). It takes three arguments:

• Memory Location (V): The address of the variable.
• Expected Value (A): The value the thread believes is currently stored.
• New Value (B): The value the thread wants to write.

The CPU updates the memory location to the new value if and only if the current value matches the expected value. This allows threads to update values atomically without acquiring locks.

C. The ABA Problem

The ABA problem occurs when Thread 1 reads value A from memory. Before it can perform a CAS write, Thread 2 runs, changes the value from A to B, and then changes it back to A. When Thread 1 executes its CAS write, it sees A and assumes the value has not changed, potentially corrupting data in structures like linked-list nodes.

• Solution: Use versioning or stamped references (e.g., AtomicStampedReference in Java). Instead of comparing just the value, compare both the value and an associated integer version stamp (e.g., comparing [value=A, stamp=1] with [value=A, stamp=2] fails).

6. Syntax Explanation

To implement pessimistic or optimistic synchronization, languages provide specific APIs:

• Java: Provides ReentrantLock for locks, and AtomicInteger / AtomicLong for lock-free CAS operations.
• Python: Provides threading.Lock() (which is reentrant in Python if using RLock) and third-party atomic wrappers.
• C++: Provides std::recursive_mutex for reentrant locks, and std::atomic<T> with compare_exchange_weak() / compare_exchange_strong() for CAS operations.

7. Step-by-Step Implementation

1. Initialize Atomic Class / Lock: Instantiate an AtomicInteger or ReentrantLock.
2. Implement Lock Increment: Acquire the lock, increment the counter, and release the lock inside a finally block.
3. Implement CAS Increment: Use a loop that reads the current value, computes the incremented value, and calls compareAndSet(). The loop continues until the CAS operation succeeds.
4. Verify Execution: Run threads concurrently and confirm that the final counter values are correct.

8. Complete Code (Lock-based vs. Lock-free Counter)

This program compares a lock-based counter using ReentrantLock with a lock-free counter using AtomicInteger (CAS).

9. Code Walkthrough

• Atomic Loop Mechanics: In LockFreeCounter.increment(), we read the current value using count.get(). We then calculate the incremented value (newValue = currentValue + 1) and attempt to write it using compareAndSet(). If another thread updated the counter in the meantime, the current value check fails, and compareAndSet() returns false, causing the loop to retry.
• C++ compare_exchange_weak: In C++, the compare_exchange_weak() method attempts to perform the CAS operation. If it fails, the method automatically updates the expected variable with the current value stored in the atomic variable, ready for the next iteration.

10. Complexity Analysis

• Time Complexity:
  • Low Contention: $O(1)$ CPU instruction.
  • High Contention: $O(\text{Retries})$ as threads spin wait in loops, which can increase CPU usage.
• Space Complexity: $O(1)$ space.

11. Best Practices

• Use CAS for Low Contention Workloads: CAS is highly efficient when lock contention is low. It avoids the overhead of blocking and resuming threads.
• Use Locks for High Contention Workloads: When lock contention is high, threads in a CAS loop will spend excessive CPU cycles spinning and retrying. In this case, pessimistic locks are more efficient because they suspend the waiting threads, freeing up CPU resources.

12. Common Mistakes

• Omitting the Loop Around CAS: Attempting to call compareAndSet() without wrapping it in a retry loop. If the CAS check fails, the update is lost.
• Ignoring the ABA Problem in Node Reference Graphs: Using raw CAS pointers to manage node transitions in stacks or queues. If a node is recycled (deleted and recreated at the same memory address), the CAS check will succeed even though the graph structure has changed, corrupting the collection. Use stamped references or versioning.

13. Interview Discussion

14. Practice Exercises

• Easy: Write a program that implements a basic thread-safe counter using AtomicInteger.
• Medium: Build a non-blocking queue using AtomicReference to manage head and tail node transitions.
• Hard: Implement a lock-free stack (Treiber Stack) using AtomicReference and demonstrate the ABA problem by recycling nodes.

15. Challenge Problem

Design a Lock-Free Concurrent Memory Allocation Registry. The registry maps string keys to memory block objects. Implement registration and de-registration operations using AtomicReferenceArray and CAS operations. Ensure that no thread blocks, and that the registry remains consistent even when memory blocks are recycled rapidly.

16. Summary & Cheat Sheet

• Reentrant Locks are pessimistic locks that support fairness, interrupts, and non-blocking acquisition (tryLock()).
• CAS (Compare-And-Swap) is a hardware-level atomic instruction used to implement lock-free, optimistic concurrency.
• Use locks for high-contention workloads to avoid spinning, and use CAS for low-contention, high-frequency operations.
• Resolve the ABA problem by using version stamps alongside references.

17. Quiz

18. Next Lesson Preview

In the next lesson, we will cover Deadlocks & Livelocks. We will study the four Coffman conditions, explore resource ordering strategies, and learn to resolve lock freezes at runtime!