Processes and Scheduling: What the Kernel Actually Runs

A process is not "a running program". It is two kernel-owned objects that live and die together: an address space and a control block.

The address space is the set of virtual memory mappings the task may touch, described on Linux by struct mm_struct. The control block is struct task_struct, the kernel's per-task record: process id, saved register state, scheduling class and priority, the file descriptor table, signal handlers, credentials, and links to parent and children.

The program's instructions live in the address space. Everything the kernel needs in order to manage that program lives in the control block. Every textbook "process control block" is this second object. The split is what makes the rest of the subject possible: one address space can host several execution contexts, and fork() can hand a child an identical address space without copying a single byte of it.

There is no struct thread in the Linux kernel. Both fork() and pthread_create() funnel into clone(), and the only difference is which resources the new task shares with its creator.

Either way the new task gets its own task_struct, its own kernel stack, and its own place in the scheduler. So the unit the scheduler picks is a task, one per thread, not a process. That is also why getpid() returns the thread group id shared by every thread in the process, while gettid() returns the per-task id the kernel is actually scheduling.

Swapping tasks means saving the outgoing task's callee-saved registers and stack pointer, then loading the incoming task's. That part is genuinely cheap, a few dozen instructions.

The expense is everything around it. If the two tasks live in different address spaces, the kernel also reloads CR3, the page table base register, which on hardware without process-context identifiers flushes the TLB. Then come the indirect costs: the resumed task finds its data evicted from L1 and L2, and a branch predictor trained on somebody else's code.

Eli Bendersky measured the direct cost on a Haswell i7-4771 at 1.2 to 1.5 microseconds per switch with both threads pinned to a single core, rising to roughly 2.2 microseconds unpinned. He is explicit that this excludes the cache effects, which are workload dependent and frequently larger than the switch itself.

The scheduler only ever chooses among tasks in the runnable set. Everything else is bookkeeping around that set.

Each CPU owns a run queue. Scheduling decisions are therefore mostly local, and a task sits on exactly one run queue at a time. Moving it elsewhere is a migration, and migrations are deliberately throttled because they discard cache locality.

Preemption is not the kernel constantly interrupting you. When something more deserving becomes runnable, or when the periodic timer tick observes that the current task has consumed its slice, the kernel merely sets a flag on the running task: TIF_NEED_RESCHED. Nothing happens yet.

The flag is acted on only at defined points: on return from an interrupt, on return from a system call, and, in kernels built with CONFIG_PREEMPT, at preemption-safe points inside kernel code too. A task can also give up the CPU voluntarily by blocking. Those two paths are why Linux distinguishes voluntary from involuntary context switches.

The Completely Fair Scheduler kept a vruntime per task: real time consumed, divided by the task's weight. Pick the smallest vruntime, and over time everybody converges on a proportional share.

Weight comes from the nice value through a fixed lookup table, sched_prio_to_weight in kernel/sched/core.c. Nice 0 maps to weight 1024, and each step of one nice level scales the weight by roughly 1.25. That constant is chosen so that one nice level is about a 10 percent difference in CPU share between two CPU-bound tasks, and the effect compounds. The table runs from nice -20 at weight 88761 down to nice +19 at weight 15, a spread of roughly 5900 to 1.

The practical consequence people miss: nice is relative. It changes nothing unless another task is competing for the same run queue.

CFS had one structural gap, described by Jonathan Corbet in LWN's coverage of the proposal: there was no way to say this task does not need more CPU, it needs the CPU sooner. Nice bought you more time, never faster response.

EEVDF, Earliest Eligible Virtual Deadline First, separates the two. It tracks lag, the gap between the CPU time a task was owed and the time it actually received. A task whose lag is at or above zero is eligible. Every eligible task gets a virtual deadline, its eligible time plus its requested slice, and the scheduler runs the earliest deadline first.

So a task that asks for a short slice gets selected more often without receiving more total CPU. It was merged as an option in Linux 6.6 and the conversion was completed in 6.12. The base slice lives at /proc/sys/kernel/sched_base_slice_ns, default 3 milliseconds.

Linux does not run a single algorithm. It walks an ordered list of scheduling classes and takes the first one with a runnable task:

1. stop_sched_class - internal only, for CPU hotplug and forced migration.
2. dl_sched_class - SCHED_DEADLINE. Tasks declare a runtime, a deadline, and a period, and the kernel refuses admission if the set is not schedulable.
3. rt_sched_class - SCHED_FIFO and SCHED_RR, 99 static priority levels, all of which outrank every normal task.
4. fair_sched_class - SCHED_OTHER and SCHED_BATCH, where EEVDF lives.
5. idle_sched_class - the idle task.

A SCHED_FIFO task at priority 1 therefore beats every normal task on its CPU and runs until it blocks or yields. That is a loaded gun. Linux defuses it with real-time throttling: per the kernel's scheduler documentation, sched_rt_runtime_us defaults to 950000 within a sched_rt_period_us of 1000000, reserving 50 milliseconds of every second for normal tasks.

Everything above is inspectable from a shell.

# Which class and priority is this task in?
$ chrt -p 1234
pid 1234's current scheduling policy: SCHED_OTHER
pid 1234's current scheduling priority: 0

# Deprioritise a batch job and pin it to two cores
$ nice -n 10 taskset -c 2,3 ./nightly_reindex

# Promote a latency-critical task to round-robin real time
$ sudo chrt -r 20 ./audio_engine

# How long has it run, and how long did it wait to run?
$ cat /proc/1234/schedstat
2841399417 190283740 1204

The three schedstat fields are, in order: nanoseconds spent on a CPU, nanoseconds spent runnable but waiting on a run queue, and the number of timeslices used. That middle number is the diagnosis. A slow service with a small first field and a huge second one is not slow because it is working, it is slow because it is queued.

• Nice does nothing on an idle machine. A nice 19 task alone on a core runs at full speed. Nice only divides a CPU two tasks are fighting over.
• SCHED_FIFO is not a speed knob. It is a correctness tool for hard-deadline work. Applied casually it produces priority inversion, where a high-priority task spins waiting for a lock held by a normal task it is starving.
• More runnable threads than cores costs twice: run-queue wait, plus cache thrash from the extra switches.
• Watch involuntary switches. /proc/PID/status reports voluntary_ctxt_switches and nonvoluntary_ctxt_switches. A high nonvoluntary count means the scheduler is taking the CPU away, not that your code is blocking.
• Pinning has a cost too. taskset buys cache locality and gives up the scheduler's ability to route work around a busy core.

Scheduler policy used to be a thing you argued about on a mailing list for a year. Since Linux 6.12, sched_ext allows a scheduling policy to be loaded at run time as a BPF program, sitting as its own class above the fair class.

The safety property is what makes it usable: if the loaded scheduler misbehaves or stops responding, the kernel ejects it and falls back to the built-in one. A failed experiment costs you a few milliseconds, not a reboot.

Structurally that moves scheduler design from a kernel-patch problem to a deployment problem, which is why workload-specific policies for interactive desktops, build farms, and container fleets became practical to ship at all. EEVDF remains the default; sched_ext is opt-in per system, and the class ordering means a loaded BPF scheduler still cannot outrank real-time tasks.