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.

Przypisy

1. An implementation of the earliest deadline first algorithm in Linux, DOI: 10.1145/1529282.1529723 [dostęp 2016-04-17] (ang.). Brak numerów stron w książce