Linux thread scheduling architecture and internals
Scope: Thread representation in the Linux kernel, scheduling classes (CFS, EEVDF, Real-Time, Deadline), vruntime mechanics, context switching, and SMP load balancing.
The Linux kernel distributes CPU hardware resources among processes and threads when executing multitasking workloads. However, the Linux architecture differs fundamentally from traditional operating systems: there is no distinct “thread” data structure inside the kernel.
Whether it is a single execution stream or a massive server application spawning hundreds of
worker threads, every schedulable unit in the Linux kernel is represented by a task_struct object.
The scheduler balances fairness, latency, and throughput when dispatching these tasks across
CPU cores.
This guide explains how threads are represented in modern Linux 6.x kernels, the modular scheduling
classes (sched_class), the CFS and Linux 6.6+ EEVDF algorithms, the hardware-level cost of
context switches, and the SMP multiprocessor load-balancing principles using diagrams.
1. Thread model in the Linux kernel (1:1 NPTL and task_struct)
In standard POSIX terminology, a process (an address-space owner) and a thread (an execution flow)
are conceptually separate entities. Linux implements a 1:1 Threading Model via NPTL (Native
POSIX Thread Library), where each userspace pthread corresponds directly to exactly one kernel
task_struct.
The clone() system call and resource sharing
In Linux, a process is created using fork(2), while a thread is created using the clone(2) (or modern clone3(2)) system
call. In fact, fork() and vfork(2) are simply wrapper calls to the kernel’s internal kernel_clone()
function; their only difference lies in the clone_flags passed:
CLONE_VM: Shares the virtual memory address space (mm_struct).CLONE_FS: Shares file system root and working directory information (fs_struct).CLONE_FILES: Shares open file descriptors (files_struct).CLONE_SIGHAND: Shares signal handlers.CLONE_THREAD: Places the task in the caller’s Thread Group.
+-----------------------------------------------------------------------------------+
| PROCESS AND THREAD ARCHITECTURE |
+-----------------------------------------------------------------------------------+
Userspace
+-------------------------------------------------------------------------+
| Process (PID: 4100) |
| |
| +--------------------+ +--------------------+ +-----------------+ |
| | Main Thread (TID 1)| | Worker Thread(TID2)| | I/O Thread (TID)| |
| | User Stack | | User Stack | | User Stack | |
| +---------+----------+ +---------+----------+ +--------+--------+ |
+------------|------------------------|-----------------------|-----------+
| clone(CLONE_VM|...) | |
Kernel | | |
Space v v v
+------------------------+ +--------------------+ +--------------------+
| task_struct (Leader) | | task_struct | | task_struct |
| pid: 4100 (TID) | | pid: 4101 (TID) | | pid: 4102 (TID) |
| tgid: 4100 (PID) | | tgid: 4100 (PID) | | tgid: 4100 (PID) |
| se: sched_entity | | se: sched_entity | | se: sched_entity |
| thread_info / stack | | thread_info/stack | | thread_info/stack |
+-----------+------------+ +---------+----------+ +---------+----------+
| | |
+------------+------------+-----------------------+
|
+---> mm_struct ──► [Shared Page Tables / Memory]
+---> files_struct ──► [Shared File Descriptors]
+---> signal_struct ──► [Shared Signal Handlers]
PID, TID and TGID terminology
There is a distinction in terminology between userspace and the kernel:
| Concept | Userspace (POSIX API) | Kernel Internal (task_struct) |
Description |
|---|---|---|---|
| Process ID | getpid(2) |
p->tgid (Thread Group ID) |
The identifier of the thread group leader. |
| Thread ID | gettid(2) / pthread_self() |
p->pid (Process ID) |
The unique identifier assigned by the kernel to each individual task_struct. |
The scheduler does not inspect tgid when dispatching; it directly enqueues the sched_entity
embedded inside the task_struct.
2. Scheduling classes and priority hierarchy (sched_class)
The Linux kernel utilizes an object-oriented style function table (struct sched_class) to provide
a modular scheduler. Each scheduling class defines its own rules for queueing (enqueue_task),
dequeueing (dequeue_task), and selecting the next task to run (pick_next_task).
When a CPU selects the next thread to execute (pick_next_task()), the kernel iterates through
the classes in strict order from highest to lowest priority.
+-----------------------------------------------------------------------------------+
| SCHEDULING CLASSES AND PRIORITY HIERARCHY |
+-----------------------------------------------------------------------------------+
Priority Scheduling Class Policy Use Case
===================================================================================
0 stop_sched_class (Kernel Private) CPU Hotplug, RCU, Migration
|
v dl_sched_class SCHED_DEADLINE Hard Real-Time (EDF/CBS)
----------------------------------------------------------------------
1-99 rt_sched_class SCHED_FIFO, SCHED_RR Soft Real-Time (Audio, Motor)
----------------------------------------------------------------------
100-139 fair_sched_class SCHED_NORMAL (OTHER) Standard User Processes
(Nice SCHED_BATCH Batch Processing (Background)
-20..+19) SCHED_IDLE Low-Priority Tasks
----------------------------------------------------------------------
140 idle_sched_class SCHED_IDLE (swapper) Power-Saving Idle Loop
1. stop_sched_class
The highest priority class. Regular user or kernel processes cannot join this class. It is used
internally by the kernel to take CPUs offline (CPU hotplug) or handle emergency kernel syncs
(stop_machine), preempting all other execution instantly.
2. dl_sched_class (SCHED_DEADLINE)
Based on Earliest Deadline First (EDF) and the Constant Bandwidth Server (CBS). Each task specifies three parameters:
- Runtime: Expected execution duration required per period.
- Deadline: Maximum allowable duration before completion.
- Period: Recurrence interval.
If the system can guarantee that the aggregate Runtime / Period ratio does not exceed CPU capacity
(Admission Control), deadline threads preempt RT and CFS tasks with deterministic scheduling.
3. rt_sched_class (SCHED_FIFO, SCHED_RR)
Handles POSIX real-time threads, configured with static priorities ranging from 1 to 99:
SCHED_FIFO(First-In, First-Out): Runs uninterrupted until it blocks on I/O, yields voluntarily (sched_yield(2)), or is preempted by a higher-priority RT task.SCHED_RR(Round-Robin): Similar toSCHED_FIFO, but shares CPU time among tasks of identical priority using a fixed timeslice (commonly 100 ms).
[!WARNING] An unbounded
SCHED_FIFOthread spinning in an infinite loop can freeze the entire desktop or system. To prevent this, the kernel reserves 50 ms out of every second for non-realtime tasks by default (/proc/sys/kernel/sched_rt_runtime_us = 950000).
4. fair_sched_class (SCHED_NORMAL / SCHED_OTHER)
The default class serving over 99% of workloads on a typical Linux system. Nice levels (-20 to +19) operate within this class. It used CFS (Completely Fair Scheduler) from Linux 2.6.23 through Linux 6.5, and transitioned to EEVDF (Earliest Eligible Virtual Deadline First) in Linux 6.6+.
5. idle_sched_class
Invoked only when no runnable tasks remain in any higher queues. Represented by the per-CPU
swapper/X task (PID 0), which places idle cores into low-power states (C-states via hlt/mwait).
3. Kernel data structures: Per-CPU Runqueues (struct rq)
A single global runqueue in a multi-core processor introduces extreme lock contention: every core must acquire the same global spinlock before dispatching a thread, destroying scalability.
Linux eliminates this bottleneck by maintaining an independent struct rq (Runqueue) for
every logical CPU core.
+-----------------------------------------------------------------------------------+
| PER-CPU RUNQUEUE (struct rq) |
+-----------------------------------------------------------------------------------+
CPU 0 CPU 1
+---------------------------------------+ +---------------------------+
| struct rq | | struct rq |
| raw_spinlock_t lock | | ... |
| struct task_struct *curr ──► (Running)| | |
| | | |
| +---------------------------------+ | | |
| | dl_rq (SCHED_DEADLINE) | | | |
| | rb_root_cached (Deadline EDF) | | | |
| +---------------------------------+ | | |
| | | |
| +---------------------------------+ | | |
| | rt_rq (SCHED_FIFO / SCHED_RR) | | | |
| | prio_array (100 priorities) | | | |
| | [0..99] bitmap + queues | | | |
| +---------------------------------+ | | |
| | | |
| +---------------------------------+ | | |
| | cfs_rq (SCHED_NORMAL / EEVDF) | | | |
| | rb_root_cached (Red-Black) | | | |
| | min_vruntime = 14205820 ns | | | |
| +---------------------------------+ | | |
+---------------------------------------+ +---------------------------+
Sub-queues inside struct rq
dl_rq: Red-black tree ordered strictly by deadline timestamps.rt_rq: 100-entry array (struct rt_prio_array) paired with a priority bitmap. The kernel uses hardware bit-scan instructions (bsfl/clz) viasched_find_first_bit()to identify the highest active priority queue in $O(1)$ time.cfs_rq: Red-black tree tracking normal tasks by virtual runtime (vruntime) or EEVDF eligibility criteria.
4. Fair scheduling mechanics: From CFS to EEVDF and vruntime
For standard tasks in fair_sched_class, the primary goal is dividing CPU execution time
proportionally to task weights derived from nice values.
Nice values and the weight matrix
The nice scale spans -20 (highest priority) to +19 (lowest priority), defaulting to 0.
The kernel converts nice values into relative execution weights via sched_prio_to_weight:
const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, ...
/* 0 */ 1024,
/* +19 */ 15
};
Each 1-point decrease or increase in nice changes CPU allocation weight by roughly 10%. For instance, a task with nice -5 gets approximately 3 times more CPU capacity than a nice 0 task.
Calculating Virtual Runtime (vruntime)
When a thread runs on a physical CPU for an interval $\Delta \text{exec}$, the kernel increments
its virtual runtime (vruntime) using this normalization formula:
- Nice 0 Task (Weight = 1024): The scaling factor is $1024 / 1024 = 1.0$. Virtual time advances in 1:1 lockstep with wall-clock time.
- Low-Priority Task (Nice +10, Weight = 110): The factor is $1024 / 110 \approx 9.3$. Running
for 1 ms advances its
vruntimeby 9.3 ms, pushing it quickly to the right of the queue. - High-Priority Task (Nice -5, Weight = 3121): The factor is $1024 / 3121 \approx 0.32$. Running
for 3 ms advances its
vruntimeby only 1 ms, keeping it near the front of the queue.
Red-Black Tree organization
Tasks are organized inside a self-balancing binary search tree (Red-Black Tree) indexed by vruntime:
+-----------------------------------------------------------------------------------+
| RED-BLACK TREE AND VIRTUAL RUNTIME (vruntime) ORDER |
+-----------------------------------------------------------------------------------+
[ Node B ]
vruntime = 120 ms
/ \
/ \
[ Node A ] [ Node C ]
vruntime = 95 ms vruntime = 160 ms
/
/
[ rb_leftmost ]
vruntime = 80 ms <-- SCHEDULER PICKS THIS NEXT (O(1) CACHED LOOKUP)
(Least CPU time consumed,
highest claim to CPU)
The scheduler caches a pointer to the leftmost leaf (rb_leftmost), allowing next-task selection
in $O(1)$ time, while tree insertions and deletions remain $O(\log N)$.
The Shift in Linux 6.6: CFS to EEVDF
While CFS was effective for throughput, it struggled with latency guarantees. CFS only guaranteed
fair aggregate CPU shares; it could not guarantee how quickly an interactive thread (such as an audio
buffer, UI event, or network packet) would wake up and gain CPU execution. Heuristics like
sched_latency and min_granularity were brittle under mixed workloads.
Linux 6.6 adopted EEVDF (Earliest Eligible Virtual Deadline First) by Peter Zijlstra.
+-----------------------------------------------------------------------------------+
| EEVDF SCHEDULING MECHANICS |
+-----------------------------------------------------------------------------------+
1. Eligibility Check:
Lag_i = V (Average Virtual Time) - vruntime_i
* If Lag_i >= 0 (task consumed less than its fair share): ELIGIBLE
* If Lag_i < 0 (task consumed more than its fair share): INELIGIBLE
2. Virtual Deadline Calculation:
d_i = vruntime_i + (Requested Slice q_i / Weight w_i)
3. Selection Rule:
The scheduler picks the task with the EARLIEST virtual deadline (d_i)
strictly among ELIGIBLE candidates (Lag >= 0).
EEVDF allows interactive tasks to request smaller timeslices ($q_i$), yielding earlier virtual deadlines ($d_i$) and enabling immediate preemption of long-running batch compute tasks without disrupting long-term fairness.
5. Anatomy of a context switch
Once the scheduler selects the next task_struct, it must swap the currently running thread with
the new one on the CPU. This is executed by context_switch().
+-----------------------------------------------------------------------------------+
| CONTEXT SWITCH EXECUTION FLOW |
+-----------------------------------------------------------------------------------+
[ __schedule() Invoked ]
|
v
[ pick_next_task() ]
|
v
[ context_switch(prev, next) ]
|
+---------------------------+---------------------------+
| |
v v
1. Memory Context Switch 2. Register Context Switch
(switch_mm_irqs_off) (switch_to)
| |
+-----+------------------------------+ +-----+----------------------+
| prev->mm == next->mm ? | | %rsp (Stack Pointer) |
| | | %rip (Instruction Pointer) |
| [YES] -> THREADS OF SAME PROCESS | | General Registers (%rbx..) |
| * CR3 register NOT touched! | | FS_BASE / GS_BASE (TLS) |
| * TLB NOT flushed! | | FPU/AVX (XSAVE/XRSTOR) |
| * NEAR ZERO MEMORY PENALTY | +----------------------------+
| | |
| [NO] -> DIFFERENT PROCESSES | v
| * CR3 reloaded (Page Tables) | [ New Task Resumes ]
| * TLB flushed (or PCID tagged) |
+------------------------------------+
1. Memory context switch (switch_mm_irqs_off)
When switching between two threads within the same process (prev->mm == next->mm), they share
the exact same virtual address space:
- The page table base register (such as
CR3on x86_64) is not reloaded. - The processor’s Translation Lookaside Buffer (TLB) remains entirely valid.
This is the primary reason why thread context switches are substantially faster than process
switches. Reloading CR3 invalidates address translations, triggering a burst of TLB misses and
memory stall cycles.
2. Architecture register context switch (switch_to)
Hardware state is transferred from the old thread to the new thread:
- Architectural stack pointer (
%rsp) and instruction pointer (%rip) are swapped. - Callee-saved general-purpose registers (
%rbx,%rbp,%r12-%r15) are saved to and restored from the kernel stack. - Thread-Local Storage base registers (
FS_BASE/GS_BASE) are redirected. - Floating-point and SIMD vector registers (SSE, AVX-512) are saved and restored using optimized
XSAVE/XRSTORinstruction sequences.
Voluntary vs involuntary context switches
- Voluntary Context Switch: The thread voluntarily releases the CPU by blocking on I/O,
waiting on a mutex, or calling
sleep(). - Involuntary (Preemptive) Context Switch: Triggered when the timer tick (
scheduler_tick) expires a timeslice or a higher-priority task wakes up. The kernel flagsTIF_NEED_RESCHED, and preemption is enforced upon return to userspace.
6. Multiprocessor (SMP / NUMA) load balancing
Leaving one core idle while another has 50 queued threads hurts system responsiveness. Linux balances
workloads using a tree of Scheduling Domains (sched_domain).
+-----------------------------------------------------------------------------------+
| NUMA AND SCHEDULING DOMAIN (sched_domain) TOPOLOGY |
+-----------------------------------------------------------------------------------+
NUMA Node 0 (Memory Bank 0) NUMA Node 1 (Memory Bank 1)
+---------------------------------------+ +---------------------------------------+
| Socket 0 | | Socket 1 |
| Shared L3 Cache (LLC Domain) | | Shared L3 Cache (LLC Domain) |
| | | |
| Core 0 (MC) Core 1 (MC) | | Core 2 (MC) Core 3 (MC) |
| +----------------+ +--------------+ | | +----------------+ +--------------+ |
| | SMT 0 | SMT 1 | | SMT 2 | SMT 3| | | | SMT 4 | SMT 5 | | SMT 6 | SMT 7| |
| | CPU 0 | CPU 1 | | CPU 2 | CPU 3| | | | CPU 4 | CPU 5 | | CPU 6 | CPU 7| |
| +--------+-------+ +-------+------+ | | +--------+-------+ +-------+------+ |
+---------------------------------------+ +---------------------------------------+
\ /
\====== High-Speed Interconnect (QPI / UPI / Infinity Fabric) ======/
Balancing hierarchy and overhead
Load balancing progresses from the cheapest hardware boundary to the most expensive:
- SMT Domain (Hyper-Threading): CPU 0 and CPU 1 share L1/L2 caches. Moving tasks between them costs almost nothing.
- MC Domain (Multi-Core): Cores on the same die share the L3 cache (LLC). Cache repopulation penalties are low.
- NUMA Domain: Migrating a task across sockets forces it to access its previously allocated RAM remotely across the interconnect fabric, incurring high memory latency. Migration across NUMA boundaries is performed only when severe load imbalances occur.
Core scheduling and CPU affinity
- CPU Affinity (
taskset/sched_setaffinity(2)): Locks threads to specific CPU cores, preserving L1/L2 cache warmth; current masks can be read viasched_getaffinity(2). - Core Scheduling (
prctl(2)): Added in Linux 5.14 withPR_SCHED_CORE, this feature ensures that only mutually trusted threads share SMT sibling threads on the same physical core, preventing hardware side-channel vulnerabilities such as Spectre and MDS.
7. Practical monitoring, diagnosis and priority control
Useful commands for inspecting and diagnosing thread scheduling behavior directly on a running system:
Listing threads and core assignments
To display threads alongside their scheduling class, priority, and current CPU core:
ps -eo pid,tid,class,rtprio,ni,pri,psr,comm -L | grep -v "TS -"
Field meanings:
tid: Thread ID.class: Scheduling class (TS= Normal/Fair,FF= FIFO,RR= Round-Robin,DL= Deadline).rtprio: Real-time priority (1-99).ni: Nice value (-20 to +19).psr: The logical processor core currently executing this thread.
For live per-thread monitoring:
top -H
Tracking voluntary and involuntary context switches
To monitor switch frequencies for a target process and its child threads:
pidstat -w -t -p <PID> 1
Example output:
14:22:01 UID TGID TID cswch/s nvcswch/s Command
14:22:02 1000 4520 - 2.00 148.00 calculator
14:22:02 1000 - 4520 1.00 50.00 |__calculator
14:22:02 1000 - 4521 1.00 98.00 |__worker_1
cswch/s(Voluntary): High counts indicate blocking on mutexes, I/O, or network sockets.nvcswch/s(Non-voluntary): High counts indicate CPU-bound tasks hitting their timeslice limits.
Inspecting scheduling metrics via /proc
Detailed runtime metrics, virtual runtime values, and migration counts are exposed under /proc:
cat /proc/<PID>/task/<TID>/sched
Key output fields:
worker_1 (4521, #threads: 2)
-------------------------------------------------------------------
se.exec_start : 1425890.124502
se.vruntime : 15420.892014
se.sum_exec_runtime : 1250.410293
se.nr_migrations : 4
nr_switches : 340
nr_voluntary_switches : 12
nr_involuntary_switches : 328
Adjusting scheduling policies: chrt and renice
The chrt command interfaces with the kernel via sched_setscheduler(2) and sched_setattr(2); policy queries use sched_getscheduler(2) and sched_getattr(2).
To switch a running thread to the SCHED_FIFO real-time class with priority 50:
sudo chrt -f -p 50 <TID>
To query a thread’s current policy:
chrt -p <TID>
Sample response:
pid 4521's current scheduling policy: SCHED_FIFO
pid 4521's current scheduling priority: 50
Measuring scheduling latency with perf sched
To measure the wake-up latency between when a thread becomes runnable and when it actually starts executing on a CPU:
sudo perf sched record -- sleep 2
sudo perf sched latency
Sample summary:
-----------------------------------------------------------------------------------------------------------------
Task | Runtime ms | Switches | Avg delay ms | Max delay ms | Max delay start | Max delay at |
-----------------------------------------------------------------------------------------------------------------
worker_1:4521 | 1820.450 ms | 450 | 0.012 ms | 0.185 ms | 142589.102345 s | 142589.102530 s |
kworker/u16:2:120 | 12.100 ms | 45 | 0.004 ms | 0.021 ms | 142588.940120 s | 142588.940141 s |
-----------------------------------------------------------------------------------------------------------------
Avg delay ms and Max delay ms quantify how long tasks waited in runqueues before being
scheduled. Minimizing these latency values is the primary objective in real-time tuning.
References and verification environment
- Linux Kernel Documentation: CFS Scheduler
- Linux Kernel Documentation: Deadline Task Scheduling
- Peter Zijlstra: EEVDF Scheduler Patchset (Linux Kernel Archives)
- Robert Love: Linux Kernel Development (3rd Edition) - Chapter 4: Process Scheduling
sched(7)manual page
Related system calls (Linux System Call Reference)
clone(2): Creating threads or child processes.clone3(2): Modern extensiblecloneinterface.fork(2)andvfork(2): Process fork system calls.getpid(2)andgettid(2): Querying process and thread IDs.sched_yield(2): Voluntarily relinquishing the processor.sched_setaffinity(2)andsched_getaffinity(2): Managing CPU affinity bitmasks.sched_setscheduler(2)andsched_getscheduler(2): Configuring scheduling policies and priorities.sched_setattr(2)andsched_getattr(2): Extended scheduling attributes (SCHED_DEADLINE and EEVDF slice tuning).prctl(2): Core scheduling isolation viaPR_SCHED_CORE.
Commands and kernel data structures in this guide were verified on Ubuntu 24.04 LTS
(Linux 6.8.0-48 x86_64) and Debian 12 (Linux 6.6+ kernel) using util-linux, procps,
and linux-tools-generic.