Schedulers

A scheduler decides which runnable task gets the CPU next, and for how long, whenever a context switch is triggered. Multitasking provides the mechanism to switch between tasks at all; the scheduler is the policy governing that mechanism, and different policies make genuinely different, often conflicting tradeoffs between throughput, responsiveness, and fairness, since there is no single scheduling algorithm that is unambiguously best for every workload.

Round-robin

The simplest widely-used scheduler, round-robin, gives every runnable task a fixed time slice (or quantum) in a fixed rotation, moving to the next task in the list once the current one’s slice expires or it voluntarily blocks. It requires no notion of task priority at all and treats every runnable task identically, which makes it simple to implement correctly and guarantees that no task can be starved indefinitely, since every task on the ready list eventually gets a turn, but it also makes no distinction between a task that genuinely needs to run frequently and one that doesn’t, applying the same fixed rotation regardless.

struct task *round_robin_next(struct task *current) {
    struct task *next = current->next ? current->next : ready_list_head;
    while (next->state != READY) {
        next = next->next ? next->next : ready_list_head;
    }
    return next;
}

The choice of time slice length itself is a real tradeoff: too long, and the system feels unresponsive, since a task waiting its turn may wait an entire slice for every other runnable task before getting one itself; too short, and the overhead of context switching, itself not free, starts to consume a meaningful fraction of total CPU time that could otherwise have gone to useful work.

Priority-based scheduling

Priority scheduling assigns each task a priority value and always runs the highest-priority runnable task available, only considering a lower-priority task when nothing higher-priority is currently runnable. This lets a scheduler favor latency-sensitive work (an interactive task waiting on user input) over background work (a batch computation with no urgency), but introduces a real risk of starvation: a low-priority task can, in principle, never run at all if higher-priority tasks remain continuously runnable. Practical priority schedulers commonly mitigate this through priority aging, gradually raising a task’s effective priority the longer it goes without running, ensuring every task eventually crosses whatever threshold makes it competitive with tasks that started at a higher priority. Priority alone also creates a subtler failure than outright starvation: a lock held by a low-priority task can stall a high-priority one indirectly through a third, unrelated task, a scenario covered in full in priority inversion.

Multilevel feedback queues

A multilevel feedback queue combines round-robin and priority scheduling: multiple round-robin queues exist simultaneously, each associated with a different priority level and, typically, a different time slice length (higher-priority queues get shorter slices, favoring responsiveness; lower-priority queues get longer slices, favoring throughput for CPU-bound work), and a task moves between queues based on its observed behavior rather than a fixed, externally assigned priority. A task that repeatedly uses its entire time slice without blocking, behavior characteristic of CPU-bound work, is demoted to a lower-priority, longer-slice queue over time; a task that frequently blocks before its slice expires, characteristic of interactive or I/O-bound work, is promoted or kept at a higher-priority, shorter-slice queue, since it is rarely actually consuming much CPU time regardless of its nominal priority. This adaptive structure, rather than any single fixed algorithm, is closer to what production general-purpose kernels actually implement, since it approximates favoring interactive responsiveness without requiring any task to explicitly declare its own behavior in advance.

Real-time considerations

Workloads with hard timing requirements, a task that must run within a bounded, guaranteed time of becoming runnable and not merely “eventually”, need scheduling guarantees none of the algorithms above provide on their own, since all three are fundamentally best-effort with respect to exactly when any given task actually runs. Real-time scheduling algorithms such as rate-monotonic or earliest-deadline-first scheduling exist specifically to provide these guarantees for workloads that need them, at the cost of additional bookkeeping (each task’s period or deadline must be known and honored) that a general-purpose hobby kernel rarely needs to implement unless it specifically targets real-time use cases.

Implementation notes

A scheduler’s correctness depends on the ready list (or lists, under a multilevel scheme) being manipulated consistently with respect to interrupts: a timer interrupt firing in the middle of the scheduler’s own bookkeeping, on a naively-written implementation, can corrupt the very structure the scheduler is trying to update, which is why the scheduling decision itself, and any list manipulation it performs, generally runs with interrupts disabled for its duration. It is also worth distinguishing, early in a design, between the scheduling decision (which task should run next) and the mechanism that carries it out (the context switch itself); conflating the two into a single routine makes it considerably harder to later swap in a different scheduling policy without also rewriting the switching code it happens to be entangled with.

References

^ A. Silberschatz, P. Galvin, and G. Gagne, Operating System Concepts, Chapter 5: the standard textbook treatment of the scheduling algorithms described above.
^ C. L. Liu and J. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” Journal of the ACM, 1973: the original rate-monotonic scheduling paper referenced above.

Schedulers

Round-robin

Priority-based scheduling

Multilevel feedback queues

Real-time considerations

Implementation notes

References

See also