CPU Scheduling Case Study: FCFS vs SJF for a Five-Process Workload

This section analyzes two classic CPU scheduling algorithms—FCFS and SJF—for the following workload, where all processes arrive at time $0$ in the order $A, B, C, D, E$.2

Because all processes arrive simultaneously, waiting time depends entirely on execution order, and average waiting time is a standard metric for comparing scheduling quality. For this problem, the priority column is not used, because the question asks only for FCFS and non-preemptive SJF schedules.2

A useful identity is:

$$\text{Waiting Time} = \text{Start Time} - \text{Arrival Time}$$

Since every arrival time is $0$, each process's waiting time is simply its start time.2

A second equivalent relation often used in operating systems is:

$$\text{Waiting Time} = \text{Turnaround Time} - \text{Burst Time}$$

where turnaround time equals completion time minus arrival time.2

The key theoretical result is that non-preemptive SJF minimizes average waiting time when burst lengths are known in advance for a fixed set of ready processes.2

Footnotes

1. Operating Systems: CPU Scheduling - Course notes explaining FCFS, SJF, Gantt charts, and the optimality of SJF for minimizing average waiting time. ↩ ↩² ↩³

2. Shortest Job First or SJF CPU Scheduling - GeeksforGeeks - Overview of non-preemptive SJF, waiting-time formulas, and worked Gantt-chart examples. ↩ ↩² ↩³ ↩⁴

3. CPU Scheduling in Operating Systems - GeeksforGeeks - Definitions of burst time, turnaround time, waiting time, and a comparison of FCFS and SJF. ↩ ↩² ↩³ ↩⁴

1. FCFS Scheduling

Under FCFS, processes execute strictly in arrival order: $A \rightarrow B \rightarrow C \rightarrow D \rightarrow E$. Since all processes arrive at the same instant, the given arrival order breaks the tie.

The Gantt chart is:

Equivalently, the execution intervals are:

• $A: 0 \to 10$
• $B: 10 \to 11$
• $C: 11 \to 13$
• $D: 13 \to 14$
• $E: 14 \to 19$

For FCFS, the waiting times are the start times:

Thus,

$$\text{Average Waiting Time}_{FCFS} = \frac{0+10+11+13+14}{5} = \frac{48}{5} = 9.6 \text{ ms}$$

This illustrates the classic FCFS weakness: short jobs may wait behind a long job, increasing the mean waiting time.2

Footnotes

1. CPU Scheduling in Operating Systems - GeeksforGeeks - Definitions of burst time, turnaround time, waiting time, and a comparison of FCFS and SJF. ↩ ↩²

2. Operating Systems: CPU Scheduling - Course notes explaining FCFS, SJF, Gantt charts, and the optimality of SJF for minimizing average waiting time. ↩ ↩²

2. SJF Scheduling

In non-preemptive SJF, the ready process with the smallest burst time is selected first.2 With all processes available at time $0$, we sort by burst length:

• $B = 1$
• $D = 1$
• $C = 2$
• $E = 5$
• $A = 10$

When two processes have equal burst times, a common tie-break rule is FCFS among tied processes.2 Since $B$ arrived before $D$, the SJF order is:

$$B \rightarrow D \rightarrow C \rightarrow E \rightarrow A$$

The Gantt chart is:

Execution intervals:

• $B: 0 \to 1$
• $D: 1 \to 2$
• $C: 2 \to 4$
• $E: 4 \to 9$
• $A: 9 \to 19$

Waiting times:

So,

$$\text{Average Waiting Time}_{SJF} = \frac{0+1+2+4+9}{5} = \frac{16}{5} = 3.2 \text{ ms}$$

This is substantially smaller than FCFS, which matches the standard result that SJF is optimal for minimizing average waiting time when burst durations are known.2

Footnotes

1. Operating Systems: CPU Scheduling - Course notes explaining FCFS, SJF, Gantt charts, and the optimality of SJF for minimizing average waiting time. ↩ ↩²

2. Shortest Job First or SJF CPU Scheduling - GeeksforGeeks - Overview of non-preemptive SJF, waiting-time formulas, and worked Gantt-chart examples. ↩ ↩² ↩³

3. CPU Scheduling in Operating Systems - GeeksforGeeks - Definitions of burst time, turnaround time, waiting time, and a comparison of FCFS and SJF. ↩

Final Answer

The required Gantt charts are:

FCFS

SJF

Average waiting times:

$$\text{FCFS} = 9.6 \text{ ms}$$ $$\text{SJF} = 3.2 \text{ ms}$$

Therefore, SJF results in the minimum average waiting time.2

Footnotes

1. Operating Systems: CPU Scheduling - Course notes explaining FCFS, SJF, Gantt charts, and the optimality of SJF for minimizing average waiting time. ↩

2. Shortest Job First or SJF CPU Scheduling - GeeksforGeeks - Overview of non-preemptive SJF, waiting-time formulas, and worked Gantt-chart examples. ↩