Locks and Synchronization Mechanisms

Overview

Basic synchronized blocks and intrinsic locks solve simple mutual exclusion problems, but production systems demand more nuanced concurrency control. When you need to acquire a lock in one method and release it in another, or when you need non-blocking lock attempts, or when readers vastly outnumber writers - intrinsic locks fall short. Explicit locks and advanced synchronization primitives provide:

• Fine-grained control - lock/unlock at arbitrary points, not just block boundaries; hand-over-hand locking in linked structures
• Try-lock semantics - attempt acquisition without blocking indefinitely; essential for latency-sensitive services
• Fairness policies - prevent thread starvation under contention via FIFO ordering guarantees
• Read-write separation - allow concurrent readers while serializing writers, dramatically improving throughput for read-heavy workloads
• Condition variables - coordinate threads waiting for specific state changes without busy-waiting
• Lock-free algorithms - eliminate locks entirely using atomic hardware instructions (CAS, LL/SC), providing progress guarantees even when threads are suspended

The evolution from coarse-grained locking to fine-grained and eventually lock-free approaches mirrors the evolution of concurrent systems themselves - from single-core machines where a global lock sufficed, to many-core processors where contention on a single lock becomes the primary bottleneck.

This article covers the full spectrum of locking mechanisms, from heavyweight mutexes to lock-free CAS-based structures, with pseudocode, diagrams, and real-world applications relevant to system design interviews and production engineering.

---

Types of Locks

Mutex (Mutual Exclusion)

Definition: A mutex ensures only one thread can access a critical section at any time. The owning thread must release it - ownership is non-transferable.

mutex m

thread_function():
    m.lock()
    // critical section  -  only one thread here
    shared_counter += 1
    m.unlock()

Use case: Protecting a single shared variable, updating a bank account balance.

---

Semaphore (Counting & Binary)

Definition: A semaphore maintains an internal counter. acquire() decrements it (blocking at zero); release() increments it. A binary semaphore (max count = 1) behaves like a mutex but without ownership semantics.

semaphore pool_sem = MAX_CONNECTIONS  // counting semaphore

acquire_connection():
    pool_sem.acquire()       // blocks if count == 0
    conn = pool.get()
    return conn

release_connection(conn):
    pool.put(conn)
    pool_sem.release()       // increments count

Use case: Limiting concurrent access to a resource pool (DB connections, thread pools).

---

Read-Write Lock (Shared/Exclusive)

Definition: Allows multiple concurrent readers OR a single exclusive writer. Readers share the lock; a writer must wait for all readers to finish.

rwlock rw

read_data():
    rw.read_lock()
    data = shared_cache.get(key)
    rw.read_unlock()
    return data

write_data(key, value):
    rw.write_lock()
    shared_cache.put(key, value)
    rw.write_unlock()

Use case: In-memory caches, configuration stores with frequent reads and rare updates.

---

Reentrant Lock

Definition: A lock that the same thread can acquire multiple times without deadlocking. An internal hold count tracks acquisitions; the lock releases only when the count reaches zero.

reentrant_lock lock

outer():
    lock.lock()        // hold_count = 1
    inner()
    lock.unlock()      // hold_count = 0, released

inner():
    lock.lock()        // hold_count = 2 (same thread, no block)
    // work
    lock.unlock()      // hold_count = 1

Use case: Recursive algorithms, calling synchronized methods from other synchronized methods on the same object.

---

Spin Lock

Definition: A lock where the waiting thread continuously polls (spins) in a loop rather than yielding the CPU. Efficient when lock hold times are extremely short.

atomic flag = FREE

spin_lock():
    while !CAS(flag, FREE, HELD):
        // spin  -  busy wait
        cpu_pause()    // hint to reduce power/pipeline stalls

spin_unlock():
    flag = FREE       // atomic store

Use case: OS kernel critical sections, interrupt handlers, very short critical sections (< 1μs).

---

StampedLock (Optimistic Reading)

Definition: Provides three modes - write lock, read lock, and optimistic read. The optimistic read doesn't actually acquire a lock; it obtains a stamp and later validates whether a write occurred.

stamped_lock sl

optimistic_read():
    stamp = sl.tryOptimisticRead()
    value = shared_data              // read without locking
    if sl.validate(stamp):
        return value                 // no write happened  -  fast path
    // fallback to pessimistic read
    stamp = sl.readLock()
    value = shared_data
    sl.unlockRead(stamp)
    return value

Use case: High-throughput read-heavy workloads where writes are rare (e.g., point-in-time snapshots, geo-coordinate reads).

---

Mutex vs Semaphore vs Monitor

---

ASCII Diagrams

Lock Acquisition and Release Flow

Thread-A            Mutex             Thread-B
   |                  |                  |
   |--- lock() ------>|                  |
   |<-- acquired -----|                  |
   |                  |<--- lock() ------|
   |  [critical       |     [BLOCKED]    |
   |   section]       |        .         |
   |                  |        .         |
   |--- unlock() --->|        .         |
   |                  |--- acquired ---->|
   |                  |  [critical       |
   |                  |   section]       |
   |                  |<-- unlock() -----|
   |                  |                  |

Reader-Writer Lock Scenario

Time ──────────────────────────────────────────────►

Reader-1:  ╠══ read_lock ══╣
Reader-2:     ╠══ read_lock ══╣        (concurrent with Reader-1)
Writer-1:        [BLOCKED...]  ╠══ write_lock ══╣
Reader-3:                      [BLOCKED...]       ╠══ read_lock ══╣

Legend: ╠══╣ = holding lock    [...] = waiting

Semaphore (Count = 3) - Connection Pool

Semaphore count: 3

T1 acquire → count=2  
T2 acquire → count=1  
T3 acquire → count=0  
T4 acquire → BLOCKED (count=0)
         ...
T1 release → count=1 → T4 unblocked → count=0

---

Pseudocode Implementation

Mutex: Protecting a Shared Resource

class BankAccount:
    mutex lock
    balance = 0

    deposit(amount):
        lock.lock()
        try:
            balance += amount
        finally:
            lock.unlock()

    withdraw(amount):
        lock.lock()
        try:
            if balance >= amount:
                balance -= amount
                return SUCCESS
            return INSUFFICIENT_FUNDS
        finally:
            lock.unlock()

Semaphore: Connection Pool with Limited Connections

class ConnectionPool:
    semaphore available = MAX_POOL_SIZE
    queue<Connection> pool

    borrow():
        available.acquire()          // blocks if pool exhausted
        synchronized(pool):
            return pool.dequeue()

    returnConn(conn):
        synchronized(pool):
            pool.enqueue(conn)
        available.release()          // wake one waiting thread

ReadWriteLock: Cache with Many Readers, Few Writers

class ThreadSafeCache:
    rwlock lock
    map<String, Object> cache

    get(key):
        lock.readLock()
        try:
            return cache[key]
        finally:
            lock.readUnlock()

    put(key, value):
        lock.writeLock()
        try:
            cache[key] = value
        finally:
            lock.writeUnlock()

    computeIfAbsent(key, loader):
        lock.readLock()
        val = cache[key]
        lock.readUnlock()
        if val != null:
            return val
        lock.writeLock()
        try:
            // double-check after acquiring write lock
            if cache[key] == null:
                cache[key] = loader(key)
            return cache[key]
        finally:
            lock.writeUnlock()

Reentrant Lock: Recursive Method Needing the Same Lock

class TreeNode:
    reentrant_lock lock
    value, children[]

    sumSubtree():
        lock.lock()
        try:
            total = value
            for child in children:
                total += child.sumSubtree()  // re-enters lock if same instance
            return total
        finally:
            lock.unlock()

---

Lock Fairness

Fair vs Unfair Locks

Starvation Prevention

Fair locks maintain an internal queue. When the lock is released, the head of the queue is signaled - not a random waiter. This guarantees bounded wait time proportional to queue length.

Lock convoys: A pathological case where a fair lock causes threads to line up in a convoy - each thread acquires the lock, does minimal work, releases, and re-queues. The overhead of context switching dominates actual work. Solutions include lock coarsening (batching work) or switching to unfair locks.

Performance Trade-off

Unfair locks outperform fair locks by 10-50% in benchmarks because a thread releasing and immediately re-acquiring the lock avoids a context switch. The "barging" optimization allows a thread that happens to request the lock at the exact moment of release to acquire it immediately, skipping the queue.

When to use fair locks:

• Real-time systems with bounded latency requirements
• SLA-bound request processing where tail latency matters
• Systems where starvation causes cascading failures (e.g., health check threads starved → false failure detection)

When unfair locks suffice:

• Throughput-optimized batch processing
• Short critical sections where starvation probability is naturally low
• Systems with homogeneous thread priorities

---

Condition Variables

Condition variables allow threads to wait for a specific predicate to become true, releasing the associated lock while waiting. They decouple "what to wait for" from "how to protect shared state."

Core Operations

• wait() - atomically releases the lock and suspends the thread; upon wakeup, re-acquires the lock before returning
• signal() / notify() - wakes one waiting thread (chosen arbitrarily by the scheduler)
• signalAll() / notifyAll() - wakes all waiting threads (they re-compete for the lock; only one proceeds at a time)

Spurious Wakeups

Operating systems may wake threads without an explicit signal (for implementation efficiency). This is why the wait condition must always be checked in a loop - never a single if statement.

Producer-Consumer with Condition Variables

class BoundedBuffer:
    mutex lock
    condition not_full  = Condition(lock)
    condition not_empty = Condition(lock)
    queue buffer, capacity = N

    produce(item):
        lock.lock()
        while buffer.size() == capacity:
            not_full.wait()            // release lock, sleep
        buffer.enqueue(item)
        not_empty.signal()             // wake one consumer
        lock.unlock()

    consume():
        lock.lock()
        while buffer.size() == 0:
            not_empty.wait()           // release lock, sleep
        item = buffer.dequeue()
        not_full.signal()              // wake one producer
        lock.unlock()
        return item

Key rule: Always use while (not if) around wait() to guard against spurious wakeups.

---

Lock-Free Data Structures

Lock-free algorithms guarantee that at least one thread makes progress in a finite number of steps, even if other threads are suspended or delayed. They eliminate problems like priority inversion, deadlock, and convoying inherent to lock-based approaches.

Progress Guarantees Hierarchy

1. Wait-free - every thread completes in bounded steps (strongest, hardest to implement)
2. Lock-free - at least one thread completes in bounded steps (system-wide progress)
3. Obstruction-free - a thread completes if run in isolation (weakest, needs contention management)

Compare-And-Swap (CAS)

CAS is a hardware-level atomic instruction: CAS(address, expected, new) - atomically sets *address = new only if *address == expected, returning success/failure.

class LockFreeCounter:
    atomic value = 0

    increment():
        loop:
            current = value
            if CAS(value, current, current + 1):
                return              // success
            // else: another thread changed it  -  retry

Lock-Free Stack (Treiber Stack)

class LockFreeStack:
    atomic top = null

    push(node):
        loop:
            node.next = top
            if CAS(top, node.next, node):
                return

    pop():
        loop:
            head = top
            if head == null: return null
            if CAS(top, head, head.next):
                return head

The ABA Problem

Thread reads value A, gets preempted. Another thread changes A→B→A. First thread's CAS succeeds (sees A) but the underlying structure has changed.

Solutions:

• Tagged pointers - append a version counter (A₁ → B₂ → A₃ - CAS fails because stamp differs)
• Hazard pointers - defer reclamation of nodes still referenced
• Epoch-based reclamation - batch-free memory after all threads advance past the epoch

---

Real-World Examples

Database Row-Level Locks

Databases use shared (S) and exclusive (X) locks on rows. SELECT ... FOR UPDATE acquires an X-lock preventing other transactions from reading or writing; SELECT ... FOR SHARE acquires an S-lock allowing concurrent reads but blocking writes. Lock escalation promotes row locks to page/table locks under high contention to reduce memory overhead of tracking thousands of individual row locks.

Isolation levels and locking: Under SERIALIZABLE, range locks prevent phantom reads. Under READ COMMITTED, locks are released after each statement. Understanding these trade-offs is critical for designing systems that balance consistency with throughput.

File Locks

POSIX flock() provides whole-file advisory locks; fcntl() supports byte-range locks for fine-grained file region locking. Mandatory locks (rare, supported on some Linux filesystems with special mount options) are enforced by the kernel at the I/O layer.

Common patterns:

• PID files for single-instance enforcement (e.g., only one cron job instance)
• Log rotation coordination between writer and rotator processes
• Database WAL (Write-Ahead Log) file access coordination

Distributed Locks

• Redis (Redlock): Acquire locks across N independent Redis nodes (typically 5); lock is valid if majority (N/2+1) grant it within a TTL. The algorithm provides reasonable guarantees for efficiency-based locking (preventing duplicate work) but is debated for correctness-based locking (preventing data corruption) under network partitions and clock skew.

• ZooKeeper: Ephemeral sequential znodes provide ordered, fault-tolerant locks. A client creates /lock/node-0000000001; it holds the lock if its znode has the lowest sequence number. Session expiry auto-releases locks. Stronger guarantees than Redis but higher latency (~10-50ms vs ~1-5ms). Used by Kafka, HBase, and Hadoop for leader election and coordination.

• etcd: Similar to ZooKeeper but uses Raft consensus. Lease-based locks with automatic expiry. Kubernetes uses etcd for distributed coordination.

Connection Pool Semaphores

Libraries like HikariCP (Java) and pgbouncer (PostgreSQL) use semaphores internally to bound the number of active connections. When all connections are in use, requesting threads block on acquire() until one is returned. This prevents overwhelming the database with unbounded connections while providing backpressure to the application layer.

Configuration considerations: Pool size = ((core_count * 2) + effective_spindle_count) is a common starting formula for database connection pools. Too large wastes database resources; too small creates unnecessary queuing.

---

Comparison Table

---

Constraints & Edge Cases

Lock Ordering (Deadlock Prevention)

Always acquire multiple locks in a globally consistent order. If Thread-A holds Lock-1 and waits for Lock-2, while Thread-B holds Lock-2 and waits for Lock-1 - deadlock.

Strategies:

• Assign a numeric ID to each lock; always acquire in ascending order
• Use a lock hierarchy (application layer → service layer → data layer)
• Use tryLock with backoff - if second lock unavailable, release first and retry
• Lock ordering violations can be detected statically with tools like ThreadSanitizer or FindBugs

Try-Lock with Timeout

if lock.tryLock(timeout=500ms):
    try:
        // critical section
    finally:
        lock.unlock()
else:
    // fallback: retry, fail fast, or use alternative path
    metrics.increment("lock.timeout")
    throw TimeoutException("Could not acquire lock within 500ms")

Prevents indefinite blocking. Essential in latency-sensitive services where holding a request for seconds is worse than failing fast. Circuit breaker patterns often wrap try-lock failures.

Lock Contention Measurement

• Metrics to track: Lock wait time (P50, P99), hold time, acquisition failure rate, queue depth
• Tools: Java's jstack for thread dumps, perf lock on Linux, JMH microbenchmarks, async-profiler lock profiling mode
• Symptom patterns:
  • High CPU with low throughput → spin-lock contention
  • Many BLOCKED threads in dumps → lock convoy
  • Periodic latency spikes → GC pausing lock holder, causing thundering herd on release

Lock Granularity

ConcurrentHashMap example: Uses lock striping - 16 segments (Java 7) or per-bin CAS (Java 8+), allowing concurrent writes to different buckets without contention.

Lock Coarsening vs Lock Elision

• Lock coarsening: JVM optimization that merges adjacent lock/unlock sequences on the same lock into a single larger critical section, reducing lock overhead
• Lock elision: JVM detects via escape analysis that a lock is thread-local (object never escapes the thread) and removes the lock entirely

---

Interview Follow-ups

Q1: How would you implement a timeout-based deadlock detection system?

A: Maintain a wait-for graph where nodes are threads and edges represent "waiting for lock held by." Periodically (or on timeout) run cycle detection (DFS). If a cycle is found, select a victim thread to abort - typically the one with the least work done or lowest priority. Alternatively, use tryLock with timeouts so threads self-detect potential deadlocks and back off.

Q2: Why might a ReadWriteLock perform worse than a simple Mutex under write-heavy workloads?

A: ReadWriteLock has higher overhead per operation (managing reader counts atomically, writer exclusion logic). If writes dominate, threads constantly compete for the exclusive lock while paying the extra bookkeeping cost. A simple mutex has lower per-operation overhead and avoids the reader-count contention. The crossover point is typically around 90%+ reads for RWLock to win.

Q3: Explain how StampedLock's optimistic read can lead to inconsistent reads and how to handle it.

A: During an optimistic read, no lock is held - a concurrent writer can modify data mid-read. The reader may observe a torn state (e.g., reading X and Y where X is pre-update and Y is post-update). After reading, validate(stamp) checks if any write occurred. If validation fails, the reader must retry or escalate to a pessimistic read lock. Never use optimistic reads for operations with side effects.

Q4: Design a fair reader-writer lock that prevents writer starvation.

Hint: Consider a policy where once a writer is waiting, new readers queue behind it rather than acquiring the shared lock. Think about maintaining separate queues for readers and writers with a "writer-preference" flag.

Q5: How would you implement a distributed lock that handles split-brain scenarios?

Hint: Think about fencing tokens - monotonically increasing values attached to each lock acquisition. The protected resource rejects operations with stale tokens. Consider how ZooKeeper's sequential znodes naturally provide this ordering.

---

Counter Questions to Ask Interviewer

1. "What's the read-to-write ratio of the shared resource?" - Determines whether a ReadWriteLock, StampedLock, or simple Mutex is appropriate.

2. "Is the critical section CPU-bound or I/O-bound?" - CPU-bound short sections favor spin locks; I/O-bound sections need blocking locks to avoid wasting CPU cycles.

3. "Do we need to support lock acquisition across multiple nodes, or is this single-process?" - Distinguishes between in-process locks and distributed locks (Redis/ZooKeeper), which have fundamentally different failure modes.

4. "What's the acceptable latency for lock acquisition? Is there a timeout requirement?" - Drives the choice between blocking locks, try-lock with timeout, or lock-free approaches.

5. "Are there ordering constraints between multiple locks, or is it always a single lock?" - Reveals deadlock risk and whether lock ordering protocols or lock hierarchies are needed.

---

References & Whitepapers

• The Art of Multiprocessor Programming - Maurice Herlihy & Nir Shavit. Comprehensive coverage of lock-free algorithms, spin locks, and concurrent data structures from first principles.
• Java Concurrency in Practice - Brian Goetz et al. Practical guide to java.util.concurrent locks, conditions, and atomic variables.
• Mellor-Crummey & Scott, 1991 - "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors" - foundational paper on MCS and CLH queue locks.
• Herlihy, 1991 - "Wait-Free Synchronization" - proves universality of CAS for wait-free implementations.
• Redlock Algorithm - Martin Kleppmann's critique ("How to do distributed locking") and Salvatore Sanfilippo's response - essential reading for distributed lock trade-offs.
• Leslie Lamport - "The Mutual Exclusion Problem" (1986) - formal treatment of fairness and bounded waiting.

---

Related Topics

• 01 - Introduction to Multithreading
• 02 - Thread Lifecycle and States
• 03 - Race Conditions and Critical Sections
• 04 - Deadlocks, Livelocks, and Starvation
• 06 - Thread Pools and Executors
• 07 - Concurrent Data Structures
• 08 - Atomic Variables and CAS Operations