I've recently started a somewhat ambitious hobby project: re-implementing the Linux fair/EEVDF scheduler 100% in BPF using sched_ext. The main goal isn't to replace the scheduler. It's to make the existing scheduler easier to experiment with, understand it and better document how it works.

The source code of the first prototype (scx_eevdf) is available here: https://github.com/sched-ext/scx/tree/main/scheds/rust/scx_eevdf

Why?

Suppose you have an idea for a small change to CPU scheduling policy: perhaps a different wakeup heuristic, a different way of selecting the next task, or a new load-balancing rule. Today, there are essentially two ways to experiment with it.

The first is to modify the kernel scheduler itself, rebuild the kernel, reboot, and repeat for every iteration. The second is to write a sched_ext scheduler from scratch. That's much faster to build and test, but you first have to reimplement everything that isn't part of your idea. Both approaches are expensive enough that many potentially interesting ideas never get tested.

What we're missing is a third option: a way to experiment with small changes to the default scheduler through sched_ext, without having to reimplement everything from scratch, while retaining the fast edit-build-test cycle that sched_ext provides.

That's the idea behind scx_eevdf. Instead of starting with a blank scheduler, start with something that looks as much as possible like the scheduler already running in the kernel. Then experiment with the parts that actually matter. If an idea turns out to be useful, it can eventually make its way back into the upstream scheduler.

How it was built

The port was built with the help of LLMs, using an incremental approach: the upstream scheduler (kernel/sched/fair.c) was decomposed into small self-contained building blocks and ported one block at a time. For each block, I asked the agent to translate the implementation to BPF. Then I manually:

1. reviewed the generated code against the kernel source;
2. tested it with focused benchmarks;
3. used tracing to validate the expected behavior;
4. accepted, rejected, or modified the result before moving on to the next block.

Then I repeated the process, block by block. In other words, the models did most of the mechanical translation; I did the decomposition, review, validation, and accept/reject decisions. This turned out to be a really effective way of tackling a port of this size.

What's in it?

At the time of writing, a very rough estimate of around 80% of the fair/EEVDF logic is implemented in scx_eevf. It currently includes:

• EEVDF core: virtual deadlines, the per-runqueue reference V, lag across sleeps, reweighting, delayed dequeue, relative deadlines, and runtime accounting
• Eligible-task selection: backed by per-CPU eligible deadline queues (EDQ)
• Preemption: PREEMPT_SHORT short-request preemption and slice enforcement from the tick
• Wakeup placement: wake_affine(), idle search with the SIS_UTIL budget, and SCHED_IDLE-aware targets
• Load balancing: periodic and new-idle balancing, capacity-normalized averaged load, sd->imbalance_pct, one elected balancer per group, capacity-pressure estimation, and misfit handling
• Utilization tracking: PELT-equivalent utilization (ravg), including feeding utilization information to the cpufreq governor
• cgroups: cgroup scheduling with cpu.weight and cpu.max bandwidth control
• Asymmetric CPUs: capacity awareness and packing for hybrid CPUs

What's missing?

Two major pieces are currently absent:

• NUMA balancing. There is no page-fault sampling, preferred-node tracking, or task grouping. Placement is topology-aware, but blind to where a task's memory actually lives.
• EAS. There is no energy model or equivalent of find_energy_efficient_cpu(). CPU selection currently relies on capacity and idleness.

There are also a few pieces that cannot currently be implemented because the required interfaces do not exist in sched_ext yet. I'll come back to those later.

Does it actually behave like EEVDF?

I compared scx_eevdf against the kernel's own fair/EEVDF scheduler on the same machine:

• Intel Core i7-13800H
• 20 logical CPUs: 12 P-core threads + 8 E-cores
• one NUMA node
• one LLC
• Linux 7.2

The results below are medians from five runs. The arm order was rotated on every iteration so thermal drift could not consistently favor one scheduler. Every sample waited for a quiet pre-window and recorded system-wide busy ticks during its measured window. This also makes it possible to identify noisy samples afterwards rather than silently averaging them away.

For each number, the +- value is the half-range across the five samples. For example, 95 +-27% means that the five samples spanned 54% of the median.

The final column indicates whether scx_eevdf was better (^), worse (v), or whether the sample ranges overlapped (~).

+----------------------------------+-------+----------------+----------------+----+
|Metric                            |Unit   |      fair/EEVDF|       scx_eevdf|    |
+==================================+=======+================+================+====+
| schbench latency                                                                |
|  light load  - wakeup p50        |us     |        71 +-16%|        95 +-27%| ~  |
|  light load  - wakeup p90        |us     |       149 +-17%|       181 +-10%| ~  |
|  light load  - request p50       |us     |       4328 +-0%|      4712 +-26%| v  |
|  light load  - request p99       |us     |     13,264 +-6%|     18,016 +-0%| v  |
|  saturated   - wakeup p50        |us     |       106 +-25%|        81 +-75%| ~  |
|  saturated   - wakeup p90        |us     |    24,352 +-50%|    12,176 +-37%| ^  |
|  saturated   - request p50       |us     |    16,240 +-15%|     12,432 +-9%| ^  |
|  saturated   - request p99       |us     |    198,400 +-5%|   203,008 +-11%| ~  |
| scheduling latency (stress-ng --cyclic)                                         |
|  idle machine - p50              |ns     |       6458 +-1%|       5744 +-0%| ^  |
|  idle machine - p90              |ns     |       6697 +-2%|       5915 +-1%| ^  |
|  idle machine - p99              |ns     |       9082 +-7%|       9659 +-5%| ~  |
|  vs 20 hogs   - p50              |ns     |      2333 +-12%|      2461 +-15%| ~  |
|  vs 20 hogs   - p90              |ns     |      2643 +-13%|      2825 +-15%| ~  |
|  vs 20 hogs   - p99              |ns     |       3161 +-9%|      3399 +-11%| ~  |
| throughput                                                                      |
|  perf bench sched messaging -t   |s      |      0.260 +-0%|     0.264 +-1%| v  |
|  perf bench sched messaging -p   |s      |      1.000 +-1%|     0.894 +-3%| ^  |
|  perf bench sched pipe           |ops/s  |    578,640 +-6%|   431,181 +-12%| v  |
|  schbench -L pinned, rps         |rps    |  1,628,689 +-0%| 1,616,687 +-0%| v  |
|  stress-ng --cpu 20              |bogo/s |     28,856 +-1%|    28,743 +-1%| ~  |
|  stress-ng --sock 8              |bogo/s |     15,867 +-1%|    16,418 +-1%| ^  |
|  stress-ng --msg 8               |bogo/s | 15,136,274 +-0%|15,134,700 +-1%| ~  |
|  stress-ng --futex 8             |bogo/s |   480,751 +-31%|  519,239 +-68%| ~  |
| cost of identical delivered work (schbench held at 1000 rps)                    |
|  system CPU busy                 |%      |      45.80 +-3%|    43.28 +-2%| ^  |
|  package power                   |W      |      24.32 +-4%|    23.61 +-1%| ~  |
| power (schedutil, intel_pstate passive)                                         |
|  idle                            |W      |       2.13 +-5%|     1.95 +-6%| ~  |
|  wakeup storm, 50k rps           |W      |       2.99 +-2%|     2.90 +-4%| ~  |
|  full load, first 6 s            |W      |      66.32 +-0%|    80.27 +-2%| v  |
|  full load, steady               |W      |      60.15 +-1%|    58.49 +-1%| ~  |
|  full load, throughput           |bogo/s |     28,527 +-0%|    28,300 +-0%| v  |
+----------------------------------+-------+----------------+----------------+----+

What do the results tell us?

The objective here isn't to beat fair/EEVDF. The objective is to get as close as possible to it. This is a port, and its value comes from behaving like the scheduler that Linux already runs.

On that measure, the first results are encouraging: more than half of the metrics are within 10% of fair/EEVDF in either direction, and the median absolute difference across the metrics is 7.2%.

That's reasonably close for a first prototype of a scheduler implemented outside the kernel and running through the sched_ext interface.

The overhead isn't uniform

For CPU-bound workloads, there is essentially no measurable difference. stress-ng --cpu is within 0.4%, a full-machine 40-second run is within 0.8%, and twenty spinners keep the machine at 100% utilization with both schedulers.

There is even a case where scx_eevdf uses less CPU: holding saturated schbench at a fixed 1000 requests per second, the same work for the same duration, scx_eevdf uses 43.3% CPU versus 45.8% for fair/EEVDF, at a marginally higher clock.

The overhead is concentrated primarily around context switching, specifically the ops.enqueue() and ops.dispatch() callbacks invoked by the sched_ext core. That's a relatively fixed per-switch cost. It dominates benchmarks that do little more than switch tasks, but tends to disappear into the noise once there is other meaningful work to do.

Some workloads are already surprisingly close

Elsewhere, the differences are smaller and mostly in the expected directions. Under saturation, scx_eevdf actually comes out ahead in several measurements: schbench wakeup p90 and request p50 both improve, with non-overlapping sample ranges. On an idle machine, stress-ng --cyclic also wakes tasks about 11% faster.

Light load is where the implementation currently performs worst, although the difference is less clear than the medians alone suggest. The two light-load wakeup measurements are nominally 22–34% behind, but their sample ranges overlap those of fair/EEVDF. The more clearly separable losses are the request latencies: p50 is 9% higher and p99 is 36% higher. This is one area that needs further investigation.

There is also an interesting power result: under full load, power ramps 21% higher during the first six seconds before converging to roughly parity. I haven't investigated the reason of this different behavior yet.

What's next?

There are the next directions I'd like to pursue.

1. Move reusable pieces into sched_ext libraries

A number of the concepts implemented here are useful beyond EEVDF. The goal is to abstract those pieces into reusable sched_ext libraries so that other schedulers can build on them rather than reimplementing the same functionality.

That could make it much easier to experiment with schedulers that differ in only one or two policy decisions.

2. Fill the remaining gaps in the sched_ext ABI

There are still several things that cannot be implemented in scx_eevdf because the sched_ext ABI doesn't currently expose the necessary functionality.

Some of the bigger gaps are:

• NUMA balancing
• effective cpuset masks for cgroups
• proxy execution
• lazy preemption

In each case, the kernel already knows something the BPF scheduler needs, but there is currently no way for a sched_ext scheduler to observe or express it. Adding these interfaces is kernel work, but it is also the part of the project that benefits every sched_ext scheduler rather than just this one.

3. Close the remaining gap

Keep benchmarking and chasing down the divergences. Again, the ultimate goal isn't to make scx_eevdf faster than fair/EEVDF. It's to make the two behave as similarly as possible. Once the baseline is sufficiently close, the interesting experiment becomes much easier. And that's the use case I'm most interested in exploring with this project.