Earliest eligible virtual deadline first scheduling: Difference between revisions
Content deleted Content added
+link |
m add wikilink for Ion Stoica |
||
| (One intermediate revision by one other user not shown) | |||
| Line 3: | Line 3: | ||
==Algorithm== |
==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.<ref>{{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}}</ref> It uses notions of virtual time, eligible time, virtual requests and virtual deadlines for determining scheduling priority.<ref name="Anderson"/> 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.<ref>{{Cite journal |
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.<ref>{{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}}</ref> It uses notions of virtual time, eligible time, virtual requests and virtual deadlines for determining scheduling priority.<ref name="Anderson"/> 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.<ref>{{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}}</ref> |
||
==Linux kernel scheduler== |
==Linux kernel scheduler== |
||
Latest revision as of 04:14, 14 May 2024
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]
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]
- ^ 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.
- ^ 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. Retrieved 2023-08-31.
- ^ "[PATCH 00/10] sched: EEVDF using latency-nice [LWN.net]". LWN.net.
- ^ "An EEVDF CPU scheduler for Linux [LWN.net]". LWN.net. Retrieved 2023-08-31.
- ^ "EEVDF Scheduler Merged For Linux 6.6, Intel Hybrid Cluster Scheduling Re-Introduced". Phoronix.
| Organization |
| ||||
|---|---|---|---|---|---|
| Technical | |||||
| Adoption |
| ||||
