Your computer is running dozens of programs right now. A browser, a terminal, a music player, background daemons, system services. If you open a task manager and count, the number of processes is usually somewhere between a hundred and several hundred on a typical desktop system. On a server it can be in the thousands.
Your CPU has a fixed number of cores. A modern consumer machine might have eight or sixteen. A server might have sixty-four or one hundred twenty-eight. The number of processes almost always exceeds the number of cores, often by a factor of ten or more.
Something has to decide which processes run on which cores and for how long. That something is the scheduler, and it is one of the most consequential pieces of software running on your machine. Every response time you experience, every latency spike, every moment where your music skips while something else is happening, every time a background task quietly finishes without you noticing: all of it reflects decisions the scheduler made, thousands of times per second, invisibly.
This is an attempt to explain how those decisions actually get made.
What scheduling is solving
The fundamental problem is simple to state. You have N processes and M cores, where N is much larger than M. At any given moment, you have to pick which M processes are running and which are waiting. You also have to decide when to switch, because switching too rarely makes interactive programs feel sluggish, and switching too often wastes CPU time on the overhead of switching itself.
The tricky part is that different processes have wildly different needs.
A video player needs to decode and render frames on a predictable schedule. Missing a deadline means a dropped frame. The work it needs to do is not huge, but it needs to happen at regular intervals without fail.
A database running a complex query needs sustained CPU time. Interrupting it frequently to let other things run just means the query takes longer. It does not care about latency in the way an interactive program does.
A text editor sitting idle needs almost no CPU at all. When you press a key it needs to respond immediately, but between keystrokes it should consume nothing.
A background compression job needs CPU when nothing else does. It should get out of the way when something more urgent needs the core.
No single scheduling policy handles all of these well simultaneously. Real schedulers are multi-part systems that make different decisions for different classes of workloads and try to keep everyone reasonably satisfied.
The basics: time slices and context switches
The core mechanism of a preemptive scheduler is the time slice, sometimes called a quantum. The scheduler assigns each process a time slice, a maximum amount of CPU time it gets before being preempted and replaced with another process.
When a time slice expires, the hardware timer fires an interrupt. The CPU stops executing the current process, saves its state (registers, program counter, stack pointer, everything needed to resume it later), and transfers control to the kernel's scheduler code. The scheduler picks the next process to run, restores that process's state, and resumes execution. From the process's perspective, nothing happened. It just ran for a while, then ran some more later. The gap in the middle is invisible to it.
This save-and-restore operation is a context switch. Context switches are not free. Saving and restoring registers takes a small number of cycles. More significantly, switching processes means the new process's data is likely not in cache. The CPU caches that were warm for the previous process are now filled with data that is useless for the new one. The new process will incur cache misses until its working set loads into cache. On a modern processor where cache misses can cost hundreds of cycles, this cache warming cost can be substantial.
This is why time slices are not arbitrarily short. If you set a 1 microsecond time slice on a 3 GHz processor, you get 3000 cycles of useful work followed by a context switch that might cost 10,000 cycles in cache misses alone. The overhead dwarfs the useful work. Real schedulers use time slices in the range of a few milliseconds to tens of milliseconds, balancing responsiveness against overhead.
The time slice length is also not universal. Different processes and different situations call for different slice lengths. Interactive processes often get shorter slices so they can respond quickly to input and then yield. CPU-bound background processes often get longer slices to minimize context switch overhead and let them make sustained progress.
Preemptive versus cooperative scheduling
There are two broad approaches to scheduling: cooperative and preemptive.
In a cooperative scheduler, processes voluntarily yield the CPU when they are done with their current work or when they choose to wait for something. The scheduler only gets control when a process explicitly gives it up. Early versions of Windows and the classic Mac OS used cooperative scheduling. The obvious problem is that a misbehaving or buggy process that never yields can freeze the entire system, because the scheduler never gets a chance to run anything else.
In a preemptive scheduler, the operating system can forcibly take the CPU away from a running process at any time, using a hardware timer interrupt. The process does not get a vote. This is what all modern general-purpose operating systems use. It means that no single process can monopolize a CPU core indefinitely, and the operating system remains in control of resource allocation regardless of what individual processes do.
Preemption requires hardware support: a timer that generates interrupts at configurable intervals, and a mechanism for those interrupts to transfer control to privileged kernel code even when user code is running. Both of these have been standard in hardware since the 1970s. The concept of preemptive multitasking is not new, but the sophistication of the policies built on top of it has grown enormously.
Priority: not all processes are equal
The simplest form of scheduling policy is round-robin: give each process a time slice, then move to the next, cycling through all processes continuously. Round-robin is fair in the sense that every process gets equal time, but fairness is not always what you want. A background indexing job should not consume the same share of CPU as the video call you are actively participating in.
Priority changes this. Each process has a priority value, and higher-priority processes get scheduled preferentially over lower-priority ones. In the simplest version, the scheduler always runs the highest-priority runnable process. A lower-priority process only runs if no higher-priority process wants the CPU.
Pure strict priority scheduling has a problem called starvation. If there are always high-priority processes that want to run, low-priority processes never get CPU time. They starve. A background task assigned a low priority on a heavily loaded system might not run for hours or at all.
The fix is aging: a process that has been waiting for a long time gets its effective priority gradually increased, until it eventually gets scheduled. Once it runs, its priority returns to its base level. This prevents starvation without abandoning the concept of priority entirely.
On Linux, user processes have priorities called nice values, ranging from negative 20 (highest priority) to positive 19 (lowest priority). The name comes from the idea that a process with a high nice value is being nice to other processes by voluntarily accepting less CPU time. Normal processes run at nice value 0. You can start a process with a specific nice value using the nice command, or change a running process's nice value with renice. The kernel translates nice values into internal scheduling weights.
The difference between I/O-bound and CPU-bound processes
Understanding how schedulers actually behave requires understanding the distinction between I/O-bound and CPU-bound processes.
A CPU-bound process is one that mostly wants to compute. It rarely waits for anything external. Given CPU time, it uses all of it. Compiling code, running numerical simulations, transcoding video: these are CPU-bound workloads.
An I/O-bound process is one that spends most of its time waiting for input or output. A web server waiting for network requests, a text editor waiting for keystrokes, a database process waiting for disk reads. These processes are runnable only intermittently. Most of the time they are blocked, waiting for something to happen.
This distinction matters enormously for scheduling. A CPU-bound process, if given a long time slice, will use all of it productively. An I/O-bound process, if given a long time slice, will use a tiny fraction of it and then block while waiting for I/O. When the I/O completes and the process becomes runnable again, you want it to run quickly, because the user or the network or whatever was waiting for its response is waiting.
Good schedulers detect this distinction and use it. A process that consistently uses its entire time slice before blocking is probably CPU-bound. A process that consistently blocks well before its time slice expires is probably I/O-bound. I/O-bound processes are rewarded with higher scheduling priority or faster scheduling after their I/O completes, because getting them back on the CPU quickly is what makes interactive programs feel responsive.
Linux's scheduler tracks how long each process has been waiting versus how long it has been running, and uses this to adjust scheduling decisions. A process that has been sleeping (waiting for I/O) for a long time gets scheduled quickly after it wakes up, because the assumption is that it needs to respond to something and every millisecond of additional waiting is latency that the user or the system will notice.
The runqueue and how the scheduler picks what runs next
Internally, the scheduler maintains data structures that track the state of every process. The key categories are:
Running: the process is currently executing on a CPU core.
Runnable: the process has work to do and is ready to run, but is waiting for a CPU core to become available.
Sleeping: the process is waiting for something, typically I/O, a timer, or a synchronization event. It is not consuming CPU and should not be scheduled until whatever it is waiting for happens.
Zombie: the process has exited but its exit status has not yet been collected by its parent. It exists only as a record.
The scheduler only concerns itself with runnable processes. Its job is to pick from the runnable pool and decide who runs on each core.
The data structure holding runnable processes is the runqueue. Naive implementations use a single sorted list of processes ordered by priority. The scheduler picks the head of the list each time. The problem is that inserting into and removing from a sorted list takes time proportional to the list length, and when the runqueue has thousands of entries, this overhead adds up across thousands of scheduling decisions per second.
Real schedulers use more efficient data structures. Linux's Completely Fair Scheduler uses a red-black tree, a self-balancing binary search tree that supports insertion, deletion, and minimum lookup all in O(log n) time. With thousands of processes, this is the difference between acceptable overhead and a scheduler that itself becomes a bottleneck.
The Completely Fair Scheduler
Linux's main scheduler for normal processes is called the Completely Fair Scheduler, or CFS. It was introduced in 2007 and replaced a previous O(1) scheduler that, despite its efficiency, had problems with fairness and interactivity.
The central concept in CFS is virtual runtime. Each process has a virtual runtime counter that tracks how much CPU time it has consumed, adjusted for its weight (which reflects its nice value). Higher-weight processes accumulate virtual runtime more slowly for the same amount of real CPU time, which means they stay near the front of the scheduling queue and get scheduled more often. Lower-weight processes accumulate virtual runtime faster and drop to the back of the queue more quickly.
The scheduler always picks the process with the lowest virtual runtime to run next. In theory, if all processes had equal weight and ran continuously, their virtual runtimes would converge: every process would get exactly equal CPU time, and the system would be perfectly fair. In practice, processes sleep and wake, have different weights, and vary in how much CPU they actually use, so the virtual runtime values diverge and reconverge continuously as the scheduler responds to what each process actually does.
When a process wakes up from sleep, CFS does not bring it back with the same virtual runtime it had when it slept. If it did, a process that slept for a long time would have a virtual runtime far below everything else and would immediately monopolize the CPU, trying to catch up on all the time it missed. Instead, CFS sets the waking process's virtual runtime to something close to the minimum virtual runtime currently in the runqueue. This gives it a scheduling boost (it will be picked to run soon) without letting it steal disproportionate time.
The time slice in CFS is not a fixed value. It is derived from the number of runnable processes and the target latency: the maximum time within which every runnable process should get at least one turn. If the target latency is 6 milliseconds and there are 3 runnable processes, each gets a 2 millisecond slice. If there are 60 runnable processes, each gets a 100 microsecond slice, which is very short and would cause excessive context switch overhead. CFS introduces a minimum granularity (typically 0.75 milliseconds) to prevent slices from becoming too small, accepting that as the number of processes grows, the latency guarantee degrades gracefully rather than catastrophically.
CFS handles the I/O-bound versus CPU-bound distinction through the wakeup mechanism. When an I/O-bound process wakes up, it has a low virtual runtime relative to the current minimum (because it has not been consuming CPU). It gets scheduled promptly. When it runs, it does a small amount of work and blocks again before its time slice expires. Its virtual runtime barely increases. The next time it wakes up, it is still near the front of the queue. The net result is that I/O-bound processes naturally get low latency without the scheduler needing to explicitly classify them.
Real-time scheduling
CFS handles normal processes. But some workloads need stronger guarantees than "you will run within the next few milliseconds on a loaded system." Audio processing, kernel drivers, industrial control systems, anything with hard timing requirements needs a different approach.
Linux provides real-time scheduling policies for this: SCHED_FIFO and SCHED_RR.
SCHED_FIFO is a first-in, first-out policy for real-time processes. A SCHED_FIFO process runs until it voluntarily yields, blocks, or is preempted by a higher-priority real-time process. There is no time slice. If it does not yield, it keeps running. This means a SCHED_FIFO process set to the highest real-time priority can, if it runs continuously and never blocks, prevent all other processes on that CPU from running at all. This is by design: real-time processes are supposed to be trusted to behave well and not abuse this power.
SCHED_RR adds a time slice to SCHED_FIFO. Real-time processes of the same priority take turns, each getting a fixed slice before yielding to the next. Processes at higher priority still preempt processes at lower priority immediately.
Real-time processes in Linux have priorities in the range 1 to 99, entirely separate from and above the nice value system used for normal processes. A process at any real-time priority level will always preempt a normal CFS process, regardless of that normal process's nice value. You need root (or the CAP_SYS_NICE capability) to set a process to a real-time scheduling policy, because a misconfigured real-time process can lock up a system.
The kernel also provides a real-time throttling mechanism: a configurable fraction of CPU time (95 percent by default) is reserved for real-time processes, with the remaining 5 percent reserved for normal processes. This prevents a runaway real-time process from making the system completely unresponsive, though it reduces the latency guarantees you can make for real-time workloads.
Multicore scheduling and the cache affinity problem
Everything so far has discussed scheduling as if there is one CPU. Real systems have multiple cores, and this introduces a new set of problems.
The obvious approach is to maintain one global runqueue and have each core pull from it whenever it needs work. This works but creates contention: every scheduling decision on every core requires acquiring a lock on the shared runqueue. On a system with many cores all scheduling frequently, this lock becomes a bottleneck.
The more common approach is per-core runqueues. Each core has its own runqueue and schedules from it independently. This eliminates the global lock. The problem is load imbalance: one core might have ten runnable processes while another sits idle.
Load balancing fixes this. At regular intervals, and when a core becomes idle, the scheduler looks across all runqueues and migrates processes from overloaded cores to underloaded ones. This balances work across the system but introduces its own cost: migrating a process from one core to another means that process's cache data, which was warm on the original core, is now cold on the new core. The process will incur cache misses until it warms up the new core's caches.
This is the cache affinity problem. All else being equal, it is better to keep a process on the same core it has been running on, because its data is more likely to still be in that core's caches. The scheduler tries to respect this. When it balances load, it prefers to move processes that have been sleeping (their caches are cold anyway) rather than processes that have been actively running. It migrates work only when the imbalance is significant enough to justify the cache disruption cost.
Modern processors also have non-uniform memory access (NUMA) architectures, where cores are grouped into nodes, and each node has its own local memory that is faster to access than memory attached to other nodes. A process running on a core in node 0, accessing memory that was allocated on node 1, pays a latency penalty on every memory access compared to accessing node 0's memory. Linux's scheduler is NUMA-aware and tries to keep processes on the same node as their memory, balancing load within a node before resorting to cross-node migration.
The scheduler and system calls
Scheduling is not just about the periodic timer interrupt. Processes frequently put themselves to sleep voluntarily, and the scheduler has to handle this correctly.
When a process calls read on a file and the data is not in cache, the process has to wait for the disk. It calls into the kernel, which starts the I/O operation and then calls the scheduler to pick something else to run. The calling process is moved from runnable to sleeping. When the I/O completes, a hardware interrupt fires, the interrupt handler marks the sleeping process as runnable again (placing it back on the runqueue), and the scheduler will pick it up the next time it makes a scheduling decision.
The same sequence happens for network I/O, for waiting on locks held by other processes, for sleeping via the sleep system call, for waiting on a child process to exit, and for dozens of other blocking operations. In every case, the process voluntarily gives up the CPU by making a system call that blocks, and the scheduler fills that core with something else while it waits.
This voluntary yielding is what makes I/O-bound processes efficient users of the system. A process that is waiting for the network is not consuming CPU. The core is free for something else. A CPU-bound process that never blocks never voluntarily yields, so it only gives up the CPU when the timer fires and the scheduler preempts it.
Scheduler latency and what it means for applications
Scheduler latency is the time between a process becoming runnable and the time it actually starts running. For interactive applications, this directly translates to responsiveness. If you press a key and the text editor is runnable but the scheduler does not get to it for 50 milliseconds, you will notice.
CFS's target latency tries to bound this. With a 6 millisecond target and a moderate number of processes, every runnable process should get a turn within 6 milliseconds. In practice, system load, real-time processes, and other factors can push this higher.
For applications that care about latency, there are tunable kernel parameters. The sched_latency_ns and sched_min_granularity_ns parameters control CFS's target latency and minimum granularity. Reducing them makes CFS switch more frequently, reducing latency at the cost of more context switch overhead. Increasing them reduces overhead at the cost of higher latency.
The kernel also provides scheduling hints through control groups (cgroups), which allow you to assign processes to groups and control the share of CPU time each group gets. A group of high-priority processes can be given 80 percent of CPU time, with everything else sharing the remaining 20 percent. This is how container runtimes like Docker implement CPU limits: they put each container's processes in a cgroup and set a CPU quota.
Priority inversion and how it is handled
Priority inversion is a scheduling problem that emerges when priorities and locks interact in unexpected ways.
Imagine a low-priority process L holds a mutex. A high-priority process H tries to acquire the same mutex and blocks, because L has it. Now a medium-priority process M becomes runnable. The scheduler runs M instead of L, because M has higher priority than L, and H is blocked so it cannot run anyway. L never gets scheduled to finish its work and release the mutex, because M keeps the CPU. H, the highest-priority process, is stuck waiting for L, which is stuck waiting for M to stop running.
The high-priority process has effectively been degraded below the medium-priority process, which is backwards. This is priority inversion.
The canonical solution is priority inheritance. When H blocks waiting for a mutex held by L, L temporarily inherits H's priority. L is now treated as a high-priority process and gets scheduled ahead of M. L finishes, releases the mutex, its priority returns to its original value, and H can run. The inversion is avoided.
Priority inheritance adds complexity to the locking subsystem and has its own edge cases (priority inheritance with multiple locks can create chains that are expensive to maintain), but it is widely implemented because priority inversion can cause severe problems. The Mars Pathfinder mission in 1997 experienced a real-time system reset caused by priority inversion in its onboard software, which contributed to interest in understanding and solving the problem in embedded and real-time systems.
The idle task and what happens when nothing needs to run
Every core always has something to run, even if that something is doing nothing. The scheduler has a special idle task for each core that runs whenever no other process is runnable on that core.
The idle task is not a normal process. It is a kernel thread that runs at the lowest possible priority and executes a loop that repeatedly asks the hardware to enter a low-power state. On modern processors, this is done with instructions like HLT on x86, which halt the core until the next interrupt arrives. The interrupt wakes the core, the interrupt handler runs, and if something became runnable (I/O completed, a timer fired, a process was migrated from another core), the scheduler picks it up. If nothing became runnable, the core returns to the idle loop.
This is how modern CPUs achieve power efficiency under low load. Cores that have nothing to do are in a low-power sleep state most of the time, waking only when work arrives or when maintenance tasks run. Power management goes further than this (cores can reduce their clock frequency, reduce voltage, and enter progressively deeper sleep states), and the scheduler interacts with the power management system to make these decisions well: a core that the scheduler knows will be needed again soon should not enter a deep sleep state that takes a long time to exit.
What all of this means from the outside
You do not normally need to think about the scheduler. It makes its decisions quietly and the results are usually good enough. But knowing how it works changes how you interpret certain things.
When your system feels sluggish despite low CPU usage, the problem is often scheduling latency. Some process that matters to you is runnable but not getting scheduled quickly. This can happen when a high-priority real-time process is holding the CPU, when the target latency is too high for the number of runnable processes, or when a NUMA migration has degraded a process's memory access patterns.
When a program that should be fast is not, and profiling shows that it is spending time sleeping rather than computing, the issue might be that it is making many small I/O calls, each of which puts it to sleep and pays the wakeup latency. Batching those calls into fewer, larger ones reduces the number of times the process goes through the sleep and wake cycle.
When CPU usage on a multicore system is not evenly distributed, load balancing is not working as well as it could. This can happen when processes have strong cache affinity and the scheduler is reluctant to migrate them, or when the workload is not easily parallelizable and one core ends up with all the work.
When a low-priority background task seems to be taking CPU away from a more important foreground process, the nice value system lets you explicitly tell the scheduler to deprioritize it. Running a compilation job at nice value 19 means it will only get CPU when nothing else wants it, without requiring you to carefully manage when it runs.
The scheduler is not magic. It is a set of algorithms making decisions based on limited information about what each process needs and what the system should optimize for. Those decisions are usually correct. When they are not, knowing what the scheduler is actually doing is what lets you diagnose and fix the problem rather than blaming the computer for being slow.
The gap between simple and real
Textbook descriptions of scheduling make it sound straightforward. Runqueue, time slice, context switch, repeat. The reality is considerably more involved. Cache affinity, NUMA topology, real-time guarantees, priority inversion, power management, cgroup quotas, load balancing across heterogeneous core types (which matters on processors with efficiency cores and performance cores, like ARM big.LITTLE and Intel's hybrid architecture): all of this has to be handled correctly and efficiently, in software that runs thousands of times per second on every machine in the world.
Linux's scheduler is several thousand lines of code and has been actively developed for decades. It has gone through multiple complete rewrites as hardware has changed and as understanding of the tradeoffs has improved. The version running today reflects lessons learned from systems that failed in production, benchmarks that exposed unexpected regressions, and careful study of where the previous approaches were wrong.
The scheduler that decides when your program runs is one of the most carefully engineered pieces of software in existence, and it does its job so well that most programmers never have to think about it. That invisibility is the point. The goal is not to be noticed. The goal is to keep everything running smoothly, allocating a finite resource fairly and efficiently, without any of the thousands of processes running on your machine ever knowing how much work went into the decision.
Top comments (0)