Shortest job first

metodo non-preemptive di scheduling

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

modifica
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica