Algoritmo di scheduling EDF

L'Earliest Deadline First (EDF), in italiano prima la deadline più vicina, è un algoritmo di scheduling tipico dei sistemi operativi real-time. Come dice il nome stesso, lo scheduler seleziona come prossimo processo da eseguire quello con la distanza minore dalla sua deadline. EDF è un algoritmo a priorità dinamica, in quanto la priorità assegnata ai processi cambia potenzialmente ad ogni esecuzione dello scheduler e il suo valore dipende unicamente dalle caratteristiche temporali degli stessi (tempo di arrivo, deadline, ecc.).

La complessità dell'algoritmo è tradizionalmente $O(n^{2})$, anche se in letteratura scientifica è possibile trovare algoritmi che ammortizzano la complessità a $O(n\log n)$.

Caratteristiche dell'algoritmo

La definizione formale dell'algoritmo di scheduling EDF può essere scritta come:

Ad ogni istante temporale t, il job j è scelto per schedulato se la sua deadline è la più vicina al tempo t.

Assumendo che ogni processo $t$ diventi pronto a intervalli di tempo di periodo $T_{t}$ e che la deadline corrisponda al periodo (deadline implicita), allora è possibile calcolare analiticamente l'utilizzazione del sistema come:

$U=\sum _{t=1}^{n}{\frac {C_{t}}{T_{t}}}$

dove $C_{t}$ è il tempo di esecuzione worst-case. Se $U\leq 1$, lo schedule è ammissibile.

Ottimalità di EDF

EDF è un algoritmo ottimo su sistemi uniprocessore preemptive: se non esiste uno schedule valido in EDF, non esisterà alcun altro algoritmo in grado di trovarlo.

Esempio

Si considerino i seguenti processi (si ipotizzi una deadline implicita, ovvero equivalente al periodo):

Processo	Tempo di esecuzione	Periodo
P1	1	8
P2	2	5
P3	4	10

Lo scheduler al tempo 0 verificherà la distanza delle deadline dei processi, è in questo caso la priorità assegnati ai processi è $P2>P1>P3$:

Uno schedule possibile dell'esempio