WCET (Worst Case Execution Time) analysis: Foundations

5.5.13 · D1 · Coding › Embedded Systems & Real-Time Software › WCET (Worst Case Execution Time) analysis

Yeh page assume karta hai ki tumhe kuch nahi pata. parent note padhne se pehle, tumhe har woh symbol bina jhijhake padhna aana chahiye jo woh tumhare saamne rakhta hai. Isliye hum har ek cheez ek picture se build karte hain. Upar se neeche padho — har idea ek ladder ki rung hai jo neeche wali rung pe tikti hai.

1. "Execution time" kya hoti hai? (cycles)

Kisi bhi subscript ya sum se pehle, hume raw material chahiye: hum measure kaise karte hain ki code kitna time leta hai?

Ek metronome ki clicking ka picture banao. Har click pe CPU thodi si kaam finish kar sakta hai. Agar koi kaam 12,994 clicks leta hai, toh hum kehte hain woh 12,994 cycles leta hai.

Figure — WCET (Worst Case Execution Time) analysis

Yeh kyun chahiye: WCET analysis ka har number — 5 cycles, 100 cycles, 12,994 cycles — inhi ticks mein count hota hai. Yeh hamare ruler ka "inch" hai. Prerequisites Compiler Optimizations aur Cache Memory Architecture mein hain, lekin dil se ek cycle bas ek tick hai.

2. "Task" kya hota hai? Aur uska subscript $i$

Parent likhta hai $R_{i}$ , $C_{i}$ , $I_{i}$ , $D_{i}$ . Woh chhota $i$ logon ko darata hai. Nahi darana chahiye.

Ek numbered to-do list ka picture banao. $D_{3}$ = "item 3 ke saath deadline likhi hui hai". Bas itna hi ek subscript hota hai: ek address label.

Yeh kyun chahiye: scheduling formula ek waqt mein ek task ke baare mein baat karta hai. Subscript hume ek formula likhne deta hai jo har task ke liye kaam kare, bajaye iske ki hum har task ke liye alag copy karein.

3. Deadline $D_{i}$ — finish line

Ek running track ka picture banao. Gun cycle 0 pe fire hoti hai; finish line $D_{i}$ pe painted hai. Late cross karo → fail, aur ek safety-critical system mein "fail" ka matlab crash ho sakta hai.

Yeh kyun chahiye: WCET tabhi matter karta hai jab kisi cheez ke relative ho. Ek task ka 12,994 cycles lena theek hai agar deadline 20,000 hai, aur catastrophe hai agar deadline 10,000 hai. Deadline woh goalpost hai.

4. Worst-case execution time $C_{i}$ — asli hero

Ab main character. Note karo ki parent $C_{i}$ aur WCET word dono ek hi cheez ke liye use karta hai.

Figure dekho: bahut saare measured runs low cluster karte hain (histogram), lekin WCET sabse right wali wall hai — woh value jise kuch cross nahi kar sakta. Woh wall $C_{i}$ hai.

Aadhe do words jo tume straight rakhne hain (parent dono pe zor deta hai):

Ek ceiling ka sochho: safe matlab ceiling tumhare sar ke upar hai (tum use kabhi nahi thokate); tight matlab yeh faaltu 40 metre upar nahi hai.

5. Interference $I_{i}$ — ek taraf dhakele jaana

Ek counter pe queue ka picture banao jahan VIPs baar baar line cut karte rehte hain. Tumhari apni service $C_{i}$ leti hai, lekin line cut karne wale VIPs tumhe $I_{i}$ ka wait cost karte hain. Yeh waiting scheduling aur interrupts se aati hai.

Yeh kyun chahiye: tum vacuum mein nahi chalte. Deadline milna tumhare kaam plus doosron ke impose kiye delays par depend karta hai.

6. Response time $R_{i}$ aur schedulability formula

Ab har piece parent ki key equation mein fit ho jaata hai:

$R_{i}$ — response time: woh real moment jab task $i$ finish line cross karta hai.
$\le$ symbol matlab less-than-or-equal: "par ya pehle". Exactly deadline par bhi pass hai.

Figure do blocks stack karta hai — waiting ( $I_{i}$ ) phir working ( $C_{i}$ ) — aur dikhata hai ki total deadline line tak pahunchta hai ya nahi. Agar bar deadline line ke left khatam hota hai: schedulable. Agar aage nikal jaata hai: fail.

Yeh poora point kyun hai: poora subject ek trustworthy $C_{i}$ is inequality mein feed karne ke liye exist karta hai. Garbage $C_{i}$ → garbage guarantee.

7. Summation symbol $\sum$ — "ek list add karo"

Parent ki WCET decomposition $\sum$ use karti hai. Yeh bhi scary nahi hai.

Ek cash register ka picture banao jo receipts ek ek karke total karta hai. Woh hai $\sum$ .

Yeh kyun chahiye: ek program ka time bahut saare chhote blocks ke times ka total hota hai. Saikdon blocks ke liye $5 + 3 + 4 + 6 + \dots$ likhna pagalpan hai; $\sum$ ek saaf symbol mein "har block ka time add karo" kehta hai.

8. Block, path, aur paths par $max$

Yeh exactly parent ki decomposition hai, ab padhne layak: $WCET = max_{path} (\sum_{blocks in path} T_{block})$ "Har path ke liye, uske blocks ke times add karo; phir sabse bada path total rakho." Control Flow Graph (CFG) in saari paths ka map hai; Static Program Analysis woh tarika hai jisse hum unhe search karte hain.

9. Example ki arithmetic padhna

Parent find_max ke liye compute karta hai, loop body 3+4+6 cycles ke saath: $WCET = 5 + (n - 1) \times (3 + 4 + 6) + 2 = 13 n - 6$

Upar ki saari cheezein use karke decode kiya:

5 aur 2: blocks A aur E, har ek ek baar run hota hai (entry/exit — boundary cases).
(n-1): loop i=1 se i<n tak chalta hai, yaani $n - 1$ baar — ek loop bound jo analyzer ko batana padta hai.
(3+4+6): loop ke through worst path — if har baar liya jaata hai, block D ek cache miss (worst hardware mood).

Yeh sab topic mein kaise fit hota hai

Ise upar se padho: cycles block times banate hain, block times paths banate hain, sabse bada path WCET hai, aur WCET deadline test mein plug hota hai jo is poore subject ke exist karne ki wajah hai.

Equipment checklist

Dayi taraf cover karo. Agar tum har ek ka jawab de sako, tum parent note ke liye ready ho.

Clock cycle kya hota hai?

CPU ki clock ki ek tick — time ki sabse chhoti unit jisme hum code count karte hain.

C_{i}

mein subscript

i

ka kya matlab hai?

"task number

i

ka" — ek label jo ek particular task ki taraf point karta hai.

D_{i}

kya hai?

Task

i

ki deadline — woh moment jis tak use finish karna hai.

C_{i}

(WCET) ko ek sentence mein define karo.

Sabse lamba time jo task

i

kabhi akele run hone mein le sakta hai, saare inputs aur hardware states mein.

"Safe" aur "tight" mein kya farak hai?

Safe = true worst se kabhi neeche nahi; tight = uselessly bahut upar nahi.

Interference

I_{i}

kya hai?

Extra waiting jo task

i

par higher-priority tasks ke aage cut karne se force hoti hai.

Schedulability test state karo aur words mein padho.

R_{i} = C_{i} + I_{i} \leq D_{i}

— apna kaam plus waiting deadline par ya usse pehle land karna chahiye.

\sum

tumhe kya karne ko kehta hai?

Ek list se guzaro aur har item add karo.

max_{path}

ka kya matlab hai?

Code ke saare possible routes mein se, sabse bada total time wala rakho.

Average time ki jagah worst-case kyun?

Averages rare slow runs chhupate hain jo eventually hogi aur deadline miss cause kar sakti hain.

for(i=1;i<n;i++) mein kitni iterations chalti hain?

n - 1

n

nahi — off-by-one dhyan rakho.