How Linux Kernel Handles Multitasking

The Linux operating system achieves multitasking at the kernel level through preemptive scheduling, abstract task representations, and efficient hardware resource management. By treating processes and threads uniformly, relying on precise hardware timer interrupts, and executing rapid context switches, the kernel rapidly alternates CPU execution among competing tasks. This architecture ensures balanced CPU distribution, system responsiveness, and fault isolation across multi-core and single-core environments.

The Task Representation: task_struct

At the kernel level, Linux does not make a fundamental structural distinction between a process and an execution thread. Instead, both are instantiated as individual schedulable entities called tasks, represented internally by the task_struct data structure. This structure holds all critical metadata required to manage and execute the task, including:

• Process state: Flags indicating whether the task is running (TASK_RUNNING), waiting for an event (TASK_INTERRUPTIBLE or TASK_UNINTERRUPTIBLE), stopped, or a zombie.
• Virtual memory mappings: Pointer to the mm_struct, detailing the memory space, page tables, and execution code. Threads created within the same process share this memory descriptor, while distinct processes maintain independent ones.
• CPU state: Stored CPU register values, stack pointers, and instruction counters.
• Priority and scheduling entity: Execution metrics including nice values, virtual runtime, and policy flags used by scheduling algorithms.

The kernel creates these tasks through system calls such as fork(), vfork(), and clone(), the latter being the core foundation used by threading libraries to establish shared or separate execution contexts.

Preemption and Hardware Timer Interrupts

Linux uses preemptive multitasking, meaning the operating system decides when a task must stop running rather than waiting for the task to voluntarily yield CPU control. This preemption relies on periodic hardware timer interrupts generated by the system clock (such as the Local APIC or HPET).

When a timer interrupt fires:

1. The CPU transfers execution from user space to kernel space.
2. The interrupt handler executes scheduler housekeeping tasks, such as tracking how long the currently running task has held the CPU.
3. The kernel evaluates whether the current task's allocated time slice has expired or if a higher-priority task has entered a runnable state.
4. If a preemption criteria is met, the kernel sets the TIF_NEED_RESCHED flag on the current task.
5. The kernel invokes schedule() during the return path to user mode (or at defined preemption points within kernel mode), triggering a task swap.

The Kernel Schedulers

The selection of the next task to run is managed by modular scheduling classes organized by priority.

1. Real-Time Schedulers (SCHED_FIFO and SCHED_RR)

Real-time tasks take precedence over standard system tasks. SCHED_FIFO (First-In, First-Out) tasks run indefinitely until they voluntarily yield or become blocked by an I/O operation. SCHED_RR (Round Robin) tasks execute similarly, but with a fixed maximum time slice, after which other real-time tasks of equal priority are executed.

2. Normal Tasks: CFS and EEVDF

For normal, non-real-time tasks, Linux historically relied on the Completely Fair Scheduler (CFS) and, in newer kernels (version 6.6+), the Earliest Eligible Virtual Deadline First (EEVDF) scheduler.

• Completely Fair Scheduler (CFS): Models an "ideal multi-tasking CPU" where tasks share processing power proportionally according to their nice value (priority). CFS tracks execution using vruntime (virtual runtime). Tasks that have executed the least receive the lowest vruntime and are placed at the leftmost node of a red-black self-balancing binary search tree. The CPU always picks the leftmost task next.
• EEVDF: Evolves CFS by introducing explicit deadlines. It balances fairness (eligibility based on virtual time) with low latency (scheduling the eligible task that has the earliest execution deadline).

The Context Switch

Once the scheduler selects a new task, the kernel performs a context switch via the internal context_switch() function. This operation consists of two primary steps:

1. Virtual Memory Switching (switch_mm): If the new task belongs to a different process, the kernel swaps the memory management context by loading the new task's page directory address into the CPU's memory management unit (e.g., the CR3 control register on x86 architectures). This invalidates the Translation Lookaside Buffer (TLB), unless process context identifiers (PCID) are supported. If the new task is a thread sharing the previous address space or a kernel thread, this step is bypassed.
2. Processor State Switching (switch_to): The kernel saves the outgoing task's hardware state (instruction pointer, stack pointer, general-purpose registers, floating-point registers) into its kernel stack or task_struct. It then restores the incoming task’s saved registers and updates the CPU's stack pointer.

When the CPU's instruction pointer resumes execution, the new task continues precisely where it was suspended, finalizing the multitask transition at the hardware boundary.