Locks and Synchronization

A mutex (mutual exclusion lock) has two operations: lock() and unlock(). At most one thread holds the mutex at a time; every other caller blocks until it is released. The region between lock and unlock is the critical section.

Correct mutex usage in Python:

import threading

_lock = threading.Lock()
_counter = 0

def safe_increment():
    global _counter
    with _lock:          # acquires on entry, releases on exit — even on exception
        _counter += 1

Key rules:

• Always use the same lock for a given piece of shared data. One unprotected access defeats the mutex entirely.
• Prefer RAII / context managers. Manual lock() / unlock() leaks on exceptions. Python's with, C++'s std::lock_guard, Go's defer mu.Unlock() all enforce this.
• Keep critical sections short. Every nanosecond inside the lock is a nanosecond other threads are blocked.

A deadlock is a cycle of threads, each waiting for a resource held by the next. Coffman (1971) identified four necessary and sufficient conditions — break any one and deadlock is impossible:

In practice, mutual exclusion and no preemption are inherent to mutexes — you can't easily remove them. Circular wait is the one you attack: establish a global lock ordering and always acquire locks in that order. If every thread locks mutex A before mutex B, the A→B→A cycle is impossible.

Classic two-thread, two-lock deadlock:

import threading, time

lock_a = threading.Lock()
lock_b = threading.Lock()

def thread1():
    with lock_a:
        time.sleep(0.01)  # yield to let thread2 grab lock_b
        with lock_b:      # blocks forever — thread2 holds lock_b
            print("T1 done")

def thread2():
    with lock_b:
        time.sleep(0.01)
        with lock_a:      # blocks forever — thread1 holds lock_a
            print("T2 done")

threading.Thread(target=thread1).start()
threading.Thread(target=thread2).start()
# Neither thread ever prints. Program hangs.

Fix — consistent lock ordering: both threads acquire lock_a then lock_b. If thread2 changes its first acquisition to lock_a, the cycle vanishes. threading.Lock() also supports acquire(timeout=...) to detect deadlocks and threading.RLock() for re-entrant acquisition in the same thread.

A condition variable pairs with a mutex to let a thread sleep until a condition holds. The canonical pattern:

import threading

_lock = threading.Lock()
_cond = threading.Condition(_lock)
_queue = []

def producer(item):
    with _cond:
        _queue.append(item)
        _cond.notify()         # wake one waiting consumer

def consumer():
    with _cond:
        while not _queue:      # MUST be a while loop, not if
            _cond.wait()       # atomically releases lock, sleeps, reacquires on wake
        return _queue.pop(0)

The while loop is mandatory, not optional. Spurious wakeups — where wait() returns without notify() being called — are permitted by POSIX and by Python's implementation. Without the loop, the consumer may proceed with an empty queue. Always re-check the predicate after waking.

A semaphore generalizes a mutex to count up to $N$ concurrent holders. Two operations:

• P() / acquire() — decrement; block if count is already 0.
• V() / release() — increment; wake a blocked waiter if any.

A binary semaphore ($N=1$) is equivalent to a mutex. A counting semaphore with $N=5$ allows up to 5 threads to hold it simultaneously — useful for bounding concurrency on a shared resource pool (DB connections, HTTP clients):

import threading

_pool = threading.Semaphore(5)  # at most 5 concurrent DB connections

def run_query(sql):
    with _pool:                  # blocks if 5 connections already in use
        conn = db.connect()
        result = conn.execute(sql)
        conn.close()
        return result

Gotcha: unlike mutexes, semaphores have no concept of ownership. Any thread can call release(), even one that never called acquire(). This makes them powerful for signaling but dangerous if misused — a stray release() breaks the bound.

Most data is read far more often than written. A plain mutex serializes all readers too, wasting concurrency. A reader-writer lock (rwlock) allows:

• Multiple concurrent readers (no writer active)
• Exactly one writer, with all readers excluded

import java.util.concurrent.locks.*;

ReadWriteLock rwl = new ReentrantReadWriteLock();
Map<String, String> cache = new HashMap<>();

void put(String k, String v) {
    rwl.writeLock().lock();
    try { cache.put(k, v); }
    finally { rwl.writeLock().unlock(); }
}

String get(String k) {
    rwl.readLock().lock();
    try { return cache.get(k); }
    finally { rwl.readLock().unlock(); }
}

Read-heavy workloads can see 10× lower latency with rwlocks. However, if writes are frequent, write-lock contention turns the rwlock into a bottleneck. Measure before adopting — the implementation overhead is higher than a plain mutex.

Thread A holds Lock 1 and wants Lock 2; Thread B holds Lock 2 and wants Lock 1. Neither can proceed.

When many threads compete for the same lock, most spend most of their time blocked — this is contention. A particularly nasty form is lock convoying: a long-running thread holds a lock; other threads queue behind it; when it releases, the next thread in the OS scheduling queue acquires it, but that thread may immediately be preempted before doing useful work, while the rest of the convoy still waits. Throughput collapses.

Strategies to reduce contention:

• Fine-grained locking: one lock per data structure element instead of one global lock. More complexity, less contention.
• Lock-free data structures: compare-and-swap instead of mutual exclusion (covered in the next lesson).
• Sharding: partition data into $N$ independent buckets, each with its own lock. Reduces contention by $N\times$ for uniformly distributed accesses.
• Reduce critical section duration: do expensive computation outside the lock; only touch shared state inside.

Contention is measurable. Linux perf, Java's JFR, and Go's pprof mutexprofile all expose lock wait time directly.

Choosing wrong costs correctness or performance:

Common mistakes:

• Using a semaphore as a mutex (no ownership, any thread can release).
• Polling a condition variable with sleep() instead of wait() — wastes CPU and delays response.
• Using notify() when you should use notifyAll() — if multiple threads wait on different predicates and you only wake one, you may wake the wrong one, leaving the other stuck forever.