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 [2], anche se in letteratura scientifica è possibile trovare algoritmi che ammortizzano la complessità a [3].
Caratteristiche dell'algoritmo
[modifica | modifica wikitesto]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 diventi pronto a intervalli di tempo di periodo e che la scadenza corrisponda al periodo (scadenza implicita), allora è possibile calcolare analiticamente l'utilizzazione del sistema come:
dove è il tempo di esecuzione worst-case. Se , lo schedule è ammissibile.
Ottimalità di EDF
[modifica | modifica wikitesto]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]
Esempio
[modifica | modifica wikitesto]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 è :
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3f/EDF_Example_Timing_Diagram.png/790px-EDF_Example_Timing_Diagram.png)
Note
[modifica | modifica wikitesto]- ^ a b Sanjoy Baruah, Scheduling Real-time Tasks: Algorithms and Complexity, The University of North Carolina at Chapel Hill.
- ^ Michael O’Boyle, Embedded Software - Lecture 6: Scheduling (PDF), su inf.ed.ac.uk. URL consultato il 23 novembre 2016.
- ^ Jagbeer Singh, An algorithm to reduce the time complexity of earliest deadline first scheduling algorithm in real-time system, 2010.
- ^ Arezou Mohammadi, Selim G. Akl, Scheduling Algorithms for Real-Time Systems (PDF), School of Computing, Queen’s University, 2005.