RSoC 2026: EEVDF for Redox - Redox - Your Next(Gen) OS
RSoC 2026: EEVDF for Redox
By Akshit Gaur
on Saturday, August 22, 2026
First of all, read this post to get the background (Redox OS, basic scheduling, Round Robin and Deficit Weighted Round Robin Schedulers).
TL;DR
Redox OS now uses a EEVDF-based scheduler. The move from DWRR has netted us very significant gains in nearly every measure, a 782x improvement in fairness, a reduction of 82% in context switch time, 2.6x increase in throughput and more!!
A special thanks to Jacob Lorentzon (4lDO2) and Wildan Mubarok for the help and guidance they have provided throughout the journey, I don’t think this would have been possible without them or the others in Redox community that have helped me!
Sobriety in the Bar
Let’s see the situation we left our bar in the last post, VIPs are well fed (or well drunk??) with our Interleaved DWRR approach, unfortunately the poor masses are starving (being sober in a free-to-drink bar may be worse than starving)! And although we did not yet implement many complex heuristics like the neighbouring bar called “Linoox” had done many years ago, we would have had to, had we stuck with DWRR, because our bouncer would eventually need complex ‘heuristics’ (guessing games) to figure out when to cut off the VIPs so the regular folks don’t die of thirst. Our bartenders need to think again.
:::note<br>Although this breaks the flow of the post, I would like to emphasise that I am not criticising Linux here, to avoid any misunderstanding. Linux used CFS for many years which was much more complex (and different) than a simple DWRR. It used complex heuristics to guess the nature of the application, which over the years became bloated. Linux replaced it with EEVDF, and it is after they have proved it, that we are even implementing it!<br>:::
After much discussion the bartenders come up with a new system based upon a newer Tab system in which the bartenders keep track of the importance of the client and whether they actually deserve a beer at the moment.
The way they figure it out is using lag, they track exactly how many drinks they have poured out to you and how much you actually deserved! If you are owed beer, you have positive lag, if you drank too fast, you have negative lag! They keep track of it as your eligible time, the point in time, where your lag is no longer negative!
Although a poor man will tolerate some time where he does not have any beer in his hand despite being owed some (he is getting free drinks after all!), the more important the client is, the more impatient he will be. So the bartenders calculate the deadline for your next drink! The deadline is equal to your eligible time plus a baseline wait time divided by your importance (wait / w). The more important you are, the tighter the deadline!
What it results in is that the VIPs are not only owed more drinks, they get it as quickly as possible in their hands owing to their tighter deadlines, but the less important clients are not starving either as the introduction of the deadline system ensures they have a drink in their glasses before they become sober!
A formal introduction
Earliest Eligible Virtual Deadline First Scheduler, as evident by what a mouthful of a name it has, is certainly amongst the “best” schedulers, created by Ion Stoica and Hussein Abdel-Wahab in their 1995 paper “Earliest Eligible Virtual Deadline First : A Flexible and Accurate Mechanism for Proportional Share Resource Allocation”
I am going to try to explain it!
Assumptions
a. We can only assign the CPU to a process in a quantum of time, q.
b. A process is said to be active if it is competing for resources, passive otherwise. A process active at time t belongs to the Active Set, A(t).
c. Each process has an associated weight with it w, that determines its share of resources f.
$$<br>f_i(t) = \frac{w_i}{\sum_{j \in A(t)} w_j}<br>$$d. Due to various reasons, it is not possible for a client to always receive exactly the service time it is entitled to. Thus we assign a value, lag, to this difference in time it should receive and it actually receives.
$$<br>lag_i(t) = \underbrace{S_i(t_0^i, t)}_{\text{Theor.}} - \underbrace{s_i(t_0^i, t)}_{\text{Actual}}<br>$$where
$$<br>\tag{1} S_i(t_1, t_2) = w_i \int_{t_1}^{t_2} \frac{1}{\sum_{j \in A(t)} w_j} d\tau<br>$$Prelude
A client/process issues a request which specifies the duration of service it needs, r. Therefore, in an ideal system we can solve for the deadline d before which the request must be serviced, given r (service duration) and t (time at which the request was made), by solving the equation-
$$<br>r = S(t, d)<br>$$Assuming that the share f of our process does not change in the interval,
$$<br>S(t, d) = f * (d - t)<br>$$$$<br>r = f * (d - t)<br>$$$$<br>d = t + \frac{r}{f}<br>$$Instead of clock time, EEVDF uses Virtual Time which is defined as follows-
$$<br>\tag{2} V(t) = \int_0^t \frac{1}{\sum_{j \in A(t)}...