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%)

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 (non-periodic) tasks with the arrival times, computation times and absolute deadlines tabulated above.

Find. (1) The FCFS schedule and its timing diagram; (2) whether FCFS meets every deadline; (3) the EDF schedule and its timing diagram.

Approach. Simulate both scheduling disciplines directly against the given arrival/computation/deadline data: FCFS runs each task to completion in arrival order (non-preemptive); EDF is preemptive and, at every arrival or completion event, always runs whichever ready task currently has the earliest absolute deadline.

1. FCFS schedule. T1 and T2 both arrive at t = 0; ties are broken in listed order (T1 before T2), so the non-preemptive run order is T1, T2, T3, T4:

   Task	Start	Finish	Deadline	Result
   T1	0	4	15	met (11 ms early)
   T2	4	7	12	met (5 ms early)
   T3	7 (arrived at 2, but CPU busy)	12	9	MISSED by 3 ms
   T4	12 (arrived at 5, but CPU busy)	14	8	MISSED by 6 ms

   Fig. Q5-1 — FCFS schedule (non-preemptive, run order T1→T2→T3→T4). Triangles mark arrival; red ticks mark each task's absolute deadline.
2. Analysis of the FCFS result. FCFS does not work for this task set: it services tasks strictly in the order they arrive, with no regard whatsoever for how urgent (close to its own deadline) each task is. T3 arrives at t=2 with the tightest deadline of the whole set (9 ms) but is queued behind T1 and T2 simply because they happened to arrive first and are already running/queued; by the time the CPU reaches T3 at t=7, only 2 ms remain before its deadline but T3 still needs 5 ms of computation, so it necessarily overruns. T4 then inherits the same problem one level worse. Two of four tasks (50%) miss their deadlines under FCFS, even though — as part (3) shows — a feasible schedule for this exact task set exists.
3. EDF schedule. EDF is preemptive: at each arrival, the scheduler compares the newcomer's deadline against the currently-running task's deadline and switches immediately if the newcomer is more urgent.
   • t=0: T1(d=15), T2(d=12) ready → run T2 (earlier deadline).
   • t=2: T3(d=9) arrives; 9 < T2's remaining deadline(12) → preempt, run T3. (T2 has done 2 of its 3 ms.)
   • t=5: T4(d=8) arrives; 8 < T3's deadline(9) → preempt, run T4. (T3 has done 3 of its 5 ms.)
   • t=7: T4 completes (needed only 2 ms) — deadline 8, met with 1 ms to spare. Next-earliest deadline among the ready set is T3(9) → resume T3 (2 ms remaining).
   • t=9: T3 completes — deadline 9, met exactly, zero slack. Next-earliest is T2(12) → resume T2 (1 ms remaining).
   • t=10: T2 completes — deadline 12, met with 2 ms to spare. Only T1 remains → run T1 (4 ms, uninterrupted).
   • t=14: T1 completes — deadline 15, met with 1 ms to spare.
   Fig. Q5-2 — EDF schedule (preemptive, earliest-absolute-deadline-first). All four tasks meet their deadlines; T3 finishes with zero slack at t=9.
   All four tasks meet their deadlines under EDF — every task in this set is schedulable, confirming (by EDF's optimality on a uniprocessor) that a feasible schedule exists for this task set at all, and that FCFS's two misses in part (2) were a failure of the policy, not a symptom of an infeasible workload.