Shortest Job First (SJF): esempio preventivo e non preventivo
Nathaniel Brooks
⚡ Riepilogo intelligente
Shortest Job First (SJF) è un algoritmo di pianificazione della CPU che seleziona il processo con il tempo di esecuzione più breve da eseguire successivamente. Può essere preemptive o non preemptive e riduce significativamente il tempo medio di attesa dei processi.
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, riducendo così potenzialmente i tempi di completamento.
- Migliora la produttività offrendo lavori più brevi, che dovrebbero essere eseguiti per primi e che generalmente hanno tempi di completamento più brevi.
SJF non preventivo
Nella pianificazione non preemptive, una volta che il ciclo della CPU viene assegnato a un processo, quest'ultimo lo mantiene fino a quando non raggiunge uno stato di attesa o non viene terminato.
Consideriamo i seguenti cinque processi, ognuno dei quali ha un proprio tempo di esecuzione e 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) All'istante t = 0, P4 arriva e inizia l'esecuzione.
Passo 1) All'istante t=1, arriva il processo P3. Ma P4 necessita ancora di 2 unità di esecuzione per completare l'esecuzione. Continuerà quindi 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 t=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 di attesa medio per l'esempio sopra riportato.
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 SJF preemptive, i processi vengono inseriti nella coda dei processi pronti man mano che arrivano. Il processo con il tempo di esecuzione più breve inizia l'esecuzione. Se arriva un processo con un tempo di esecuzione ancora più breve, il processo corrente viene rimosso o interrotto e al processo con il tempo di esecuzione più breve viene assegnato un ciclo di CPU.
Si considerino 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) All'istante t = 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) All'istante t=1, arriva il processo P3. Ma P4 ha un tempo di esecuzione 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) All'istante t=5, arriverà il processo P2. Vengono confrontati i tempi di esecuzione di P1, P2, P3 e P5. Il processo P2 viene eseguito perché il suo tempo di esecuzione è il più breve. Il processo P5 viene interrotto.
| 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 t = 6, P2 è in esecuzione.
Passo 7) All'istante t=7, P2 termina la sua esecuzione. Viene confrontato il tempo di esecuzione di P1, P3 e P5. Il processo P5 viene eseguito perché il suo tempo di esecuzione è minore.
| 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 t = 10, P5 terminerà la sua esecuzione. Viene confrontato il tempo di esecuzione di P1 e P3. Il processo P1 viene eseguito perché il suo tempo di esecuzione è minore.
Passo 9) All'istante t=15, P1 termina la sua esecuzione. P3 è l'unico processo rimasto. Inizierà l'esecuzione.
Passo 10) All'istante t=23, P3 termina la sua esecuzione.
Passo 11) Calcoliamo il tempo di attesa medio per l'esempio sopra riportato.
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/benefici 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 una specifica serie 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 la soluzione ottimale in termini di tempo medio di elaborazione.
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.
- Ciò porta alla fame senza ridurre il tempo medio di rotazione.
- È difficile conoscere la lunghezza della prossima richiesta della CPU.
- Il tempo trascorso dovrebbe essere registrato, il che comporta un maggiore carico di lavoro per il processore.
