</>EmbeddedInterview

Compare FCFS, SJF, SRTF and Round Robin with a worked example.

MediumOperating System Concepts

Short answer: FCFS runs jobs in arrival order (simple, but short jobs wait behind long ones). SJF picks the shortest next CPU burst (optimal average waiting time if bursts are known, non-pre-emptive). SRTF is the pre-emptive version: a newly arrived job pre-empts the current one if its burst is shorter than the remaining time. Round Robin gives each job a fixed time slice in turn (fair, good response time; performance depends on the quantum).

Example processes (times in ms)

Process Arrival Burst
P1 0 8
P2 1 4
P3 2 9
P4 3 5

Waiting time = finish − arrival − burst.

FCFS

| P1 0-8 | P2 8-12 | P3 12-21 | P4 21-26 |

Waiting: P1 0, P2 7, P3 10, P4 18 → average 8.75 ms.

SJF (non-pre-emptive): at t = 0 only P1 is there, so it runs to completion. At t = 8 the shortest is P2 (4), then P4 (5), then P3 (9).

| P1 0-8 | P2 8-12 | P4 12-17 | P3 17-26 |

Waiting: P1 0, P2 7, P4 9, P3 15 → average 7.75 ms.

SRTF (pre-emptive SJF): at t = 1, P2 (4) is shorter than P1's remaining 7, so P2 pre-empts.

| P1 0-1 | P2 1-5 | P4 5-10 | P1 10-17 | P3 17-26 |

Waiting: P1 17−0−8 = 9, P2 0, P3 15, P4 2 → average 6.5 ms (the best of the four).

Round Robin, quantum 4 ms (new arrivals join the queue before a pre-empted job is re-queued)

| P1 0-4 | P2 4-8 | P3 8-12 | P4 12-16 | P1 16-20 | P3 20-24 | P4 24-25 | P3 25-26 |

Finish: P1 20, P2 8, P3 26, P4 25. Waiting: P1 12, P2 3, P3 15, P4 17 → average 11.75 ms, worse average waiting, but every job got the CPU within 12 ms of arriving (best worst-case response).

Comparison

Algorithm Pre-emptive Avg waiting Starvation? Notes
FCFS no poor (convoy effect) no simplest
SJF no optimal among non-pre-emptive yes, for long jobs needs burst prediction
SRTF yes optimal yes more context switches
RR yes often worse no response time bounded by (n−1) × quantum
Priority either depends yes, fixed by aging RTOS default

Predicting bursts: real schedulers do not know burst lengths, so SJF uses an exponential average of previous bursts: τ(n+1) = α·t(n) + (1−α)·τ(n).

Related: SETF (shortest elapsed time first) picks the job that has run the least so far. It needs no prediction and favours new and short jobs, the idea behind multilevel feedback queues: new jobs start at high priority and sink as they use CPU time.

Quantum choice for RR: too small → overhead dominates; too large → becomes FCFS. A rule of thumb: 80% of CPU bursts should be shorter than the quantum.