Pre-emptive Priority Scheduling vs. Cooperative Scheduling: 19-Soft-A4 Real-Time Systems, December 2015, Q5

Question 5: Pre-emptive Priority Scheduling vs. Cooperative Scheduling (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.

Check: the source states only an arrival order, not distinct arrival times, so this solution reads all four tasks as arriving at (or infinitesimally after) t=0 in the stated order 1,2,3,4 — i.e. the CPU is first given Task 1 (nothing else is ready yet), and Tasks 2/3/4 join the ready queue essentially immediately after. Interrupt latency is modelled as genuine overhead (CPU time spent servicing the preemption itself, not progress on any task) charged only when a strictly higher-priority task's arrival actually preempts the one currently running — not on every dispatch.

Given. Task 1: 10 ms, priority 2. Task 2: 20 ms, priority 1 (highest). Task 3: 30 ms, priority 3. Task 4: 40 ms, priority 4 (lowest). Arrival order (1,2,3,4); interrupt latency λ = 1.0 ms.

Find. (a) Task 3's completion time under pre-emptive fixed-priority scheduling. (b) Task 3's completion time under cooperative (non-preemptive) scheduling.

Approach. Under pre-emptive priority scheduling the CPU always runs the highest-priority ready task, so only Task 2's arrival (priority 1, higher than the running Task 1) causes an actual preemption — Tasks 3 and 4 arrive with lower priority than whatever is currently running, so they simply queue. Under cooperative scheduling no running task is ever interrupted, so the CPU processes strictly in dispatch order: whichever task the (idle) CPU picks up first runs to completion before the next dispatch decision is made.

Pre-emptive priority: Task 1 starts, is immediately preempted by Task 2. Task 1 begins at t=0 (nothing else is ready). Task 2 arrives essentially at once and, having strictly higher priority, preempts it; 1.0 ms of interrupt-latency overhead is spent servicing the preemption before Task 2's own execution begins (Task 1 has made 0 ms of progress at this point, since the arrival is coincident with its own start). $$t_{\text{Task2 starts}} = \lambda = 1.0\ \text{ms}$$
Task 2 runs to completion (no further preemption — Tasks 3, 4 are both lower priority). $$t_{\text{Task2 finish}} = 1.0 + 20 = 21.0\ \text{ms}$$ Task 1 then resumes with its full 10 ms remaining (it had made no progress before being preempted), and no further interrupt latency is charged — this is a normal dispatch on completion, not a priority preemption. $$t_{\text{Task1 finish}} = 21.0 + 10 = 31.0\ \text{ms}$$
Dispatch Task 3, then Task 4, strictly in priority order (both still lower priority than nothing now running). $$t_{\text{Task3 finish}} = 31.0 + 30 = \boxed{61.0\ \text{ms}}$$ $$t_{\text{Task4 finish}} = 61.0 + 40 = 101.0\ \text{ms}$$ (a) Task 3 completes at t = 61.0 ms under pre-emptive priority scheduling.
Cooperative scheduling: no task is ever interrupted once dispatched. Task 1 arrives first to an idle CPU and runs uninterrupted to completion (Task 2's higher priority is irrelevant under cooperative scheduling — it can only wait). $$t_{\text{Task1 finish, coop}} = 10\ \text{ms}$$ The CPU is then free and dispatches the highest-priority task in the ready queue — Task 2 — which likewise runs to completion uninterrupted. $$t_{\text{Task2 finish, coop}} = 10 + 20 = 30\ \text{ms}$$ Task 3 is dispatched next (the only remaining higher-priority-than-Task-4 candidate): $$t_{\text{Task3 finish, coop}} = 30 + 30 = \boxed{60.0\ \text{ms}}$$ (b) Task 3 completes at t = 60.0 ms under cooperative scheduling — 1.0 ms sooner than under pre-emptive priority scheduling, exactly the interrupt-latency overhead that pre-emption paid to get the higher-priority Task 2 finished earlier (t=21 vs. t=30).

Quantity	Pre-emptive priority	Cooperative
Task 2 (highest priority) finish	21.0 ms	30.0 ms
Task 1 finish	31.0 ms	10.0 ms
Task 3 finish (asked)	61.0 ms	60.0 ms
Task 4 finish	101.0 ms	100.0 ms

Concept & Theory

Topic. Fixed-priority pre-emptive scheduling with interrupt-latency overhead, contrasted with cooperative (run-to-completion) scheduling.

Key relations. Pre-emptive: highest-priority ready task always runs; each genuine preemption costs a fixed interrupt-latency λ of overhead. Cooperative: a running task is never interrupted; the ready queue is consulted only at each voluntary dispatch point.

Why this works. Pre-emption buys the highest-priority task (Task 2) a 9 ms earlier finish (21 vs. 30 ms) — the entire point of a priority scheduler — at the cost of a small, fixed overhead tax (1.0 ms here) that is paid once, at the single point where a higher-priority task actually displaces a running lower-priority one. Every lower-priority task downstream (Task 3, Task 4) is delayed by exactly that overhead relative to the cooperative case, since no useful work happens during the interrupt-latency window.

Common pitfall. Assuming pre-emptive scheduling is unconditionally "faster" for every task — it is faster only for the task(s) whose priority triggered the preemption; every task queued behind the preemption point pays the latency overhead pre-emption introduced, which is exactly why Task 3 finishes 1 ms later here under the pre-emptive scheme than under cooperative scheduling.

Source. Liu, Real-Time Systems, Ch. 3, 6 (priority-driven pre-emptive vs. non-preemptive scheduling); Buttazzo, Hard Real-Time Computing Systems, Ch. 2, 4 (interrupt latency and its effect on schedulability).

Question 5 of 6: Pre-emptive Priority Scheduling vs. Cooperative Scheduling

Question 5: Pre-emptive Priority Scheduling vs. Cooperative Scheduling (20%)