I sistemi batch sono ancora utilizzati per attività periodiche e di elaborazioni di grandi volumi di dati, sopratutto in ambito aziendale (banche e assicurazioni).
Nei sistemi batch, non ci sono utenti impazienti in attesa di una risposta, quindi gli algoritmi non-preemptive sono accettabili.
Gli algoritmi tipici utilizzati sono:
- first-come first-served (FCFS): lo scheduler assegna la CPU nell’ordine in cui i processi la richiedono
- shortest job first (SJF): lo scheduler sceglie il processo con il tempo di esecuzione più breve (assumendo che i tempi di esecuzioni siano noti in anticipo)
- shortest remaining time next (SRTN): versione preemptive di SJF
First-come First-served - FCFS
Questo algoritmo è il più semplice (facile da programmare - con linked list) tra gli algoritmi non-preemptive, infatti si basa sull’idea che viene “servito” il primo processo che arriva.
Quindi la CPU è assegnata ai processi in ordine di arrivo e c’è un’unica coda dei processi in stato ready e i processi che passano dallo stato blocked a quello ready, vengono messi in fondo alla coda.
Il problema con questo algoritmo è che in sistema con processi che hanno tempi di esecuzioni molto diversi, l’algoritmo FCFS rallenta i processi veloci a causa della mancanza di preemption.
Shortest job first - SJF
L’algoritmo SJF sceglie sempre il processo con il tempo di esecuzione più breve.
L’obiettivo di questo algoritmo è di massimizzare il throughput e minimizzare il tempo di tournaround, ovvero il tempo medio di esecuzione di tutti i processi.
Vediamo un esempio di esecuzione di 4 job A, B, C e D, con la seguente stima dei tempi di esecuzione:
- A: 8 minuti
- B: 4 minuti
- C: 4 minuti
- D: 4 minuti
Se utilizziamo l’algoritmo FCFS:
- A termina in tournaround (TA) di A sarà 8
- B termina in TB = 12
- C termina in TC = 16
- D termina in TD = 20 ora se vogliamo sapere il tournaround totale e medio saranno:
- tournaround totale = 8 + 12 + 16 + 20 = 56 minuti
- tournaround medio = 56/4 = 14 minuti
Se ora utilizziamo l’algoritmo SJF:
- B termina in TB = 4
- C termina in TC = 8
- D termina in TD = 12
- A termina in TA = 20 e quindi avremo che:
- tournaround totale = 4+8+12+20 = 44 minuti
- tournaround medio = 44/4 = 11 minuti
Quindi come notiamo con SJF otteniamo un tournaround di 11 minuti (meno del FCFS).
Il problema dell’algoritmo SJF (non-preemptive) è che per garantire il funzionamento ottimale, tutti i job devono essere disponibili al momento della decisione dello scheduler. Infatti se i job arrivano in momenti diversi (come nei sistemi interattivi), l’algoritmo non garantisce l’ottimizzazione.
Shortest Remaining Time Next - SRTN
L’algoritmo SRTN è una versione preemptive del SJF, dove il tempo di esecuzione è noto a priori.
La logica di funzionamento è molto semplice, e si basa sull’idea che quando arriva un nuovo job, il tempo di esecuzione totale (T1) viene confrontato con il tempo rimanente del job attuale in esecuzione (T2), se T1 < T2 allora il job attuale in esecuzione viene sospeso (preemption) e il nuovo job viene avviato.
In questo modo si risolve il problema del SJF, e i nuovi job arrivati vengono considerati e data una risposta rapida.