Algoritmo di scheduling EDF

L'Earliest Deadline First (EDF), in italiano prima la scadenza più vicina, è un algoritmo di scheduling tipico dei sistemi operativi in tempo reale. 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.)^[1].

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

La definizione formale dell'algoritmo di scheduling EDF può essere scritta come^[1]:

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

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

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

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

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.^[4]

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

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

• (EN) Denis Howe, earliest deadline first, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Portale Informatica: accedi alle voci di Teknopedia che trattano di informatica