Shortest Job First (SJF): esempio preventivo e non preventivo

Che cos'è la pianificazione del lavoro più breve?

Il lavoro più corto per primo (SJF) è un algoritmo in cui il processo con il tempo di esecuzione più breve viene scelto per l'esecuzione successiva. Questo metodo di pianificazione può essere preventivo o non preventivo. Riduce significativamente il tempo medio di attesa per altri processi in attesa di esecuzione. La forma completa di SJF è Shortest Job First.

Esistono fondamentalmente due tipi di metodi SJF:

SJF non preventivo
SJF preventivo

Caratteristiche della pianificazione SJF

È associato a ciascun lavoro come unità di tempo da completare.
Questo metodo dell'algoritmo è utile per l'elaborazione di tipo batch, dove l'attesa del completamento dei lavori non è fondamentale.
Può migliorare la produttività del processo garantendo che i lavori più brevi vengano eseguiti per primi, quindi possibilmente con tempi di consegna brevi.
Migliora la produzione lavorativa offrendo lavori più brevi, che dovrebbero essere eseguiti per primi, e che nella maggior parte dei casi hanno tempi di consegna più brevi.

SJF non preventivo

Nella pianificazione non preventiva, una volta assegnato il ciclo della CPU al processo, il processo lo mantiene finché non raggiunge uno stato di attesa o termina.

Si considerino i seguenti cinque processi, ciascuno dotato di un proprio tempo di burst e di un proprio tempo di arrivo.

Coda di elaborazione	Tempo di scoppio	Orario di arrivo
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Passo 0) Al tempo=0, P4 arriva e inizia l'esecuzione.

Passo 1) Al tempo = 1, arriva il processo P3. Ma P4 necessita ancora di 2 unità di esecuzione per essere completata. Continuerà l'esecuzione.

Passo 2) Al tempo =2, il processo P1 arriva e viene aggiunto alla coda di attesa. P4 continuerà l'esecuzione.

Passo 3) Al tempo = 3, il processo P4 terminerà la sua esecuzione. Viene confrontato il tempo di burst di P3 e P1. Il processo P1 viene eseguito perché il suo tempo di burst è inferiore rispetto a P3.

Passo 4) Al tempo = 4, il processo P5 arriva e viene aggiunto alla coda di attesa. P1 continuerà l'esecuzione.

Passo 5) Al tempo = 5, il processo P2 arriva e viene aggiunto alla coda di attesa. P1 continuerà l'esecuzione.

Passo 6) Al tempo = 9, il processo P1 terminerà la sua esecuzione. Viene confrontato il tempo di burst di P3, P5 e P2. Il processo P2 viene eseguito perché il suo tempo di burst è il più basso.

Passo 7) All'istante=10, P2 è in esecuzione e P3 e P5 sono in coda di attesa.

Passo 8) Al tempo = 11, il processo P2 terminerà la sua esecuzione. Viene confrontato il tempo di burst di P3 e P5. Il processo P5 viene eseguito perché il suo tempo di burst è inferiore.

Passo 9) Al tempo = 15, il processo P5 terminerà la sua esecuzione.

Passo 10) Al tempo = 23, il processo P3 terminerà la sua esecuzione.

Passo 11) Calcoliamo il tempo medio di attesa per l'esempio sopra.

Wait time 
P4= 0-0=0
P1=  3-2=1
P2= 9-5=4
P5= 11-4=7
P3= 15-1=14

Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2

SJF preventivo

Nella pianificazione preventiva SJF, i lavori vengono inseriti nella coda di preparazione non appena arrivano. Inizia l'esecuzione un processo con il tempo di burst più breve. Se arriva un processo con un tempo di burst ancora più breve, il processo corrente viene rimosso o interrotto dall'esecuzione e al lavoro più breve viene assegnato il ciclo della CPU.

Consideriamo i seguenti cinque processi:

Coda di elaborazione	Tempo di scoppio	Orario di arrivo
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Passo 0) Al tempo=0, P4 arriva e inizia l'esecuzione.

Coda di elaborazione	Tempo di scoppio	Orario di arrivo
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Passo 1) Al tempo = 1, arriva il processo P3. Ma P4 ha un tempo di burst più breve. Continuerà l'esecuzione.

Passo 2) Al tempo = 2, il processo P1 arriva con tempo di burst = 6. Il tempo di burst è maggiore di quello di P4. Pertanto, P4 continuerà l'esecuzione.

Passo 3) Al tempo = 3, il processo P4 terminerà la sua esecuzione. Viene confrontato il tempo di burst di P3 e P1. Il processo P1 viene eseguito perché il suo tempo di burst è inferiore.

Passo 4) Al tempo = 4 arriverà il processo P5. Viene confrontato il tempo di burst di P3, P5 e P1. Il processo P5 viene eseguito perché il suo tempo di burst è più basso. Il processo P1 è anticipato.

Coda di elaborazione	Tempo di scoppio	Orario di arrivo
P1	Ne restano 5 su 6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Passo 5) Al tempo = 5 arriverà il processo P2. Viene confrontato il tempo di burst di P1, P2, P3 e P5. Il processo P2 viene eseguito perché il suo tempo di burst è minimo. Il processo P5 è anticipato.

Coda di elaborazione	Tempo di scoppio	Orario di arrivo
P1	Ne restano 5 su 6	2
P2	2	5
P3	8	1
P4	3	0
P5	Ne restano 3 su 4	4

Passo 6) All'istante =6, P2 è in esecuzione.

Passo 7) Al tempo =7, P2 termina la sua esecuzione. Viene confrontato il tempo di burst di P1, P3 e P5. Il processo P5 viene eseguito perché il suo tempo di burst è inferiore.

Coda di elaborazione	Tempo di scoppio	Orario di arrivo
P1	Ne restano 5 su 6	2
P2	2	5
P3	8	1
P4	3	0
P5	Ne restano 3 su 4	4

Passo 8) Al tempo =10, P5 terminerà la sua esecuzione. Viene confrontato il tempo di burst di P1 e P3. Il processo P1 viene eseguito perché il suo tempo di burst è inferiore.

Passo 9) Al tempo =15, P1 termina la sua esecuzione. P3 è l'unico processo rimasto. Inizierà l'esecuzione.

Passo 10) Al tempo =23, P3 termina la sua esecuzione.

Passo 11) Calcoliamo il tempo medio di attesa per l'esempio sopra.

Wait time 
P4= 0-0=0
P1=  (3-2) + 6 =7
P2= 5-5 = 0
P5= 4-4+2 =2
P3= 15-1 = 14

Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6

Vantaggi dell'SJF

Ecco i vantaggi/pro dell'utilizzo del metodo SJF:

SJF viene spesso utilizzato per la pianificazione a lungo termine.
Riduce il tempo medio di attesa rispetto all'algoritmo FIFO (First in First Out).
Il metodo SJF fornisce il tempo di attesa medio più basso per un insieme specifico di processi.
È appropriato per i lavori eseguiti in batch, dove i tempi di esecuzione sono noti in anticipo.
Per il sistema batch di pianificazione a lungo termine, è possibile ottenere una stima del tempo di burst dalla descrizione del lavoro.
Per la pianificazione a breve termine, dobbiamo prevedere il valore del prossimo burst time.
Probabilmente ottimale per quanto riguarda il tempo medio di consegna.

Svantaggi/contro di SJF

Ecco alcuni svantaggi/contro dell'algoritmo SJF:

Il tempo di completamento del lavoro deve essere noto in anticipo, ma è difficile da prevedere.
Viene spesso utilizzato in un sistema batch per la pianificazione a lungo termine.
SJF non può essere implementato per Programmazione della CPU per il breve termine. Ciò è dovuto al fatto che non esiste un metodo specifico per prevedere la durata del prossimo burst della CPU.
Questo algoritmo può causare tempi di consegna molto lunghi o fame.
Richiede la conoscenza della durata di esecuzione di un processo o di un lavoro.
Porta alla fame che non riduce i tempi medi di consegna.
È difficile conoscere la lunghezza della prossima richiesta della CPU.
Il tempo trascorso dovrebbe essere registrato, il che si traduce in un maggiore sovraccarico sul processore.

Sintesi

SJF è un algoritmo in cui il processo con il tempo di esecuzione più breve viene scelto per l'esecuzione successiva.
La pianificazione SJF è associata a ciascun lavoro come unità di tempo da completare.
Questo metodo dell'algoritmo è utile per l'elaborazione di tipo batch, dove l'attesa del completamento dei lavori non è fondamentale.
Esistono fondamentalmente due tipi di metodi SJF 1) SJF non preventivo e 2) SJF preventivo.
Nella pianificazione non preventiva, una volta assegnato il ciclo della CPU al processo, il processo lo mantiene finché non raggiunge uno stato di attesa o termina.
Nella pianificazione preventiva SJF, i lavori vengono inseriti nella coda di preparazione non appena arrivano.
Sebbene inizi un processo con un tempo di burst breve, il processo corrente viene rimosso o interrotto dall'esecuzione e il lavoro più breve viene eseguito per primo.
SJF viene spesso utilizzato per la pianificazione a lungo termine.
Riduce il tempo medio di attesa rispetto all'algoritmo FIFO (First in First Out).
Nella pianificazione SJF, il tempo di completamento del lavoro deve essere noto in anticipo, ma è difficile da prevedere.
SJF non può essere implementato per la pianificazione della CPU a breve termine. Ciò è dovuto al fatto che non esiste un metodo specifico per prevedere la durata del prossimo burst della CPU.