Jump to content

Earliest eligible virtual deadline first scheduling

Add links
From Wikipedia, the free encyclopedia

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

Algorithm

[edit]

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.[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

[edit]
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.[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

[edit]

References

[edit]
  1. ^ a b 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.233-267&rft.pub=Springer+Nature&rft.date=2022-09-02&rft_id=info:doi/10.1007/978-981-287-251-7_4&rft.aulast=Erickson&rft.aufirst=Jeremy+P.&rft.au=Anderson,+James+H.&rft_id=https://doi.org/10.1007/978-981-287-251-7_4&rfr_id=info:sid/en.wikipedia.org:Earliest+eligible+virtual+deadline+first+scheduling" class="Z3988">
  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.367-415&rft.date=1998-11-02&rft_id=info:doi/10.1145/292523.292535&rft.aulast=Epema&rft.aufirst=D.+H.+J.&rft_id=https://doi.org/10.1145%2F292523.292535&rfr_id=info:sid/en.wikipedia.org:Earliest+eligible+virtual+deadline+first+scheduling" class="Z3988">
  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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Earliest_eligible_virtual_deadline_first_scheduling&oldid=1230204826"