FCFS vs. EDF Scheduling of Four Single-Instance Tasks: 19-Soft-A4 Real-Time Systems, December 2015, Q4

Question 4: 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. Task arrival times, computation times and absolute deadlines per the table above; FCFS ties (T1, T2 both arrive at t=0) broken by listing order.

Find. (1) The FCFS completion schedule; (2) whether every task meets its deadline under FCFS; (3) the EDF completion schedule and whether it meets every deadline.

Approach. FCFS is non-preemptive and ignores deadlines entirely, so it is simulated by simply running tasks in arrival order to completion. EDF is preemptive: at every instant the ready task with the earliest absolute deadline runs, so it must be simulated event-by-event (every arrival is a potential preemption point).

FCFS schedule. T1 and T2 both arrive at t=0; by listing order T1 runs first. Each subsequent task starts the instant the previous one finishes (its own arrival having already occurred by then). $$\text{T1: } 0\text{-}4 \quad \text{T2: } 4\text{-}7 \quad \text{T3: } 7\text{-}12 \quad \text{T4: } 12\text{-}14$$

Fig. Q4-1 — FCFS schedule. T3's deadline (9) falls inside its own execution window and T4's deadline (8) has already passed before T4 even starts.
Check FCFS against every deadline — does it work? T1 finishes at 4 (deadline 15, MET); T2 finishes at 7 (deadline 12, MET); T3 finishes at 12 but its deadline was 9 (MISSED by 3 ms); T4 finishes at 14 but its deadline was 8 (MISSED by 6 ms). FCFS does not work: it schedules purely by arrival order and is blind to deadlines, so the two tasks with the tightest deadlines (T3, T4) — which also happen to arrive latest — are forced to the back of the queue and both miss.
Re-schedule with EDF. EDF always runs the ready task with the earliest absolute deadline, preempting on every new arrival that has an earlier deadline than the task currently running. $$\text{T2: }0\text{-}2\ (\to\text{T3 arrives, }d{=}9<d_{T2}{=}12,\text{ preempt})\qquad \text{T3: }2\text{-}5\ (\to\text{T4 arrives, }d{=}8<d_{T3}{=}9,\text{ preempt})$$ $$\text{T4: }5\text{-}7\ (\text{completes, no preemption pending})\qquad \text{T3 resumes: }7\text{-}9\qquad \text{T2 resumes: }9\text{-}10\qquad \text{T1: }10\text{-}14$$

Fig. Q4-2 — EDF schedule. T4 finishes at 7 (deadline 8), T3 at 9 (deadline 9, exactly on time), T2 at 10 (deadline 12), T1 at 14 (deadline 15) — every deadline met.

Under EDF: T4 finishes at 7 (deadline 8, MET); T3 finishes at 9 (deadline 9, MET exactly, zero slack); T2 finishes at 10 (deadline 12, MET); T1 finishes at 14 (deadline 15, MET). All four deadlines are met — EDF succeeds precisely where FCFS failed, by continuously re-ranking the ready queue on urgency (deadline proximity) instead of arrival order.

Task	FCFS finish	FCFS result	EDF finish	EDF result
T1 (deadline 15)	4	Met	14	Met
T2 (deadline 12)	7	Met	10	Met
T3 (deadline 9)	12	Missed	9	Met (exact)
T4 (deadline 8)	14	Missed	7	Met

Concept & Theory

Topic. Non-preemptive arrival-order scheduling (FCFS) versus preemptive dynamic-priority deadline scheduling (EDF) on the same task set.

Key relations. FCFS completion: strictly cumulative sum of computation times in arrival order, independent of any deadline. EDF: at every ready-queue change, dispatch argmin(deadline) among ready tasks.

Why this works. FCFS is deadline-blind by construction — its schedule depends only on when tasks arrive, so a task with an urgent deadline but a late arrival (T4: arrives at 5, deadline 8) is structurally disadvantaged. EDF re-evaluates urgency at every event, so the same task set becomes schedulable simply by re-ordering execution around actual deadline pressure rather than arrival order, with no change to any task's computation time.

Common pitfall. Forgetting that EDF is preemptive and stopping a task's simulation at its first dispatch instead of resuming it later when a higher-urgency task's segment ends (T2 and T3 each run in two separate segments here); and reporting T3's EDF finish as anything other than exactly 9 — a zero-slack finish is a valid MET, not a borderline miss.

Source. Liu, Real-Time Systems, Ch. 3, 6 (scheduling algorithms, EDF); Buttazzo, Hard Real-Time Computing Systems, Ch. 4 (EDF optimality and schedulability).

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

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