Earliest eligible virtual deadline first (EEVDF) is adynamic priority proportional sharescheduling algorithm forsoft real-time systems.[1]
Algorithm
editEEVDF was first described in the 1995 paper "Earliest Eligible Virtual Deadline First : A Flexible and Accurate Mechanism for Proportional Share Resource Allocation" byIon Stoica and Hussein Abdel-Wahab.[2] It uses notions of virtual time, eligible time, virtual requests and virtual deadlines for determining scheduling priority.[1] 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.[3]
Linux kernel scheduler
editIn 2023, Peter Zijlstra proposed replacing theCompletely Fair Scheduler (CFS) in theLinux kernel with an EEVDFprocess scheduler.[4][5] The aim was to remove the need for CFS "latency nice" patches.[6] The EEVDF scheduler replaced CFS in version 6.6 of the Linux kernel.[7]
See also
editReferences
edit- ^abErickson, 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.
- ^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.
- ^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.
- ^"EEVDF Scheduler May Be Ready For Landing With Linux 6.6".Phoronix. Retrieved2023-08-31.
- ^"[PATCH 00/10] sched: EEVDF using latency-nice [LWN.net]".LWN.net.
- ^"An EEVDF CPU scheduler for Linux [LWN.net]".LWN.net. Retrieved2023-08-31.
- ^"EEVDF Scheduler Merged For Linux 6.6, Intel Hybrid Cluster Scheduling Re-Introduced".Phoronix.