10.1 Scheduling Metrics and Classic Algorithms

Now it's your turn to decide who gets to use the CPU next. Multiple processes or threads are in a ready queue, and the scheduler must pick one. There's no perfect strategy, only trade-offs tailored to different scenarios.

Synchronization determines when a thread becomes runnable, and the scheduler decides when a runnable task gets CPU time. This article compares FCFS, SJF, RR, priority, and MLFQ using computable workloads; Linux's sched classes, CFS, and EEVDF will be covered in the next post.

A "fair" order might leave everyone dissatisfied

Compare three tasks that arrive together:

Task	Arrival	CPU service	Explanation
A	0	10	Long batch processing
B	0	1	Short request
C	0	2	Background task

Individual completion and first-response times depend on order. With one CPU, no overhead, and no deliberate idle time, all work still finishes at time 13. The CPU did not get faster; someone got to submit their work sooner.

Real-world tasks don't pre-supply an accurate "total runtime." Here, service time is an input to the teaching model used for strategy comparison, not a directly readable attribute of the OS.

Different Metrics Answer Different Questions

Let task i's arrival, first-run, completion, and CPU service times be a_i, f_i, c_i, and s_i respectively.

response_i   = f_i - a_i
turnaround_i = c_i - a_i
waiting_i = turnaround_i - service_i  # Applies only to the simplified model without I/O

Other useful metrics include:

• throughput: How many tasks are completed per unit of time;
• CPU utilization: The proportion of time the CPU is actively working during the observed period;
• tail latency: p95/p99 response/turnaround, rather than the average alone;
• slowdown: turnaround/service, avoid long tasks from completely dominating the absolute time scale;
• fairness / starvation bound: Whether each task's CPU allocation matches its weight, and the maximum waiting time;
• deadline miss ratio: The percentage of jobs that miss their deadline in real-time workloads.

"Fast response, short turnaround, and fairness" aren't strictly just three metrics, and no single algorithm can independently minimize all of them. Frequent preemption improves short-task response but increases cache disruption and scheduler overhead; maintaining CPU affinity might compromise global load balancing.

FCFS: arrival order determines convoy

First-come, first-served on a non-preemptive CPU lets the current task run to completion or block. If tasks A, B, C enter in the order listed in the table:

timeline: A [0,10) -> B [10,11) -> C [11,13)

response:   A=0,  B=10, C=11
turnaround: A=10, B=11, C=13

Short tasks are blocked by long ones, creating a convoy effect. FCFS is easy to implement and maintains clear arrival order, but it's unsuitable for interactive workloads that require short response times.

Calling it "the most unfair" is inaccurate. It's fair in terms of waiting order, but doesn't distinguish between service length and urgency. Fairness must first be defined.

SJF and SRTF: Theoretical Advantages Depend on Knowledge of the Future

If all tasks arrive at t=0 and service times are known, the non-preemptive shortest-job-first schedule orders them as B, C, A:

timeline: B [0,1) -> C [1,3) -> A [3,13)

response:   B=0, C=1, A=3
turnaround: B=1, C=3, A=13

Under conditions like "all jobs are ready, known lengths, single machine, no preemption," shortest-processing-time-first scheduling minimizes average completion/turnaround time. Removing those conditions would be misleading.

Shortest-remaining-time-first is a preemptive version: when a new task arrives, if its remaining service time is less than that of the current task, it preempts. It still requires accurate knowledge or prediction of remaining service time; continuously arriving short tasks may cause long tasks to starve.

A general OS typically makes indirect judgments based on past CPU bursts, sleep/wake patterns, and priority, rather than knowing exactly how many seconds the process will continue to run. Exponential smoothing can predict the next burst:

prediction_next = α × observed + (1-α) × prediction_previous

α usually lies in [0,1]; a larger value gives the latest burst more weight. Prediction errors and adversarial workloads change scheduling performance.

Round Robin: quantum combines response time with overhead

RR maintains a runnable queue, giving each task at most one quantum at a time; if it doesn't complete, the task is moved to the back of the queue. For A/B/C with quantum = 1:

[0,1) A
[1,2) B completes
[2,3) C
[3,4) A
[4,5) C completes
[5,13) A completes

response:   A=0, B=1, C=2
turnaround: A=13, B=2, C=5

B completes at t=2 and C at t=5, giving an average turnaround of (13+2+5)/3 = 20/3. The final uninterrupted series of A’s quanta is shown as one interval.

When quantum is long, RR approaches FCFS; when it's short, runnable tasks get their turns sooner, but scheduling, cache/TLB, and timer overhead increase. An appropriate value depends on workload, CPU topology, scheduler design, and latency target, and cannot be generalized as "modern OSes all use 1–20 ms" or any fixed range.

If only A is runnable, it typically receives consecutive quanta without needing to switch out for a non-existent competitor.

Verify the Timeline with a Simulator

Save as scheduling.py and run with Python 3.10+. Task names must be unique nonempty strings, arrivals nonnegative integers, and service times and quanta positive integers. An empty workload produces an empty result. The model copies its input and breaks ties by name.

from collections import deque
from dataclasses import dataclass, replace

@dataclass
class Task:
    name: str
    arrival: int
    service: int
    remaining: int = 0
    first_run: int | None = None
    completion: int | None = None

    def fresh(self):
        return replace(self, remaining=self.service,
                       first_run=None, completion=None)

def fresh_workload(tasks):
    copies = []
    names = set()
    for task in tasks:
        if (not isinstance(task.name, str) or not task.name
                or task.name in names):
            raise ValueError("task names must be unique nonempty strings")
        if type(task.arrival) is not int or task.arrival < 0:
            raise ValueError("arrival must be a nonnegative integer")
        if type(task.service) is not int or task.service <= 0:
            raise ValueError("service must be a positive integer")
        names.add(task.name)
        copies.append(task.fresh())
    return copies

def summarize(tasks):
    return {
        task.name: {
            "response": task.first_run - task.arrival,
            "turnaround": task.completion - task.arrival,
        }
        for task in tasks
    }

def run_nonpreemptive(tasks, key):
    pending = fresh_workload(tasks)
    time = min((task.arrival for task in pending), default=0)
    completed = []

    while pending:
        ready = [task for task in pending if task.arrival <= time]
        if not ready:
            time = min(task.arrival for task in pending)
            continue

        task = min(ready, key=key)
        task.first_run = time
        time += task.service
        task.remaining = 0
        task.completion = time
        pending.remove(task)
        completed.append(task)
    return completed

def run_round_robin(tasks, quantum):
    if type(quantum) is not int or quantum <= 0:
        raise ValueError("quantum must be a positive integer")

    pending = sorted(fresh_workload(tasks),
                     key=lambda task: (task.arrival, task.name))
    ready = deque()
    completed = []
    time = pending[0].arrival if pending else 0

    while pending or ready:
        while pending and pending[0].arrival <= time:
            ready.append(pending.pop(0))
        if not ready:
            time = pending[0].arrival
            continue

        task = ready.popleft()
        if task.first_run is None:
            task.first_run = time

        duration = min(quantum, task.remaining)
        task.remaining -= duration
        time += duration

        while pending and pending[0].arrival <= time:
            ready.append(pending.pop(0))
        if task.remaining == 0:
            task.completion = time
            completed.append(task)
        else:
            ready.append(task)
    return completed

workload = [
    Task("A", arrival=0, service=10),
    Task("B", arrival=0, service=1),
    Task("C", arrival=0, service=2),
]

fcfs = run_nonpreemptive(workload,
                         key=lambda task: (task.arrival, task.name))
sjf = run_nonpreemptive(workload,
                        key=lambda task: (task.service,
                                         task.arrival, task.name))
rr = run_round_robin(workload, quantum=1)

assert summarize(fcfs) == {
    "A": {"response": 0, "turnaround": 10},
    "B": {"response": 10, "turnaround": 11},
    "C": {"response": 11, "turnaround": 13},
}
assert summarize(sjf) == {
    "B": {"response": 0, "turnaround": 1},
    "C": {"response": 1, "turnaround": 3},
    "A": {"response": 3, "turnaround": 13},
}
assert summarize(rr) == {
    "B": {"response": 1, "turnaround": 2},
    "C": {"response": 2, "turnaround": 5},
    "A": {"response": 0, "turnaround": 13},
}

The simulator omits context-switch costs, I/O bursts, and multicore execution. At a quantum boundary, newly arrived tasks enter the queue before the unfinished current task rejoins it. Changing that rule changes the trace. List scans and pop(0) keep the event order visible here; they are not an efficient scheduler implementation.

Priority scheduling must address starvation

Priority can express business importance, deadline class, or resource weight. A static priority scheduler, if it always selects the highest priority, may cause lower-priority tasks to remain runnable forever without ever getting CPU time.

Aging increases effective priority with longer wait times; weighted fair scheduling ensures long-term fair share; admission control rejects workloads that cannot be met in real-time systems. The choice depends on how "important" is defined.

A higher "nice" value isn't universally equivalent to "higher urgency" as a priority. In Unix, a larger nice value typically means a lower weight for regular tasks; real-time policies use a separate priority semantics. Applications should not directly map business priorities to kernel RT priorities, or a single bug could starve system services.

Priority Inversion from Lock Dependency

Assume low-priority L holds a mutex, high-priority H is waiting for it; medium-priority M doesn't need the mutex but continuously preempts L. H is thus indirectly blocked by M.

L owns lock
H blocks on lock
M preempts L
=> H waits for M, although H outranks M

Priority inheritance allows L to temporarily inherit a higher priority when holding the mutex required by H, enabling it to run quickly and release it. Priority ceiling is another protocol. Both require coordination between mutex implementation, scheduler policy, and lock graph, rather than calling nice once on a thread to fix the issue alone.

Real-time design must also limit the length of critical sections to avoid page faults, allocations, or unbounded I/O while holding locks. Priority inheritance cannot eliminate all blocking.

MLFQ Estimates Workload Type from Behavior

A multi-level feedback queue maintains multiple runnable queues. A common teaching rule is:

• A new task starts with high priority and a short quantum;
• CPU-heavy tasks move to lower-priority queues after using their allotment;
• Frequently blocked interactive tasks maintain a high response level;
• Regular priority boosts to prevent starvation at the base level.

Looking only at "whether to sleep before a single quantum is exhausted" makes task scheduling vulnerable to being tricked by frequent short sleeps, and also over-rewards I/O-intensive background jobs. A more complete model degrades based on accumulated allotment over a period of time, combined with aging and boosting mechanisms.

MLFQ is a family of scheduling policies, not "all general-purpose operating systems are based on the same MLFQ." Different systems use combinations like priority queues, fair schedulers, deadlines, and work stealing.

Multicore scheduling adds one more dimension: which CPU to place it on

The uniprocessor algorithm picks only "who comes first". The SMP scheduler also has to decide:

• Whether to keep a task on a CPU with a warm cache or migrate it to an idle CPU;
• Whether wakeup should favor the CPU used previously;
• Which execution resources SMT siblings share;
• How far the task’s NUMA memory is from the target CPU;
• Which heterogeneous core matches the task’s capacity and energy needs;
• How per-CPU run queue load balancing works.

Global queues are fair and easy to implement but suffer from high contention; per-CPU queues scale better but require balancing. Work-stealing runtimes let idle workers pull tasks from elsewhere, but they face trade-offs between locality and stealing granularity.

Task scheduling with a thread pool and kernel CPU scheduling are two separate layers: the pool decides which job goes to which worker, and the kernel decides when and on which CPU the worker thread runs.

Hard Real-Time Systems Need Deadline Bounds

A general-purpose scheduler focuses on throughput, interactivity, and long-term fairness; hard real-time systems require proving deadline bounds under known workloads and resources.

Algorithms like EDF, rate-monotonic, and fixed-priority preemptive scheduling all have admission and utilization conditions. A good average response time does not compensate for a missed hard deadline.

Soft real-time audio/video tolerates only minimal drops, commonly using RT policies, memory locking, preallocation, and bounded code paths. Blindly increasing priority can cause the machine to fail responding to management tasks and must be paired with resource limits, watchdogs, and testing.

Do the math instead of memorizing rankings

1. Add different arrival times to the simulator to clearly define the queue order for simultaneous events.
2. Implement SRTF and construct a workload that causes long task starvation.
3. Add a cost of 1 time unit per actual task switch in RR. Shorten the integer quantum and compare useful execution with switching overhead; consecutive quanta for the same task do not count as a task switch.
4. Output the average and p95 response; identify a scheduling strategy that has better average performance but worse tail behavior.
5. Implement an MLFQ with periodic boost and test the longest waiting time for CPU-intensive tasks.
6. Extend the simulator to two CPUs and compare the migration numbers between global queue and per-CPU queue.

Next Level: Linux Builds Fairness and Latency into Its Scheduling Class

Classic algorithms provide vocabulary and boundaries but can't directly describe current Linux. The next article will rely on official documentation to distinguish between historic CFS, the currently used EEVDF approach, real-time and deadline classes, and then explain nice, lag, and virtual deadline.