The metrics, FCFS and SJF

Aisha starts the compile at 0 ms. The music player wakes at 1 ms, the browser at 2 ms, and she presses a key in the editor at 3 ms.

The editor needs the core for one millisecond. That is all.

Run these in arrival order and the editor gets its answer at 16 ms. It waited twelve milliseconds for one millisecond of work.

Aisha sees a stutter. Nothing was broken. It was just the order.

Why & what

The four times you must be able to name.

• Arrival time — when the process joined the ready queue.
• Burst time — how long its CPU burst needs.
• Completion time — when it finished.
• Response time — when it first got a core, minus arrival.

The three measures built from those.

• Turnaround time = completion − arrival. Total time in the system.
• Waiting time = turnaround − burst. Time spent doing nothing.
• Response time = first run − arrival. How long before anything at all happens.

The one people get wrong is waiting time. It is not "time before it started". It is all the time it was in the system but not on the core, including time after a preemption.

FCFS — first come, first served. Exactly what the name says. Run them in arrival order. Non-preemptive.

On our snapshot the order is 2317, 2088, 2104, 2210. The compile job holds the core for its full 8 ms, and everything else queues behind it.

• Average turnaround: 10.75 ms
• Average waiting: 6.75 ms
• The editor waits 12 ms for 1 ms of work.

This is the convoy effect: short jobs stuck behind one long job, like small cars behind a truck on a single-lane road. FCFS is simple and completely fair by arrival, and it produces terrible waiting times whenever a long job arrives first.

SJF — shortest job first. Whenever the core is free, pick the process with the smallest CPU burst. Still non-preemptive: once a job starts, it finishes.

On our snapshot the compile job still runs first, because at 0 ms it is the only process that has arrived. But at 8 ms the scheduler picks the 1 ms editor, then the 2 ms music player, then the 5 ms browser.

• Average turnaround: 9.5 ms
• Average waiting: 5.5 ms

SJF is provably optimal for average waiting time among non-preemptive algorithms. Putting short jobs first always lowers the average, because a short job's own gain is bigger than the small delay it adds to each long one.

How it works

Reading a Gantt chart, which is what an interview will ask you to draw:

1. Start at time 0 and list which processes have arrived.
2. Apply the rule — earliest arrival for FCFS, smallest burst for SJF — and pick one.
3. Draw its block from the current time to current time plus its burst. Non-preemptive means the block is never split.
4. Advance the clock to the end of that block and add any process that arrived during it.
5. Repeat until the queue is empty, then read the completion times off the chart and compute the three measures.

Common confusion

"SJF is the best algorithm, so why not always use it?" Because it requires knowing the burst length before running the process. The OS cannot know that. Real systems estimate the next burst from previous ones, which works reasonably for steady programs and badly for erratic ones. SJF is a benchmark to measure against, not a thing you can simply switch on.

"SJF has no downside." It can starve long jobs. If short jobs keep arriving, the compile job never becomes the shortest and never runs. Topic 3.4 deals with this.

"FCFS is preemptive if a higher-priority job arrives." No. FCFS has no priorities and no preemption at all. If you want the preemptive version of "shortest first", that is SRTF, and it is the next topic.

Interview angle

You will be handed a table of arrival and burst times and asked to draw the Gantt chart and compute averages. Practise until the arithmetic is automatic.

Two things earn extra credit beyond the numbers.

First, naming the convoy effect when FCFS produces a bad result, and explaining it in one line: short jobs stuck behind one long job.

Second, saying that SJF is optimal for average waiting time but not implementable, because burst lengths are not known in advance. Interviewers ask "why not just use SJF?" specifically to see whether you know this.