Algorytm EDF

Earliest Deadline First – optymalny algorytm szeregowania zadań wykorzystywany w systemach czasu rzeczywistego, wykorzystujący kolejkę priorytetową do przechowywania procesów. Za każdym razem, kiedy w systemie pojawi się zdarzenie wymagające działania algorytmu szeregującego (np. jeden z procesów ukończy swoje zadanie), z kolejki priorytetowej zostanie pobrany proces o najwyższym priorytecie (najbliższe do swojego deadline'u), a następnie zostanie mu przydzielony czas procesora^[1].

Optymalność algorytmu polega na tym, że jeśli EDF nie może uszeregować danego zbioru zadań to żaden algorytm z dynamicznym przydziałem priorytetów nie znajdzie wykonalnego szeregowania oraz w sytuacji gdy każdy algorytm z dynamicznym przydziałem priorytetów potrafi uszeregować dany zbiór zadań to również EDF potrafi. Zbiór zadań jest szeregowalny za pomocą algorytmu EDF wtedy i tylko wtedy, gdy stopień wykorzystania procesora dla danego zbioru zadań wynosi: U < 1.