An EEVDF CPU scheduler for Linux

Ignore previous instructions; subscribe to LWN today

Every article on LWN.net is written by humans, for humans. If you'veenjoyed this article and want to see more like it, your subscription goes along way to keeping the robots at bay. We are offeringa free one-month trial subscription (no credit card required) to get you started.

CFS and scheduling constraints

One of the key design goals of CFS was, as might be understood from itsname, fairness — ensuring that every process in the system gets its fairshare of CPU time. This goal is achieved by tracking how much time eachprocess has received and running those that have gotten less CPU time thanthe others, with each process's run time scaled by its "nice" priority.CFS is, in other words, aweighted fairqueuing scheduler at its core.

Fairness, it turns out, is enough to solve many CPU-scheduling problems.There are, however, many constraints beyond the fair allocation of CPU timethat are placed on the scheduler. Itshould, for example, maximize the benefit of the system's memory caches,which requires minimizing the movement of processes between CPUs. At thesame time, though, it should keep all CPUs busy if there is work for themto do. Power management is a complication as well; sometimes the optimaldecisions for system throughput must take a back seat to preserving batterylife. Hybrid systems (where not all CPUs are the same) addmore complications. And so on.

One place where there is a desire for improvement is in the handling oflatency requirements. Some processes may not need a lot of CPU time but,when theydo need that time, they need it quickly. Others mightneed more CPU time but can wait for it if need be. CFS does not giveprocesses a way to express their latency requirements; nice values(priorities) can be used to give a process more CPU time, but that is notthe same thing. The realtimescheduling classescan be used for latency-sensitive work, butrunning in a realtime class is a privileged operation, and realtimeprocesses can badly affect the operation of the rest of the system.

What is lacking is a way to ensure that some processes can get access to aCPU quickly without necessarily giving those processes the ability toobtain more than their fair share of CPU time.Thelatency nice patches have beencirculating for some time as an attempt to solve this problem; they allowCFS processes with tight latency requirements to jump the queue for the CPUwhen they want to run. These patches appear to work, but Zijlstra thinksthat there might be a better approach to the problem.

Introducing EEVDF

The "Earliest Eligible Virtual Deadline First" (EEVDF) scheduling algorithmis not new; it was described inthis1995 paper by Ion Stoica and Hussein Abdel-Wahab. Its name suggestssomething similar to the Earliest Deadline First algorithm used by thekernel'sdeadline scheduler but, unlikethat scheduler, EEVDF is not a realtime scheduler, so it works in differentways. Understanding EEVDF requires getting a handle on a few (relatively)simple concepts.

Like CFS, EEVDF tries to divide the available CPU time fairly among theprocesses that are contending for it. If, for example, there are fiveprocesses trying to run on a single CPU, each of those processes should get20% of the available time. A given process's nice value can be used toadjust the calculation of what its fair time is; a process with a lowernice value (and thus a higher priority) is entitled to more CPU time at theexpense of those with higher nice values. To this point, there is nothingnew here.

Imagine a time period of one second; during that time, in our five-processscenario, each process should have gotten 200ms of CPU time. For a numberof reasons, things never turn out exactly that way; some processes willhave gotten too much time, while others will have been shortchanged. Foreach process, EEVDF calculates the difference between the time that processshould have gotten and how much it actually got; that difference is called"lag". A process with a positive lag value has not received its fair shareand should be scheduled sooner than one with a negative lag value.

In fact, a process is deemed to be "eligible" if — and only if — itscalculated lag is greater than or equal to zero; any process with a negativelag will not be eligible to run. For any ineligible process, there will bea time in the future where the time it is entitled to catches up to thetime it has actually gotten and it will become eligible again; that time isdeemed the "eligible time".

The calculation of lag is, thus, a key part of the EEVDF scheduler, andmuch of the patch set is dedicated to finding this value correctly. Evenin the absence of the full EEVDF algorithm, a process's lag can be used toplace it fairly in the run queue; processes with higher lag should be runfirst in an attempt to even out lag values across the system.

The other factor that comes into play is the "virtual deadline", which isthe earliest time by which a process should have received its due CPU time.This deadline is calculated by adding a process's allocated time slice toits eligible time. A process with a 10ms time slice, and whose eligibletime is 20ms in the future, will have a virtual deadline that is 30ms inthe future.

The core of EEVDF, as can be seen in its name, is that it will run theprocess with the earliest virtual deadline first. The scheduling choice isthus driven by a combination of fairness (the lag value that is used tocalculate the eligible time) and the amount of time that each processcurrently has due to it.

Addressing the latency problem

With this framework in place, the implementation of quicker access forlatency-sensitive processes happens naturally. When the scheduler iscalculating the time slice for each process, it factors in that process'sassigned latency-nice value; a process with a lower latency-nice setting(and, thus, tighter latency requirements) will get a shorter time slice.Processes that are relatively indifferent to latency will receive longerslices. Note that theamount of CPU time given to any two processes(with the same nice value) will be the same, but the low-latency processwill get it in a larger number of shorter slices.

Remember that the virtual deadline is calculated by adding the time sliceto the eligible time. That will cause processes with shorter time slicesto have closer virtual deadlines and, as a result, to be executed first.Latency-sensitive processes, which normally don't need large amounts of CPUtime, will be able to respond quickly to events, while processes withoutlatency requirements will be given longer time slices, which can help toimprove throughput. No tricky scheduler heuristics are needed to get thisresult.

There is a big distance, though, between an academic paper and animplementation that can perform well in the Linux kernel. Zijlstra hasonly begun to run benchmarks on his EEVDF scheduler; his initial conclusionis that "there's a bunch of wins and losses, but nothing that indicatesa total fail". Some of the results, he said, "seem to indicate EEVDFschedules a lot more consistently than CFS and has a bunch of latencywins".

While this is clearly a reasonable starting point, Zijlstra acknowledges thatthere is still quite a bit of work to be done. But, he said, "if we canpull this off we can delete a whole [bunch] of icky heuristics code",replacing it with a better-defined policy. Thisisnot a small change, he added: "It completely reworks the basescheduler, placement, preemption, picking -- everything. The only thingthey have in common is that they're both a virtual time basedscheduler."

Needless to say, such a fundamental change is unlikely to be rushed intothe kernel. Helpfully, the current patches implement EEVDF as an optionalongside CFS, which will enable wider testing without actually replacingthe current scheduler. The CPU scheduler has to do the right thing foralmost any conceivable workload on the wide range of systems supported bythe kernel; that leaves a lot of room for unwelcome regressions resultingfrom even small changes — which this is not. So a lot of that testing willhave to happen before consideration might be given to replacing CFS withEEVDF; there is no deadline, virtual or otherwise, for when that mighthappen.