Earliest eligible virtual deadline first scheduling
{{Short description|Dynamic scheduling algorithm}}
Earliest eligible virtual deadline first (EEVDF) is a dynamic priority proportional share scheduling algorithm for soft real-time systems.{{Cite book|url=https://doi.org/10.1007/978-981-287-251-7_4|title=Handbook of Real-Time Computing|first1=Jeremy P.|last1=Erickson|first2=James H.|last2=Anderson|author2-link=James H. Anderson (computer scientist)|editor-first1=Yu-Chu|editor-last1=Tian|editor-first2=David Charles|editor-last2=Levy|date=September 2, 2022|publisher=Springer Nature|pages=233–267|via=Springer Link|doi=10.1007/978-981-287-251-7_4}}
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.{{cite tech report |last1=Stoica |first1=Ion |last2=M. Abdel-Wahab |first2=Hussein |date=1995 |title=Earliest Eligible Virtual Deadline First : A Flexible and Accurate Mechanism for Proportional Share Resource Allocation |institution=CS Dpt., Old Dominion Univ.|url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564 |number=TR-95-22}} 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.{{Cite journal|title=Decay-usage scheduling in multiprocessors|first=D. H. J.|last=Epema|date=November 2, 1998|journal=ACM Transactions on Computer Systems|volume=16|issue=4|pages=367–415|doi=10.1145/292523.292535|doi-access=free}}
Linux kernel scheduler
{{See also|Linux kernel#Scheduling}}
In 2023, Peter Zijlstra proposed replacing the Completely Fair Scheduler (CFS) in the Linux kernel with an EEVDF process scheduler.{{Cite web |title=EEVDF Scheduler May Be Ready For Landing With Linux 6.6 |url=https://www.phoronix.com/news/Linux-6.6-EEVDF-Likely |access-date=2023-08-31 |website=Phoronix |language=en}}{{Cite web|url=https://lwn.net/ml/linux-kernel/20230306132521.968182689@infradead.org/|title=[PATCH 00/10] sched: EEVDF using latency-nice [LWN.net]|website=LWN.net}} The aim was to remove the need for CFS "latency nice" patches.{{Cite web |title=An EEVDF CPU scheduler for Linux [LWN.net] |url=https://lwn.net/Articles/925371/ |access-date=2023-08-31 |website=LWN.net}} The EEVDF scheduler replaced CFS in version 6.6 of the Linux kernel.{{Cite web|url=https://www.phoronix.com/news/Linux-6.6-EEVDF-Merged|title=EEVDF Scheduler Merged For Linux 6.6, Intel Hybrid Cluster Scheduling Re-Introduced|website=Phoronix}}