Algorytm EDF

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Earliest Deadline First – optymalny algorytm szeregowania zadań wykorzystywany w systemach czasu rzeczywistego, wykorzystujący kolejkę priorytetową do przechowywania zadań i przydzielania ich do wolnych procesów. Za każdym razem, kiedy w systemie pojawi się niezajęty proces (np. jeden z procesów ukończy swoje zadanie), z kolejki priorytetowej zostanie pobrane zadanie o najwyższym priorytecie (najbliższe do swojego deadlinu), a następnie przekazane do wykonania dla procesu[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