CPU scheduling: FCFS and SJF

Processes alternate between CPU bursts (computing) and I/O bursts (waiting for a disk, the network, the user). Whenever the CPU becomes free, the CPU scheduler picks a process from the ready queue, and the dispatcher switches to it.

A scheduler is non-preemptive if a running process keeps the CPU until it finishes its burst or waits, and preemptive if the OS can take the CPU away (with the timer interrupt). This lesson covers two non-preemptive algorithms; the next one covers preemptive ones.

How to judge a scheduler

For each process, with its arrival time (AT) and burst time (BT, the CPU time it needs):

A good scheduler keeps the CPU busy (utilization), finishes many processes per second (throughput), and keeps turnaround, waiting and response times low. These goals pull against each other.

First come, first served (FCFS)

Run the processes in the order they arrive, each to the end of its burst. Simple and fair, but one long process makes everyone behind it wait: the convoy effect.

Step through time, then open Compare the algorithms. SJF cannot help here: P1 is alone when the CPU first becomes free, and a non-preemptive scheduler never stops it. SRTF, from the next lesson, may stop P1 for the short jobs, and cuts the average waiting time from 16 to under 3.

#include <stdio.h>

#define N 4

int main(void) {
    /* Sorted by arrival time */
    int arrival[N] = {0, 1, 2, 3};
    int burst[N]   = {5, 3, 8, 2};
    int finish[N], tat[N], wait[N];
    int time = 0, total_wait = 0, total_tat = 0;

    for (int i = 0; i < N; i++) {
        if (time < arrival[i]) time = arrival[i];   /* the CPU idles until it arrives */
        time += burst[i];                           /* it runs to the end */
        finish[i] = time;
        tat[i] = finish[i] - arrival[i];
        wait[i] = tat[i] - burst[i];
        total_tat += tat[i];
        total_wait += wait[i];
    }

    printf("P   AT  BT  CT  TAT  WT\n");
    for (int i = 0; i < N; i++)
        printf("P%d  %2d  %2d  %2d  %3d  %2d\n", i + 1, arrival[i], burst[i], finish[i], tat[i], wait[i]);
    printf("average waiting %.2f, average turnaround %.2f\n", (double)total_wait / N, (double)total_tat / N);
    return 0;
}

This is the classic lab program: with the processes sorted by arrival, each one starts when both it has arrived and the one before it has finished. Its numbers match the simulator's.

Shortest job first (SJF)

When the CPU is free, pick the arrived process with the shortest burst (ties: the one that arrived first). SJF gives the smallest possible average waiting time of all non-preemptive schedulers. It has two problems:

• The future is unknown: the OS does not know how long the next burst will be. Real systems predict it from past bursts, with an exponential average: τ_next = α·t_last + (1 − α)·τ_last, often with α = ½.
• Starvation: a long process may wait forever if short ones keep arriving.

#include <stdio.h>

#define N 4

int main(void) {
    int arrival[N] = {0, 1, 2, 3};
    int burst[N]   = {5, 3, 8, 2};
    int done[N] = {0};
    int time = 0, total_wait = 0;

    int finished = 0;
    while (finished < N) {
        int pick = -1;
        for (int i = 0; i < N; i++)        /* the shortest job that has arrived */
            if (!done[i] && arrival[i] <= time && (pick < 0 || burst[i] < burst[pick]))
                pick = i;
        if (pick < 0) {                    /* nothing has arrived yet: the CPU idles */
            time++;
            continue;
        }
        total_wait += time - arrival[pick];
        time += burst[pick];
        done[pick] = 1;
        finished++;
        printf("P%d runs until %d\n", pick + 1, time);
    }
    printf("average waiting %.2f\n", (double)total_wait / N);
    return 0;
}

Try both programs with the simulator: type the same processes and switch between FCFS and SJF.

Mark lesson complete