CPU Scheduling

Why scheduling is needed

Open Task Manager's Performance tab on an ordinary laptop and you will see a few thousand threads on 8 or 12 cores. Most of those threads are waiting — for a key press, a network packet, a timer — but at any moment there can still be more threads ready to run than there are cores. Something has to choose.

The scheduler is the part of the kernel that decides which ready thread runs on which CPU core next, and for how long. It runs every time a thread starts waiting, a waiting thread becomes ready, a thread ends, or a time slice runs out. Its choices determine whether the mouse pointer moves smoothly while a video renders, and whether a backup finishes overnight.

Cooperative and preemptive multitasking

There are two ways for the operating system to get the CPU back from a running program.

In cooperative multitasking, a program runs until it gives up the CPU voluntarily, by waiting for input or calling a "yield" function. That works as long as every program behaves. One program stuck in a loop never yields, and the entire computer freezes. Windows 3.x and the classic Mac OS (up to Mac OS 9) worked this way, which is why one hung program could lock up the whole machine.

In preemptive multitasking, the operating system can interrupt a running program at any moment and give the CPU to another, without the program's cooperation. The tool that makes it possible is the timer interrupt: a hardware timer interrupts the CPU at regular intervals, the kernel takes control, and the scheduler decides whether the current thread may continue. A program in an endless loop then only wastes its own share of CPU time. Every current desktop, server and mobile operating system — Windows (since the NT line and Windows 95), macOS, Linux, Android and iOS — is preemptive.

Time slices

A time slice (also called a quantum) is the maximum time a thread may run on a core before the scheduler reconsiders and may give the core to another ready thread. If the thread blocks earlier — to wait for the disk, say — it gives up the rest of its slice. Time slices on desktop systems are typically a few milliseconds to a few tens of milliseconds, so a thread that has to wait for one full round among a handful of others still gets the CPU many times per second.

Choosing the length is a trade-off:

• Short slices make the system feel responsive, because every ready thread gets a turn quickly, but spend more time on context switches instead of real work.
• Long slices waste less on switching and suit long computations, but a thread that needs to react (the one moving your mouse pointer) may wait longer for its turn.

Windows makes this trade-off visible: in System Properties › Advanced › Performance Settings › Advanced, "Adjust for best performance of Programs" (the default on Windows 10 and 11) uses short slices and favors the foreground app, while "Background services" (the default on Windows Server) uses longer, equal slices.

Scheduling goals

A scheduler cannot optimize everything at once. The usual goals are:

• High CPU utilization and throughput: keep the cores busy and finish as many jobs per hour as possible — important on servers and batch systems.
• Short waiting and turnaround time: the time a job spends ready but not running, and the time from arrival to completion.
• Short response time: the time until a job first gets the CPU. This is what users feel as "responsive".
• Fairness: comparable threads get comparable shares, and no thread waits forever.

These goals pull against each other. The simulations below use the same workload for four classic algorithms, so you can see the trade-offs in numbers: four processes arriving at different times, each needing some milliseconds of CPU (its burst), on one core.

Waiting time is the time a process spends ready but not running: completion time minus arrival time minus burst.

Scheduling algorithms

First-come, first-served

First-come, first-served (FCFS) runs processes in order of arrival, each to completion. It is simple and fair in the sense of a queue at a counter, but short jobs get stuck behind long ones (the convoy effect): here P3 needs 1 ms of CPU and waits 7.

# name, arrival time, burst time (in milliseconds)
workload = [("P1", 0, 7), ("P2", 2, 4), ("P3", 4, 1), ("P4", 5, 4)]

clock = 0
waits = {}
for name, arrival, burst in sorted(workload, key=lambda p: p[1]):
    start = max(clock, arrival)
    print(f"{start:2}-{start + burst:2}  {name}")
    waits[name] = start - arrival
    clock = start + burst

print("Waiting:", waits)
print("Average waiting time:", sum(waits.values()) / len(waits))

 0- 7  P1
 7-11  P2
11-12  P3
12-16  P4
Waiting: {'P1': 0, 'P2': 5, 'P3': 7, 'P4': 7}
Average waiting time: 4.75

Shortest job first

Shortest job first (SJF) picks, whenever the CPU becomes free, the ready process with the shortest burst. Short jobs no longer wait behind long ones, and the average waiting time drops. (When all jobs are available at the same moment, SJF gives the lowest possible average waiting time.) The catch: the OS does not know in advance how long a burst will be. Real schedulers can only estimate it from a thread's recent behavior — and a steady stream of short jobs can keep a long one waiting indefinitely.

# name, arrival time, burst time (in milliseconds)
workload = [("P1", 0, 7), ("P2", 2, 4), ("P3", 4, 1), ("P4", 5, 4)]

clock = 0
waiting = list(workload)
waits = {}
while waiting:
    ready = [p for p in waiting if p[1] <= clock]
    if not ready:                        # CPU idle until the next arrival
        clock = min(p[1] for p in waiting)
        continue
    job = min(ready, key=lambda p: (p[2], p[1]))   # shortest burst first
    name, arrival, burst = job
    print(f"{clock:2}-{clock + burst:2}  {name}")
    waits[name] = clock - arrival
    clock += burst
    waiting.remove(job)

print("Waiting:", dict(sorted(waits.items())))
print("Average waiting time:", sum(waits.values()) / len(waits))

 0- 7  P1
 7- 8  P3
 8-12  P2
12-16  P4
Waiting: {'P1': 0, 'P2': 6, 'P3': 3, 'P4': 7}
Average waiting time: 4.0

Round robin

Round-robin scheduling gives each ready process one time slice in turn; a process whose slice runs out goes to the back of the ready queue. It is FCFS made preemptive. Nobody waits more than one round, so response times are short and predictable — which is exactly what an interactive system needs. This simulation uses a time slice of 2 ms; a process that arrives at the moment another's slice ends joins the queue first.

from collections import deque

# name, arrival time, burst time (in milliseconds)
workload = [("P1", 0, 7), ("P2", 2, 4), ("P3", 4, 1), ("P4", 5, 4)]
QUANTUM = 2

remaining = {name: burst for name, _, burst in workload}
arrivals = deque(sorted(workload, key=lambda p: p[1]))
queue = deque()
clock = 0
finish = {}

def admit(until):
    """Move every process that has arrived by `until` into the ready queue."""
    while arrivals and arrivals[0][1] <= until:
        queue.append(arrivals.popleft()[0])

admit(clock)
while queue or arrivals:
    if not queue:
        clock = arrivals[0][1]
        admit(clock)
    name = queue.popleft()
    run = min(QUANTUM, remaining[name])
    print(f"{clock:2}-{clock + run:2}  {name}")
    clock += run
    remaining[name] -= run
    admit(clock)                  # newcomers join the queue first
    if remaining[name] > 0:
        queue.append(name)        # time slice used up: back of the queue
    else:
        finish[name] = clock

waits = {name: finish[name] - arrival - burst for name, arrival, burst in workload}
print("Waiting:", waits)
print("Average waiting time:", sum(waits.values()) / len(waits))

 0- 2  P1
 2- 4  P2
 4- 6  P1
 6- 7  P3
 7- 9  P2
 9-11  P4
11-13  P1
13-15  P4
15-16  P1
Waiting: {'P1': 9, 'P2': 3, 'P3': 2, 'P4': 6}
Average waiting time: 5.0

The average waiting time (5.0 ms) is higher than with FCFS or SJF, because long jobs are chopped up and finish later. But look at the response time — how long each process waits before it first runs: 0, 0, 2 and 4 ms, an average of 1.5 ms, against 4.75 ms with FCFS. Users notice response time, not average completion time, which is why interactive systems are built on round robin plus priorities.

Priority scheduling

Process priority is a number the scheduler uses to decide which ready thread runs first: work that matters more, or must react faster, gets a higher priority. In priority scheduling the ready process with the highest priority always runs; in the preemptive version simulated here, a newly arrived process with a higher priority immediately takes the CPU away from a lower one. In this example 1 is the most important. (Watch out: numbering conventions differ. In Windows a higher number is a higher priority; in Linux a lower nice value is.)

# name, arrival time, burst time (ms), priority (1 = most important)
workload = [("P1", 0, 7, 3), ("P2", 2, 4, 1), ("P3", 4, 1, 4), ("P4", 5, 4, 2)]

remaining = {name: burst for name, _, burst, _ in workload}
finish = {}
timeline = []                        # [name, start, end] per run
for clock in range(sum(remaining.values())):   # one step = 1 ms
    ready = [p for p in workload if p[1] <= clock and remaining[p[0]] > 0]
    name = min(ready, key=lambda p: p[3])[0]   # highest priority wins
    if timeline and timeline[-1][0] == name:
        timeline[-1][2] += 1
    else:
        timeline.append([name, clock, clock + 1])
    remaining[name] -= 1
    if remaining[name] == 0:
        finish[name] = clock + 1

for name, start, end in timeline:
    print(f"{start:2}-{end:2}  {name}")
waits = {name: finish[name] - arrival - burst for name, arrival, burst, _ in workload}
print("Waiting:", waits)
print("Average waiting time:", sum(waits.values()) / len(waits))

 0- 2  P1
 2- 6  P2
 6-10  P4
10-15  P1
15-16  P3
Waiting: {'P1': 8, 'P2': 0, 'P3': 11, 'P4': 1}
Average waiting time: 5.0

P2 arrives at 2 ms and preempts P1 at once; it waits 0 ms. P3, with the lowest priority, needs just 1 ms of CPU and still waits 11 ms, until nothing more important is left.

Comparing the results

Starvation and aging

Starvation is when a ready thread waits indefinitely because the scheduler keeps choosing other threads — in the example above, if new high-priority processes kept arriving, P3 would never run. The standard cure is aging: the longer a thread waits, the more its effective priority rises, until even the least important thread gets a turn. Real schedulers all contain some form of it, as the next section shows.

Real-world schedulers

Production schedulers combine the ideas above — round robin within a priority, preemption, and a form of aging — and add awareness of multiple cores, caches and power.

Windows

Windows schedules threads by priority on a scale of 0 to 31, where a higher number is more important. Levels 16–31 are the real-time range; normal applications live in 1–15. Each process has a priority class — Idle, Below normal, Normal (the default), Above normal, High or Realtime — that sets its threads' base priority, and threads of equal priority take turns round-robin. Within the normal range, Windows raises a thread's priority temporarily (a priority boost) when its I/O completes, when it wakes up after waiting, and when the foreground window receives input, so the app you are using reacts quickly. As protection against starvation, a thread that has been ready for about four seconds without running gets a short boost as well. On processors with performance and efficiency cores, Windows 11 also decides which kind of core suits each thread.

Linux

Linux aims at fairness rather than strict priority for normal tasks. From 2007 its default was the Completely Fair Scheduler (CFS), which tracks how much CPU time each task has had (weighted by its nice value) and always runs the task that has had the least. Starvation cannot happen, because a waiting task's share only becomes more overdue. In Linux 6.6 (2023) CFS was replaced by EEVDF (Earliest Eligible Virtual Deadline First), which keeps the fair-share idea and handles latency-sensitive tasks better. Separate real-time policies (SCHED_FIFO and SCHED_RR) always run before normal tasks and are used for audio and industrial control.

Priorities in practice

Most of the time you should leave priorities alone: the schedulers above do well on their own. Changing them is useful when a long-running background job (a video encode, a large compression, a scan) makes a machine sluggish — lower its priority, and it still uses every idle cycle but gives way as soon as someone needs the CPU.

Windows. In Task Manager, open Details, right-click the process and choose Set priority. The change lasts until the process ends. To start a program at a lower priority, or to change one from PowerShell:

start "" /belownormal "C:\Tools\encoder.exe"

(Get-Process -Id 5120).PriorityClass = 'BelowNormal'

Linux and macOS. The nice value runs from −20 (highest priority) to 19 (lowest), default 0; the name says how "nice" a process is to others. Each step changes a task's share of the CPU by roughly 10% relative to others. Any user may make their own processes nicer; only root may lower the value (raise priority).

nice -n 10 tar -czf backup.tar.gz /home/alex   # start with nice 10
renice -n 15 -p 4620                            # change a running process
sudo renice -n -5 -p 4620                       # raising priority needs root

4620 (process ID) old priority 10, new priority 15
4620 (process ID) old priority 15, new priority -5

Load, CPU usage and why a system feels slow

CPU usage and load average

CPU usage is the share of time the cores spent running something rather than idling. Task Manager shows it per process and overall; the "System Idle Process" on the Details tab is simply the idle time, so a high value there is good news.

Linux adds the load average: the average number of tasks that were running, ready to run, or waiting for disk I/O in an uninterruptible state, over the last 1, 5 and 15 minutes. Compare it with the number of cores: a load of 4 on a 4-core machine means full use; a load of 12 means that on average 8 tasks were waiting, for a core or for disk I/O.

nproc
top

4
top - 10:42:07 up 2 days,  3:15,  1 user,  load average: 3.91, 2.14, 1.20
Tasks: 214 total,   5 running, 209 sleeping,   0 stopped,   0 zombie
%Cpu(s): 94.1 us,  4.2 sy,  1.0 ni,  0.4 id,  0.2 wa,  0.0 hi,  0.1 si,  0.0 st

    PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND
   5120 alex      20   0 1846520 612300  18220 R 391.7   3.8  12:41.07 ffmpeg

Read it from the top: load is rising (1.20 over 15 minutes, 3.91 over the last minute) toward the 4 cores; the CPU is 94% busy in user programs (us) and nearly never idle (id) or waiting for I/O (wa); and one video encoder uses 391.7% — in top, 100% means one full core, so it is keeping all four busy. Press q to leave top. Windows has no load average; the nearest equivalent is the Performance Monitor counter System › Processor Queue Length.

CPU-bound or I/O-bound?

When a user says "the computer is slow", find out what the work is waiting for:

• CPU-bound: threads are ready but the cores are busy. Task Manager shows CPU near 100% (or one core at 100%), and usually one process at the top of the CPU column. Fixes: find out why that process is busy (a runaway process, a scan, malware), lower its priority, or wait for it to finish.
• I/O-bound: threads spend their time waiting for disk or network, and the CPU is mostly idle. Task Manager shows the disk's "Active time" near 100%, or Linux shows a high wa value and a high load with low CPU use. Fixes lie in storage (a failing or full disk, an HDD instead of an SSD), the network, or heavy paging because memory is short (see Memory Management).

OS Troubleshooting works through slow systems step by step.