NivaarExam PrepOfficial exam papers ↗

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

Question 5 of 6: FCFS vs. EDF Scheduling of Four Periodic Real-Time Tasks

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 5: FCFS vs. EDF Scheduling of Four Periodic Real-Time 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.

TaskArrival $a_i$ (ms)Computation $C_i$ (ms)Absolute deadline $D_i$ (ms)
T10412
T2025
T3228
T45114

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

Approach. FCFS is non-preemptive and dispatches strictly in arrival order; EDF is preemptive and, at every instant, runs whichever ready task has the earliest absolute deadline, preempting the current task if a newly-ready one is more urgent.

(1) FCFS schedule.

  1. Dispatch order. Arrival order is T1(0), T2(0), T3(2), T4(5); T1 and T2 tie at $t=0$ and are taken in index order.
  2. Run each to completion, back to back. $$\text{T1: } [0,4) \quad \text{T2: } [4,6) \quad \text{T3: } [6,8) \quad \text{T4: } [8,9).$$
FCFS schedule (non-preemptive, arrival order T1,T2,T3,T4)01234567891011121314t (ms)T14D=12T22D=5T32D=8T41D=14^ = arrival | (red) = absolute deadline
Figure 3 — FCFS schedule. T2 finishes at $t=6$, one ms past its 5 ms deadline.

(2) Analysis — does FCFS meet every deadline? No. T1 finishes at 4 (deadline 12, met by 8 ms); T2 finishes at 6 but its deadline is 5 — missed by 1 ms; T3 finishes at 8, exactly meeting its deadline of 8; T4 finishes at 9 (deadline 14, met). FCFS ignores deadline urgency entirely — it let the low-urgency, long T1 (12 ms slack) run first purely because it arrived first, which delayed the high-urgency T2 (only 5 ms deadline) past its due time. This is the classic FCFS failure mode: arrival order and deadline urgency are unrelated, so FCFS provides no deadline guarantee even when the total workload is schedulable.

(3) EDF reschedule.

  1. t=0: ready = {T1(D12), T2(D5)}; earliest deadline T2 runs.
  2. t=2: T2 finishes (ran 2 ms, deadline met at 2≤5); T3 arrives (D8). Ready={T1(D12),T3(D8)}; T3 (earlier deadline) runs.
  3. t=4: T3 finishes (deadline met at 4≤8). Ready={T1(D12)} only (T4 not yet arrived); T1 runs.
  4. t=5: T4 arrives (D14) but T1 (D12) still has the earlier deadline and is already running — EDF does not preempt for a later deadline, so T1 continues.
  5. t=8: T1 finishes (ran 4 ms total, deadline met at 8≤12). Ready={T4(D14)}; T4 runs.
  6. t=9: T4 finishes (deadline met at 9≤14).
EDF schedule (preemptive, earliest absolute deadline first)01234567891011121314t (ms)T14D=12T22D=5T32D=8T41D=14^ = arrival | (red) = absolute deadline
Figure 4 — EDF schedule. All four deadlines are met (T2 at 2, T3 at 4, T1 at 8, T4 at 9).
TaskFCFS finishFCFS resultEDF finishEDF result
T1 (D=12)4met8met
T2 (D=5)6MISSED2met
T3 (D=8)8met (exactly)4met
T4 (D=14)9met9met

Note on the source: this question's stem, table structure and figure notes are printed identically three times (as "Question 1/Table 1 for Q1," "Question 2/Table 1 for Q2," "Question 3/Table 1 for Q3") with the same Table 1 values each time.