Real-time constraints — hard and soft deadlines: Question bank

5.5.12 · D5 · Coding › Embedded Systems & Real-Time Software › Real-time constraints — hard and soft deadlines

Traps se pehle, hum un paanch symbols ko banate hain jinpar sab kuch tika hai — scratch se, ek picture pe — taaki ye page apne aap mein poora ho.

The symbols, on one timeline

Neeche ke har sawal mein single CPU pe chal rahe tasks ki baat hoti hai. Ek task ek piece of code hai (jaise, "sensor padho") jo baar baar release hota hai. Har release ko job kehte hain. Time ko left→right jaata socho; har job ek stopwatch hai jo tab shuru hota hai jab job release hota hai aur tab rukta hai jab wo khatam hota hai.

Definition Paanch symbols — inhe upar ki timeline se padho

== $C_{i}$ (WCET)== — sabse zyada kitna time code ek baar run hone mein le sakta hai, sabse chauda possible green block. "Worst-Case Execution Time". Hum hamesha worst case use karte hain, kabhi average nahi.
== $T_{i}$ (period)== — same task ke do consecutive releases ke beech ki spacing (do blue release arrows).
== $D_{i}$ (relative deadline)== — release ke baad kitne time mein job khatam honi chahiye (red flag). Job on time hai agar wo flag pe ya pehle khatam ho jaaye.
== $R_{i}$ (response time)== — release se finish tak ka actual gap (black bracket). Job apna deadline tab meet karta hai jab $R_{i} \leq D_{i}$ .
== $U$ (utilisation)== — ek task set jo CPU ki fraction maangta hai. Ek task ko har $T_{i}$ seconds mein $C_{i}$ seconds chahiye, toh wo ek slice $U_{i} = C_{i} / T_{i}$ leta hai; saare $n$ tasks ke slices jodte hain to milta hai $U = \sum_{i} C_{i} / T_{i}$ .

Exact test kahan se aata hai — formula drop nahi, ek picture

Utilisation bound sirf ek rough gate hai. Exact sawaal "kya task $i$ kabhi miss karta hai?" ka jawab tab milta hai jab dekha jaaye ki kitni baar higher-priority tasks usse aage dhakelte hain. $h p (i)$ ka matlab hai "tasks ka set jinki priority $i$ se zyada hai". Rate-Monotonic ke under, ye woh tasks hain jinke periods chote hain.

Formula Response-Time Analysis — term by term build kiya

Figure dekho. Task $i$ ko apna $C_{i}$ kaam chahiye (base yellow block). Lekin jab bhi window ke andar ek higher-priority task $j$ release hota hai, wo $i$ ko preempt karta hai aur $i$ ki finish baad mein dhakelta hai.

$R_{i}$ length ki window mein, task $j$ ko $⌈ \frac{R _{i}}{T _{j}} ⌉$ baar release kiya jaata hai — ceiling isliye kyunki ek partial overlap bhi ek poora release trigger karta hai. Har release mein $C_{j}$ interference lagti hai. Saare higher-priority tasks pe sum karke: $R_{i} = C_{i} + \sum_{j \in h p (i)} ⌈ \frac{R _{i}}{T _{j}} ⌉ C_{j}$ $R_{i}$ dono sides pe kyun hai? Lambi window mein zyada preemptions aate hain, jo window ko aur lamba kar dete hain — toh hum iterate karte hain: $R_{i} = C_{i}$ se shuru karo, plug in karo, bada $R_{i}$ milega, phir plug in karo, jab tak grow karna band na ho. Task schedulable hai agar converged $R_{i} \leq D_{i}$ ho. $⌈ \cdot ⌉$ ceiling hai — agla poora number leke upper round karo, kyunki "aadha preemption" nahi hota.

True or false — justify karo

Hard real-time system ke liye bas bahut fast CPU chahiye.

False. Hard real-time mein provably bounded worst case chahiye, speed nahi; ek fast CPU jisme unbounded pauses hon (garbage collection, cache misses) wo deadlines miss kar sakta hai jab ek slow-but-deterministic MCU kabhi nahi karta.

Agar total utilisation

U \leq 1

ho, toh koi bhi task set schedulable hai.

False.

U \leq 1

ka sirf matlab hai CPU physically over-subscribed nahi hai; fixed-priority scheduling ke under worst-case phasing mein CPU waste hoti hai, toh tumhe

U \leq n (2^{1/ n} - 1)

chahiye ho sakta hai (jitna low as

0.693

Liu–Layland RM bound fail karna prove karta hai ki task set unschedulable hai.

False. Bound sufficient hai, necessary nahi — bound se upar bhi bahut sets har deadline meet karte hain; pakka karne ke liye exact Response-Time Analysis run karni padegi.

Firm deadline miss aur soft deadline miss utne hi haanikaarak hote hain.

False. Firm miss mein result bekar ho jaata hai toh tum use discard karte ho (value = 0); soft miss mein reduced lekin nonzero value rehti hai, toh tum late result rakh lete ho.

EDF koi bhi single-processor periodic set

U \leq 1

ke saath schedule kar sakta hai.

True (jab har

D_{i} = T_{i}

ho). EDF ek CPU pe periodic tasks ke liye optimal hai, toh implicit-deadline model mein

U \leq 1

pe saari deadlines meet hoti hain — poora processor use hota hai.

Average execution time ki jagah WCET use karna safe schedulability verdict deta hai.

False. Deadlines worst case mein miss hoti hain; averages demand undercount karte hain aur falsely "safe" answer dete hain, isliye WCET

C_{i}

use karna zaroori hai.

Soft real-time system mein deadline miss karna ek system error hai.

False. Soft real-time mein occasional misses design by tolerated hain; goal statistics bound karna hai (jaise 99.9% on time), zero misses prove karna nahi.

Rate-Monotonic lambe periods wale tasks ko higher priority deta hai.

False. RM chote periods (higher frequency) wale tasks ko higher fixed priority deta hai, kyunki un tasks ke paas next release se pehle kam slack

D_{i}

hota hai.

Agar har task ka response time uske WCET ke barabar ho, toh CPU pe koi preemption nahi ho raha.

True.

R_{i} = C_{i} + \sum ⌈ R_{i} / T_{j} ⌉ C_{j}

sirf tab

R_{i} = C_{i}

pe collapse hota hai jab interference sum zero ho, matlab koi higher-priority task ne usse preempt nahi kiya.

Error dhundo

"Humne loop ko 10,000 baar test kiya aur wo hamesha time pe khatam hua, toh hard deadline guaranteed hai."

Testing observed cases measure karti hai, worst case nahi; hard guarantee ke liye ek proof chahiye (WCET

C_{i}

+ schedulability test), kyunki untested worst path abhi bhi exist kar sakta hai.

"Hamaari utilisation

n = 3

ke liye

0.79

hai, jo RM bound

0.78

fail karta hai, toh hume redesign karna hoga."

Sufficient RM bound fail karna unschedulability prove nahi karta; pehle exact Response-Time Analysis run karo — set abhi bhi saari deadlines meet kar sakta hai.

"Humne utilisation sum mein average CPU cost

C_{i}

use kiya aur

U = 0.6

mila, safely schedulable."

Utilisation test ke liye WCET chahiye, average cost nahi; real worst-case values se

U

bound exceed kar sakta hai aur deadlines miss ho sakti hain.

"Deadline period ke barabar hai, toh hum analysis mein period ignore kar sakte hain."

Period

T_{i}

phir bhi govern karta hai ki task kitni baar release hota hai aur higher-priority tasks kitni baar preempt karte hain (

⌈ R_{i} / T_{j} ⌉

term), toh jab

D_{i} = T_{i}

ho tab bhi ignore nahi kar sakte.

"Late video frame ko buffer karke jaise hi aaye dikhana chahiye."

Ek video frame firm deadline hai — ek baar uska display slot guzar gaya toh uski zero value hai aur usse discard karna chahiye, late dikhana nahi, jo playback timing corrupt kar dega.

"Kyunki hamaara airbag controller usually 5 ms mein fire karta hai aur deadline 20 ms hai, toh hamare paas bahut margin hai."

Hard deadline ke liye "usually" irrelevant hai; guarantee worst-case execution (

C_{i}

) aur worst-case interference ke liye hold karni chahiye, typical run ke liye nahi.

"Humne CPU clock badhaaya, toh priority inversion ab concern nahi hai."

Faster clock unbounded blocking nahi hatata — ek low-priority task jo lock hold kar raha hai wo high-priority task ko stall karta hai; tumhe priority inheritance chahiye, zyada MHz nahi.

"Hamare tasks strict fixed period pe aate hain, toh unke arrivals by definition jitter-free hain."

Periodic model perfect spacing

T_{i}

assume karta hai, lekin real releases mein arrival jitter hota hai; agar arrivals bunch up ho sakti hain (sporadic/jittery model), toh tumhara worst-case interference pure-periodic analysis se zyada hoga.

Why questions

Real-time mein correctness mein kab kyun include hota hai, sirf kya nahi?

Kyunki deadline

D_{i}

ke baad deliver kiya gaya logically correct result bekar ya dangerous ho sakta hai (jaise crash ke baad airbag fire karna), toh timeliness specification ka hissa hai.

RM utilisation bound

1

se neeche kyun hai jabki EDF ka exactly

1

hai?

Fixed priorities worst-case phasing mein CPU ko idle force kar dete hain, capacity waste karte hain; EDF nearest deadline ke hisaab se priority re-decide karta hai, toh

U \leq 1

ke under kaam pending hone par kabhi idle nahi hota.

Response-Time Analysis mein ceiling

⌈ R_{i} / T_{j} ⌉

kyun aata hai?

Ye count karta hai ki higher-priority task

j

response window

R_{i}

mein kitni baar release hota hai — aur isliye task

i

ko kitni baar preempt karta hai — aur preemptions poore releases mein aate hain toh hum round up karte hain.

Response-Time Analysis ko iteration se kyun solve karna padta hai?

R_{i}

dono sides pe hai (badi response window zyada preemptions allow karti hai, jo window ko aur badhata hai), toh tum

R_{i} = C_{i}

se fix-point iterate karte ho jab tak value change karna band na ho.

U > 1

kyun guarantee karta hai ki deadline miss hogi chahhe scheduler koi bhi ho?

Kyunki tasks collectively ek CPU ke 100% se zyada time demand karte hain — ek physical impossibility — toh koi bhi scheduling order unhe saari time pe serve nahi kar sakta.

Graceful degradation soft ke liye design knob kyun hai, hard ke liye nahi?

Soft systems overload mein partial value rakhte hain (quality drop karo, frames skip karo), jabki hard system kabhi miss nahi kar sakta, toh load shed karna proof ka acceptable substitute nahi hai.

Sporadic task (sirf ek minimum inter-arrival gap) ko periodic ki tarah analyze kyun kiya jaata hai?

CPU ke liye uska worst case utni tez arrive karna hai jitna allowed hai, yaani exactly har minimum-gap pe; us minimum gap ko period

T_{i}

maanna interference ka safe upper bound deta hai.

Edge cases

Jab ek task ka WCET unbounded ho, toh schedulability ka kya hoga?

Koi bound nahi hoga, toh hard guarantee possible nahi hai; task ko redesign karna padega taaki uska finite, analyzable

C_{i}

ho, tab koi test apply hoga.

Exactly

U = n (2^{1/ n} - 1)

pe, kya RM task set schedulable hai?

Haan — bound

U \leq

threshold hai, toh equality abhi bhi sufficient test pass karta hai aur saari deadlines guarantee karta hai.

Jab

n \to \infty

, RM utilisation bound kis taraf jaata hai, aur iska kya matlab hai?

ln 2 \approx 0.693

approach karta hai, matlab bahut saare tasks ke saath tum RM ke under worst case mein sirf ~69% CPU safely use kar sakte ho.

Ek hard-deadline result jo ek instant late deliver ho, uski value kya hai?

Effectively

- \infty

(invalid/catastrophic) — hard deadline ek cliff hai, toh chota sa bhi overrun total failure maana jaata hai.

Agar task ka relative deadline

D_{i}

uske period

T_{i}

se chota hai (constrained deadline), toh kya EDF ke liye

U \leq 1

kaafi hai?

Zaroor nahi — simple

U \leq 1

bound

D_{i} = T_{i}

assume karta hai;

D_{i} < T_{i}

ke saath tumhe demand-bound ya processor-demand test chahiye, kyunki kam slack full utilisation se neeche bhi misses cause kar sakta hai.

Agar task ka relative deadline

D_{i}

uske period

T_{i}

se lamba hai (arbitrary deadline), toh simple analysis mein kya toot jaata hai?

Ek naya job release ho sakta hai pehle wali same task ki job khatam hone se pehle, toh tumhe multiple outstanding jobs per task track karne padte hain; plain single-job RTA aur

U \leq 1

EDF test apply nahi hote, aur processor-demand / busy-period analysis zaroori hai.

Arrival jitter wale sporadic task ke liye, safe rehne ke liye effective period ke roop mein kaun si value plug karein?

Minimum inter-arrival time (worst-case bunching), kyunki isse task doosron ko sabse zyada preempt karta hai; average ya nominal spacing use karna interference undercount karega aur false pass dega.

Ek soft task jo deadline miss kare 0 ms se (exactly

D_{i}

pe khatam ho) — kya usne deadline meet kiya?

Haan — condition

R_{i} \leq D_{i}

(inclusive) hai, toh exactly deadline pe khatam hona meet karna count hota hai, tardiness

max (0, R_{i} - D_{i}) = 0

ke saath.

In traps ke peechhe ki gehri machinery ke liye, dekho Worst-Case Execution Time analysis, Rate-Monotonic Scheduling, Earliest Deadline First (EDF), Priority Inversion and Priority Inheritance, Periodic vs Aperiodic Tasks, aur Jitter and Latency.

Recall Jaane se pehle ek-line self-test

Answers dhako aur har section se koi teenn items dobara karo; agar tum har ek ke liye reason bol sako (sirf verdict nahi), toh ye topic tumhara ho gaya.