Shortest Job First (SJF), anche conosciuto come Shortest Job Next (SJN) è un metodo non-preemptive di scheduling che seleziona il processo in attesa con la più piccola sequenza successiva di operazioni. Shortest job first è efficiente grazie alla relativa semplicità e perché eleva il throughput ossia il numero di processi portati a termine in un dato tempo. Tuttavia, possiede un potenziale problema di starvation, in cui è possibile che un processo rimanga in attesa troppo tempo prima di essere completato se vengono aggiunti continuamente piccoli processi alla coda dei processi pronti. Questo algoritmo è praticamente non implementabile in quanto non è possibile stabilire con certezza la durata del prossimo CPU-burst del processo.
Ecco un esempio di esecuzione di SJF non preemptive
Data la seguente tabella:
processi tempo di arrivo tempo di burst p1 0.0 7 p2 2.0 5 p3 4.0 1 p4 5.0 4
avremo il seguente ordine di esecuzione dei processi:
p1 p3 p4 p2
tutto questo per la regola che dice che si esegue prima il processo che ha burst più breve. Infatti p1 ha tempo di burst pari a 7 e il successivo più breve è quello che arriva a tempo 4.0 che è p3 e poi si somma il tempo di burst p1 con quello di p3 che fa 8 e quello a tempo 8 è p4 e poi infine p2.
Una variante preemptive dell'algoritmo è lo Shortest Remaining Time First (SRTF).
Voci correlate Scheduler
Categoria:kernel Categoria:Algoritmi di scheduling