Scheduling algorithms

First come first served, round robin, shortest job first, shortest remaining time and multi-level feedback queues, compared on one set of processes.

A10.5Operating systems, software and translatorsA level45 min

At GCSE (F9.9) you wrote a round-robin scheduler: each job gets a time slice, then goes to the back of the queue. At A level you need five scheduling algorithms, what each is good and bad at, and the ability to work out which process runs when. The part of the operating system that chooses is the scheduler.

What a scheduler is trying to do

A single processor core runs one process at a time. The scheduler decides which of the ready processes runs next, and for how long. It is trying to balance aims that pull against each other:

• throughput: finish as many processes as possible per hour;
• response time: interactive programs should react quickly to the user;
• fairness: every process gets a reasonable share of the processor;
• no starvation: no process waits forever because others keep jumping ahead;
• low overhead: switching processes takes time, so do not switch more than needed.

A process is not always ready. It can be running (on the processor), ready (waiting for a turn), or blocked (waiting for something else, such as input or a disk). A blocked process is not scheduled until its event happens, usually signalled by an interrupt.

Algorithms are either pre-emptive, where the scheduler can take the processor away from a running process (using the timer interrupt from A10.4), or non-pre-emptive, where a process keeps the processor until it finishes or blocks.

One set of processes, five algorithms

Every example below uses these four processes. The burst time is how much processor time each needs, in units.

A process's waiting time is the time it spends ready but not running: finish time minus arrival time minus burst time.

First come first served (FCFS)

Non-pre-emptive. Processes run in the order they arrive, each to completion: A 0 to 8, B 8 to 12, C 12 to 21, D 21 to 26. Waiting times are A 0, B 7, C 10 and D 18, an average of 8.75.

FCFS is simple and every process eventually runs. But one long process holds up all the short ones behind it, so short interactive jobs can wait a long time.

processes = [("A", 0, 8), ("B", 1, 4), ("C", 2, 9), ("D", 3, 5)]

def fcfs(processes):
    time = 0
    total_wait = 0
    for name, arrival, burst in sorted(processes, key=lambda p: p[1]):
        time = max(time, arrival)                 # the processor may sit idle until it arrives
        print(f"{name} runs {time} to {time + burst}, waited {time - arrival}")
        total_wait = total_wait + time - arrival
        time = time + burst
    return total_wait / len(processes)

print(f"FCFS average wait: {fcfs(processes):.2f}")

Run this in the simulator

Round robin (RR)

Pre-emptive. Each process runs for at most one time slice (quantum), then goes to the back of the queue. With a slice of 3, and new arrivals joining the queue before the process whose slice just ended: A 0 to 3, B 3 to 6, C 6 to 9, D 9 to 12, A 12 to 15, B 15 to 16, C 16 to 19, D 19 to 21, A 21 to 23, C 23 to 26. The average wait is 13.5, the worst of the five here.

Round robin is fair and gives good response times, because nobody waits more than one lap of the queue for a turn. It does not favour short jobs, and switching has an overhead. Too short a slice and the processor spends its time switching; too long and it turns into FCFS.

Shortest job first (SJF)

Non-pre-emptive. When the processor becomes free, the waiting process with the shortest burst time runs to completion. At time 0 only A has arrived, so A runs 0 to 8. At 8, B (4), C (9) and D (5) are waiting: B runs 8 to 12, then D 12 to 17, then C 17 to 26. Average wait: 7.75.

SJF gives a low average wait and high throughput. But the scheduler must know or estimate how long each process will take, and a long process can starve if short ones keep arriving.

Shortest remaining time (SRT)

The pre-emptive version of SJF. Whenever a process arrives, the scheduler compares the time left for every ready process and runs the least. At time 1, B needs 4 but A still needs 7, so B takes over. The order is A 0 to 1, B 1 to 5, D 5 to 10, A 10 to 17, C 17 to 26. Waiting times are A 9, B 0, C 15 and D 2, an average of 6.50, the lowest here.

SRT is excellent for throughput, but it has the same problems as SJF (estimating run times, starving long processes) plus the overhead of pre-emption.

Multi-level feedback queues (MLFQ)

MLFQ uses several ready queues, each with its own priority, and moves processes between them based on how they behave:

• a new process joins the highest-priority queue, which has a short time slice;
• a process that uses its whole slice is probably long and processor-heavy, so it moves down a queue;
• a process that gives up the processor before its slice ends (to wait for input, for example) is probably interactive, so it stays high or moves up;
• the scheduler always runs a process from the highest non-empty queue;
• to stop starvation, a process that has waited a long time in a low queue is moved up (ageing).

MLFQ does not need to know burst times in advance: it learns them by watching. It gives interactive processes quick responses while long jobs still finish. The cost is complexity, and it needs tuning: how many queues, and what slice for each.

Comparing them

Task: waiting times

Write sjf(processes) and srt(processes). processes is a list of tuples (name, arrival, burst): name is a string, and arrival and burst are whole numbers of time units (arrival 0 or more, burst 1 or more). Each function returns the average waiting time as a float, where a process's waiting time is its finish time minus its arrival time minus its burst time.

• sjf: non-pre-emptive. Whenever the processor is free, run the arrived process with the smallest burst time to completion. If nothing has arrived, move the clock on to the next arrival.
• srt: pre-emptive. Move the clock one unit at a time; each unit, run the arrived, unfinished process with the least time left.
• In both, break a tie by choosing the process that arrived first.

Keep the fcfs line and print all three, to 2 decimal places, one per line: FCFS average wait: <x>, SJF average wait: <x> and SRT average wait: <x>. The robot stays still.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

processes = [("A", 0, 8), ("B", 1, 4), ("C", 2, 9), ("D", 3, 5)]

def fcfs(processes):
    time = 0
    total_wait = 0
    for name, arrival, burst in sorted(processes, key=lambda p: p[1]):
        time = max(time, arrival)
        total_wait = total_wait + time - arrival
        time = time + burst
    return total_wait / len(processes)

print(f"FCFS average wait: {fcfs(processes):.2f}")

Challenges

1. Write round_robin(processes, quantum) and check it gives 13.50 for a slice of 3. Which slice gives the lowest average wait for these processes?
2. Add a fifth process E that arrives at 4 with a burst of 1. Which algorithm helps it most?
3. Show SJF starving a process: invent a stream of short processes, arriving one after another, that keeps C waiting for as long as they keep coming.