Why Simple FIFO Scheduling Fails and How CFS Achieves Fair CPU Allocation

Background: The Scheduling Problem

In a single‑CPU system with many programs, the kernel must decide which task runs next. A naïve approach leads to long waits for important tasks, slow user interaction, and some programs never receiving CPU time.

First Attempt – FIFO Queue

The initial scheduler simply dequeues the oldest task (first‑come‑first‑served):

void schedule() {
    if (head != tail) {
        struct task *t = &queue[head++];
        t->run(); // execute task
    }
}

This works but causes severe latency; a long‑running scientific computation blocks all other tasks, making the system unresponsive.

Introducing Priorities

Assign each task a numeric priority (lower number = higher importance) and always run the highest‑priority task:

void schedule() {
    struct task *highest = NULL;
    // find task with smallest priority value
    for (int i = 0; i < num_tasks; i++) {
        if (highest == NULL || tasks[i].priority < highest->priority) {
            highest = &tasks[i];
        }
    }
    if (highest) {
        highest->run();
    }
}

While this solves the FIFO problem, low‑priority tasks can suffer starvation, never getting CPU time.

1990 – Fixed Time‑Slice Quotas

Give each task a fixed CPU quota (time slice). When the quota expires, the task is moved to a waiting queue and its quota is recomputed based on priority:

void schedule() {
    struct task *current = get_highest_priority_task();
    if (current->quota > 0) {
        current->run();
        current->quota -= 1; // consume 1 ms
    } else {
        // quota exhausted, recalculate and re‑queue
        current->quota = compute_new_quota(current->priority);
        move_to_wait_queue(current);
    }
}

This eliminates starvation but introduces another issue: interactive programs (e.g., a terminal) still feel sluggish because the scheduler cannot distinguish them from CPU‑heavy jobs.

Heuristic Detection of Interactive Tasks

A heuristic tries to raise the priority of tasks that spend more time sleeping than running:

void detect_interactive_task(struct task *t) {
    // if the task sleeps more than it runs, treat it as interactive
    if (t->sleep_time > t->run_time) {
        t->is_interactive = 1;
        t->priority -= 5; // boost priority
    }
}

This works sometimes but misclassifies I/O‑heavy background jobs (e.g., a database) as interactive, causing them to starve true interactive tasks.

Rethinking Fairness: Track Runtime

Instead of fixed quotas or heuristics, record how long each task has actually run and always schedule the task with the smallest accumulated runtime:

struct task {
    int pid;
    uint64 runtime; // total CPU time used
};

void schedule() {
    // find task with minimal runtime
    struct task *next = find_task_with_min_runtime();
    uint64 start = now();
    next->run();
    uint64 delta = now() - start;
    next->runtime += delta; // update accumulated runtime
}

This simple rule yields near‑equal CPU distribution among tasks. When a long‑running compile job dominates, a terminal that has slept most of the time retains a tiny runtime value, so it instantly preempts the compiler on user input.

Virtual Runtime and Weighting (CFS)

To re‑introduce priority without starvation, each task gets a weight (derived from its nice value). The scheduler records a *virtual runtime* that scales actual runtime by the weight:

struct task {
    int pid;
    int nice;          // -20 (high) to +19 (low)
    u64 vruntime;      // scaled runtime
    int weight;       // conversion factor based on nice
};

void schedule() {
    struct task *next = find_task_with_min_vruntime();
    u64 start = now();
    next->run();
    u64 delta = now() - start; // actual runtime
    // scale by weight (higher weight = lower priority)
    next->vruntime += delta * 1024 / next->weight;
}

This is the core of Linux’s Completely Fair Scheduler (CFS). Tasks with higher priority accrue virtual runtime more slowly, so they are chosen more often, while low‑priority tasks accumulate faster and yield the CPU.

Conclusion

The progression from FIFO to priority, to time‑slice, to runtime‑tracking and finally to weighted virtual runtime demonstrates how operating‑system designers balance fairness, responsiveness, and priority. The CFS algorithm embodies these lessons, providing a simple yet powerful mechanism for equitable CPU distribution.