Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 66 ยท CPU Scheduling

FCFS and SJF Scheduling

Learn First-Come First-Served and Shortest Job First scheduling with worked Gantt charts, the convoy effect, why SJF is optimal for waiting time, and how to predict burst length.

The simplest way to schedule is to serve processes in the order they arrive: First-Come, First-Served (FCFS, also FIFO). The smartest simple way, at least for average waiting time, is to always run the shortest job first: Shortest Job First (SJF, also Shortest Job Next). Both are non-preemptive in their basic form, so a process that gets the CPU keeps it until it finishes its burst.

In this lesson you will work through both algorithms by hand and in code on the same set of five processes, see why FCFS suffers from the convoy effect, learn why SJF gives the minimum possible average waiting time, and meet its two problems: it needs to know the future, and long jobs can starve.

Two non-preemptive policies

FCFS Earliest arrival runs first.
SJF Smallest burst runs first.

Neither one interrupts a running process.

1 / 2

The example workload

All schedules below use five processes (time in arbitrary units):

Process Arrival Burst
A 0 6
B 1 8
C 2 2
D 3 4
E 4 3

First-Come, First-Served

Rule: keep a FIFO ready queue; the process at the head runs to completion.

By hand: A runs 0-6; B (arrived at 1) runs 6-14; C runs 14-16; D 16-20; E 20-23.

Waiting times (start minus arrival): A = 0, B = 5, C = 12, D = 13, E = 16, average = 46 / 5 = 9.2.

FCFS is easy to implement (a queue) and fair in the sense of arrival order, with no starvation. But look at C: it needs only 2 units but waits 12 because B, a long job, got there first. This is the convoy effect: many short processes queue behind one long process, like cars behind a slow truck, lowering CPU and device utilization. FCFS is also poor for interactive systems because response time depends entirely on what happened to arrive earlier.

Shortest Job First

Rule: whenever the CPU becomes free, choose the ready process with the smallest burst time (break ties by arrival).

By hand: at time 0 only A is ready, so A runs 0-6. At time 6 the ready processes are B(8), C(2), D(4), E(3): pick C (6-8), then E (8-11), then D (11-15), then B (15-23).

Waiting times: A = 0, C = 6-2 = 4, E = 8-4 = 4, D = 11-3 = 8, B = 15-1 = 14; average = 30 / 5 = 6.0, much better than FCFS's 9.2.

Why optimal? If two adjacent jobs are in the wrong order (a long one before a short one), swapping them lowers the short job's wait by more than it raises the long job's. Repeating swaps gives the shortest-first order. SJF is therefore provably optimal for average waiting time among non-preemptive algorithms.

Both policies in code

The simulator picks the next process with a key function, so FCFS and SJF differ by one line.

Python FCFS vs. SJF

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both numbers match the hand calculations (9.2 and 6.0 average waiting time).

The convoy effect, measured

Now make the convoy dramatic: one huge job arrives first, followed by nine tiny jobs. Compare the average waiting time under both policies.

Python Convoy effect

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note that non-preemptive SJF cannot fix this: at time 0 only the long job is present, so it starts, and the short ones still wait. Preemptive SJF (SRTF) addresses that case.

The problems of SJF

  1. Burst time is not known in advance. A job scheduler in a batch system can ask users to state a time limit, but a short-term CPU scheduler cannot. The usual approach is to predict the next CPU burst from the history of previous bursts with an exponential average:

    next_prediction = alpha ร— last_actual_burst + (1 - alpha) ร— previous_prediction

    with 0 โ‰ค alpha โ‰ค 1. With alpha = 0 history is ignored, with alpha = 1 only the last burst matters; alpha = 0.5 is typical.

  2. Starvation. If short jobs keep arriving, a long job may wait forever. Remedies: aging, which raises the priority of waiting jobs over time.

Python Predicting the next burst

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The prediction lags behind but follows the trend: after three bursts of 13 it is climbing toward 13.

FCFS vs. SJF summary

FCFS SJF (non-preemptive)
Selection Earliest arrival Shortest burst
Preemptive No No (preemptive form is SRTF)
Average waiting time Often high Minimum possible
Starvation None Possible for long jobs
Convoy effect Yes Reduced
Implementation Simple queue Needs burst estimates and a priority queue

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In FCFS, which process is chosen next?

    FCFS is a FIFO queue ordered by arrival.
  2. 2. What is the convoy effect?

    One long CPU-bound job holds the CPU while many short or I/O-bound jobs queue behind it.
  3. 3. Why is SJF optimal for average waiting time?

    An exchange argument shows that any order with a long job before a short one can be improved by swapping them.
  4. 4. What is the main practical difficulty of SJF?

    Schedulers have to estimate burst lengths, typically with an exponential average of past bursts.
  5. 5. For the workload A(0,6), B(1,8), C(2,2), D(3,4), E(4,3), which process runs right after A under non-preemptive SJF?

    At time 6 the ready processes are B(8), C(2), D(4), E(3); C has the shortest burst.

Summary

  • FCFS serves in arrival order: simple and starvation-free, but it suffers the convoy effect and has high average waiting time.
  • SJF serves the shortest burst first and gives the minimum average waiting time, but needs burst estimates and can starve long jobs.
  • Burst time is predicted with an exponential average of past bursts.
  • The preemptive version of SJF is covered next.

Next: SRTF and Priority Scheduling