I - O management — polling, interrupt-driven, DMA: Worked examples

4.2.37 · D3 · Coding › Operating Systems › I - O management — polling, interrupt-driven, DMA

Intuition Yeh page kya karti hai

Parent note ne tumhe teen techniques diye — Polling, Interrupt-driven, DMA — aur unke cost formulas. Ab hum har corner case ko exercise karte hain taaki koi bhi scenario tumse reason nahi karwa sake. Hum shuru karte hain ek matrix se jo is topic ke har case-class ko cover kare, phir worked examples solve karte hain jab tak us matrix ka har cell cover na ho jaaye.

Neeche sab kuch sirf wahi symbols use karta hai jo parent ne already earn kiye hain:

$T_{d e v}$ = woh time jo slow device ko ready hone mein lagta hai.
$t_{p o l l}$ = status register ka ek poll karne ki cost (CPU time mein).
$t_{in t}$ = ek interrupt lene + service karne ki cost (context save karo, ISR run karo, context restore karo).
$N$ = transfer mein bytes (ya words) ki sankhya. Agar inme se koi shaky lage, toh parent note unhe zero se build karta hai pehle.

Scenario matrix

Har I/O costing question inhi case classes mein se ek (ya mix) hota hai. Ise ek coordinate plane ke quadrants ki tarah socho: humein SABHI cover karne chahiye, including degenerate edges.

Cell	Case class	Distinguishing input	Kaunsa method jeetna chahiye?
A	Slow device, single unit	$T_{d e v}$ bahut bada, $N = 1$	Interrupt
B	Fast device, almost-always-ready	$T_{d e v} \approx t_{p o l l}$	Polling
C	High-rate stream, per-byte interrupt	$N$ bahut bada, ek IRQ/byte	Polling beats interrupt (!)
D	Large block transfer	$N$ bahut bada, block-capable	DMA
E	Crossover / break-even	tie point ke liye solve karo	depends — threshold dhundho
F	Degenerate: $N = 0$	transfer karne ko kuch nahi	sab ka cost $\approx$ sirf setup
G	Limiting: $T_{d e v} \to 0$	device instant	Polling (overlap karne ko wait nahi)
H	Limiting: $T_{d e v} \to \infty$	device kabhi ready nahi	Polling waste $\to \infty$
I	Cycle-stealing correction	DMA + bus contention	DMA, lekin CPU 100% free nahi
J	Real-world word problem	method chuno	reasoning, sirf arithmetic nahi
K	Exam twist	mixed/misleading numbers	trap pakdo

Ab hum A–K ko examples ke saath cover karte hain. Har example apne cell(s) ke saath tagged hai.

Worked examples

Worked example Example 1 — Cell A: slow device, ek byte

Ek disk sensor ek status byte produce karta hai. Device ko ready hone mein $T_{d e v} = 10, 000$ CPU-time-units lagte hain. Ek poll ki cost $t_{p o l l} = 1$ unit hai. Ek interrupt ki cost $t_{in t} = 200$ units hai. Polling sasta hai ya interrupt?

Forecast: padhne se pehle guess karo — 10,000-unit wait vs 200-unit interrupt. Kaun jeetega?

Polling cost. Wasted polls $\approx \frac{T _{d e v}}{t _{p o l l}} = \frac{10000}{1} = 10000$ units, sab pure waste, phir 1 transfer. Yeh step kyun? Parent ka polling-cost formula: CPU back-to-back spin karta hai jab tak last poll use ready na paaye.
Interrupt cost. CPU command issue karta hai, doosra kaam karta hai, $t_{in t} = 200$ ek baar pay karta hai. Yeh step kyun? Overhead ek baar per unit pay hota hai, aur yahan exactly ek unit hai.
Compare karo. $10000 ≫ 200$ .

Verify: ratio $10000/200 = 50 \times$ interrupts ke saath sasta. Slow, rare device → interrupts. ✅

Worked example Example 2 — Cell B & Cell G: fast, almost-always-ready device

Ek status flag almost turant ready hai: $T_{d e v} = 1$ unit (essentially agla poll succeed ho jaata hai). $t_{p o l l} = 1$ , $t_{in t} = 200$ . Poll ya interrupt?

Forecast: device basically instant hai. Kya fancy interrupt machinery ab bhi help karti hai?

Polling cost. Wasted polls $\approx T_{d e v} / t_{p o l l} = 1/1 = 1$ . Toh $\approx 1$ wasted poll + 1 transfer $\approx 2$ units. Yeh step kyun? Jab $T_{d e v} \to t_{p o l l}$ , loop lagbhag ek baar chalta hai — koi meaningful waste nahi. Yeh $T_{d e v} \to 0$ limit hai (Cell G).
Interrupt cost. Phir bhi $t_{in t} = 200$ units ka fixed overhead har baar. Yeh step kyun? Interrupt overhead fast device ke saath shrink nahi hota — context save/restore ek fixed price hai.
Compare karo. $2 ≪ 200$ .

Verify: polling $100 \times$ sasta hai. Parent ka claim confirm hota hai: ek device ke liye jo almost hamesha ready hai, polling sabse fast option ho sakta hai. ✅

Worked example Example 3 — Cell H: never-ready limit

Same numbers, lekin ek broken device: $T_{d e v} \to \infty$ (woh kabhi ready nahi hota). Polling vs interrupts mein kya hoga?

Forecast: kaun sa method CPU ko hang karta hai aur kaun use survive karne deta hai?

Polling. Wasted polls $\approx T_{d e v} / t_{p o l l} \to \infty$ . CPU busy-wait loop mein hamesha ke liye spin karta hai — machine freeze ho jaati hai. Yeh step kyun? Polling CPU ko sirf check karne ke liye de deta hai; koi timeout nahi toh kabhi exit nahi karta.
Interrupt. CPU ne command issue ki aur chala gaya. Woh useful kaam karta rehta hai; interrupt simply kabhi nahi aata. CPU freeze nahi hota. Yeh step kyun? Interrupt-driven I/O device idle time ko real work ke saath overlap karta hai, toh ek stuck device ke liye CPU ko kuch nahi lagta (jab tak software timeout fire na kare).

Verify: limiting behaviour: polling waste $\to \infty$ , interrupt CPU cost bounded rehti hai. Isliye real polling loops ko timeouts chahiye hote hain. ✅

Worked example Example 4 — Cell C: high-rate stream, per-byte interrupts (surprise wala)

Ek fast network card $N = 1, 000, 000$ bytes deliver karta hai, ek byte har $T_{d e v} = 5$ units mein ready hota hai. Per-byte interrupt cost $t_{in t} = 200$ units; ek poll $t_{p o l l} = 1$ . Polling vs interrupt ke liye total CPU cost compare karo (abhi DMA nahi).

Forecast: interrupts polling ka "smart" upgrade maane jaate hain. Ek firehose device ke liye, kya yeh ab bhi sach hai?

Polling cost per byte. Wait $\approx T_{d e v} / t_{p o l l} = 5/1 = 5$ polls + 1 move $\approx 6$ units/byte. Total $\approx 6 \times 1 0^{6} = 6, 000, 000$ units. Yeh step kyun? Device fast hai toh har busy-wait tiny hai; total = per-byte cost $\times N$ .
Interrupt cost per byte. Ek IRQ per byte $= t_{in t} = 200$ units/byte. Total $= 200 \times 1 0^{6} = 200, 000, 000$ units. Yeh step kyun? Parent ka catch — high rate par ek interrupt per byte ISR overhead ko dominate kara deta hai.
Compare karo. $6 \times 1 0^{6}$ vs $2 \times 1 0^{8}$ : polling $\approx 33 \times$ sasta hai.

Verify: high-rate device ke liye, polling interrupt-driven se jeet jaata hai — exactly wahi paradox jo parent ne warn kiya tha, aur precisely isliye DMA invent hua. ✅

Worked example Example 6 — Cell E: polling aur interrupts ke beech break-even dhundho

Ek device $T_{d e v}$ units mein ready hota hai; $t_{p o l l} = 1$ , $t_{in t} = 200$ . Single-byte transfer ke liye, kin $T_{d e v}$ par polling aur interrupt ki cost same hogi?

Forecast: tie wahan hai jahan "wasted spinning" pehli baar "interrupt overhead" ke barabar ho. Number guess karo.

Costs equal karo. Polling waste $\approx T_{d e v} / t_{p o l l} = T_{d e v}$ . Interrupt cost $= t_{in t} = 200$ . Break-even: $T_{d e v} = t_{in t}$ . Yeh step kyun? Parent ka rule "interrupts jeetate hain jab $T_{d e v} ≫ t_{in t}$ " — boundary literally equality hai.
Solve karo. $T_{d e v} = 200$ units. Yeh step kyun? Is se neeche device "itna fast" hai ki spinning sasta hai; is se upar, interrupts jeetate hain.

Verify: $T_{d e v} = 200$ par, polling waste $= 200 = t_{in t}$ . $T_{d e v} < 200$ ke liye → poll; $T_{d e v} > 200$ ke liye → interrupt. ✅ Yeh tumhe ek decision threshold deta hai, sirf ek answer nahi. Figure dekho.

Worked example Example 7 — Cell F: degenerate zero-byte transfer

Ek driver ek "transfer" issue karta hai lekin count $N = 0$ bytes hai (empty read). Har method mein cost kya hai? $t_{p o l l} = 1, t_{in t} = 200$ , DMA setup $= 200$ .

Forecast: move karne ko kuch nahi, toh kya cost truly zero hai?

Polling. $N = 0$ moves. Phir bhi "ready/no data" confirm karne ke liye ek baar poll ho sakta hai $\approx 1$ unit. Yeh step kyun? Zero bytes free mein move nahi ho sakte — status kam se kam ek baar check hoti hai.
Interrupt. $N \cdot t_{in t} = 0 \times 200 = 0$ transfer interrupts, lekin ek completion IRQ phir bhi fire ho sakta hai $\approx 200$ units depending on device. Yeh step kyun? Per-byte kaam khatam ho jaata hai; sirf fixed protocol overhead reh sakta hai.
DMA. Setup $200$ + final IRQ $200 = 400$ units chahe kuch move na hua ho. Yeh step kyun? DMA ki cost by design $O (1)$ hai — yeh $N = 0$ par zero nahi hoti; setup same rehti hai.

Verify: degenerate case dikhata hai ki low end par ordering flip ho jaati hai — $N = 0$ ke liye, polling sabse sasta hai (1 unit) aur DMA sabse mahanga (400), exactly large- $N$ ordering ka ulta. ✅

Worked example Example 8 — Cell I: cycle-stealing correction

Ek DMA transfer $N = 1000$ words move karta hai. Har word ke liye DMA memory bus 1 cycle ke liye grab karta hai, CPU ko us cycle ke liye stall karta hai (cycle stealing). CPU 1 cycle/unit par run karta hai. Contention se kitna CPU time kho jaata hai, aur kya CPU "100% free" hai?

Forecast: parent ka mistake callout kehta hai DMA CPU ko fully free nahi karta. Loss estimate karo.

Stall cost. DMA 1 cycle per word $\times 1000$ words $= 1000$ stolen cycles $= 1000$ units steal karta hai. Yeh step kyun? Cycle stealing = DMA aur CPU ek bus share karte hain; har stolen cycle ek CPU stall hai.
Interrupt-driven cost se compare karo. Interrupt ka cost hota $1000 \times t_{in t} = 1000 \times 200 = 200, 000$ units active CPU kaam. Yeh step kyun? Cycle stealing ke saath bhi, DMA ke stolen 1000 units $≪$ 200,000.
Interpretation. CPU 100% free nahi hai (usne 1000 units khoe), lekin usne interrupt method se $200 \times$ kam khoya. Yeh step kyun? "DMA = totally idle CPU" misconception ko correct karta hai jabki DMA ko clear winner rakhta hai.

Verify: stolen $= 1000$ units $> 0$ (toh 100% free nahi), phir bhi $1000 ≪ 200000$ (toh phir bhi kaafi better). ✅

Worked example Example 9 — Cell J: real-world word problem (method chuno)

Ek driver author ko teen devices ke liye technique choose karni hai: (a) ek keyboard — har ~200 ms mein ek keystroke, 1 byte each; (b) ek 10 Gbps NIC — millions of packets/sec, large frames; (c) ek temperature sensor jise ek tight control loop poll karta hai jo ek fresh value padhti hai jo hamesha ek poll mein ready rehti hai. Har ek ke liye polling / interrupt / DMA chuno aur justify karo.

Forecast: choose karne se pehle har device ko ek matrix cell par map karo.

Keyboard → interrupt-driven (Cell A). Rare events, ek byte each. Polling 200 ms spinning waste karta hai; DMA ek single byte ke liye overkill hai. Yeh step kyun? Method ko rate (rare) aur block size (tiny) se match karo. $T_{d e v}$ bada $\Rightarrow$ interrupts polling se jeette hain.
NIC → DMA (Cell D). $N$ bada, block-capable. Per-byte interrupts CPU ko duba denge (Cell C); DMA ek frame mein 1 IRQ deta hai. Yeh step kyun? High-rate + large block textbook DMA case hai.
Sensor → polling (Cell B/G). Ek poll mein hamesha ready, $T_{d e v} \approx t_{p o l l}$ ; interrupt overhead $t_{in t}$ tiny poll cost se zyada hoga. Yeh step kyun? Jab device essentially instant ho, ek baar spin karna $t_{in t}$ se sasta hai.

Verify: har choice apne matrix cell aur Examples 1–5 ke cost inequalities se match karti hai. ✅

Worked example Example 10 — Cell K: exam twist (trap pakdo)

"Ek student claim karta hai: kyunki DMA ko 200 units setup chahiye aur polling ko sirf 1 unit per poll, polling hamesha sasta hota hai." $N = 100, 000$ -byte transfer ke liye numbers se refute karo jahan har byte ka device-wait $T_{d e v} = 5$ units hai, $t_{p o l l} = 1$ .

Forecast: trap yeh hai ki ek per-unit number ko ek whole-transfer number se compare kar rahe hain. Galti dhundho.

Real polling total. Per byte $\approx T_{d e v} / t_{p o l l} + 1 = 5 + 1 = 6$ units. Total $= 6 \times 100000 = 600, 000$ units. Yeh step kyun? Polling ka "1 unit" per poll hai, aur bahut saare polls per byte hain times bahut saare bytes — yeh $O (N)$ scale karta hai.
DMA total. $200$ setup $+ 200$ final IRQ $= 400$ units, $N$ se independent. Yeh step kyun? DMA $O (1)$ hai; uska ek-baar ka 200 ek fixed cost hai, per-byte nahi.
Fallacy expose karo. $600000 ≫ 400$ . Student ne DMA ki total cost ko polling ki per-poll cost se compare kiya. Yeh step kyun? Hamesha puri transfer ke liye total CPU cost compare karo, kabhi per-unit vs whole mat karo.

Verify: polling $600, 000$ vs DMA $400$ → DMA $1500 \times$ se jeetta hai. "Polling hamesha sasta" claim bade $N$ ke liye galat hai. ✅

Poori matrix ka recap

Recall Har limit mein kaun sa method jeetata hai?

$T_{d e v} \to 0$ (instant device) → jeetega? ::: Polling — overlap karne ko kuch nahi, interrupt overhead waste hai. $T_{d e v} \to \infty$ (kabhi ready nahi) → polling kya karta hai? ::: Hamesha spin karta hai, waste $\to \infty$ ; interrupts CPU ko free rakhte hain. High byte-rate, ek IRQ/byte → polling vs interrupt? ::: Polling interrupt se jeet sakta hai kyunki per byte $t_{in t}$ dominate karta hai. Large block transfer → best method? ::: DMA — interrupt count $N$ se gir ke $1$ ho jaata hai. $N = 0$ degenerate transfer → sabse sasta method? ::: Polling ( $\approx 1$ unit); DMA phir bhi apna $O (1)$ setup pay karta hai. Poll aur interrupt ke beech break-even $T_{d e v}$ (single byte)? ::: $T_{d e v} = t_{in t}$ . Kya DMA CPU ko 100% free banata hai? ::: Nahi — cycle stealing bus cycles steal karta hai, lekin loss interrupts ke mukable mein tiny hai.

Related: Context switching (har interrupt par pay hota hai), CPU utilization and throughput (yahi sab optimize karta hai), Disk Scheduling (DMA transfers ko order karta hai), Memory-mapped I/O vs Port-mapped I/O (registers kaise address hote hain).