title: Algoritmo di scheduling EDF
text: # 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.).
  
  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 essere schedulato se la sua scadenza è la più vicina al tempo t.
  
  Assumendo che ogni processo $t$ diventi pronto a intervalli di tempo di periodo $T_{t}$ e che la scadenza corrisponda al periodo (scadenza 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 scadenza 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 scadenze dei processi, è in questo caso la priorità assegnati ai processi è $P2>P1>P3$:
  
  