Concurrency Foundations

📘 Learn Concurrency Foundations from zero

Start with the words. A program is a recipe written on paper. A process is one cook actually making that recipe in their own kitchen, with their own ingredients (memory) the OS forbids other cooks from touching. A thread is a pair of hands inside that one kitchen. One process can have many threads — many hands sharing the same counters and fridge (the same address space). That sharing is the whole point and the whole danger.

Concurrency means multiple tasks make progress in overlapping time windows (even on one core, by interleaving); parallelism means they literally execute at the same instant on different CPU cores. Concurrency is about structure; parallelism is about execution — you can have concurrency without parallelism.

The danger, concretely. Two threads both run balance = balance + 100 on a shared account starting at $0. That one line is really three steps: read balance, add 100, write balance. Interleave them: Thread A reads 0, Thread B reads 0, A writes 100, B writes 100. Two deposits happened but the balance is $100, not $200. One update vanished. The block of code that touches the shared balance is the critical section, and the lost-update bug from uncontrolled interleaving there is a race condition.

The fix. Put a lock (mutex) around the critical section: a thread must acquire it before entering and release after, so only one thread is inside at a time. Now A finishes (100) before B starts (200). Correct.

Key insight: Threads are fast because they share memory; they are dangerous for exactly the same reason. Every synchronization construct — mutex, semaphore, condition variable, barrier — exists to control when threads are allowed to touch that shared memory.

✨ Added by the guide to build intuition — not from the source course.

🎯 Guided practice

1. Easy — Atomic counter. Ten threads each increment a shared counter 1,000 times. Expected final value is 10,000 but you keep seeing less. Fix it.

   Step 1 — Find the critical section. counter++ is read-modify-write: three non-atomic steps. Two threads can both read the same old value, so increments are lost (the same race as the bank example).

   Step 2 — Pick the construct. A single shared variable mutated by many threads is the textbook trigger for a mutex. Acquire the lock, do counter++, release.

   Step 3 — Reason about correctness. The lock makes the three steps indivisible from any other thread's view (mutual exclusion). No interleaving inside the critical section means no lost updates, so the result is always 10,000. (For a single counter the lock-free alternative — an atomic integer doing a compare-and-swap loop — is faster and avoids blocking entirely.)

   Pattern learned: wrap every read-modify-write on the same shared state in the same lock.

2. Medium — Bounded producer-consumer (capacity N=5). Producers add items to a shared queue; consumers remove them. Producers must block when full, consumers must block when empty. No busy-waiting.

   Step 1 — Identify the two conditions. "Not full" gates producers; "not empty" gates consumers. Waiting on a condition without spinning is the trigger for condition variables — two of them (notFull, notEmpty), both paired with the one mutex that protects the queue.

   Step 2 — Producer logic. Acquire lock. while (queue.size == N) notFull.wait() — wait() atomically releases the lock and sleeps, reacquiring it on wake. After waking, push the item, then notEmpty.signal() to wake a waiting consumer. Release lock.

   Step 3 — Consumer logic. Acquire lock. while (queue.isEmpty) notEmpty.wait(). Pop the item, then notFull.signal() to wake a producer. Release lock.

   Step 4 — Why while, not if. A thread can wake spuriously, or another consumer can grab the item first in the gap between the signal and this thread reacquiring the lock. Re-checking the condition in a loop guarantees you only proceed when it truly holds — this prevents the classic lost/spurious-wakeup bug. (The semaphore equivalent: a counting semaphore initialized to N for empty slots and one to 0 for filled slots. With multiple producers/consumers you still need a separate mutex around the buffer mutation itself, since semaphores only gate the slot counts, not the queue's internal state.)

✨ Added by the guide — work these before the full problem set.