FCFS, SJF and Waiting Time

Use three CPU-only jobs: A arrives at time 0 and needs 4 time units, B arrives at 1 and needs 3, and C arrives at 2 and needs 1. Assume one processor, zero switching overhead and no I/O blocking. First-come, first-served (FCFS) runs ready jobs in arrival order without preempting the current job in this model.

Shortest job first (SJF) selects the shortest ready CPU burst when the processor becomes available. Here it is also non-preemptive: a shorter arrival does not displace a running job. State a tie rule, such as earlier arrival then label, when equal estimates occur. SJF depends on available burst information or estimates; it does not magically know every program’s future execution time.

FCFS runs A from 0 to 4, B from 4 to 7 and C from 7 to 8. SJF also starts A at 0 because no other job is ready. At time 4, both B and C are waiting, so SJF runs C from 4 to 5 and B from 5 to 8. The same total CPU work completes at time 8, but individual waiting differs.

Turnaround is completion time minus arrival time. In this CPU-only, no-overhead model, waiting is turnaround minus CPU burst. For FCFS, A waits 0, B waits 3 and C waits 5, giving mean 8/3. For SJF, A waits 0, B waits 4 and C waits 2, giving mean 2. A lower mean does not mean every job benefits: B waits longer under SJF here.

FCFS is simple and preserves arrival order, but short tasks can wait behind a long CPU-bound task: a convoy effect. SJF can reduce average waiting for a suitable batch workload, but long jobs can be postponed when short jobs continue arriving. An ageing or fairness policy may address that risk, but it must be part of the stated rules rather than silently added during a trace.

Do not substitute shortest remaining time for non-preemptive SJF. That is a different policy, comparing unfinished remaining bursts and potentially preempting a running job. For Pearson’s named IAS content, understand RR, FCFS, SJF and multilevel queue. Trace the exact variant supplied and attach each performance claim to the workload, estimates, overhead and fairness objective.

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.