NivaarExam PrepOfficial exam papers ↗

19-Soft-A4 Real-Time Systems · Undated paper

Question 6 of 6: Pre-emptive Priority Scheduling with Interrupt Overhead

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

Note. Pages 3–4 print the same question stem three times side by side with only the supporting data table changed. The six distinct question stems are solved once each below, using the first data variant printed for each; the repeated variants are noted at the end of the relevant question.

National Exams — 04-Soft-A4 Real-Time Systems. Three-hour, closed-book exam (Casio or Sharp approved calculators only). Cover page states: "Any five questions constitute a complete paper. Only the first five questions as they appear in your answer book will be marked. All questions are of equal value (20% each)." All six distinct questions recovered from the source are solved below for completeness. Where a doubt exists as to interpretation, the candidate is expected to state assumptions — engineering assumptions used below are flagged in check callouts.

Reference texts: Jane W. S. Liu, Real-Time Systems (Prentice Hall, 2000) — task models, timing requirements, FCFS/EDF and priority scheduling; Giorgio C. Buttazzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Springer, 3rd ed.) — preemptive fixed-priority and dynamic-priority scheduling; Hermann Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications (Springer, 2nd ed.) — distributed real-time control, network-induced delay; Katsuhiko Ogata, Modern Control Engineering (Pearson, 5th ed.) — frequency-domain stability, phase margin, transport-lag systems; Ian Sommerville, Software Engineering (Pearson, 10th ed.) — general software-engineering process context.

Question 6: Pre-emptive Priority Scheduling with Interrupt Overhead (20%)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given.

TaskTime required (ms)Priority (1 = highest)
Task 152
Task 2101
Task 324
Task 483

Arrival order: Task 1, Task 2, Task 3, Task 4 (each arriving in quick succession, before the currently-running task finishes); every context switch (an interrupt-driven preemption, or the dispatcher choosing the next task after a completion) costs 1.0 ms.

Find. (a) Elapsed time from $t=0$ until Task 3 completes, under preemptive-priority scheduling. (b) The same, under cooperative (non-preemptive) scheduling.

Approach. Under preemptive priority, the CPU always runs the highest-priority ready task, interrupting a lower-priority task in progress; each such switch costs the 1.0 ms overhead. Under cooperative scheduling, a task that has started keeps the CPU until it finishes — no in-progress task is ever interrupted — after which the dispatcher (still, in general, respecting priority order among the tasks waiting) picks the next one; because nothing is pre-empted, no interrupt overhead is incurred at all.

(a) Preemptive-priority trace.

  1. Task 1 starts on an idle CPU (no switch needed). Task 2 (priority 1, highest) arrives immediately after and preempts Task 1: switch cost $1.0$ ms, so Task 2 begins at $t=1$.
  2. Task 2 runs to completion (priority 1 — nothing can preempt it): $1+10=\boxed{t=11}$.
  3. Resume Task 1 (still the highest-priority task ready, over Task 3/Task 4 which are lower priority): switch cost $1.0$ ms $\to t=12$; Task 1 runs its full remaining $5$ ms $\to t=17$.
  4. Dispatch the next-highest ready task — Task 4 (priority 3) over Task 3 (priority 4): switch cost $1.0$ ms $\to t=18$; Task 4 runs $8$ ms $\to t=26$.
  5. Finally dispatch Task 3 (lowest priority, last to run): switch cost $1.0$ ms $\to t=27$; Task 3 runs its $2$ ms $\to \boxed{t=29}$.
Preemptive-priority schedule (1 = highest), interrupt overhead = 1.0 ms0246810121416182022242628t (ms)T210T15T48T32solid colour = execution grey sliver = context-switch / interrupt overhead
Figure 5 — preemptive-priority execution order (Task 2 → Task 1 → Task 4 → Task 3), each block preceded by its 1.0 ms switch overhead. Task 3 completes at $t=29$ ms.

(b) Cooperative (non-preemptive) scheduling. Task 1 starts at $t=0$ and — since nothing preempts it under cooperative scheduling — runs to completion: $[0,5)$. At $t=5$ the dispatcher picks the highest-priority task among those waiting (Task 2, Task 3, Task 4): Task 2 (priority 1) runs $[5,15)$. Next, Task 4 (priority 3) outranks Task 3 (priority 4): Task 4 runs $[15,23)$. Finally Task 3 runs $[23,25)$. No interrupt overhead is incurred anywhere, since no task is ever forced off the CPU mid-execution: $$t_{\text{cooperative}} = 5+10+8+2 = \boxed{25\ \text{ms}}.$$

Scheduling policyTask 3 completion time
(a) Preemptive priority (4 switches × 1.0 ms overhead)29 ms
(b) Cooperative / non-preemptive (0 ms overhead)25 ms

The two policies dispatch the four tasks in the same priority order (Task 2, Task 1, Task 4, Task 3) and do the same 25 ms of total work; the entire 4 ms difference is the cost of the four context switches that preemption introduces — the price paid for Task 2 being able to interrupt Task 1 immediately on arrival, rather than waiting for Task 1 to finish first.

Back to the paper →