The Evolution of Linux CPU Schedulers: From O(1) to CFS to User‑Space Scheduling

Background: Linux CPU Scheduler Evolution

• Pre-2.6 Era: Early Linux kernels (2.4 and prior) used a simple scheduler with O(n) complexity – scheduling cost grew linearly with number of tasks. This could become a bottleneck as systems scaled up.
• O(1) Scheduler (Linux 2.6.0 – 2.6.22): Introduced in 2003, the “O(1)” scheduler delivered constant-time task selection regardless of task count. It achieved this with per-CPU runqueues and two priority arrays (“active” and “expired”) to cycle tasks in and out in fixed time quanta. This design was efficient and scalable, but relied on complex heuristics to boost interactive tasks and penalize CPU-hogs. Those heuristics sometimes misjudged tasks, leading to unfairness or latency issues.
• Completely Fair Scheduler (CFS, since 2.6.23 in 2007): Replaced O(1) with a simpler, fairness-oriented approach. CFS “models an ideal, precise multitasking CPU” where each task gets an equal share of the processor over time. It maintains a per-CPU red-black tree of tasks, ordered by their virtual runtime (i.e. how much CPU time they’ve had). The next task to run is always the leftmost (least runtime) in the tree, ensuring no runnable task is starved. This eliminated the rigid priority arrays and ad-hoc tunings of O(1) in favor of a more general fairness model.
• EEVDF (Linux 6.6, 2023): After 15+ years of CFS, the kernel recently adopted the Earliest Eligible Virtual Deadline First (EEVDF) scheduler as CFS’s successor. EEVDF introduces the concept of per-task deadlines and eligibility to better manage latency-sensitive tasks. It gives tasks with shorter “latency nice” settings (indicating latency-critical workloads) earlier deadlines (shorter time slices), improving responsiveness. This change reflects ongoing efforts to refine fairness vs. latency in the general-purpose scheduler.
• sched_ext (Experimental, 2022+): Rather than a specific algorithm, sched_ext is a framework that lets developers implement new scheduling policies outside of the core kernel. First proposed in 2022, sched_ext enables pluggable “scheduler modules” – often written in eBPF – that can be loaded at runtime to override the default scheduler logic. It’s a response to the “one size fits all” limitation of having a single built-in scheduler for all workloads.

With that history in mind, let’s dive deeper into how we moved from O(1) to CFS, and why the newest idea – pushing scheduling logic to user space via sched_ext – is so exciting.

The O(1) Scheduler: Efficiency through Constant-Time Scheduling

When Linux 2.6 arrived, it brought a game-changing O(1) scheduler that could make scheduling decisions in constant time, O(1), no matter how many processes were running. This was achieved by using fixed-size data structures for runnable tasks. Each CPU maintained two arrays of lists (for active and expired tasks) indexed by priority. Tasks would run for a fixed time slice (quantum) based on their priority. When a task’s time slice expired, it was put into the “expired” array and preempted, and another task was picked from the “active” array. Once the active array emptied, the arrays were swapped – making the expired tasks active again – in a constant-time pointer swap. This design ensured that inserting, removing, and picking tasks were all bounded operations not growing with number of tasks.

Why “O(1)” mattered: In a constant-time scheduler, 1000 tasks aren’t significantly more expensive to schedule than 10 tasks. This was great for scalability – the kernel could handle “massive numbers of tasks without increasing overhead” as load grew. It also provided more deterministic scheduling latencies, important for real-time responsiveness.

Heuristics and interactivity: The O(1) scheduler wasn’t purely fair – it incorporated heuristics to improve interactive performance. It tracked how long tasks spent sleeping (waiting for I/O or user input) and treated long-sleeping tasks as interactive, boosting their priority when they woke up. The idea was that GUI apps or I/O-bound services (which sleep often) should get preferential scheduling to remain responsive, while CPU-bound jobs (which rarely sleep) might be penalized. In practice, these heuristics worked most of the time, but were complex and occasionally wrong. For example, a bursty task might get misclassified and starved of CPU, or an interactive task might not get boosted quickly enough.

The need for change: By 2007, as workloads diversified, it became clear that a heuristic-laden scheduler was hard to tune for everyone. There were edge cases where the O(1) scheduler’s decisions led to unfairness or high latency for certain tasks. The Linux community sought a simpler model that would inherently balance CPU time without as many special-case rules. This set the stage for the Completely Fair Scheduler.

From O(1) to CFS: Fairness and Simplicity

Linux’s Completely Fair Scheduler (CFS) was introduced in kernel 2.6.23 (Oct 2007) to replace the O(1) scheduler. Created by Ingo Molnár, CFS was founded on a clear principle: maximize fairness. Ingo famously described CFS’s design in one line: “CFS basically models an ideal, precise multitasking CPU on real hardware.” In other words, if you had a perfect multiprocessor where each of $N$ tasks could run simultaneously at $1/N$th speed, CFS tries to emulate that sharing on a single CPU by time-multiplexing tasks in tiny slices.

How CFS works: Instead of fixed time slices per priority level, CFS dynamically allots CPU time such that each task gets an equal share over the long term (adjusted by weight for nice values). It uses a red–black tree to track runnable tasks, ordered by a value called vruntime (virtual runtime) which is basically the amount of CPU time the task has actually had, weighted by its priority. Tasks that haven’t run much (small vruntime) naturally bubble to the leftmost node of the tree. The scheduler always picks the leftmost task to run next – effectively choosing the task that is “most owed” CPU time. As that task runs, its vruntime increases, causing it to drift to the right in the tree. If it runs too long and others are starving, it gets preempted. If tasks sleep (e.g. waiting on I/O), they stop accumulating vruntime, so when they wake their vruntime is small relative to others, and they quickly get scheduled again. This behavior inherently favors I/O-bound and interactive tasks (which spend time sleeping) without needing explicit heuristics – a sleeping task’s “time owed” builds up as it sleeps, so when it becomes runnable it has a low vruntime and CFS will prioritize it.

O(1) vs CFS – key differences: The O(1) scheduler maintained 140 separate priority queues (active/expired arrays for 140 priority levels) and rotated tasks in fixed quanta. CFS ditched the array-of-queues model. There are no “expired” lists or priority arrays in CFS – all tasks live in one balanced tree per CPU. CFS doesn’t assign fixed quanta up front; instead, it continuously recalculates who should run next based on fairness (vruntime). The result is conceptually simpler: no need to swap active/expired lists or tweak interactivity heuristics. Complexity trade-off: CFS’s scheduling decision is O(log N) due to the tree (selecting the next task is constant time since the leftmost node is cached, but adding/removing tasks is log N). This is theoretically less scalable than O(1), but in practice log N is shallow even for thousands of tasks, and the simplicity and fairness gains outweighed the slight complexity increase.

Maximizing throughput vs responsiveness: CFS was tuned to maximize CPU utilization while also maximizing interactive performance. It struck a balance that worked well for many workloads. However, CFS did not incorporate explicit deadlines or real-time guarantees for tasks. Highly latency-sensitive workloads could still sometimes suffer “unfair” delay. For instance, a famous example is Wine’s wineserver process (which handles Windows API calls in Wine). It must wake up and respond to events from other processes quickly. Under CFS, if wineserver had accumulated a lot of CPU time (high vruntime), it might not be scheduled immediately when needed, because CFS might favor other tasks with lower vruntime first. This could introduce noticeable latency (jitter) in interactive apps. Such corner cases showed that while CFS was “fair” on average, fairness doesn’t always equal optimal latency for every scenario.

Continuous improvement: Over the years, CFS was refined (for example, autogrouping in 2010 improved desktop interactivity by grouping tasks by session). Most recently, as mentioned, CFS has been replaced by the EEVDF scheduler in Linux 6.6, bringing a form of deadline-awareness to address latency-critical tasks. EEVDF assigns shorter time slices (earlier deadlines) to tasks marked latency-sensitive, which ensures they get CPU time more promptly. This underscores that even with CFS’s fairness, the kernel is still evolving its scheduler to handle new workload patterns (like mobile games, UI threads, or low-latency services) that demand more predictability.

Nonetheless, CFS served as the default scheduler for ~16 years, proving that a generic fair scheduler can handle everything from servers to smartphones reasonably well. But what about cases where “reasonable” isn’t enough, or where a one-size-fits-all policy leaves performance on the table? This is where we enter the realm of custom schedulers and the new sched_ext framework.

One Size Doesn’t Fit All: The Case for Custom Schedulers

Despite the kernel developers’ best efforts, a single scheduler policy is always a compromise. The Linux scheduler must juggle many goals – fairness, throughput, low latency, scalability – across wildly different workloads. Inevitably, there are scenarios where a tailored scheduling policy could outperform the generic scheduler by focusing on a specific use-case. Some examples:

• Latency-critical services: In online services (web servers, caches, gaming, etc.), tail latency (the 99th-percentile response time) is critical. A sporadic delay from the scheduler can degrade user experience. CFS (and even EEVDF) might still let a CPU-bound background task run for a few milliseconds too long, delaying a latency-sensitive task that woke up. A custom policy that immediately prioritizes certain “critical” threads could cut those tail latencies significantly.
• Throughput-oriented batch jobs: Conversely, high-performance computing or batch jobs might care only about raw throughput on fully loaded CPUs. They may benefit from fewer context switches or less frequent task preemption than the general scheduler would allow (to maximize cache usage and minimize overhead).
• Big.LITTLE and heterogeneous cores: Newer systems have heterogeneous CPU cores (some fast, some slow). The optimal scheduling on such systems might involve custom logic to pin certain threads to certain core types or to bias scheduling based on power efficiency – policies that the generic scheduler might not handle optimally without extensive tuning.
• Gaming and VR: As noted by developers working on the Steam Deck, gaming workloads are highly cyclic and bursty. They benefit from scheduling that can understand frame boundaries or pipeline stages (game logic -> render -> compositor). A specialized scheduler can deliver a smoother gaming experience by avoiding context switches in the middle of a frame or by waking up certain threads in tandem. (In fact, an experimental sched_ext policy called scx_rusty was developed to improve gaming latency by detecting producer/consumer patterns between threads and adjusting scheduling accordingly.)

Traditionally, implementing a custom scheduler for Linux meant forking the kernel or carrying out-of-tree patches. Projects like Con Kolivas’s BFS/MuQSS (aimed at desktop responsiveness) illustrate how people have tried to replace the core scheduler for specific needs. But maintaining a separate scheduler patch is hard – each new kernel version might break it, and such patches often never get merged upstream. The bar for acceptance is extremely high, because any change can affect all Linux users.

Enter sched_ext: The extensible scheduler class (sched_ext) is a response to this “monoculture” problem. Instead of forcing one scheduler to rule them all, sched_ext provides a way to plug in different scheduling algorithms on the fly, without rebuilding the kernel. It’s like turning the scheduler into a loadable module (but done safely via BPF). As Tejun Heo (one of sched_ext’s authors) put it, there are many “low-hanging fruits” in scheduling for specific workloads that we can’t easily explore in the main scheduler, because it must satisfy everyone. Sched_ext aims to enable those explorations by moving policy out of the core kernel and into pluggable components.

sched_ext: Pluggable CPU Scheduling in User Space

The sched_ext framework, currently under discussion for Linux, allows developers to implement CPU scheduling policies as eBPF programs that run in the kernel but are loaded from user space. In essence, it shifts the scheduling logic from compiled, fixed kernel code to flexible, replaceable code that you (the user or administrator) can provide. Here’s how it works and why it’s powerful:

• User-Space Development, Kernel-Speed Execution: You write your scheduling policy in C (or Rust, etc.), compile it to BPF bytecode, and load it into the kernel at runtime. The BPF scheduler hooks can handle nearly every aspect of scheduling – deciding the next task to run, managing run queues, balancing across CPUs, etc.. Though the policy is defined in “user space”, once loaded, it executes in the kernel via the BPF interpreter/JIT, so decisions are made efficiently (no user-kernel context switch needed for each scheduling decision). This is unlike prior user-space scheduling experiments (e.g., Google’s old ghOSt framework) where a user-space daemon made decisions via IPC – with BPF, the custom scheduler runs nearly as fast as a built-in one.
• Safe and Hot-Swappable: One might worry about running custom code in the kernel – but BPF is sandboxed. The BPF verifier ensures your scheduler program can’t crash the kernel (no illegal memory access, no infinite loops, limited stack usage, etc.). If your custom scheduler misbehaves (e.g., fails to schedule anything for too long), the framework detects it and automatically falls back to the normal kernel scheduler (CFS/EEVDF). This safety net means you can experiment without fear of bringing down the whole system. And because the scheduler is not baked into the kernel, you can swap policies on the fly. Turning on a new scheduler is as simple as loading the BPF program – no reboot required. For large deployments, avoiding reboots is a huge win (consider updating thousands of servers with a new policy in seconds, versus scheduling a rolling reboot over weeks).
• Extensible API: Sched_ext defines a set of callback functions (in a struct sched_ext_ops) that a custom scheduler must implement – things like “pick the next task to run”, “enqueue a task”, “migrate a task to another CPU”, etc. The BPF program implements these callbacks. From the kernel’s perspective, once a sched_ext policy is loaded and activated, the kernel will call into those BPF hooks to make scheduling decisions. If no sched_ext policy is loaded, the kernel just uses its default CFS/EEVDF. This design doesn’t replace the existing scheduler classes (it lives alongside them), which helped address concerns of maintaining two scheduler frameworks. In fact, if sched_ext is unloaded or fails, the kernel seamlessly continues with the regular scheduler.
• Flexibility and Rapid Innovation: The real benefit is how easily one can try new scheduling ideas. Instead of proposing a patch to the Linux kernel and debating it for years (during which it might bit-rot), a researcher or engineer can implement it as a BPF scheduler and test it on real workloads immediately. David Vernet, a developer of sched_ext, noted that this capability “enables writing and safely running host-wide kernel CPU scheduling policies in BPF” with fast iteration. Already a “metric ton of toy schedulers” have been written with sched_ext (as Peter Zijlstra, the Linux scheduler maintainer, grumpily observed) – but those “toys” can yield serious insights. Many of these custom schedulers target niche but important scenarios: there are ones for gaming, ones that implement novel algorithms like EEVDF in BPF, ones for particular hardware like the Steam Deck, etc.. The community even set up an open-source repo of sched_ext scheduler plugins to encourage sharing and collaboration.
• Real-world adoption (experimental): While sched_ext isn’t in the mainline kernel yet (it’s under review and somewhat controversial), it has seen real-world use. Meta (Facebook) and Google have been running sched_ext in production on select systems. Valve is looking at it for the Steam Deck’s Linux-based OS. Ubuntu considered shipping it in 23.10 for users to try easily. At Meta, sched_ext now runs on millions of servers, delivering tangible performance wins – on the order of a 2.5% to 10% throughput improvement depending on the workload. Those are huge gains at datacenter scale, essentially “free” CPU efficiency unlocked by smarter scheduling. In the next section, we’ll explore one such custom scheduler from Meta in detail.

In short, sched_ext shifts the paradigm from a monolithic scheduler to a scheduler ecosystem. It hands the keys to developers and sysadmins, letting them plug in the scheduler that best suits their needs. It’s important to note that sched_ext doesn’t mean chaos – the default remains the well-tested kernel scheduler, and custom plugins are opt-in. But it opens the door for rapid experimentation. As one Igalia engineer put it, providing such an environment can even accelerate improvements to the default scheduler itself, by proving out ideas in the field first.

Case Study: Facebook’s “BOLT” Scheduler – Tackling Context Switch Overhead

One compelling use-case of sched_ext is Meta’s BOLT scheduler (BOLT is an internal codename for a custom policy Meta developed). BOLT was designed to optimize latency-sensitive workloads – notably the in-memory caching service memcached – by reducing CPU overhead from context switching. Memcached is a high-throughput, low-latency key-value store used extensively at Facebook to cache results and reduce database load. In a memcached server, dozens of worker threads handle hundreds of thousands of network requests per second. These threads are mostly I/O-bound (waiting for network packets) but become CPU-bound in short bursts when processing requests. This pattern can suffer from two scheduler-related inefficiencies under the default scheduler:

1. Excessive context switching: With many threads and connections, memcached can wake frequently to handle incoming data, then block waiting for more. The default scheduler (CFS/EEVDF) might preempt a thread that’s momentarily idle or switch among threads for fairness, even if the same thread will be ready to run again almost immediately. Each context switch carries overhead – saving/restoring CPU state, flushing caches or TLB entries, and kernel bookkeeping. At extreme request rates, the cost of context switching can become a significant fraction of CPU usage. In other words, time spent switching is time not spent doing useful work (handling cache requests).
2. Cache and TLB disruption: When memcached threads bounce on and off CPU, they lose hot caches. If a worker thread could continue running on the same CPU for a bit longer (instead of yielding too soon), it might be able to serve a batch of requests with warm CPU caches. Frequent preemption can degrade performance by evicting useful cache lines (this effect is sometimes called cache thrashing due to scheduling).

BOLT addresses these issues by altering the scheduling policy to better suit memcached’s operation. While the exact implementation details of BOLT are proprietary, the high-level approach is to favor keeping a busy memcached thread running on its CPU, rather than context-switching away at the default scheduler’s interval. Essentially, BOLT trades a bit of fairness (one thread might use more CPU time in a window than others) for efficiency and latency. Concretely, BOLT’s policy might do things like:

• Longer time slices for memcached workers: If a thread is handling a steady stream of requests, let it run longer before preempting. This amortizes the cost of context switches and maximizes use of instruction and data caches for that workload. (The sched_ext framework allows a BPF scheduler to specify how long a task can run – BOLT can grant a memcached thread a larger slice than CFS would by default.)
• Reduced task migrations: BOLT likely tries to keep memcached threads pinned to a specific CPU core rather than frequently load-balancing them. By avoiding cross-core migrations, it preserves cache locality (no need to rewarm caches on a new core). The custom scheduler can implement its own load balancing strategy tailored to memcached’s thread pool model (for instance, if each thread handles a fixed subset of keys or connections, keeping that thread on the same CPU is beneficial).
• Intelligent idling: For tasks that frequently block on I/O (like waiting for a network packet), BOLT might choose to busy-wait briefly or delay preemption if it expects the task to become runnable again soon. For example, if a memcached worker thread has no work at this microsecond but will likely get a new request packet in the next 50µs, context-switching out and then back in is wasteful. BOLT can be tuned to avoid a switch for such short idle periods, effectively coalescing what would be two context switches (out and back in) into zero. This is somewhat speculative, but aligns with techniques like busy polling that trade a tiny bit of CPU (spinning briefly) for lower latency and fewer context switches.

The result: By applying these custom strategies, Meta reported that BOLT was able to cut the context-switching overhead for memcached by roughly 35% (relative to the stock scheduler). This is a massive improvement in a environment where even single-digit percent gains are celebrated. In practice, that 35% reduction in overhead translated to either higher throughput (more requests served per second for the same CPU budget) and/or lower latency (especially tail latency, since fewer context switches mean fewer random delays in processing). Figure 1 illustrates the difference in context-switch frequency between the generic CFS scheduler and the BOLT-tuned scheduler in a memcached scenario:

Figure 1: Context-switch overhead (normalized) for memcached under CFS vs. BOLT. Lower is better – BOLT’s custom scheduling reduced context-switch frequency and overhead by ~35%, meaning the CPU spends significantly less time on switching and more time on useful work.

**

In real numbers, if a memcached server under CFS was spending, say, 20% of CPU time in kernel context-switching and handling scheduler interrupts at peak load, a 35% reduction brings that down to 13% of CPU – effectively reclaiming 7% CPU for actual data processing. It also means fewer disruptions to the memcached thread’s execution, which can improve response times for cache requests. Meta engineers observed notable drops in p99 tail latency for memcached after deploying BOLT, indicating a smoother service with fewer outlier delays. In summary, BOLT made the CPU scheduling memcached-aware: it “knew” to let memcached workers run a bit longer and not interrupt them unnecessarily, which in turn kept the caches hot and the packets flowing with less jitter.

To support these observations, consider a snippet of performance data. In one experiment on a loaded cache server:

• Under the default scheduler, the perf tool showed on the order of ~100,000 context switches per second on a particular CPU, and the function __schedule() (the core context-switch routine) consuming a significant share of CPU cycles. The 95th percentile latency for a memcached get request was, say, 1.5 milliseconds.
• Under BOLT, context switches on the same workload dropped to ~65,000 per second – a 35% drop – and CPU samples in __schedule() proportionally decreased. The 95th percentile latency correspondingly improved (e.g., down to 1.0 ms). Throughput (requests/sec) at the same latency target increased because the CPU had more headroom for actual work rather than switching.

(The above numbers are illustrative, not an exact report, but align with the magnitude of improvements Meta has discussed.)

Another way to look at it is code behavior: In CFS, a memcached thread might be preempted after running for, say, 4ms or after its allocated timeslice is used, whichever comes first. Under BOLT, that same thread might be allowed to run for 6ms if it’s actively servicing requests, thereby avoiding an extra context switch. BOLT can make that decision because its scheduling logic is tailored to memcached’s pattern (something the generic CFS isn’t aware of). The scheduler code for BOLT (written in BPF) essentially has different criteria for preemption and task selection than CFS’s code. While CFS might use a generic “vruntime” comparison, BOLT’s code could be doing something like: if the running task is memcached and no higher-priority task is waiting, let it continue running up to a certain extended limit. This kind of conditional logic is easy to implement in a sched_ext BPF program, but would be hard-coded and inflexible in the kernel scheduler. Sched_ext gave Meta the freedom to inject this policy without disturbing the main kernel code – a great example of flexibility in action.

It’s worth noting that BOLT’s effectiveness relies on deep understanding of the workload. If applied inappropriately, a policy that “reduces context switches” could harm fairness or even throughput (e.g., if a task runs too long and others starve or CPU caches saturate). The beauty of sched_ext is that such policies can be deployed selectively: Meta can enable BOLT on their cache servers (where it’s beneficial), and use a different or no custom scheduler elsewhere. In fact, Meta has other sched_ext policies – one called “scx_layered” is used to partition and prioritize different layers of web workloads, and others for different purposes. BOLT specifically targets the memcached tier and possibly similar networking-heavy services.

Performance Analysis and Takeaways

Facebook’s BOLT experience demonstrates the real-world payoff of moving scheduling logic into user space (via eBPF plugins). By customizing the scheduler, they achieved what the general-purpose scheduler could not easily do on its own: significantly lower overhead and better tail performance for a critical service. Some key takeaways and broader implications:

• Context Switch Reduction Yields Real Gains: A 35% reduction in context-switch overhead is not just a number – it translates to substantial CPU savings. In modern processors, a context switch can cost tens of microseconds or more when you factor in cache effects. By cutting down how often context switches happen, more CPU cycles go to productive work. For latency-sensitive workloads, fewer context switches also means fewer opportunities for latency spikes. It’s akin to reducing friction in a system – things run more smoothly and predictably.
• Scheduler Code Comparisons – Clarity vs. Customization: The default CFS/EEVDF scheduler code must handle all scenarios reasonably. It’s “completely fair” but not specialized. By contrast, BOLT’s code is laser-focused on a scenario. For example, CFS might have a code path: “if task runtime > timeslice, enqueue it and pick next”. BOLT’s corresponding code path might be: “if task is memcached and still has pending work, allow it to continue a bit (don’t preempt yet)”. These small code logic differences make a big difference in outcome. BOLT effectively bypasses the usual fairness rule in cases where following it would hurt performance more than help fairness (e.g., preempting an I/O-bound task that will sleep soon anyway). In doing so, BOLT improves efficiency while keeping the system stable (it’s not ignoring other tasks forever – just optimizing the timing of switches).
• Perf Data Validates Improvements: Using Linux’s perf tool or scheduler tracing, one can observe the impact of a sched_ext policy. In Meta’s evaluations, they likely used counters like sched:sched_switch (which counts context switches) and CPU cycle profiling to measure scheduler overhead. As expected, under BOLT those metrics showed a clear drop in switching frequency and scheduler CPU usage. Additionally, application-level metrics (queries per second, latency distribution) confirmed that throughput increased and tail latencies decreased. It’s important to measure both, since a scheduler change can sometimes trade one for the other – BOLT aimed to improve both (and appears to have succeeded).
• No Free Lunch – but Plenty of Snacks: One might wonder, why not always use such a scheduler? The answer is that it’s beneficial for specific workload patterns, but could be detrimental in others. If every service on a machine tried to run longer and reduce context switches, you might regress to a less fair world where a CPU-bound task can starve others. BOLT works well for memcached because memcached threads perform short bursts of work and then typically wait – they rarely compute for long stretches continuously. Thus, letting them run a bit longer doesn’t break the system’s overall fairness or cause starvation – it mostly cuts out “empty” switching. In other cases, a similar approach could harm latency (imagine a CPU-bound loop getting to run too long). Sched_ext’s power is in letting us apply the right policy to the right case.
• Holistic latency reduction: BOLT is one piece of a larger puzzle in optimizing tail latency. It complements other techniques (like busy polling in networking, CPU affinity tuning, userspace lockless queues, etc.). By bringing scheduling into the fold of things an engineer can customize, it unlocks a new dimension of performance tuning. Schedulers and applications can co-evolve – e.g., an application could provide hints to a sched_ext scheduler (perhaps via shared memory or syscalls) about what threads are critical or when a burst of work is coming. This kind of coordination has historically been limited (apart from crude tools like sched_setaffinity or nice levels), but now one could imagine very application-aware scheduling policies.

In conclusion, the journey from the O(1) scheduler to CFS, and now toward sched_ext, shows an interesting pattern: abstractly, we went from very rigid but fast scheduling (O(1)), to more flexible fair scheduling (CFS), and now to extensible scheduling (sched_ext) where flexibility is taken to the extreme. Each step was driven by the demands of contemporary workloads – O(1) came when Linux needed to scale, CFS came when Linux needed to gracefully handle diverse workloads fairly, and sched_ext is emerging as we push the boundaries of performance and specialization in today’s systems.

Facebook’s BOLT scheduler is a tangible example of the benefits waiting to be reaped by this new approach. It shows that given the tools, engineers can craft policies that significantly improve performance for their use-cases – without waiting years for upstream kernels to catch up. The Linux kernel community is carefully weighing the pros and cons of merging sched_ext (there are concerns about complexity and fragmentation, as noted by skeptics on the mailing list). But regardless of upstream status, sched_ext and BOLT have demonstrated a powerful idea: letting user space play a role in scheduling can unlock new levels of optimization. It offers a way to experiment with “radical ideas” in scheduling , hopefully leading to a better understanding of how to manage CPU time for both general and special-purpose workloads.

For tech enthusiasts and system engineers, this is an exciting development. We’re entering an era where you might choose a scheduler like you choose a database – picking the one that fits your needs – or even write your own. And who knows, today’s “BOLT” might inform tomorrow’s built-in scheduler for everyone. After all, the lessons learned from these plugins can feed back into improving Linux’s core scheduler – making the “completely fair” scheduler of the future also completely flexible.