Introduction
First-Come-First-Served (FCFS) and Shortest-Job-First (SJF) are the two simplest classic scheduling algorithms, and together they illustrate the core tradeoff in scheduling: simplicity and fairness of arrival order versus statistically optimal average waiting time. FCFS is non-preemptive and requires no knowledge of burst time. SJF exists in two forms — non-preemptive SJF, which picks the shortest job among those currently ready, and its preemptive variant, Shortest Remaining Time First (SRTF), which can interrupt a running process the instant a shorter one arrives.
Cricket analogy: A club nets session that lets batters bat strictly in arrival order (FCFS) needs no info about how long each will bat; letting whoever needs the least practice time go first (SJF) requires the coach to estimate each batter's session length in advance, and a version that yanks a batter out mid-session the moment a quicker one arrives (SRTF) is even more aggressive.
Algorithm
/* FCFS: sort strictly by arrival time, run each to completion, in order. */
void fcfs_order(process_t procs[], int n) {
/* sort procs[] by arrival_time ascending (ties broken by original order) */
int clock = 0;
for (int i = 0; i < n; i++) {
if (clock < procs[i].arrival_time) clock = procs[i].arrival_time;
clock += procs[i].burst_time;
procs[i].completion_time = clock;
}
}
/* Non-preemptive SJF: among processes that have ARRIVED and are not yet
* completed, always pick the one with the smallest burst_time. */
int pick_next_sjf(process_t procs[], int n, int done[], int clock) {
int best = -1;
for (int i = 0; i < n; i++) {
if (!done[i] && procs[i].arrival_time <= clock) {
if (best == -1 || procs[i].burst_time < procs[best].burst_time)
best = i;
}
}
return best; /* -1 means: no process has arrived yet, advance the clock */
}Explanation
FCFS's weakness is the convoy effect: if a long CPU-bound process runs first, every short process behind it (even I/O-bound ones that would otherwise return quickly) is forced to wait, dragging down average waiting time and starving the CPU/I/O overlap that keeps devices busy. Non-preemptive SJF fixes this by always choosing the shortest available job, which is provably optimal for minimizing average waiting time among non-preemptive algorithms when all jobs are ready simultaneously. Its own weakness is starvation: a long job can be repeatedly passed over by a stream of short arrivals and wait indefinitely. SJF also requires the scheduler to know (or estimate) burst times in advance, which is not always realistic.
Cricket analogy: If a team sends its slowest accumulator in first (convoy effect), every quick-scoring batter behind him is stuck padded up waiting; always promoting the fastest scorer next (SJF) fixes average time-to-boundary, but the naturally slow, patient accumulator can be repeatedly skipped down the order and never bat (starvation), and a coach must estimate scoring rates in advance to even plan it.
Example
/*
* Process | Arrival | Burst
* P1 | 0 | 5
* P2 | 1 | 3
* P3 | 2 | 8
* P4 | 3 | 6
*
* ---- FCFS Gantt chart (run strictly in arrival order) ----
* |--P1--|--P2--|-----P3-----|-----P4-----|
* 0 5 8 16 22
*
* ---- SJF (non-preemptive) Gantt chart ----
* At t=0 only P1 has arrived -> run P1.
* At t=5, P2(3), P3(8), P4(6) have arrived -> shortest is P2 -> run P2.
* At t=8, P3(8), P4(6) remain -> shortest is P4 -> run P4.
* At t=14, only P3(8) remains -> run P3.
* |--P1--|--P2--|-----P4-----|-----P3-----|
* 0 5 8 14 22
*/
Output
FCFS: completion times are P1=5, P2=8, P3=16, P4=22. Waiting times = completion - arrival - burst: P1 = 5-0-5 = 0, P2 = 8-1-3 = 4, P3 = 16-2-8 = 6, P4 = 22-3-6 = 13, giving average waiting time (0+4+6+13)/4 = 23/4 = 5.75. Average turnaround time is (5+7+14+19)/4 = 45/4 = 11.25. SJF: completion times are P1=5, P2=8, P4=14, P3=22. Waiting times: P1 = 5-0-5 = 0, P2 = 8-1-3 = 4, P4 = 14-3-6 = 5, P3 = 22-2-8 = 12, giving average waiting time (0+4+5+12)/4 = 21/4 = 5.25. Average turnaround time is (5+7+11+20)/4 = 43/4 = 10.75. SJF reduces both averages versus FCFS on this workload — but notice P3, the longest job, waits the most (12) under SJF, an early sign of the starvation risk.
Cricket analogy: In a net session, batting strictly in arrival order gives an average wait of 5.75 minutes per batter, but reordering by shortest session needed drops it to 5.25 -- though the one batter who genuinely needed the longest net time (P3) ends up waiting the longest of anyone, 12 minutes, foreshadowing that patient accumulators can get sidelined.
Key Takeaways
- FCFS is non-preemptive, simple, and fair by arrival order, but suffers from the convoy effect when a long job leads.
- Non-preemptive SJF minimizes average waiting time among ready processes but needs burst-time estimates and can starve long jobs.
- SRTF is the preemptive version of SJF: it re-evaluates on every new arrival and can interrupt a running process mid-burst.
- On the worked example, SJF beat FCFS: average waiting time 5.25 vs 5.75, average turnaround 10.75 vs 11.25.
- Always compute completion time first from the Gantt chart, then derive turnaround (completion - arrival) and waiting (turnaround - burst).
Practice what you learned
1. What causes the 'convoy effect' in FCFS scheduling?
2. In the worked example, what is the average waiting time under FCFS?
3. Why can non-preemptive SJF cause starvation?
4. What is the key difference between SJF and SRTF?
5. In the worked example, which process has the longest waiting time under SJF?
Was this page helpful?
You May Also Like
Scheduling Algorithms Overview
How the CPU scheduler picks the next ready process, the metrics used to judge it, and the family of algorithms available.
Priority and Round Robin Scheduling
Priority scheduling with starvation and aging, and Round Robin with a fully worked quantum-based Gantt chart.
Introduction to Process Scheduling
Learn why the OS schedules processes, the queues involved, and the basic goals of a scheduler.