Algorytm EDF

Earliest Deadline First (EDF) – algorytm przydzielania czasu procesora w systemach czasu rzeczywistego. Jest to metoda planowania zadań oparta na priorytetach dynamicznych, w której w każdej chwili procesowi przydzielany jest najwyższy priorytet tym zadaniom, których deadline (termin wykonania) jest najbliższy.

Definicja

Algorytm EDF przydziela CPU zadaniom tak, aby w każdym momencie czasu procesor był wykorzystywany przez zadanie o najwcześniejszym nadchodzącym terminie zakończenia. Priorytet zadania jest więc funkcją jego aktualnego deadline – im krótszy czas do terminu, tym wyższy priorytet.

Zasada działania

1. Po przybyciu nowego zadania określa się jego deadline oraz czas wykonania (wcześniej znany jako C).
2. Wszystkie zadania umieszcza się w kolejce priorytetowej, w której priorytet jest wyznaczany na podstawie najbliższego deadline.
3. CPU przydzielany jest zadaniu znajdującemu się na szczycie kolejki. Jeśli w trakcie wykonywania pojawi się zadanie z wcześniejszym deadline, następuje przerwanie i przełączenie na nowe zadanie.
4. Po zakończeniu zadania lub jego przejściu w stan gotowości (np. po operacji wejścia‑wyjścia) algorytm ponownie selekcjonuje zadanie o najwcześniejszym terminie.

Warunki optymalności

Algorytm EDF jest optymalny w sensie, że jeśli istnieje jakikolwiek harmonogram spełniający wszystkie deadline’y przy określonym obciążeniu, to właśnie EDF zrealizuje ten harmonogram.

Warunek konieczny i wystarczający dla zestawu zadań periodicznych o stałych okresach i stałych czasach wykonania, aby były wykonalne pod EDF, wyrażony jest następującym wzorem:

U = Σ (C_i / T_i) ≤ 1

gdzie C_i to czas wykonania zadania i‑tego, a T_i – jego okres. Jeśli sumaryczne obciążenie U nie przekracza 1, to EDF znajdzie poprawny harmonogram.

Porównanie z innymi algorytmami

Cecha	EDF	Rate‑Monotonic (RM)
Typ priorytetu	Dynamiczny (zmienia się w czasie)	Statyczny (zależny od okresu)
Optymalność	Tak (dla jednego procesora)	Nie (górna granica wykorzystania ≈ 69 % dla nieskończenie many zadań)
Prostota implementacji	Średnia – wymaga kolejki priorytetowej	Wysoka – kolejka stałych priorytetów
Reaktywność na zmiany	Wysoka – natychmiastowy przeliczenie priorytetu	Niska – wymaga ponownej analizy przy zmianie parametrów

Zalety

• Pełna optymalność przy jednoprotocessorowej architekturze.
• Prosta kontrola obciążenia – warunek U ≤ 1 jest jedynym wymogiem.
• Dobre zachowanie przy zmiennych deadline’ach i nie‑periodicznych zadaniach.

Wady

• Potrzeba kolejki priorytetowej zdolnej do szybkiego wyciągania elementu o najniższym deadline.
• Możliwość częstych przełączeń kontekstowych przy dużej liczbie krótkoterminowych zadań.
• Nie zapewnia deterministycznych limitów liczb przełączeń, co może być problematyczne w systemach o ścisłych ograniczeniach czasu przełączania.

Zastosowania

Algorytm EDF znajduje zastosowanie w wielu dziedzinach, w których kluczowa jest terminowość wykonania:

• Systemy sterowania lotem i systemy embedded.
• Systemy multimedialne (np. synchronizacja audio‑video).
• Systemy sterowania procesami przemysłowymi.
• Platformy RTOS (Real‑Time Operating Systems), np. VxWorks, FreeRTOS (w trybach EDF).

Implementacja

Poniżej przedstawiono prosty szkic implementacji EDF w języku C:

typedef struct {
    int id;
    double deadline;   // czas absolutny deadline
    double execution; // pozostały czas wykonania
} Task;

int compare_deadline(const void *a, const void *b) {
    double d1 = ((Task*)a)->deadline;
    double d2 = ((Task*)b)->deadline;
    return (d1 > d2) - (d1 < d2);
}

/* Główna pętla planera */
while (system_running) {
    qsort(task_queue, task_count, sizeof(Task), compare_deadline);
    Task *t = &task_queue[0];          // zadanie z najbliższym deadline
    execute(t);                        // symulacja wykonywania
    if (t->execution <= 0) {
        remove_task(t);
    }
    update_deadlines();                 // ewentualne nowe zadania
}

W praktyce używa się bardziej wydajnych struktur, takich jak drzewo czerwono‑czarne lub kopiec, aby uzyskać O(log n) operacje wstawiania i usuwania.

Historia

Algorytm EDF został po raz pierwszy opisany w klasycznej pracy Liu i Layland z 1973 roku, w której przedstawiono podstawy teorii systemów czasu rzeczywistego. Od tego czasu EDF stał się podstawą wielu współczesnych RTOS‑ów oraz narzędzi do analizy harmonogramów.

Bibliografia i dalsze czytanie

• Liu, C. L.; Layland, J. W. “Scheduling Algorithms for Multiprogramming in a Hard‑Real‑Time Environment”, Journal of the ACM, 1973.
• Stankovic, J. A. “Real‑Time Systems: Scheduling, Analysis, and Verification”, 2006.
• G. Buttazzo, *Hard Real‑Time Computing Systems: Predictable Scheduling Algorithms and Applications*, 2011.

W niniejszym artykule starano się przedstawić najważniejsze aspekty algorytmu EDF, jego teoretyczne podstawy oraz praktyczne implikacje w nowoczesnych systemach czasu rzeczywistego.