CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 6 of 7 · 4 min read

EEVDF

EEVDF, the scheduler of current Linux

In plain words: From version 6.6, Linux replaced the Completely Fair Scheduler, which picked the smallest vruntime, with a design called earliest eligible virtual deadline first (EEVDF). The kernel documentation says that it aims, like the old scheduler, to divide the processor equally among tasks of the same priority, and it uses the same weights and the same nice values. The test machine runs kernel 6.18, so it uses this design, and the measurements above come from it. What is new is that it can also take care of latency (how soon a task runs), not only the share.

The documentation describes the idea like this. Each task has a lag: the difference between the time it should have received (its fair share so far) and the time it actually received. A task with positive lag is owed time, and a task with negative lag has had more than its share. A task is eligible if its lag is zero or positive. For each eligible task, the scheduler works out a virtual deadline, roughly the virtual time by which the task's next slice should be finished, and runs the eligible task with the earliest deadline.

A task that asks for a shorter slice gets an earlier deadline, so it runs sooner, though it still receives no more total time over a long period. This helps programs that wake up, do a little work and sleep again (interactive and I/O-bound tasks). The sleeper test of page 1 showed those in action: the sleeping program was never forced off the processor.

Real systems add many details (lag after sleeping, groups of tasks, several processors), and they change from version to version. What does not change are the points of this page: weights from the nice value, a counter of virtual time, and the choice of the task that is behind.

Earliest eligible virtual deadline first

Earliest eligible virtual deadline first (EEVDF) is the scheduling algorithm of the Linux fair class since kernel 6.6: among the tasks whose lag is zero or positive, it runs the one with the earliest virtual deadline, where lag measures the time a task is owed against its fair share.

Example: a task that has run less than its fair share has positive lag, is eligible, and runs once its deadline is the earliest among the eligible tasks.

Common mistake

Assuming that nice sets an absolute speed. A nice value matters only when tasks compete: a nice 19 task alone on an idle processor runs at full speed.

Interview angle

Answer in your head first, then open it.

What does nice do on Linux?

It sets a task's weight, so competing tasks share the processor in proportion to their weights.

What is virtual runtime?

A per-task counter that grows with run time divided by weight; the scheduler favours the smallest.

How is lottery scheduling fair?

Shares are probabilities, so it is fair over many draws and rough over a few.

What scheduler does Linux use?

The fair class has used EEVDF since kernel 6.6, and CFS before it.

What is the difference between a priority and a share?

A priority orders tasks, and a share divides time.

Check yourself: 1. What does a positive lag mean? 2. How does a shorter slice help a sleeping, interactive task? 3. Does nice slow a task that has the machine to itself?

Words you will meet

Word Meaning
Proportional share Each process gets its weight's fraction of the processor
Ticket A unit of weight in lottery scheduling
Stride A step that is large for processes with few tickets
Pass The counter that stride scheduling compares
Nice value A user-set number from -20 to 19 that sets a task's weight
Virtual runtime Run time scaled by weight, used to choose the next task
Lag Time a task is owed or has overused
Virtual deadline The time by which a task's next slice should end

Quick notes

  • Proportional-share scheduling is a policy that assigns each process a weight and aims to give it, over time, the fraction of processor time equal to its weight divided by the total weight of all ready processes.
  • Lottery scheduling is a proportional-share policy in which each process holds tickets, and at every scheduling decision a ticket is drawn at random and its owner runs next, so that.
  • Stride scheduling is a deterministic proportional-share policy that gives each process a stride inversely proportional to its tickets and a pass counter, runs the process with the lowest pass, and then adds the stride to that pass.
  • The virtual runtime of a task is a counter that grows with the time the task has run, divided by its weight (scaled so that nice 0 counts at real.
  • Earliest eligible virtual deadline first (EEVDF) is the scheduling algorithm of the Linux fair class since kernel 6.6: among the tasks whose lag is zero or positive, it runs the.