Thread synchronization needs — shared memory issues

---

WHY do shared-memory issues even arise?

WHY this is dangerous: the CPU does not execute a high-level line like count++ atomically. The OS scheduler can preempt a thread at any machine instruction boundary.

WHAT goes wrong (the core problem): a race condition — the final result depends on the timing/order of thread execution, not just the inputs.

---

HOW a single count++ breaks — derive it from instructions

count++ is really three machine steps. Let me derive the failure from scratch.

\underbrace{R \leftarrow \text{mem}[count]}_{\text{load}}\;;\; \underbrace{R \leftarrow R + 1}_{\text{add}}\;;\; \underbrace{\text{mem}[count] \leftarrow R}_{\text{store}}$$ Suppose `count = 5`, and Thread A and Thread B each do `count++`. **Correct** answer must be `7`. > [!example] A lost update (race condition) > | Time | Thread A | Thread B | count in memory | > |------|----------|----------|-----------------| > | t1 | load R=5 | | 5 | > | t2 | | load R=5 | 5 | > | t3 | add R=6 | | 5 | > | t4 | | add R=6 | 5 | > | t5 | store 6 | | 6 | > | t6 | | store 6 | **6 ❌** | > > **Why this step?** At t2 the scheduler preempts A *after* its load but before its store, > so B reads the **stale** value 5. Both compute 6; the second store overwrites the first. > One increment was **lost**. > [!formula] Bound on lost updates > If $N$ threads each do one increment on a counter starting at $0$, **without** sync the > final value can be **as low as** $1$ (every thread reads $0$, all store $1$). With proper > sync it is exactly: > $$\text{final} = N$$ > So the possible final range is $\boxed{[1,\,N]}$ — derived because the *minimum* happens > when all loads finish before any store, and the *maximum* when every increment is serialized. --- ![[4.2.08-Thread-synchronization-needs-—-shared-memory-issues.png]] --- ## The vocabulary of the fix (WHAT we need) > [!definition] Critical section > The block of code that accesses shared resources. The rule: at most ==one thread== may be > inside a given critical section at a time (**mutual exclusion**). > [!definition] The three correctness requirements (Dijkstra) > 1. **Mutual exclusion** — only one thread in the critical section. > 2. **Progress** — if no one is in the CS, a waiting thread must be allowed in (no needless blocking). > 3. **Bounded waiting** — a thread can't be starved forever; there's a finite bound on others entering first. **HOW we enforce it (tools, not yet the deep dive):** locks/mutexes, semaphores, condition variables, atomic instructions. The hardware gives one indivisible primitive (`test-and-set` / `compare-and-swap`); everything else is built on it. > [!intuition] Why atomic hardware is the bedrock > You cannot build mutual exclusion purely from ordinary loads and stores *reliably and > simply* — you need **one** instruction the CPU promises to run without interruption. > CAS (compare-and-swap) is that promise. --- ## Other shared-memory hazards (not just lost updates) > [!definition] Other classic issues > - **Torn read/write**: a non-atomic 64-bit value read while half-updated → garbage. > - **Visibility / stale cache**: thread A's write sits in its cache; thread B never sees it > without a ==memory barrier==. (This is why `volatile`/`atomic` matter.) > - **Reordering**: compiler/CPU may reorder independent instructions, breaking assumptions. > - **Deadlock**: the *cure* (locks) creates a new disease if acquired in inconsistent order. --- ## Worked example 2 — bank balance > [!example] Two ATM withdrawals > Balance = ₹100. Thread A withdraws ₹80, Thread B withdraws ₹80. Each checks > `if (bal >= amt) bal -= amt;`. > > | Step | A | B | > |------|---|---| > | 1 | reads bal=100, 100≥80 ✓ | | > | 2 | | reads bal=100, 100≥80 ✓ | > | 3 | bal = 100−80 = 20 | | > | 4 | | bal = 100−80 = 20 ❌ | > > **Why this step?** Both passed the `if` on the *same* old balance before either wrote. > Result: ₹160 withdrawn from ₹100. **Fix:** put check **and** update in one critical section. --- > [!mistake] Steel-man: "Increment is one operation, so it's safe." > **Why it feels right:** in source code `count++` *looks* atomic — one symbol, one line. > **Why it's wrong:** the CPU executes it as load–add–store; the scheduler can interrupt > between them. **Fix:** treat any read-modify-write on shared data as non-atomic unless you > used an `atomic` type or a lock. > [!mistake] Steel-man: "If a bug appears 1 in a million runs, it's basically not real." > **Why it feels right:** the test usually passes, so the code "works." > **Why it's wrong:** under load and on real hardware the rare interleaving *will* happen, > and it's nearly impossible to reproduce/debug. Heisenbugs. **Fix:** make correctness > structural (locks/atomics), not probabilistic. > [!mistake] Steel-man: "Make everything `volatile` to fix races." > **Why it feels right:** `volatile` controls *visibility*, which is one of the symptoms. > **Why it's wrong:** `volatile` (in C/Java) does **not** make `count++` atomic; it doesn't > provide mutual exclusion. **Fix:** use proper atomics or locks for read-modify-write. --- ## Feynman > [!recall]- Explain to a 12-year-old > Imagine two kids sharing one notebook that says "Cookies left: 5". Each kid reads it, > mentally does "5 − 1 = 4", and writes 4. But they read at the *same moment*, so both write > 4 even though **two** cookies were eaten — it should say 3! The notebook is **shared > memory**, and the messed-up answer is a **race condition**. The fix is a rule: "Only the > kid holding the **pencil** may change the notebook." That pencil is a **lock**. > [!mnemonic] Remember the dangers: **"LV-RD"** > **L**ost updates, **V**isibility (stale cache), **R**eordering, **D**eadlock. > *("Love R&D" — sharing memory needs careful R&D.)* > And the three rules of a good fix: **M-P-B** = **M**utual exclusion, **P**rogress, **B**ounded waiting. --- ## #flashcards/coding Why does `count++` cause a race condition? ::: It compiles to load–add–store; a thread can be preempted between these steps, so another thread reads the stale value and an update is lost. What memory do threads of one process share vs keep private? ::: Shared: code, globals, heap. Private: stack and registers. Define a race condition. ::: Outcome depends on the non-deterministic interleaving of threads when ≥1 of them writes shared data. What is a critical section? ::: A code block accessing shared data that must be entered by at most one thread at a time. Name the three correctness requirements for synchronization. ::: Mutual exclusion, progress, bounded waiting. For N threads each incrementing a shared counter from 0 with no sync, what is the range of the final value? ::: From 1 (min) to N (max). What hardware primitive underlies most locks? ::: An atomic instruction like test-and-set or compare-and-swap (CAS). Does `volatile` make `count++` atomic? ::: No — it only affects visibility/ordering, not atomicity of read-modify-write. What is a torn read/write? ::: Reading a multi-word value while it's only half-updated, giving a garbage value. Why might thread B not see thread A's write even after A finished? ::: Visibility: A's write may sit in cache/registers; without a memory barrier B reads stale data. --- ## Connections - [[Mutex and Lock implementation]] — the concrete fix for these issues. - [[Semaphores]] — generalizing mutual exclusion to N resources. - [[Compare-and-Swap (CAS)]] — the atomic hardware bedrock. - [[Deadlock and the four Coffman conditions]] — the disease the cure introduces. - [[Memory model and barriers]] — visibility and reordering hazards. - [[Process vs Thread]] — why memory is shared in the first place. ## 🖼️ Concept Map ```mermaid flowchart TD T[Threads of same process] -->|share| SM[Shared code globals heap] T -->|own private| ST[Stack and registers] SM -->|enables| DANGER[Uncontrolled access] SCHED[OS scheduler preempts] -->|at instruction boundary| RACE[Race condition] DANGER -->|leads to| RACE INC[count++ is 3 steps load add store] -->|bad interleaving| LOST[Lost update] RACE -->|manifests as| LOST LOST -->|final range| BOUND[1 to N possible] RACE -->|fixed by| SYNC[Synchronization] SYNC -->|protects| CS[Critical section] CS -->|requires| MUTEX[Mutual exclusion progress bounded wait] ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Dekho, ek hi process ke andar jo threads hote hain, woh **shared memory** use karte hain — > yaani globals aur heap sabke common hote hain (sirf stack aur registers alag hote hain). Yeh > sharing fast communication ke liye accha hai, lekin yahin se problem shuru hoti hai. Jab do > threads **same variable** ko ek saath chhuti hain aur kam se kam ek likh rahi hai, toh order > ke hisaab se answer galat aa sakta hai. Isko **race condition** kehte hain. > > Sabse classic example: `count++`. Yeh ek line dikhti hai par CPU ke liye yeh teen steps hain — > **load, add, store**. Maan lo count = 5 hai. Thread A load karke 5 padhti hai, beech mein > scheduler usko rok deta hai, ab Thread B bhi 5 hi padhti hai. Dono 6 banate hain, dono 6 store > karte hain — answer 7 hona chahiye tha par 6 aaya. Ek increment **lost** ho gaya. Diagram mein > yahi timeline dekho. > > Fix kya hai? **Critical section** — woh code jisme shared data touch hota hai, usmein ek time > par sirf ek thread jaaye. Isko **mutual exclusion** kehte hain, aur achhe solution ke teen > rules hote hain: mutual exclusion, progress, bounded waiting (yaad rakho **M-P-B**). Implement > karne ke liye locks/mutex/semaphore use hote hain, jo andar se ek **atomic** hardware > instruction (CAS / test-and-set) pe bani hoti hai. > > Ek important galti se bacho: socho mat ki `count++` apne aap atomic hai, ya sirf `volatile` > laga dene se race fix ho jayegi — `volatile` sirf visibility theek karta hai, atomicity nahi. > Aur agar bug 10 lakh runs mein ek baar aaye toh bhi woh real bug hai — real hardware aur load > pe definitely aayega. Correctness ko structure se laao (lock/atomic), luck se nahi. ![[audio/4.2.08-Thread-synchronization-needs-—-shared-memory-issues.mp3]]