With many processes ready to run and only one CPU, the OS scheduler decides which runs next. A good scheduler keeps the CPU busy, gives fair access and keeps response times short.

Process states

A process is ready (waiting for CPU), running (using CPU) or blocked (waiting for I/O). It moves from ready to running when dispatched, from running to blocked when it requests I/O, from blocked to ready when I/O completes, and from running back to ready when its time slice ends or a higher priority job arrives. The scheduler can be pre-emptive (it may take the CPU away) or non-pre-emptive (a process keeps the CPU until it finishes or blocks).

The algorithms

First Come First Served (FCFS): processes run in the order they arrive, using a queue. It is simple and fair in order, but a long job at the front makes everything behind it wait (the “convoy effect”).

Shortest Job First (SJF): the process with the shortest estimated run time goes next. This gives the lowest average waiting time, but long jobs may be starved and run times must be estimated. A pre-emptive version is called Shortest Remaining Time First.

Round Robin (RR): each process gets a fixed time slice (quantum), then goes to the back of the queue if not finished. It is pre-emptive, fair and gives good response times for interactive systems. If the quantum is too large it behaves like FCFS; too small and time is wasted switching.

Priority scheduling: the highest priority process runs first. Low priority jobs may starve unless their priority rises as they wait (ageing).

Worked example

Three processes arrive at time 0 with burst times P1 = 6, P2 = 2, P3 = 4.

FCFS:  P1 (0-6), P2 (6-8), P3 (8-12)
       waits: 0, 6, 8   average = 4.67

SJF:   P2 (0-2), P3 (2-6), P1 (6-12)
       waits: 0, 2, 6   average = 2.67

RR, quantum 2:  P1 P2 P3 P1 P3 P1
       finish: P2 = 4, P3 = 10, P1 = 12

SJF clearly gives the lowest average wait in this case.

Check your understanding

Which algorithm uses a fixed time slice?

  • FCFS
  • SJF
  • Round Robin
  • None

Answer: Round Robin. Each process gets one quantum per turn.

What is the convoy effect?

  • Short jobs finish first
  • Short jobs wait behind a long job in FCFS
  • The CPU overheats
  • Priorities rise over time

Answer: Short jobs wait behind a long job in FCFS. This hurts average waiting time.

Which algorithm minimises average waiting time?

  • SJF
  • FCFS
  • Round Robin
  • Random

Answer: SJF. It is hard to use because run times must be estimated.

What does ageing prevent?

  • Context switches
  • Starvation of low priority processes
  • Page faults
  • Interrupts

Answer: Starvation of low priority processes. Waiting jobs gradually gain priority.

PreviousNext