Shared lock - exclusive lock

Use Cases Where Shared Lock / Exclusive Lock Are Useful

Shared and exclusive locks are essential for managing concurrent access to shared resources, ensuring correctness and consistency while maximizing performance. Here are key scenarios:

1. Read-Write Access Control:
   • Use shared locks (read locks) when multiple threads need to read data concurrently.
   • Use exclusive locks (write locks) when a thread needs to modify data, ensuring no other thread can read or write during the modification.
2. Database Systems:
   • Shared locks are used for read-only transactions, allowing multiple readers.
   • Exclusive locks are used for write operations, preventing concurrent reads or writes to ensure consistency.
3. Deduplication in Storage:
   • Writers (shared lock) may upload the same file concurrently, while deleters (exclusive lock) need to ensure the file is not being written when deleting.
4. Cache or Memory Management:
   • Shared locks allow threads to read a cached object concurrently.
   • Exclusive locks allow one thread to update or invalidate the cache entry.

---

Implementation in Java Using Compare-And-Set and a Mask

A shared lock and exclusive lock system can be implemented using compareAndSet with a mask to differentiate shared and exclusive states. The lock state is stored as an integer, where:

• The lower 16 bits track the exclusive lock count.
• The upper 16 bits track the shared lock count.

Why Use a Mask (e.g., SHARED_UNIT)?

Instead of incrementing by 1, we increment by a constant (SHARED_UNIT = 1 << 16 = 0x00010000) for shared locks. This allows the upper 16 bits to track shared locks independently of exclusive locks in the lower 16 bits. This separation avoids conflicts between shared and exclusive locks.

Java Implementation

Here’s a simplified implementation of a shared-exclusive lock:

public class SharedExclusiveLock {
    private static final int SHARED_UNIT = (1 << 16); // Increment for shared locks
    private static final int MAX_SHARED = 0xFFFF0000; // Maximum shared count
    private static final int MAX_EXCLUSIVE = 0x0000FFFF; // Maximum exclusive count
 
    private final AtomicInteger state = new AtomicInteger(0);
 
    // Acquire shared lock
    public boolean acquireShared() {
        for (;;) {
            int current = state.get();
            int sharedCount = current & MAX_SHARED;
 
            // Fail if exclusive lock is held
            if ((current & MAX_EXCLUSIVE) > 0) return false;
 
            // Increment shared count
            if (sharedCount < MAX_SHARED) {
                if (state.compareAndSet(current, current + SHARED_UNIT)) {
                    return true;
                }
            } else {
                throw new IllegalStateException("Too many shared locks");
            }
        }
    }
 
    // Release shared lock
    public void releaseShared() {
        for (;;) {
            int current = state.get();
            if (state.compareAndSet(current, current - SHARED_UNIT)) {
                return;
            }
        }
    }
 
    // Acquire exclusive lock
    public boolean acquireExclusive() {
        for (;;) {
            int current = state.get();
            if (current != 0) return false; // Shared or exclusive lock is held
            if (state.compareAndSet(0, 1)) {
                return true;
            }
        }
    }
 
    // Release exclusive lock
    public void releaseExclusive() {
        if (!state.compareAndSet(1, 0)) {
            throw new IllegalStateException("Invalid exclusive lock release");
        }
    }
}

Key Points:

1. Shared and exclusive locks operate on separate portions of the state variable.
2. The SHARED_UNIT ensures increments for shared locks affect only the upper 16 bits.
3. Exclusive locks use the lower 16 bits, allowing independent tracking.

---

How It Works Under the Hood (CMPXCHG, LDXR/STXR)

Atomicity with CPU Primitives

The compareAndSet method relies on atomic compare-and-swap (CAS) instructions provided by the CPU. These instructions ensure atomicity without requiring OS-level synchronization.

CMPXCHG (x86)

• Instruction: CMPXCHG (Compare and Exchange)
• Behavior:
  1. Compare the value in a memory location with an expected value.
  2. If they match, replace the value with a new one.
  3. If not, return the current value.
• Usage in Java:
  • The JVM emits the CMPXCHG instruction for compareAndSet operations.

Example:

lock cmpxchg [mem], reg

LDXR/STXR (ARM)

• ARM uses Load-Exclusive (LDXR) and Store-Exclusive (STXR) instructions:
  1. LDXR: Loads the value from memory and marks it for exclusive access.
  2. STXR: Stores a new value only if the memory location hasn’t been modified since the load.

Example:

ldxr w0, [mem]      // Load exclusive
cmp  w0, expected   // Compare with expected
b.ne fail           // Branch if not equal
stxr w1, new_value, [mem] // Store exclusive
cbnz w1, retry      // Retry if store failed

Why CAS Is Fast:

1. Entirely handled in hardware (no syscall overhead).
2. Atomicity ensures no need for explicit locking.
3. Used extensively in lock-free data structures and synchronization primitives.