Free lesson · Operating Systems

Demonstration

Easy13 min readoperating-systemsosconcurrency

From Spinning to Sleeping

In Topic 1 you saw that hardware atomic instructions like test-and-set and compare-and-swap can solve the critical section problem. But the simple spinlock implementations using those instructions have a major flaw: they burn CPU cycles while waiting. A thread that cannot acquire the lock sits in a tight loop checking the lock variable millions of times per second, consuming its entire CPU time slice doing nothing useful.

For critical sections that last a few microseconds - the time it takes to update a counter or flip a flag - spinning is fine. The thread grabs the lock almost immediately, and the wasted cycles are negligible. But for critical sections that might take milliseconds or longer - database queries, file I/O, network requests - spinning is catastrophically wasteful. A thread spinning for 10 milliseconds on a 3 GHz processor executes 30 million useless loop iterations. That is 30 million opportunities to do actual work, thrown away.

A mutex (short for mutual exclusion) solves this by combining a hardware atomic operation with OS scheduling. When a thread cannot acquire the lock, instead of spinning, it tells the OS to put it to sleep. The OS removes the thread from the CPU and does not schedule it again until the lock is released. When the lock holder releases the lock, the OS wakes up one waiting thread and lets it acquire the lock and run.

This approach trades spinning overhead for context-switch overhead. A context switch costs roughly 1-10 microseconds depending on the platform. If the lock is held for less than two context switches worth of time, spinning is actually faster. If the lock is held for longer, sleeping wins because the CPU can run other threads instead of wasting cycles. This is why modern systems have both spinlocks (for short critical sections in kernel code) and mutexes (for longer critical sections in application code).

How a Mutex Works Internally

A mutex is a data structure maintained by the OS or threading library that contains three components:

A lock state - a single bit or integer indicating whether the mutex is currently locked (held by some thread) or unlocked (available). This is the variable that the atomic instruction operates on.

An owner - the identity of the thread that currently holds the lock. The owner field serves two purposes: it enables error detection (trying to unlock a mutex you do not own is a bug), and it enables recursive locking (some mutex implementations allow the owner to lock the same mutex multiple times without deadlocking).

A wait queue - a list of threads that tried to acquire the mutex while it was locked and are now sleeping. When the mutex is released, the OS picks one thread from this queue and wakes it up.

The lock and unlock operations work as follows:

Lock (acquire): The thread executes an atomic compare-and-swap on the lock state: "if the state is UNLOCKED, change it to LOCKED." If the CAS succeeds, the thread now owns the mutex and enters its critical section. If the CAS fails (the mutex was already locked), the thread adds itself to the wait queue and calls the OS scheduler to put itself to sleep. The thread does not return from the lock call until it holds the mutex.

Unlock (release): The thread sets the lock state back to UNLOCKED. If the wait queue is not empty, the OS removes one thread from the queue and wakes it up. That thread's pending lock call now succeeds, and it enters its critical section.

sequenceDiagram
    participant TA as Thread A
    participant M as Mutex<br/>(state: UNLOCKED<br/>queue: empty)
    participant OS as OS Scheduler
    participant TB as Thread B
    
    TA->>M: lock() - CAS(UNLOCKED → LOCKED)
    Note over M: state: LOCKED<br/>owner: Thread A
    Note over TA: Enters critical section
    
    TB->>M: lock() - CAS fails (LOCKED)
    TB->>M: Add to wait queue
    TB->>OS: Put me to sleep
    Note over TB: SLEEPING
    
    Note over TA: Exits critical section
    TA->>M: unlock()
    Note over M: state: UNLOCKED
    M->>OS: Wake Thread B
    OS->>TB: You are runnable
    TB->>M: CAS(UNLOCKED → LOCKED)
    Note over M: state: LOCKED<br/>owner: Thread B
    Note over TB: Enters critical section

This sequence diagram shows how a mutex works. Thread A calls lock, the compare-and-swap succeeds because the mutex is unlocked, and Thread A enters the critical section. Thread B calls lock, but the compare-and-swap fails because the mutex is locked. Thread B adds itself to the wait queue and tells the OS to put it to sleep. When Thread A finishes and calls unlock, the OS wakes Thread B. Thread B's pending lock call succeeds, and Thread B enters the critical section.

Using Mutexes in Practice

Every major programming language and threading library provides a mutex implementation. The API is almost always the same: create, lock, unlock, destroy. The syntax varies but the semantics are identical.

POSIX Threads (C/C++)

#include <pthread.h>

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int shared_counter = 0;

void *thread_function(void *arg) {
    for (int i = 0; i < 100000; i++) {
        pthread_mutex_lock(&lock);      // Acquire - blocks if held
        shared_counter++;                // Critical section
        pthread_mutex_unlock(&lock);    // Release - wakes a waiter
    }
    return NULL;
}

Python (threading module)

import threading

lock = threading.Lock()
counter = 0

def worker():
    global counter
    for _ in range(100000):
        with lock:           # Acquire on entry, release on exit
            counter += 1     # Critical section

threads = [threading.Thread(target=worker) for _ in range(4)]
for t in threads:
    t.start()
for t in threads:
    t.join()

print(f"Counter: {counter}")
print(f"Expected: 400000")
print(f"Correct: {counter == 400000}")

Java (synchronized and ReentrantLock)

// Option 1: synchronized keyword (implicit mutex on the object)
public class Counter {
    private int count = 0;
    
    public synchronized void increment() {
        count++;  // Only one thread can be here at a time
    }
}

// Option 2: Explicit ReentrantLock
import java.util.concurrent.locks.ReentrantLock;

public class Counter {
    private int count = 0;
    private final ReentrantLock lock = new ReentrantLock();
    
    public void increment() {
        lock.lock();
        try {
            count++;
        } finally {
            lock.unlock();  // ALWAYS unlock in finally
        }
    }
}

Go (sync.Mutex)

import "sync"

var (
    mu      sync.Mutex
    counter int
)

func worker(wg *sync.WaitGroup) {
    defer wg.Done()
    for i := 0; i < 100000; i++ {
        mu.Lock()
        counter++
        mu.Unlock()
    }
}

Tip: In every language, the pattern is the same: acquire before the critical section, release after, and always release - even if the critical section throws an exception. Python's with statement, Java's try/finally, and Go's defer are all language features designed to guarantee that the unlock happens even when things go wrong. Forgetting to unlock a mutex is one of the most common concurrency bugs, and it deadlocks your entire program.

Mutex Properties and Variants

Not all mutexes are the same. Different implementations offer different guarantees, and knowing the differences matters for both production code and interviews.

Recursive vs Non-Recursive Mutexes

A non-recursive (or non-reentrant) mutex deadlocks if the thread that holds it tries to lock it again. The thread is waiting for itself to release the lock, which will never happen.

lock = threading.Lock()  # Non-recursive in Python

def outer():
    with lock:
        inner()   # DEADLOCK - outer already holds the lock

def inner():
    with lock:    # Blocks forever waiting for outer to release
        pass

A recursive (or reentrant) mutex allows the same thread to lock it multiple times. The mutex keeps a count of how many times it has been locked and only truly unlocks when the count reaches zero.

import threading

rlock = threading.RLock()  # Recursive lock in Python
counter = 0

def outer():
    global counter
    with rlock:
        counter += 1
        inner()   # No deadlock - same thread, recursive lock

def inner():
    global counter
    with rlock:    # Succeeds - same thread owns the lock
        counter += 10

outer()
print(f"Counter: {counter}")  # 11

When to use recursive mutexes: When a function that holds the lock calls another function that also needs the lock. This happens often in object-oriented code where methods call other methods on the same object, and each method individually needs to be thread-safe.

The argument against recursive mutexes: They can hide design problems. If you need recursive locking, it might mean your lock granularity is wrong - you are locking at too high a level and should restructure the code so that the inner function does not need the lock independently. Many experienced concurrency programmers prefer non-recursive mutexes because they surface these design issues as immediate deadlocks rather than hiding them.

Fair vs Unfair Mutexes

When the lock is released and multiple threads are waiting, which one gets it?

An unfair mutex does not guarantee any ordering. The OS might wake any waiting thread, or a thread that arrives at exactly the right moment might grab the lock before any waiting thread gets a chance. Unfair mutexes can cause starvation - one thread keeps getting skipped while others keep grabbing the lock.

A fair mutex uses a FIFO queue: threads acquire the lock in the order they requested it. No thread can be starved because the queue guarantees bounded waiting. Java's ReentrantLock supports fairness as an explicit constructor parameter: new ReentrantLock(true) creates a fair lock.

The tradeoff is performance. Unfair mutexes are faster because they avoid the overhead of maintaining a strict queue. On many workloads, unfair mutexes have 10-30% higher throughput. Fair mutexes have predictable latency but lower overall throughput.

Property	Unfair Mutex	Fair Mutex
Ordering	No guarantee	FIFO
Starvation possible	Yes	No
Throughput	Higher	Lower
Latency predictability	Low	High
Default in most systems	Yes	No

Read-Write Mutexes (RWLock)

A standard mutex allows only one thread at a time, regardless of whether the thread is reading or writing. But if the shared data is read far more often than it is written, this is unnecessarily restrictive - multiple readers could safely access the data simultaneously.

A read-write lock (or RWLock) distinguishes between readers and writers:

Multiple readers can hold the lock simultaneously (shared access)
Only one writer can hold the lock, and no readers can hold it at the same time (exclusive access)
A writer waiting for the lock blocks new readers from acquiring it (to prevent writer starvation)

import threading
import time

class SimpleRWLock:
    """A basic read-write lock implementation for demonstration."""
    def __init__(self):
        self._readers = 0
        self._lock = threading.Lock()        # Protects _readers count
        self._write_lock = threading.Lock()  # Exclusive access for writers
    
    def acquire_read(self):
        with self._lock:
            self._readers += 1
            if self._readers == 1:
                self._write_lock.acquire()   # First reader blocks writers
    
    def release_read(self):
        with self._lock:
            self._readers -= 1
            if self._readers == 0:
                self._write_lock.release()   # Last reader unblocks writers
    
    def acquire_write(self):
        self._write_lock.acquire()           # Exclusive access
    
    def release_write(self):
        self._write_lock.release()

# Demonstration
rwlock = SimpleRWLock()
data = {"value": 0}
log = []

def reader(reader_id):
    rwlock.acquire_read()
    val = data["value"]
    log.append(f"Reader {reader_id} read: {val}")
    rwlock.release_read()

def writer(new_value):
    rwlock.acquire_write()
    data["value"] = new_value
    log.append(f"Writer set value to: {new_value}")
    rwlock.release_write()

threads = []
for i in range(5):
    threads.append(threading.Thread(target=reader, args=(i,)))
threads.append(threading.Thread(target=writer, args=(42,)))
for i in range(5, 10):
    threads.append(threading.Thread(target=reader, args=(i,)))

for t in threads:
    t.start()
for t in threads:
    t.join()

for entry in log:
    print(entry)

Read-write locks are used in database systems (readers can query simultaneously, writers get exclusive access), configuration management (many threads read config, rare updates need exclusivity), and caching layers (concurrent reads, exclusive cache invalidation).

Interview: "When would you use a mutex vs a read-write lock?"

"A standard mutex is simpler and should be the default choice. I would switch to a read-write lock when two conditions are met: the shared data is read significantly more often than it is written (at least a 10:1 read-to-write ratio), and the critical section is long enough that the cost of serializing readers is noticeable.

If the critical section is short - a few microseconds - the overhead of the read-write lock's more complex internal bookkeeping can outweigh the benefit of concurrent reads. And if reads and writes are roughly equally frequent, a read-write lock provides little advantage because writes still require exclusive access.

In production, read-write locks shine in caches, configuration stores, and in-memory databases where data changes infrequently but is queried constantly."

Follow-up: "What is the starvation problem with read-write locks?"

"If readers continuously hold the lock, a writer might wait indefinitely - new readers keep arriving and acquiring shared access before the writer gets a chance. This is the writer starvation problem. The fix is a write-preferring policy: once a writer is waiting, new readers are blocked until the writer has had its turn. Most production implementations (like Java's ReentrantReadWriteLock) default to this policy."

The Danger of Incorrect Mutex Usage

Mutexes solve the critical section problem, but they introduce their own failure modes. Using a mutex incorrectly can produce bugs that are worse than the race conditions they were supposed to prevent.

Forgetting to Unlock

If a thread acquires a mutex and then encounters an exception, a return statement, or a goto before the unlock call, the mutex is never released. Every other thread that tries to acquire it will block forever. The program hangs.

This is why every language has a pattern for guaranteed unlock: Python's with statement, Java's try/finally, Go's defer, C++'s std::lock_guard (RAII). Use them without exception.

# BROKEN - exception before unlock
lock.acquire()
result = risky_operation()  # If this throws, lock is never released
lock.release()

# FIXED - with statement guarantees release
with lock:
    result = risky_operation()  # Even if this throws, lock is released

Locking the Wrong Mutex

If two pieces of code access the same shared data but protect it with different mutexes, the protection is useless. Each mutex only synchronizes the threads that use it - using mutex A for some accesses and mutex B for others provides no mutual exclusion between those accesses.

# BROKEN - two different locks for the same data
lock_a = threading.Lock()
lock_b = threading.Lock()
shared_counter = 0

# Thread 1 uses lock_a
with lock_a:
    shared_counter += 1

# Thread 2 uses lock_b - NOT mutually exclusive with lock_a
with lock_b:
    shared_counter += 1

# Both threads can be in their "critical sections" simultaneously

This bug is more common than you might think, especially in large codebases where the same data is accessed from multiple files or modules and each developer assumes someone else set up the locking.

Holding Locks Too Long

A mutex that is held while performing a slow operation (network request, disk I/O, database query) blocks every other thread that needs that lock for the entire duration. This turns a concurrent program into a sequential one.

The fix is to minimize the critical section: hold the lock only for the actual shared-state access, and do any slow work outside the lock.

# BROKEN - lock held during slow network call
with lock:
    data = read_shared_data()
    result = slow_network_call(data)    # Other threads blocked for seconds
    write_shared_data(result)

# FIXED - minimize critical section
with lock:
    data = read_shared_data()           # Fast: read shared state

result = slow_network_call(data)        # Slow: done outside the lock

with lock:
    write_shared_data(result)           # Fast: write shared state

Deadlock: The Mutex Death Spiral

Deadlock is the most severe mutex failure mode. It occurs when two threads each hold a lock that the other thread needs, and neither can make progress. Both threads wait forever.

# DEADLOCK scenario
lock_1 = threading.Lock()
lock_2 = threading.Lock()

# Thread A                          # Thread B
lock_1.acquire()                    lock_2.acquire()
# ... does some work ...            # ... does some work ...
lock_2.acquire()  # BLOCKED         lock_1.acquire()  # BLOCKED
# Waiting for Thread B              # Waiting for Thread A
# to release lock_2                 # to release lock_1
# DEADLOCK - neither can proceed

graph LR
    TA["Thread A<br/>holds Lock 1"] -->|"waiting for"| L2["Lock 2<br/>held by Thread B"]
    TB["Thread B<br/>holds Lock 2"] -->|"waiting for"| L1["Lock 1<br/>held by Thread A"]
    
    style TA fill:#dc2626,stroke:#b91c1c,color:#fff
    style TB fill:#dc2626,stroke:#b91c1c,color:#fff
    style L1 fill:#4f46e5,stroke:#4338ca,color:#fff
    style L2 fill:#4f46e5,stroke:#4338ca,color:#fff

This diagram shows a deadlock between two threads. Thread A holds Lock 1 and is waiting for Lock 2. Thread B holds Lock 2 and is waiting for Lock 1. Both threads are blocked, waiting for each other, and neither can make progress. This is a circular dependency that results in a deadlock.

Deadlock requires four conditions to be true simultaneously (the Coffman conditions):

Mutual exclusion - the resources are non-shareable (only one thread can hold a lock)
Hold and wait - a thread holds one resource while waiting for another
No preemption - locks cannot be forcibly taken from a thread
Circular wait - a cycle of threads, each waiting for a lock held by the next

Breaking any one condition prevents deadlock. The most practical strategy is to prevent circular wait by ordering locks - always acquire locks in a consistent global order. If every thread acquires Lock 1 before Lock 2, no thread can hold Lock 2 while waiting for Lock 1, and the cycle cannot form.

Mutex Performance Considerations

In interviews and production code, understanding mutex performance helps you make the right tradeoff.

Uncontended lock cost: When no other thread holds the mutex, acquiring and releasing it costs roughly 25-100 nanoseconds - the time for the atomic CAS instruction plus the function call overhead. This is fast enough that you should not hesitate to use mutexes for correctness.

Contended lock cost: When another thread holds the mutex, the acquiring thread goes to sleep (context switch: 1-10 microseconds), waits, and then wakes up (another context switch). The total cost is 2-20 microseconds of overhead plus the actual wait time. If many threads contend on the same mutex, throughput drops because threads spend most of their time sleeping and waking rather than doing work.

Lock granularity tradeoff: A single global lock (coarse-grained locking) is simple but limits concurrency - only one thread can do work at a time. Many fine-grained locks allow more concurrency but increase complexity and the risk of deadlock. The right granularity depends on the workload: if different threads typically access different data, fine-grained locks help. If all threads access the same data, a single lock is simpler and not much slower.

Granularity	Concurrency	Complexity	Deadlock Risk	Example
Single global lock	Lowest	Lowest	None	Python's GIL
Per-object lock	Medium	Medium	Low	Java synchronized methods
Per-field lock	High	High	Medium	ConcurrentHashMap segments
Lock-free (atomics)	Highest	Highest	None	Lock-free queue

Exercise: Starter: Write a Python program that creates two threads. Each thread increments a shared counter 500,000 times without any lock. Run it and observe the final count. Then add a threading.Lock() and verify the count is correct. Measure the execution time with and without the lock using time.time().

Intermediate: Implement a thread-safe bank account class in Python with deposit(), withdraw(), and balance() methods, each protected by a mutex. Then implement a transfer(from_account, to_account, amount) function that locks both accounts to perform an atomic transfer. Be careful about deadlock - use lock ordering (lock the account with the smaller ID first) to prevent it. Test with 10 accounts and 100 concurrent transfer threads.

Advanced: Write a reader-writer lock from scratch in C using pthread_mutex_t and pthread_cond_t (condition variables from Topic 5). Implement read_lock(), read_unlock(), write_lock(), and write_unlock(). Test it with 8 reader threads and 2 writer threads, each performing 100,000 operations. Compare the throughput to a plain pthread_mutex_t protecting all operations.

Back to Operating Systems