Misplaced Pages

Earliest eligible virtual deadline first (EEVDF) is a dynamic priority proportional share scheduling algorithm for soft real-time systems.

Algorithm

EEVDF was first described in the 1995 paper "Earliest Eligible Virtual Deadline First : A Flexible and Accurate Mechanism for Proportional Share Resource Allocation" by Ion Stoica and Hussein Abdel-Wahab. It uses notions of virtual time, eligible time, virtual requests and virtual deadlines for determining scheduling priority. It has the property that when a job keeps requesting service, the amount of service obtained is always within the maximum quantum size of what it is entitled.

Linux kernel scheduler

In 2023, Peter Zijlstra proposed replacing the Completely Fair Scheduler (CFS) in the Linux kernel with an EEVDF process scheduler. The aim was to remove the need for CFS "latency nice" patches. The EEVDF scheduler replaced CFS in version 6.6 of the Linux kernel.

See also

• Brain Fuck Scheduler
• Earliest deadline first scheduling (EDF)
• nice (Unix)
• SCHED_DEADLINE

References

1. ^ Erickson, Jeremy P.; Anderson, James H. (September 2, 2022). Tian, Yu-Chu; Levy, David Charles (eds.). Handbook of Real-Time Computing. Springer Nature. pp. 233–267. doi:10.1007/978-981-287-251-7_4 – via Springer Link.
2. Stoica, Ion; M. Abdel-Wahab, Hussein (1995). Earliest Eligible Virtual Deadline First : A Flexible and Accurate Mechanism for Proportional Share Resource Allocation (Technical report). CS Dpt., Old Dominion Univ. TR-95-22.
3. Epema, D. H. J. (November 2, 1998). "Decay-usage scheduling in multiprocessors". ACM Transactions on Computer Systems. 16 (4): 367–415. doi:10.1145/292523.292535.
4. "EEVDF Scheduler May Be Ready For Landing With Linux 6.6". Phoronix. Retrieved 2023-08-31.
5. "[PATCH 00/10] sched: EEVDF using latency-nice [LWN.net]". LWN.net.
6. "An EEVDF CPU scheduler for Linux [LWN.net]". LWN.net. Retrieved 2023-08-31.
7. "EEVDF Scheduler Merged For Linux 6.6, Intel Hybrid Cluster Scheduling Re-Introduced". Phoronix.

• Processor scheduling algorithms
• Real-time computing
• Linux kernel process schedulers