How a scheduler decides who runs next

Your laptop has a handful of cores but runs hundreds of processes. Each core still does exactly one thing at a time, so something must decide, thousands of times a second, who runs next and for how long. That something is the scheduler, and its policy is the difference between a snappy machine and one that stutters. Let us build two policies and measure them.

The one idea

The scheduler's job is to share one CPU among many ready processes. The metric users feel is waiting time: how long a process sits ready but not running. Different policies optimize different things, and there is no free lunch, favoring one workload penalizes another. We will compare the two foundational policies on the same set of jobs and watch the average waiting time move.

Policy 1: first come, first served

The simplest rule: run each process to completion in arrival order. A job's waiting time is just the sum of the burst times ahead of it.

#include <stdio.h>

int main(void) {
    int burst[] = {24, 3, 3};       // three jobs, CPU time each
    int n = 3;

    // FCFS: wait[i] = sum of bursts before i
    int wait = 0, total = 0;
    for (int i = 0; i < n; i++) {
        printf("FCFS job %d waits %d\n", i, wait);
        total += wait;
        wait += burst[i];
    }
    printf("FCFS average wait: %.1f\n\n", (double)total / n);
    return 0;
}

FCFS job 0 waits 0
FCFS job 1 waits 24
FCFS job 2 waits 27
FCFS average wait: 17.0

Notice the damage: two tiny 3-unit jobs got stuck behind a 24-unit hog and waited 24 and 27. This is the convoy effect, short jobs starving behind a long one. FCFS is fair in order but cruel to latency.

Policy 2: round-robin

Round-robin gives each process a fixed time slice (a quantum), then preempts it and moves to the next, cycling until all finish. Short jobs get to run soon instead of waiting out the hog.

#include <stdio.h>

int main(void) {
    int burst[]  = {24, 3, 3};
    int remain[] = {24, 3, 3};
    int n = 3, quantum = 4, time = 0, done = 0;
    int finish[3] = {0};

    while (done < n) {
        int progressed = 0;
        for (int i = 0; i < n; i++) {
            if (remain[i] <= 0) continue;
            progressed = 1;
            int slice = remain[i] < quantum ? remain[i] : quantum;
            remain[i] -= slice;
            time += slice;
            if (remain[i] == 0) { finish[i] = time; done++; }
        }
        if (!progressed) break;
    }

    int total = 0;
    for (int i = 0; i < n; i++) {
        int wait = finish[i] - burst[i];   // turnaround minus CPU time
        printf("RR job %d waits %d\n", i, wait);
        total += wait;
    }
    printf("RR average wait: %.1f\n", (double)total / n);
    return 0;
}

RR job 0 waits 6
RR job 1 waits 4
RR job 2 waits 7
RR average wait: 5.7

Average waiting time dropped from 17.0 to 5.7. The two short jobs finished quickly instead of languishing. The long job paid a little (it now gets interrupted), but the system as a whole feels far more responsive, which is exactly what you want on an interactive machine.

The trade-off is the point

Round-robin is not universally better; it just optimizes a different thing. Too small a quantum and the CPU spends its time on context switches (saving and restoring registers) instead of real work. Too large and round-robin degrades back into FCFS. And neither policy knows that some jobs are interactive and some are batch. Real kernels layer these ideas into a multi-level feedback queue: several round-robin queues at different priorities, promoting and demoting processes based on how they behave, so an interactive process that mostly waits gets to run the instant it is ready.

Once you have measured 17.0 become 5.7 by changing one rule, "the scheduler" stops being a vague kernel component and becomes a design decision with visible consequences. Building these internals, and feeling the trade-offs, is the whole approach of the operating systems track.