Round robin, SRTF and priority

A preemptive scheduler can take the CPU away from a running process: when the timer interrupt fires, or when a more important process arrives. That keeps interactive programs responsive.

Shortest remaining time first (SRTF)

The preemptive version of SJF. When a new process arrives, compare its burst with the remaining time of the running process; if the newcomer is shorter, it takes the CPU. SRTF gives the lowest average waiting time of all, at the cost of more context switches.

Priority scheduling

Each process has a priority, and the highest one runs. In these lessons, as in most textbooks, a smaller number means a higher priority (some systems use the opposite, so always check). It can be non-preemptive or preemptive.

Its danger is starvation: a low-priority process may never run. The cure is aging: raise a process's priority the longer it waits, so in the end everyone runs.

Round robin (RR)

Every process gets the CPU for at most one time quantum q (say 2 units), then goes to the back of the ready queue. A process that finishes or waits for I/O before its quantum ends gives the CPU up early.

The rule this simulator and the example follow (most textbooks do too): a process that arrives at the very moment a quantum ends joins the queue before the process that was just stopped.

The quantum is a trade-off:

• Too big, and RR becomes FCFS.
• Too small, and the CPU spends its time on context switches instead of work.
• A common rule: about 80% of CPU bursts should be shorter than the quantum. Real systems use 10 to 100 milliseconds, while a context switch takes a few microseconds.

RR usually has a worse average turnaround than SJF, but a much better response time: no process waits long for its first turn.

#include <stdio.h>

#define N 4
#define QUANTUM 2

int main(void) {
    int arrival[N] = {0, 1, 2, 3};     /* sorted by arrival */
    int burst[N]   = {5, 3, 1, 2};
    int left[N], finish[N];
    int queue[64], head = 0, tail = 0;
    int time = 0, next = 0, done = 0;

    for (int i = 0; i < N; i++) left[i] = burst[i];
    queue[tail++] = next++;            /* P1 arrives at 0 */

    while (done < N) {
        int p = queue[head++];
        int run = left[p] < QUANTUM ? left[p] : QUANTUM;
        time += run;
        left[p] -= run;
        while (next < N && arrival[next] <= time)   /* arrivals join first */
            queue[tail++] = next++;
        if (left[p] > 0) {
            queue[tail++] = p;                       /* then the stopped one */
        } else {
            finish[p] = time;
            done++;
            printf("P%d finishes at %d\n", p + 1, time);
        }
    }
    for (int i = 0; i < N; i++)
        printf("P%d: turnaround %d, waiting %d\n", i + 1, finish[i] - arrival[i], finish[i] - arrival[i] - burst[i]);
    return 0;
}

The example keeps the ready queue in an array used as a circular queue. Step through it next to the simulator: the order and completion times match.

Multilevel queues

Real schedulers combine algorithms. A multilevel queue keeps separate queues (system, interactive, batch), each with its own algorithm, served by priority. A multilevel feedback queue also moves processes between queues: a process that uses its whole quantum drops to a lower queue (it looks like a long batch job), and one that waits too long moves up (aging). Linux's scheduler (CFS, and EEVDF since 2023) instead gives each process a fair share of CPU time, tracked as the time it has used.

Mark lesson complete