Scheduling: Introduction

Simplifying Assumptions About the Workload

Before analyzing any policy we adopt a set of idealized assumptions about jobs (sometimes called tasks): every job has identical run length, all jobs arrive together, once started a job runs to completion, jobs use only the CPU and perform no I/O, and the scheduler already knows each job’s exact duration. The assumptions are unrealistic, yet they let us see the essential behavior of each policy before we relax them one by one.

The Scheduling Metric of Turnaround Time

Comparing policies requires a concrete metric. For now we use turnaround time: the moment a job finishes minus the moment it arrived. Under the current assumption that every job arrives at time zero, turnaround time simply equals completion time. Turnaround time captures performance; fairness is a separate concern and the two often trade off against each other.

FIFO and the Convoy Problem

The most basic policy is first-in first-out (also called first-come first-served): jobs run to completion in the order they arrived. It works reasonably when every job has the same length. As soon as a long job sits at the head of the queue, many short jobs are forced to wait, average turnaround time explodes, and the situation is known as the convoy effect.

Shortest Job First

Shortest-job-first always selects the job that currently has the smallest remaining run time. When every job arrives together it yields the lowest possible average turnaround time and is optimal under the stated assumptions. Once jobs may arrive at arbitrary instants, pure shortest-job-first encounters new difficulties that later chapters address by relaxing further assumptions.

Pitfalls

• Believing FIFO remains efficient when job lengths differ
• Overlooking the convoy effect created by a long job blocking short ones
• Assuming a real scheduler always knows each job’s exact run time in advance

Minimum C11 · complete program · Download .c

#include <stdio.h>

int main(void) {
    /* FIFO: A=100, B=10, C=10, order A then B then C */
    int fifo_a = 100;
    int fifo_b = 100 + 10;
    int fifo_c = 110 + 10;
    double fifo_avg = (fifo_a + fifo_b + fifo_c) / 3.0;
    printf("FIFO average turnaround: %.2f\n", fifo_avg);

    /* SJF: shortest first, B then C then A */
    int sjf_b = 10;
    int sjf_c = 10 + 10;
    int sjf_a = 20 + 100;
    double sjf_avg = (sjf_a + sjf_b + sjf_c) / 3.0;
    printf("SJF average turnaround: %.2f\n", sjf_avg);

    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-07-cpu-scheduling.c -o example && ./example

Expected result

FIFO average turnaround: 110.00
SJF average turnaround: 50.00

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

Three jobs A, B and C arrive at the same instant with run times 100 s, 10 s and 10 s. FIFO executes them in order A-B-C; SJF always runs the currently shortest job. Compute the average turnaround time of each policy.

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.