Earliest deadline first

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2023-07) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Earliest Deadline First (EDF) kan översättas till "tidigaste tidsgräns först" och är en schemaläggningsalgoritm som används inom datavetenskap, speciellt inom realtidssystem.

Algoritmen fungerar genom att den process som har kortast tid tills den måste vara färdig kör först. Algoritmen använder sig därför inte av prioritet när den avgör vilken process som ska köra näst.

Algoritmen kan schemalägga om och endast om

${\displaystyle U\leq 1}$

Förutsättningarna är att:

• Alla processer är oberoende av varandra och delar inga enheter eller resurser.
• Alla processer har sin tidsgräns satt till början av nästa period.
• Alla processer släpps i början av perioden de ska köra i.

Utnyttjandegraden får man fram genom följande ekvation:

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}}$

Där ${\displaystyle C_{i}}$ är exekveringstid (den tid det tar att köra en process) och ${\displaystyle T_{i}}$ är periodtid (tidslängden från att en process körs, tills att den vill köra igen).

Earliest Deadline First är optimal om ovanstående uppfylls, och är en av de effektivaste schemaläggningsalgoritmerna. Problemet med den är att den är svår att implementera på annat än specialdesignade realtidssystem som bygger på att alla processer har just en tidsgräns.