BookOps/

Shared Space

Two strangers reach for the last apple. Their hands collide. This is a race condition---the outcome depends on who gets there first.

When concurrent activities share mutable state, timing becomes fate. The same program, run twice, might produce different results. This chapter explores the dangers of shared mutable state and the mechanisms we use to tame them.

The Race

Let's revisit our counter:

    counter = 0
    
    // Thread A            // Thread B
    counter = counter + 1  counter = counter + 1

Both threads increment. We expect counter to be 2. But consider the interleaving:

    Thread A:                   Thread B:
    
    read counter (= 0)
                                read counter (= 0)
    compute 0 + 1 = 1
                                compute 0 + 1 = 1
    write counter = 1
                                write counter = 1
    
    // Result: counter = 1, not 2

Both threads did their job correctly. But the combination is wrong. This is a race condition: the result depends on which thread wins the race.

Data Races vs Race Conditions

Two related but distinct concepts:

Data race: Two threads access the same memory location, at least one writes, with no synchronization. This is a bug by definition---undefined behavior in most languages.

Race condition: Program behavior depends on timing. This is a logic bug---the program doesn't do what you intended.

python
    // Data race: unsynchronized write/read
    shared = 0
    Thread A: shared = 1
    Thread B: print(shared)  // Might print 0 or 1
    
    // Race condition: logic depends on timing
    if not file_exists("lock"):
        create_file("lock")
        // Another thread might create it between check and create!

Critical Sections

The dangerous code---where shared state is accessed---is called a critical section. The solution is ensuring only one thread executes it at a time.

    counter = 0
    
    // Critical section: this must not interleave
    increment():
        counter = counter + 1

We need mutual exclusion: a way to say "while I'm in here, no one else can enter."

Locks

The most common tool is a lock (or mutex, for "mutual exclusion"):

python
    counter = 0
    lock = new Lock()
    
    increment():
        lock.acquire()         // Wait until lock is available, then take it
        counter = counter + 1  // Safe: we have exclusive access
        lock.release()         // Let others in

When Thread A holds the lock, Thread B's acquire() blocks---waits---until A releases. No interleaving of the critical section.

    Thread A:                   Thread B:
    
    acquire lock (success)
                                acquire lock (blocked...)
    read counter (= 0)
    compute 0 + 1 = 1
    write counter = 1
    release lock
                                acquire lock (success!)
                                read counter (= 1)
                                compute 1 + 1 = 2
                                write counter = 2
                                release lock
    
    // Result: counter = 2. Correct!

The Dangers of Locks

Locks solve the race condition but introduce new dangers:

Deadlock

Imagine two people at a table, each wanting to eat. To eat, you need both a fork and a knife. Person A grabs the fork. Person B grabs the knife. Now A waits for the knife that B holds, while B waits for the fork that A holds.

python
    // Person A                 // Person B
    fork.acquire()              knife.acquire()
    knife.acquire()  // wait    fork.acquire()  // wait

    // Both waiting forever. Both starve.

Person A holds the fork, wants the knife. Person B holds the knife, wants the fork. Neither can proceed. The system is frozen.

In code:

python
    // Thread A                 // Thread B
    lock1.acquire()             lock2.acquire()
    lock2.acquire()  // wait    lock1.acquire()  // wait

    // Both waiting forever!

Starvation

One thread keeps acquiring the lock before others can. Some threads never make progress.

Priority Inversion

A low-priority thread holds a lock needed by a high-priority thread. The high-priority thread is effectively demoted.

Convoying

Many threads pile up waiting for a popular lock, even if each holds it briefly. The lock becomes a bottleneck.

Lock Granularity

How much should one lock protect?

Coarse-grained: One lock for everything.

wollok
    big_lock = new Lock()
    
    any_operation():
        big_lock.acquire()
        // ... do anything ...
        big_lock.release()

Simple and safe, but threads wait even when accessing unrelated data.

Fine-grained: Many locks for different data.

wollok
    account_locks = {}  // One lock per account
    
    transfer(from, to, amount):
        account_locks[from].acquire()
        account_locks[to].acquire()
        // ... transfer ...
        account_locks[to].release()
        account_locks[from].release()

More parallelism, but harder to get right. (This code can deadlock!)

Atomic Operations

For simple updates, locks may be overkill. Atomic operations provide thread-safe updates without locks:

    atomic_counter = new AtomicInteger(0)
    
    increment():
        atomic_counter.increment()  // Thread-safe, no lock needed

Common atomic operations:

  • increment, decrement
  • compare_and_swap: "if value is X, change to Y"
  • fetch_and_add: "add N, return old value"
python
    // Compare-and-swap (CAS)
    success = atomic.compareAndSwap(expected: 5, new: 6)
    // If current value is 5, set to 6 and return true
    // Otherwise, leave unchanged and return false

Higher-Level Constructs

Locks are low-level. Many languages offer higher-level synchronization:

Synchronized blocks: Automatic acquire/release.

    synchronized(lock) {
        // Lock is held for this block
        counter = counter + 1
    }  // Automatically released, even if exception thrown

Read-write locks: Multiple readers, single writer.

wollok
    rwlock = new ReadWriteLock()
    
    read_data():
        rwlock.read_acquire()   // Many readers allowed
        result = shared_data
        rwlock.read_release()
        return result
    
    write_data(value):
        rwlock.write_acquire()  // Exclusive: no readers or writers
        shared_data = value
        rwlock.write_release()

Semaphores: Allow N threads (not just 1) into a section.

wollok
    pool = new Semaphore(5)  // Allow 5 concurrent threads
    
    use_connection():
        pool.acquire()  // Wait if 5 already in
        // ... use connection ...
        pool.release()

Condition variables: Wait for a condition to be true.

wollok
    queue = []
    lock = new Lock()
    not_empty = new Condition(lock)
    
    consume():
        lock.acquire()
        while queue.isEmpty():
            not_empty.wait()  // Release lock and sleep until signaled
        item = queue.pop()
        lock.release()
        return item
    
    produce(item):
        lock.acquire()
        queue.push(item)
        not_empty.signal()  // Wake one waiting consumer
        lock.release()

The Cost of Synchronization

Synchronization isn't free:

  • Waiting: Threads blocked on locks do no useful work
  • Contention: Popular locks become bottlenecks
  • Overhead: Lock operations have CPU cost
  • Complexity: Getting it right is hard; bugs are subtle

The Deeper Truth

Shared mutable state is the root of concurrent complexity. Every mechanism we've seen---locks, atomics, semaphores---exists to manage access to shared mutable state.

What if we didn't share mutable state at all?

  • Immutable data: If data never changes, sharing is safe
  • Thread-local data: If data isn't shared, no conflict
  • Message passing: Copy data instead of sharing it

Locks and atomics let us survive shared mutable state. But what if we architected our systems differently? The next chapter explores message passing---an alternative where concurrent entities never share state at all.