The Linux Kernel/Multitasking

multitaskingexecutionthreads or taskssynchronizationSchedulerinterrupts coreCPU specific Linux kernel is a preemptive Computer multitasking multitasking operating system. As a multitasking OS, it allows multiple processes to share processors (CPUs) and other system resources. Each CPU executes a single task at a time. However, multitasking allows each processor to switch between tasks that are being executed without having to wait for each task to finish. For that, the kernel can, at any time, temporarily interrupt a task being carried out by the processor, and replace it by another task that can be new or a previously suspended one. The operation involving the swapping of the running task is called context switch. Execution ⚲ API ↪ ⚙️ implementations 2 execve ↪ do_execveat_common runs an executable file in the context of current process, replacing the previous executable. This system call is used by family of functions of libc 3 exec. The Executable and Linkable Format ELF binary format is loaded by fs/binfmt_elf.c. 2 clone. Clone creates a child process that may share parts of its execution context with the parent. It is often used to implement threads (though programmers will typically use a higher-level interface such as 7 pthreads, implemented on top of clone). 2 wait ↪ kernel_waitid suspends the execution of the calling process until one of its child processes terminates. Syscall 2 getpid ↪ task_tgid_vnr returns PID of the current process which internally is called TGID - thread group id. A process can contain many threads. 2 gettid ↪ task_pid_vnr returns thread id. Which internally is historically called PID. ⚠️ Warning: confusion. User space PID ≠ kernel space PID. 1 ps -AF lists current processes and thread as Light-weight process LWP. For a single thread process all these IDs are equal. High-resolution delays: 2 nanosleep ↪ sys_nanosleep hrtimer_nanosleep 2 clock_nanosleep ↪ sys_clock_nanosleep Wait for a signal: 2 pause ↪ sys_pause 2 sigsuspend ↪ sys_sigsuspend 🔨 stress-ng --context, --switch See Processes for process creation and termination. Inter-process communication Inter-process communication (IPC) refers specifically to the mechanisms an operating system provides to allow processes it manages to share data. Methods for achieving IPC are divided into categories which vary based on software requirements, such as performance and modularity requirements, and system circumstances. Linux inherited from Unix the following IPC mechanisms: Signals (⚲ API ↪ ⚙️ implementations): 2 kill sends signal to a process 2 tgkill ↪ do_tkill sends a signal to a thread 2 process_vm_readv ↪ process_vm_rw - zero-copy data transfer between process address spaces 2 sigaction ↪ do_sigaction – examine and change a signal action 2 sigprocmask – examine and change blocked signals 2 sigpending ↪ do_sigpending – examine pending signals 2 sigsuspend – wait for a signal 2 sigaltstack – set or get signal stack context 2 sigtimedwait ↪ do_sigtimedwait – synchronously wait for queued signals 7 signal – overview of signals linux/sched/signal.h – signal-related task accessors kernel/signal.c – signal delivery and handling 🔨 stress-ng --sigq Anonymous pipes and named pipes (FIFOs) 2 mknod ↪ do_mknodat S_IFIFO Express Data Path PF_XDP Unix domain socket PF_UNIX Memory-mapped files 2 mmap ⤑ ksys_mmap_pgoff 2 eventfd ↪ do_eventfd – event notification via file descriptor 2 signalfd ↪ do_signalfd4 – receive signals via file descriptor 2 timerfd_create – timer notification via file descriptor Sys V IPC: Message queues: 2 msgget, 2 msgsnd, 2 msgrcv ↪ ipc/msg.c Semaphores Shared memory: 2 shmget, 2 shmctl, 2 shmat, 2 shmdt ↪ ipc/shm.c POSIX message queues: 7 mq_overview, 3 mq_open, 3 mq_send, 3 mq_receive ↪ ipc/mqueue.c 🔨 --mq 📖 References Inter-process communication 7 sysvipc Threads or tasks In Linux kernel "thread" and "task" are almost synonyms. ⚲ API linux/sched.h - the main scheduler API task_struct arch/x86/include/asm/current.h – x86 current task pointer current and get_current () return current task_struct uapi/linux/taskstats.h per-task statistics linux/thread_info.h current_thread_info() returns thread_info linux/sched/task.h - interface between the scheduler and various task lifetime (fork()/exit()) functionality linux/kthread.h - simple interface for creating and stopping kernel threads without mess. kthread_run creates and wakes a thread kthread_create ⚙️ Internals kthread_run ↯ hierarchy: kernel/kthread.c – kernel thread creation and management kthreadd – parent kernel thread and the creator of all other kernel threads. Dequeues kthread_create_info from kthread_create_list. create_kthread kernel_thread kthread – invokes threadfn __kthread_create_on_node – enqueues kthread_create_info into kthread_create_list kernel/fork.c – process creation and cloning kernel_thread kernel_clone 🔨 stress-ng --clone, --fork, --pthread Scheduler The Scheduling_(computing)#Linux scheduler is the part of the operating system that decides which process runs at a certain point in time. It usually has the ability to pause a running process, move it to the back of the running queue and start a new process. Active processes are placed in an array called a run queue, or runqueue - rq. The run queue may contain priority values for each process, which will be used by the scheduler to determine which process to run next. To ensure each program has a fair share of resources, each one is run for some time period (quantum) before it is paused and placed back into the run queue. When a program is stopped to let another run, the program with the highest priority in the run queue is then allowed to execute. Processes are also removed from the run queue when they ask to sleep, are waiting on a resource to become available, or have been terminated. Since version 6.6 the Linux kernel uses the Earliest eligible virtual deadline first scheduling (EEVDF) algorithm, which replaced the Completely Fair Scheduler (CFS). While much of the CFS infrastructure remains: sched_entity, cfs_rq, the red-black tree, load balancing, and kernel/sched/fair.c — the task selection logic is fundamentally different. EEVDF is based on a classic scheduling algorithm originally designed for packet networks. The scheduler has a scheduling complexity of O(log N), where N is the number of tasks in the runqueue. Both picking and reinserting a task require O(log N) operations, because the run queue is implemented as a red–black tree. The runqueue (cfs_rq) is implemented as a red-black tree representing a "timeline" of future task execution. The scheduler uses nanosecond granularity accounting and requires no heuristics or interactivity estimators. EEVDF improves sleeper fairness over CFS by tracking lag (vlag) — the difference between the service a task was entitled to and the service it actually received. When a sleeping task wakes up, its lag determines eligibility, ensuring interactive tasks get prompt service without starving long-running tasks. The data structure used for the scheduling algorithm is a red-black tree in which the nodes are sched_entity structures, embedded in task_struct. With EEVDF, each task has a time slice (sysctl_sched_base_slice, default 0.7ms) that determines its request length. EEVDF computes a virtual deadline for each task: vd_i = ve_i + r_i/w_i, where ve_i is the eligible time, r_i is the request size, and w_i is the weight (determined by nice value). The scheduler picks the eligible task with the earliest virtual deadline via pick_eevdf. The Linux kernel contains different scheduler classes (or policies). The EEVDF scheduler handles SCHED_NORMAL (aka SCHED_OTHER). The kernel also contains two additional classes SCHED_BATCH and SCHED_IDLE, and another two real-time scheduling classes named SCHED_FIFO (realtime first-in-first-out) and SCHED_RR (realtime round-robin), with a third realtime scheduling policy known as SCHED_DEADLINE that implements the Earliest deadline first scheduling earliest deadline first algorithm (EDF) added later. Any realtime scheduler class takes precedence over any of the "normal" —i.e. non realtime— classes. The scheduler class is selected and configured through the 2 sched_setscheduler ↪ do_sched_setscheduler system call. Properly balancing latency, throughput, and fairness in schedulers is an open problem.Malte Skarupke. "Measuring Mutexes, Spinlocks and how Bad the Linux Scheduler Really is". ⚲ API 1 renice – priority of running processes 1 nice – run a program with modified scheduling priority 1 chrt – manipulate the real-time attributes of a process 2 sched_getattr ↪ sys_sched_getattr – get scheduling policy and attributes linux/sched.h – the main scheduler API schedule 2 getpriority, 2 setpriority 2 sched_setscheduler, 2 sched_getscheduler /sys/kernel/debug/sched/ – scheduler debugfs tuning directory features – toggle scheduler feature flags base_slice_ns – EEVDF base time slice (default 700000) migration_cost_ns – cost threshold for task migration between CPUs nr_migrate – max tasks to migrate per balancing pass debug – dump detailed scheduler state numa_balancing/ – NUMA balancing scan parameters ⚙️ Internals sched_init is called from start_kernel __schedule is the main scheduler function. runqueues, this_rq kernel/sched – scheduler subsystem kernel/sched/core.c – core scheduling logic kernel/sched/fair.c implements SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE pick_eevdf – core of EEVDF sched_setscheduler, sched_getscheduler task_struct::rt_priority and other members with less unique identifiers 🔨 stress-ng --schedpolicy 🛠️ Utilities 1 pidstat 1 pcp-pidstat 1 perf-sched Understanding Scheduling Behavior with SchedViz 📖 References 7 sched Scheduling scheduler EEVDF Scheduler scheduler/sched-eevdf.html An EEVDF CPU scheduler for Linux LWN Delaying and scheduling routines driver-api/basics.html#delaying-and-scheduling-routines CFS Completely Fair Scheduler scheduler/sched-design-CFS.html CFS Bandwidth Control scheduler/sched-bwc.html CPU cgroup controller CPU cgroup interface files admin-guide/cgroup-v2.html#cpu-interface-files Completely fair scheduler LWN Tuning the task scheduler stop using CPU limits on Kubernetes Deadline Task Scheduler scheduler/sched-deadline.html kernel sched kernel/syscalls sched_setparam kernel/syscalls sched_getscheduler kernel/syscalls sched_setscheduler 📚 Further reading about the scheduler Tuning scheduling policy, RHEL Scheduler tracing bcc/ebpf CPU and scheduler tools Preemption Preemption refers to the ability of the system to interrupt a running task to switch to another task. This is essential for ensuring that high-priority tasks receive the necessary CPU time and for improving the system's responsiveness. In Linux, preemption models define how and when the kernel can preempt tasks. Different models offer varying trade-offs between system responsiveness and throughput. 📖 References Proper Locking Under a Preemptible Kernel locking/preempt-locking.html preempt_enable – decrement the preempt counter preempt_disable – increment the preempt counter preempt_enable_no_resched – decrement, but do not immediately preempt preempt_check_resched – if needed, reschedule preempt_count – return the preempt counter kernel/Kconfig.preempt – preemption model configuration CONFIG_PREEMPT_NONE – no forced preemption for servers CONFIG_PREEMPT_VOLUNTARY – voluntary preemption for desktops CONFIG_PREEMPT – preemptible except for critical sections for low-latency desktops CONFIG_PREEMPT_RT – real-time preemption for highly responsive applications CONFIG_PREEMPT_DYNAMIC – allows runtime switching of preemption model /sys/kernel/debug/sched/preempt – shows and controls the active preemption model sched_ext Since version 6.12 the kernel supports SCHED_EXT — an extensible scheduler class whose behavior is defined by a set of eBPF programs. Any scheduling algorithm can be implemented on top of sched_ext, loaded and unloaded dynamically at runtime. The system integrity is maintained no matter what the BPF scheduler does: the default scheduling behavior is restored on error or when a runnable task stalls. ⚙️ Internals CONFIG_SCHED_CLASS_EXT kernel/sched/ext.c – extensible BPF scheduler class sched_ext_ops – BPF scheduler operations sched_ext_entity – per-task sched_ext data, embedded in task_struct 👁 Examples tools/sched_ext – in-tree example BPF schedulers 📖 References Extensible Scheduler Class scheduler/sched-ext.html sched-ext/scx – production BPF schedulers Scheduler BPF LWN Energy Aware Scheduling 🚀 advanced topic Since version 5.0, Energy Aware Scheduling (EAS) gives the scheduler the ability to predict the impact of its decisions on the energy consumed by CPUs. EAS relies on an Energy Model (EM) to select an energy efficient CPU for each task, with minimal impact on throughput. EAS operates only on heterogeneous CPU topologies (such as ARM big.LITTLE) where the potential for energy savings is highest. ⚲ API /proc/sys/kernel/sched_energy_aware – enable or disable EAS linux/energy_model.h em_perf_domain – performance domain descriptor em_cpu_get – get the EM for a given CPU ⚙️ Internals CONFIG_ENERGY_MODEL find_energy_efficient_cpu – find most energy-efficient target CPU for a waking task kernel/power/energy_model.c – CPU energy model framework 📖 References Energy Aware Scheduling scheduler/sched-energy.html Energy Model of devices power/energy-model.html Wait queues A wait queue in the kernel is a data structure that allows one or more processes to wait (sleep) until something of interest happens. They are used throughout the kernel to wait for available memory, I/O completion, message arrival, and many other things. In the early days of Linux, a wait queue was a simple list of waiting processes, but various scalability problems (including the thundering herd problem) have led to the addition of a fair amount of complexity since then. ⚲ API linux/wait.h wait_queue_head consists of double linked list of wait_queue_entry and a spinlock. Waiting for simple events: Use one of two methods for wait_queue_head initialization: init_waitqueue_head initializes wait_queue_head in function context DECLARE_WAIT_QUEUE_HEAD - actually defines wait_queue_head in global context Wait alternatives: wait_event_interruptible - preferable wait wait_event_interruptible_timeout wait_event - uninterruptible wait. Can cause deadlock ⚠ wake_up etc 👁 For example usage see references to unique suspend_queue. Explicit use of add_wait_queue instead of simple wait_event for complex cases: DECLARE_WAITQUEUE actually defines wait_queue_entry with default_wake_function add_wait_queue inserts process in the first position of a wait queue remove_wait_queue ⚙️ Internals ___wait_event __add_wait_queue __wake_up_common, try_to_wake_up kernel/sched/wait.c – wait queue implementation Simple wait queues – simplified version with raw spinlock, suitable for RT and restricted contexts: linux/swait.h swait_queue_head, swait_queue kernel/sched/swait.c – simple wait queue implementation 📖 References Wait queues and Wake events driver-api/basics.html#wait-queues-and-wake-events Real-time Time ⚲ UAPI uapi/linux/time.h timespec – nanosecond resolution timeval – microsecond resolution timezone ... uapi/linux/time_types.h __kernel_timespec – nanosecond resolution, used in syscalls ... ⚲ API linux/delay.h – busy-wait delay functions for timing control linux/sched/clock.h sched_clock ... linux/time.h tm get_timespec64 ... linux/ktime.h ktime_t – nanosecond scalar representation for kernel time values ktime_sub ... linux/timekeeping.h ktime_get, ktime_get_ns ktime_get_real ... linux/time64.h timespec64 time64_t ns_to_timespec64 timespec64_sub ktime_to_timespec64 ... uapi/linux/rtc.h linux/jiffies.h ⚙️ Internals kernel/time – timekeeping, timers and clocks timekeeper – central timekeeping state tkr_mono – monotonic clock, frequency corrected by NTP for accurate real-world seconds 8 chronyd → 2 adjtimex ↪ sys_adjtimex tkr_raw – raw monotonic clock, no NTP correction, drifts with crystal error update_wall_time ← tick_periodic → timekeeping_advance (blocks readers with write_seqcount_begin): tk_clock_read – reads clocksource hardware logarithmic_accumulation – accumulates ticks in doubling steps (efficient for NO_HZ) timekeeping_adjust – corrects mult to steer toward NTP frequency accumulate_nsecs_to_secs – rolls nanoseconds into seconds timekeeping_update_from_shadow – publishes shadow timekeeper to live update_vsyscall – copies time data to vDSO page for userspace 2 clock_gettime without syscall update_fast_timekeeper – NMI-safe copy via write_seqcount_latch_begin (two copies, ktime_get_mono_fast_ns and other ktime_get*_fast readers spin on read_seqcount_latch_retry) ktime_get and all ktime_get* readers spin on read_seqcount_retry until consistent ktime_get = tkr_mono.base + timekeeping_get_ns timekeeping_get_ns → tk_clock_read, timekeeping_cycles_to_ns – converts cycles to ns (delta only, added to base by caller) tk_clock_read → arch_inlined_clocksource_read → rdtsc_ordered – x86 Time_Stamp_Counter TSC fast path via static key timekeeping_get_ns and rdtsc_ordered are safe to trace timekeeping (no seqcount), unlike ktime_get which would block on read_seqcount_retry 🔨 stress-ng --timer, --hrtimers Precision Time Protocol PTP provides sub-microsecond clock synchronization over a network using hardware timestamping. ⚲ API /sys/class/ptp/ – PTP hardware clock devices ptp4l – PTP boundary/ordinary clock daemon phc2sys – synchronize system clock to PTP hardware clock uapi/linux/ptp_clock.h ⚙️ Internals drivers/ptp – PTP hardware clock drivers 📖 References PTP hardware clock infrastructure for Linux driver-api/ptp.html ktime accessors core-api/timekeeping.html Clock sources, Clock events, sched_clock() and delay timers timers/timekeeping.html Time and timer routines driver-api/basics.html#time-and-timer-routines Year 2038 problem