Qual è la pianificazione del primo lavoro più breve?
Shortest Job First (SJF) è un algoritmo in cui il processo con il tempo di esecuzione più piccolo viene scelto per l'esecuzione successiva. Questo metodo di pianificazione può essere preventivo o non preventivo. Riduce notevolmente 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
In questo tutorial sul sistema operativo imparerai:
- Qual è la pianificazione del primo lavoro più breve?
- Caratteristiche della pianificazione SJF
- SJF non preventivo
- SJF preventivo
- Vantaggi di SJF
- Svantaggi / Contro di SJF
Caratteristiche della pianificazione SJF
- È associato a ogni lavoro come unità di tempo da completare.
- Questo metodo di algoritmo è utile per l'elaborazione di tipo batch, dove l'attesa del completamento dei lavori non è fondamentale.
- Può migliorare la produttività del processo assicurandosi che i lavori più brevi vengano eseguiti per primi, quindi possibilmente avere un breve tempo di consegna.
- Migliora la produzione di lavoro offrendo lavori più brevi, che dovrebbero essere eseguiti per primi, che per lo più hanno un tempo di consegna più breve.
SJF non preventivo
Nella pianificazione non preventiva, una volta che il ciclo della CPU viene allocato al processo, il processo lo trattiene fino a quando non raggiunge uno stato di attesa o viene terminato.
Considera i seguenti cinque processi, ciascuno con il proprio tempo di burst e orario di arrivo univoci.
| Coda di elaborazione | Tempo di scoppio | Orario di arrivo |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Step 0) All'istante = 0, P4 arriva e inizia l'esecuzione.
Passaggio 1) All'ora = 1, arriva il processo P3. Tuttavia, P4 necessita ancora di 2 unità di esecuzione per essere completato. Continuerà l'esecuzione.
Passaggio 2) All'ora = 2, il processo P1 arriva e viene aggiunto alla coda di attesa. P4 continuerà l'esecuzione.
Passaggio 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.
Passaggio 4) All'ora = 4, il processo P5 arriva e viene aggiunto alla coda di attesa. P1 continuerà l'esecuzione.
Passaggio 5) All'ora = 5, il processo P2 arriva e viene aggiunto alla coda di attesa. P1 continuerà l'esecuzione.
Passaggio 6) All'ora = 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.
Passaggio 7) All'ora = 10, P2 è in esecuzione e P3 e P5 sono in coda di attesa.
Passaggio 8) All'ora = 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.
Passaggio 9) All'ora = 15, il processo P5 terminerà la sua esecuzione.
Passaggio 10) All'ora = 23, il processo P3 terminerà la sua esecuzione.
Passaggio 11) Calcoliamo il tempo di attesa medio per l'esempio sopra.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
SJF preventivo
In Preemptive SJF Scheduling, i lavori vengono inseriti nella coda Pronto non appena arrivano. Inizia l'esecuzione di un processo con il tempo di burst più breve. Se arriva un processo con un tempo di burst anche più breve, il processo corrente viene rimosso o impedito dall'esecuzione e al lavoro più breve viene assegnato il ciclo della CPU.
Considera i cinque processi seguenti:
| Coda di elaborazione | Tempo di scoppio | Orario di arrivo |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Step 0) All'istante = 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 |
Passaggio 1) All'ora = 1, arriva il processo P3. Ma P4 ha un tempo di raffica più breve. Continuerà l'esecuzione.
Fase 2) Al tempo = 2, il processo P1 arriva con il tempo di burst = 6. Il tempo di burst è maggiore di quello di P4. Quindi, P4 continuerà l'esecuzione.
Passaggio 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.
Passaggio 4) All'ora = 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 è il più basso. Il processo P1 è sospeso.
| Coda di elaborazione | Tempo di scoppio | Orario di arrivo |
| P1 | Rimangono 5 su 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Passaggio 5) All'ora = 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 è interrotto.
| Coda di elaborazione | Tempo di scoppio | Orario di arrivo |
| P1 | Rimangono 5 su 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Rimangono 3 su 4 | 4 |
Passaggio 6) All'ora = 6, P2 è in esecuzione.
Passaggio 7) All'ora = 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 è minore.
| Coda di elaborazione | Tempo di scoppio | Orario di arrivo |
| P1 | Rimangono 5 su 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Rimangono 3 su 4 | 4 |
Passaggio 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.
Passaggio 9) Al tempo = 15, P1 termina la sua esecuzione. P3 è l'unico processo rimasto. Inizierà l'esecuzione.
Passaggio 10) Al tempo = 23, P3 termina la sua esecuzione.
Passaggio 11) Calcoliamo il tempo di attesa medio per l'esempio sopra.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Vantaggi di SJF
Ecco i vantaggi / vantaggi dell'utilizzo del metodo SJF:
- SJF viene spesso utilizzato per la pianificazione a lungo termine.
- Riduce il tempo di attesa medio sull'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 in esecuzione in batch, in cui 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, è necessario prevedere il valore del tempo di burst successivo.
- Probabilmente ottimale per quanto riguarda i tempi medi di consegna.
Svantaggi / Contro di SJF
Ecco alcuni svantaggi / svantaggi dell'algoritmo SJF:
- Il tempo di completamento del lavoro deve essere conosciuto prima, ma è difficile prevederlo.
- Viene spesso utilizzato in un sistema batch per la pianificazione a lungo termine.
- SJF non può essere implementato per la pianificazione della CPU a breve termine. È perché 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.
Sommario
- SJF è un algoritmo in cui il processo con il tempo di esecuzione più piccolo viene scelto per l'esecuzione successiva.
- La pianificazione SJF è associata a ciascun lavoro come unità di tempo da completare.
- Questo metodo di 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 che il ciclo della CPU viene allocato al processo, il processo lo trattiene fino a quando non raggiunge uno stato di attesa o viene terminato.
- In Preemptive SJF Scheduling, i lavori vengono inseriti nella coda Pronto non appena arrivano.
- Sebbene inizi un processo con un tempo di burst breve, il processo corrente viene rimosso o anticipato dall'esecuzione e il lavoro più breve viene eseguito per primo.
- SJF viene spesso utilizzato per la pianificazione a lungo termine.
- Riduce il tempo di attesa medio sull'algoritmo FIFO (First in First Out).
- Nella pianificazione SJF, il tempo di completamento del lavoro deve essere conosciuto prima, ma è difficile prevederlo.
- SJF non può essere implementato per la pianificazione della CPU a breve termine. È perché non esiste un metodo specifico per prevedere la durata del prossimo burst della CPU.