WHY ye dangerous hai: CPU ek high-level line jaise count++ ko atomically execute nahi karta. OS scheduler kisi bhi machine instruction boundary par thread ko preempt kar sakta hai.
WHAT galat hota hai (core problem): ek race condition — final result thread execution ki timing/order par depend karta hai, sirf inputs par nahi.
count++ asal mein teen machine steps hai. Chaliye failure ko scratch se derive karte hain.
\underbrace{R \leftarrow \text{mem}[count]}_{\text{load}}\;;\;
\underbrace{R \leftarrow R + 1}_{\text{add}}\;;\;
\underbrace{\text{mem}[count] \leftarrow R}_{\text{store}}$$
Maan lo `count = 5` hai, aur Thread A aur Thread B dono `count++` karte hain. **Correct** answer `7` hona chahiye.
> [!example] Ek 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 ❌** |
>
> **Ye step kyun?** t2 par scheduler A ko *load ke baad lekin store se pehle* preempt karta hai, isliye B **stale** value 5 padhta hai. Dono 6 compute karte hain; doosra store pehle wale ko overwrite kar deta hai. Ek increment **lost** ho gaya.
> [!formula] Lost updates ka bound
> Agar $N$ threads mein se har ek ek counter par jo $0$ se shuru hota hai ek increment kare, **bina** sync ke final value **as low as** $1$ ho sakti hai (har thread $0$ padhta hai, sab $1$ store karte hain). Proper sync ke saath ye exactly hai:
> $$\text{final} = N$$
> Toh possible final range hai $\boxed{[1,\,N]}$ — ye derive hota hai kyunki *minimum* tab hota hai jab saare loads kisi bhi store se pehle complete ho jaate hain, aur *maximum* tab jab har increment serialize ho.
---
![[4.2.08-Thread-synchronization-needs-—-shared-memory-issues.png]]
---
## Fix ki vocabulary (WHAT chahiye hume)
> [!definition] Critical section
> Wo code block jo shared resources access karta hai. Rule ye hai: ek given critical section mein ek waqt mein zyada se zyada ==ek thread== ho sakta hai (**mutual exclusion**).
> [!definition] Teen correctness requirements (Dijkstra)
> 1. **Mutual exclusion** — critical section mein sirf ek thread.
> 2. **Progress** — agar koi CS mein nahi hai, toh ek waiting thread ko andar aana chahiye (bewaajah blocking nahi).
> 3. **Bounded waiting** — ek thread ko forever starve nahi kiya ja sakta; dusron ke pehle andar jaane ki ek finite bound hoti hai.
**HOW hum enforce karte hain (tools, abhi deep dive nahi):** locks/mutexes, semaphores, condition variables, atomic instructions. Hardware ek indivisible primitive deta hai (`test-and-set` / `compare-and-swap`); baaki sab usi par build hota hai.
> [!intuition] Atomic hardware bedrock kyun hai
> Aap mutual exclusion sirf ordinary loads aur stores se *reliably aur simply* build nahi kar sakte — aapko **ek** aisi instruction chahiye jise CPU bina interruption ke chalane ka promise kare. CAS (compare-and-swap) wahi promise hai.
---
## Doosre shared-memory hazards (sirf lost updates nahi)
> [!definition] Doosre classic issues
> - **Torn read/write**: ek non-atomic 64-bit value half-update hote waqt padhi jaaye → garbage.
> - **Visibility / stale cache**: thread A ki write uske cache mein baithti hai; thread B usse bina ==memory barrier== ke kabhi nahi dekhega. (Isliye `volatile`/`atomic` matter karte hain.)
> - **Reordering**: compiler/CPU independent instructions ko reorder kar sakta hai, assumptions tod ke.
> - **Deadlock**: *ilaaj* (locks) ek nayi bimari create kar deta hai agar unhein inconsistent order mein acquire kiya jaaye.
---
## Worked example 2 — bank balance
> [!example] Do ATM withdrawals
> Balance = ₹100. Thread A ₹80 withdraw karta hai, Thread B ₹80 withdraw karta hai. Har ek check karta hai `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 ❌ |
>
> **Ye step kyun?** Dono ne `if` *same purane balance* par pass kiya, kisi ne bhi likhne se pehle. Result: ₹100 se ₹160 withdraw ho gaye. **Fix:** check **aur** update dono ko ek critical section mein rakho.
---
> [!mistake] Steel-man: "Increment ek operation hai, toh safe hai."
> **Kyun sahi lagta hai:** source code mein `count++` *atomic lagta hai* — ek symbol, ek line.
> **Kyun galat hai:** CPU ise load–add–store ke roop mein execute karta hai; scheduler in ke beech interrupt kar sakta hai. **Fix:** shared data par kisi bhi read-modify-write ko non-atomic treat karo jab tak aapne `atomic` type ya lock use na kiya ho.
> [!mistake] Steel-man: "Agar bug 10 lakh mein ek baar aata hai, toh basically real nahi hai."
> **Kyun sahi lagta hai:** test usually pass ho jaata hai, toh code "kaam karta hai."
> **Kyun galat hai:** load ke neeche aur real hardware par rare interleaving *hoga zaroor*, aur ise reproduce/debug karna almost impossible hai. Heisenbugs. **Fix:** correctness ko structural banao (locks/atomics), probabilistic nahi.
> [!mistake] Steel-man: "Sab kuch `volatile` kar do races fix karne ke liye."
> **Kyun sahi lagta hai:** `volatile` *visibility* control karta hai, jo ek symptom hai.
> **Kyun galat hai:** `volatile` (C/Java mein) `count++` ko atomic **nahi** banata; ye mutual exclusion provide nahi karta. **Fix:** read-modify-write ke liye proper atomics ya locks use karo.
---
## Feynman
> [!recall]- Ek 12-saal ke bachche ko samjhao
> Socho do bachche ek notebook share karte hain jisme likha hai "Cookies left: 5". Har bachcha ise padhta hai, mentally "5 − 1 = 4" karta hai, aur 4 likhta hai. Lekin dono ne *same moment par* padha, toh dono 4 likhte hain, jabki **do** cookies khayi gayi thi — 3 likhna chahiye tha! Notebook **shared memory** hai, aur ganda answer ek **race condition** hai. Fix ye rule hai: "Sirf woh bachcha notebook badal sakta hai jiske haath mein **pencil** hai." Woh pencil ek **lock** hai.
> [!mnemonic] Dangers yaad karo: **"LV-RD"**
> **L**ost updates, **V**isibility (stale cache), **R**eordering, **D**eadlock.
> *("Love R&D" — memory share karne mein careful R&D chahiye.)*
> Aur ek achche fix ke teen rules: **M-P-B** = **M**utual exclusion, **P**rogress, **B**ounded waiting.
---
## #flashcards/coding
`count++` race condition kyun cause karta hai? ::: Ye load–add–store mein compile hota hai; ek thread in steps ke beech preempt ho sakta hai, toh doosra thread stale value padhta hai aur ek update lost ho jaata hai.
Ek process ke threads kya share karte hain aur kya private rakhte hain? ::: Shared: code, globals, heap. Private: stack aur registers.
Race condition define karo. ::: Outcome non-deterministic interleaving of threads par depend karta hai jab ≥1 shared data likhta hai.
Critical section kya hota hai? ::: Ek code block jo shared data access karta hai aur jisme ek waqt mein zyada se zyada ek thread enter kar sakta hai.
Synchronization ke teen correctness requirements batao. ::: Mutual exclusion, progress, bounded waiting.
N threads ek shared counter ko 0 se bina sync ke increment karein toh final value ka range kya hoga? ::: 1 (min) se N (max) tak.
Zyaadatar locks ke neeche kaunsa hardware primitive hai? ::: Ek atomic instruction jaise test-and-set ya compare-and-swap (CAS).
Kya `volatile` `count++` ko atomic banata hai? ::: Nahi — ye sirf visibility/ordering ko affect karta hai, read-modify-write ki atomicity ko nahi.
Torn read/write kya hota hai? ::: Ek multi-word value ko padhna jab wo sirf half-update hui ho, jo ek garbage value deta hai.
Thread B thread A ki write kyun nahi dekh sakta, chahe A finish ho gaya ho? ::: Visibility: A ki write cache/registers mein baith sakti hai; bina memory barrier ke B stale data padhta hai.
---
## Connections
- [[Mutex and Lock implementation]] — in issues ka concrete fix.
- [[Semaphores]] — mutual exclusion ko N resources tak generalize karna.
- [[Compare-and-Swap (CAS)]] — atomic hardware bedrock.
- [[Deadlock and the four Coffman conditions]] — ilaaj se paida hone wali bimari.
- [[Memory model and barriers]] — visibility aur reordering hazards.
- [[Process vs Thread]] — memory pehli jagah share kyun hoti hai.
## 🖼️ 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]
```