Earliest deadline first

Från Rilpedia

Texten från svenska Wikipedia

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

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:

Där C_i är exekveringstid (den tid det tar att köra en process) och 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.