FCFS vs. EDF Scheduling of Four Single-Instance Tasks: 19-Soft-A4 Real-Time Systems, May 2016, Q5

Question 5: FCFS vs. EDF Scheduling of Four Single-Instance Tasks (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. Four independent, single-instance (aperiodic) tasks, each with an arrival time $a_i$, a computation time $C_i$ and an absolute deadline $D_i$ (all in ms):

Task	Arrival $a_i$	Computation $C_i$	Absolute deadline $D_i$
T1	0	4	15
T2	0	3	12
T3	2	5	9
T4	5	2	8

Find. (1) The FCFS schedule and timing diagram. (2) Whether FCFS meets every deadline. (3) The EDF schedule and timing diagram, and whether EDF meets every deadline.

Approach. FCFS is non-preemptive: tasks are queued in arrival order (T1 and T2 both arrive at $t=0$; T1 is served first, in the order listed) and each runs to completion once started. EDF is preemptive: at every arrival or completion event, the processor switches to whichever ready task has the earliest absolute deadline.

Part (1) — FCFS schedule. Running each task to completion in arrival order T1→T2→T3→T4:

T1 runs $[0,4)$ — finishes at 4 (deadline 15, met).
T2 runs $[4,7)$ — finishes at 7 (deadline 12, met).
T3 arrived at $t=2$ but the CPU is busy until $t=7$; it runs $[7,12)$ — finishes at 12, but its deadline is 9: $\boxed{\text{T3 misses by 3 ms}}$.
T4 arrived at $t=5$ but the CPU is busy until $t=12$; it runs $[12,14)$ — finishes at 14, but its deadline is 8: $\boxed{\text{T4 misses by 6 ms}}$.

Figure 3 — FCFS timing diagram. T3 and T4 both finish after their absolute deadlines (red markers).

Part (2) — does FCFS work? No. FCFS runs tasks strictly in arrival order with no regard for urgency, so it lets T1 and T2 — both arriving first but with the loosest deadlines (15 ms, 12 ms) — occupy the CPU while T3 (deadline 9 ms) sits ready and idle from $t=2$ onward, and later T4 (deadline 8 ms, the tightest of all four) waits behind everything. Two of the four tasks, T3 and T4, miss their deadlines. FCFS is deadline-blind and is unsuitable whenever tasks with tight deadlines can arrive after tasks with loose ones.

Part (3) — EDF schedule. At each decision point the scheduler picks the ready task with the smallest absolute deadline, preempting the running task if a more urgent one becomes ready:

$t=0$: ready = {T1 (D=15), T2 (D=12)}. Run T2 (earlier deadline).
$t=2$: T3 arrives (D=9), more urgent than T2's remaining work. Preempt T2 (1 ms done, 2 ms left) and run T3.
$t=5$: T4 arrives (D=8), more urgent than T3 (D=9). Preempt T3 (3 ms done, 2 ms left) and run T4 to completion: finishes at $t=7$ (deadline 8, met).
$t=7$: ready = {T1 (D=15), T2 (D=12, 1 ms left), T3 (D=9, 2 ms left)}. Resume T3, finishes at $t=9$ (deadline 9, met exactly).
$t=9$: ready = {T1 (D=15), T2 (D=12, 1 ms left)}. Resume T2, finishes at $t=10$ (deadline 12, met).
$t=10$: only T1 remains. Run T1 to completion: finishes at $t=14$ (deadline 15, met). $\boxed{\text{All four deadlines met under EDF.}}$

Figure 4 — EDF timing diagram. Every task's completion (end of its last segment) falls at or before its red deadline marker.

Scheduler	Finish times (T1,T2,T3,T4)	Deadlines met?
FCFS (non-preemptive, arrival order)	4, 7, 12, 14	No — T3 (by 3 ms), T4 (by 6 ms) miss
EDF (preemptive, earliest deadline first)	14, 10, 9, 7	Yes — all four met

Concept & Theory

Topic. Fixed queue-order (FCFS) vs. dynamic-priority preemptive (EDF) uniprocessor scheduling of aperiodic real-time tasks.

Key relations. FCFS priority = arrival order (static, deadline-blind). EDF priority $=1/D_i(t)$ — the task with the smallest remaining absolute deadline always runs; ties aside, EDF is proven optimal for scheduling a single processor: if any algorithm can meet all deadlines for a given task set, EDF can too (Horn's theorem, extending the periodic-task EDF optimality result of Liu & Layland, 1973).

Why this works. EDF continuously re-ranks the ready queue as new, more urgent tasks arrive, which is exactly what lets it rescue T3 and T4 — both of which FCFS starves behind less urgent work that merely happened to arrive first. Because EDF is preemptive, it can interrupt T2's or T3's execution the instant a tighter deadline appears, then resume the interrupted task later without losing correctness, provided the total processor demand still fits.

Common pitfall. Treating EDF as non-preemptive (it must be able to interrupt a running task) or confusing a task's relative deadline (time after arrival) with its absolute deadline (the wall-clock instant used for comparison) — the schedule above compares absolute deadlines throughout.

Source. Liu, Real-Time Systems, Ch. 6 (dynamic-priority scheduling, EDF); Buttazzo, Hard Real-Time Computing Systems, Ch. 4 (EDF optimality and preemptive scheduling).

Question 5 of 6: FCFS vs. EDF Scheduling of Four Single-Instance Tasks

Question 5: FCFS vs. EDF Scheduling of Four Single-Instance Tasks (20%)