Computer Organization & Embedded System — Real-Time Operating and Control System, NEC licence examination syllabus (Nepal Engineering Council).
Task Scheduling: the numerical goldmine of this subject
Every scheduling question reduces to one skill: drawing a correct Gantt chart.
Key formulas (memorize these):
Completion Time (CT) = when the process finishes
Turnaround Time (TAT) = CT − Arrival Time
Waiting Time (WT) = TAT − Burst Time
Response Time = time of first CPU allocation − Arrival Time
average wait depends on the ORDER, not the total work With long = 7 ms, n = 3, fcfs = 5.25, sjf = 1.75.
Push the long job to 20 ms with 8 jobs behind it — FCFS makes everyone wait for it, while SJF makes only that one job wait.
Worked example — FCFS (First Come First Serve)
Processes P1(burst=4), P2(burst=3), P3(burst=1), all arrive at time 0, in that order.
P1: CT=4, TAT=4−0=4, WT=4−4=0
P2: CT=7, TAT=7−0=7, WT=7−3=4
P3: CT=8, TAT=8−0=8, WT=8−1=7
Average Waiting Time = (0+4+7)/3 = 3.67
FCFS is simple but suffers from the convoy effect — short jobs stuck waiting behind one long job. Imagine standing behind someone doing a huge grocery run at a single-checkout store — that's the convoy effect.
Worked example — SJF (Shortest Job First, non-preemptive)
Same three processes — SJF picks the shortest burst first: order becomes P3(1), P2(3), P1(4).
P3: CT=1, WT=0
P2: CT=4, WT=4−3=1
P1: CT=8, WT=8−4=4
Average Waiting Time = (0+1+4)/3 = 1.67 ← better than FCFS!
SJF minimizes average waiting time — it's provably optimal for that metric — but it needs to know burst times in advance, which is unrealistic, and can starve long jobs.
Worked example — Round Robin (quantum = 2)
Same processes, time quantum = 2. Each process gets a 2-unit turn, then goes to the back of the queue if not finished.
P1: runs 0–2, then 5–7 → CT=7, TAT=7, WT=7−4=3
P2: runs 2–4, then 7–8 → CT=8, TAT=8, WT=8−3=5
P3: runs 4–5 (finishes, burst=1) → CT=5, TAT=5, WT=5−1=4
Average Waiting Time = (3+5+4)/3 = 4.0
Round Robin is fair (every process gets regular turns) but a badly-chosen quantum hurts performance — too small → too many context switches; too large → behaves like FCFS. This exact algorithm is what your phone uses to keep dozens of apps feeling "responsive" at once.
EDFEarliest Deadline First — dynamic priority: whichever task's deadline is soonest runs next. Provably optimal for meeting deadlines if any schedule can.
RMS schedulability test (sufficient condition):
Σ (Cᵢ / Tᵢ) ≤ n(2^(1/n) − 1)
Cᵢ = execution time, Tᵢ = period, n = number of tasks
For n=3, bound ≈ 0.7798 — if utilization exceeds this, RMS may or may not still work (test is sufficient, not necessary).
💡 Practice full Gantt charts for FCFS, SJF (both preemptive/non-preemptive), Round Robin, and Priority scheduling with the SAME set of processes — that's the most efficient way to compare them for revision.
The comparison, on one set of processes
Take P1 = 7, P2 = 4, P3 = 1, P4 = 4, all arriving at time 0. Total work is 16 units either way — only the order changes.
FCFS — run them in arrival order P1, P2, P3, P4
P1 waits 0 P1 runs 0–7
P2 waits 7 P2 runs 7–11
P3 waits 11 P3 runs 11–12
P4 waits 12 P4 runs 12–16
Average waiting time = (0 + 7 + 11 + 12) / 4 = 7.5
The average wait halves — 7.5 down to 3.75 — with the same jobs doing the same total work. Nothing ran faster; the CPU was busy for exactly 16 units in both cases. Only the order changed.
💡 This is the convoy effect: one long job at the front of the queue makes every short job behind it wait. Putting the short jobs first means only one job — the long one — pays a large wait, instead of everyone paying it. SJF is provably optimal for average waiting time, and this is why.
What SJF costs, and why it cannot be used as stated
Two problems, and both are standard exam questions.
⚠️ The objections to shortest-job-first
StarvationA long job can be postponed indefinitely if short jobs keep arriving. Its wait is unbounded — it may never run at all.
Burst time is unknownThe scheduler does not know how long a job will run until it has finished. SJF requires information it cannot have.
The second is why SJF is a benchmark rather than an implementable algorithm: it defines the best achievable average wait, and real schedulers estimate burst times from recent history — typically an exponential average of a process's previous bursts — to approximate it.
💡 The fix for starvation is ageing: gradually raise the priority of any job that has been waiting a long time, so eventually it outranks the newcomers and runs. The same technique fixes starvation in priority scheduling, where a low-priority job can otherwise be blocked forever by a stream of higher-priority ones.
Why Round Robin exists despite being worse on average
Round Robin usually gives a higher average waiting time than SJF. It is still the default in interactive systems, and the reason is that average waiting time is the wrong measure there.
What an interactive user notices is response time — how long until the program reacts at all, not how long until it finishes. Round Robin gives every process the CPU within one cycle of the queue, so nothing appears frozen. A scheduler that finishes work sooner on average while leaving one window unresponsive for ten seconds is worse to use, however good its numbers look.
💡 The time quantum sets the trade-off. Too large and Round Robin degenerates into FCFS, since most jobs finish within their slice. Too small and context-switch overhead dominates, so the CPU spends its time switching rather than working. The quantum should be comfortably larger than a context switch and comfortably smaller than a typical burst.