Lo scheduler è un algoritmo che basa il suo funzionamento sul fatto che ogni processo divide la propria esistenza in cicli di utilizzo della CPU e attesa di I/O.Naturalmente, un processo inizia sempre con un’operazione sulla CPU (che prende il nome di CPU-burst) per poi proseguire con un’operazione di I/O (che prende il nome di I/O-burst), e ripete quest’alternanza di operazioni per un certo numero di volte.Alla fine però il processo termina sempre con un CPU-burst.È possibile catalogare i processi in due categorie:

1. Quelli che hanno pochi CPU-burst brevi e molti CPU-burst lunghi, detti: CPU-bound.
2. Quelli che hanno pochi CPU-burst lunghi e molti CPU-burst brevi, detti: I/O-bound.

Lo scheduling della CPU è gestito dallo scheduler a breve termine, che in generale interviene ogni volta che un processo smette di usare (volontariamente o no) la CPU. A questo punto lo scheduler deve selezionare uno dei processi pronti per eseguire computazioni, quindi la scelta del processo è ristretta all’insieme dei processi in stato di Ready, e assegnargli la CPU. I processi in stato di Ready, o per essere più precisi i loro PCB, sono inseriti in una coda chiamata readyQueue che è una coda di tipo FIFO, quindi lo scheduler selezionerà i processi da assegnare alla CPU semplicemente leggendo il prossimo processo restituito da tale coda.Lo scheduler può essere con o senza prelazione a seconda che il processo lasci d’autorità o volontariamente la CPU.Scheduling senza prelazione (nonpreemptive)Lo scheduling senza prelazione non interviene mai durante un CPU-burst di un processo in esecuzione, che può occupare la CPU per tutto il tempo necessario. Questo scheduling è ottimo per massimizzare l’uso della CPU ma non per dare l’illusione all’utente che tutti i suoi processi lavorino simultaneamente, perché finché la CPU è occupata da questo processo, gli altri dovranno attendere.Scheduling con prelazione (preemptive)Lo scheduling con prelazione viene usato da quei sistemi che hanno la possibilità di interrompere un processo mentre è in stato di Running (cioè è in corso il suo CPU-burst), reinserendolo nell’insieme dei processi in stato di Ready, e dando la CPU ad un altro processo.Lo scheduler può intervenire perché il nuovo processo ha una priorità più alta di quello attualmente sulla CPU, o perché esiste un limite di tempo sull’uso della CPU che il processo ha superato, quindi sarà prelazionato e potrà finire le sue computazioni solo quando verrà di nuovo estratto dalla readyQueue.Uno scheduler nonpreemptive non presenta grossi ostacoli d’implementazione, cosi come non ne presenta lo scheduler preemptive. Quest’ultimo però deve essere accompagnato da una corretta politica di gestione dei processi cooperanti (che lavorano su dati condivisi), prelazionati.Infatti, in assenza di un meccanismo di sincronizzazione o di sicurezza (lock dei dati e gestione delle sezioni critiche), può verificarsi il seguente caso:

1. Il processo A lavora in cooperazione con il processo B, condividendo con esso un file nel quale è memorizzato un numero intero il cui valore in un dato momento e 5.
2. Al tempo T0 A legge dal file (che si trova sul disco, quindi sta effettuando un’operazione I/O burst) il numero 5 e lo memorizza in una sua vbl, poi entra in stato di Ready (perché vuole incrementare questo valore è questa operazione la deve fare la CPU) e attende che il S.O. gli dia la CPU.
3. Al tempo T1 B fa la stessa cosa di A, legge 5 e si accoda nella readyQueue dietro A.
4. Al tempo T2 finalmente A passa in stato di Running, esegue 5=5+1, quindi il valore della sua vbl è 6, ma non fa in tempo a terminare il suo CPU-burst che viene prelazionato in favore del processo B, quindi A ora è di nuovo nella readyQueue e non ha ancora salvato il nuovo valore ( =6 ) della sua vbl nel file condiviso ( =5 ).
5. Al tempo T3 quindi B che ha nella vbl il valore di 5 effettua l’incremento di 1 e nella vbl ha il nuovo valore =6, anche B viene prelazionato in favore di A e torna nella readyQueue
6. Al tempo T4 A torna sulla CPU è fa richiesta mediante una system call di scrivere il valore della sua vbl=6 sul file, il S.O. pone A in stato di Waiting e A scrive 6 nel file.
7. Al tempo T5 B fa lo stesso, e scrive nel file il suo valore che è sempre 6.

Il valore corretto avrebbe dovuto essere a questo punto 7, perché 5 + 1(sommato da A) +1(sommato da B)=7, sul file è invece presente 6.Questo perché un processo è stato prelazionato prima che potesse memorizzare le modifiche, in favore di un atro processo che lavorava sugli stessi dati e che non sapeva nulla del lavoro concorrente di altri processi. La soluzione a questo problema prevede l’adozione di politiche di sincronizzazione dei processi mediante l’uso di tecniche descritte più avanti.Criteri per scegliere l’algoritmo di schedulingIn fase di progettazione di un S.O. occorre stabilire a che tipo di attività è rivolto e l’algoritmo di scheduling deve essere scelto in base ai seguenti criteri:

1. Se si vuol massimizzare l’utilizzo della CPU è opportuno scegliere un’algoritmo di scheduling che garantisca un carico della CPU che vari dal 40 al 90%, e per questo sia un algoritmo con prelazione che senza prelazione può andar bene, ma bisogna considerare che un algoritmo con prelazione spreca un po’ di tempo di CPU (il 10% è accettabile) per la gestione dei più frequenti context switch, mentre in un algoritmo senza prelazione tutto il tempo di CPU è destinato al lavoro utente.
2. Se si vuol massimizzare il Throughput, cioè il numero di processi completati in un’unità di tempo, la scelta è l’uso di algoritmi senza prelazione, perché hanno un’incidenza minore del context-switch sul tempo totale di un processo, un solo context switch per ogni processo (altrimenti al tempo di durata del processo, va sommato il tempo di più context-switch con il risultato che nella stessa unità di tempo vengono completati meno processi).
3. Se si vuol minimizzare il tempo di turnaround, che è dato dalla somma dei tempi che il processo passa in attesa di entrare in memoria (scheduling a lungo e medio termine), in attesa nella readyQueue, in esecuzione sulla CPU e effettuando operazioni I/O burst, l’algoritmo da scegliere è con prelazione perché almeno per quanto riguarda la CPU che è una risorsa prelazionabile, nessun processo la monopolizzerà per molto tempo a svantaggio di altri processi. Ma un disco, per esempio, non è una risorsa prelazionabile, quindi se si usa questo criterio di scelta, usando un algoritmo piuttosto che un altro le differenze che si hanno non sono sostanziali, ecco perché di solito si usa di più il seguente criterio di scelta anziché questo.
4. minimizzare il tempo di attesa che è dato solo dalla somma dei tempi che il processo passa nella readyQueue, dove l’algoritmo di schedulig può incidere. In questo caso la scelta va su un algoritmo con prelazione, o almeno con priorità, cioè viene data la precedenza ai processi con tempi di utilizzo della CPU (CPU burst) minori.
5. minimizzare il tempo di risposta, cioè l’intervallo che intercorre tra lo stato di New di un processo è la stampa dei suoi primi risultati, in questo caso è opportuno usare un algoritmo senza prelazione, perché un processo che si trova in Running, non viene mai interrotto dal S.O. e può produrre un output molto prima che se ritornasse come ultimo elemento nella readyQueue a seguito di una prelazione.

Scheduling first-come, first-servedQuesto scheduler è senza prelazione ed è il più semplice sia da capire che da implementare. Usa una readyQueue implementata come FIFO, e ciò che fa, è attendere che il processo attualmente sulla CPU, termini il suo CPU burst, e richieda di effettuare un  I/O burst, di uscire dal sistema oppure di attendere un determinato evento (il completamento del lavoro di un figlio).A questo punto lo scheduler FCFS interviene selezionando il prossimo processo dalla readyQueue e lo assegna alla CPU. Questo algoritmo massimizza l’uso della CPU (che viene usata sempre), ma non è adeguato per sistemi time-sharing, perché non minimizza il tempo di attesa di un processo, che dipende dall’ordine con cui entrano nella coda.Inoltre, presenta un’inconveniente noto come effetto convoglio, dove molti processi I/O bound sono costretti ad accodarsi e ad attendere un processo CPU bound.Per esempio nell’ Applet seguente è possibile simulare tale situazione creando i seguenti processi:P1 cpu-burst= 100 io-burst=100P2 cpu-burst= 10  io-burst=10P3 cpu-burst= 10  io-burst=10P4 cpu-burst= 10  io-burst=10Ciò che accade è che il processo CPU bound (P1) occupa per molto tempo la CPU e i processi I/O bound si trovano in attesa nella readyQueue. Quando il processo CPU bound (P1) lascia la CPU e effettua operazioni di I/O i processi I/O bound la usano e la liberano presto, entrando nella waitingQueue e rimanendoci per un po’ perché il dispositivo di I/O è ancora occupato da P1. Ora la CPU è inutilizzata. Per lo stesso motivo lo sarà il dispositivo d’I/O al prossimo CPU burst del processo CPU bound (P1).Lancia L’applet , ma ricordati di deselezionare la pausa prima di creare i processi.Sheduling shortest-job-firstQuesto algoritmo, riesce a ottimizzare (minimizzando) il tempo medio di attesa dei processi nella readyQueue riordinandola in base al successivo CPU burst. Processi con il CPU burst più breve vengono eseguiti per primi. Questo dato però non è noto al sistema e quindi può solo essere calcolato basandosi sui CPU burst passati, assumendo che i futuri CPU burst saranno simili ai passati.Per predire i CPU burst questo algoritmo effettua la media esponenziale delle lunghezze dei CPU burst precedenti nel seguente modo:τ n+1 = α tn + ( 1 – α ) τ ndove:α =peso relativo alla storia recente ( α tn )  e a quella passata ( ( 1 – α ) τ n ).Se: α=0 la storia recente non ha effetto.Se α=1 ha peso solo il CPU burst recente.Se α=1/2 storia recente e passata hanno lo stesso peso.τ n+1 =Valore previsto per il CPU burst successivo.τ n =Valore previsto, calcolato in passato.α tn =Lunghezza del CPU burst attuale.I processi in stato di ready vengono, quindi, inseriti in una coda ordinata o readyQueue con priorità o in un’altra struttura dati (come un heap) dalla quale è possibile estrarre i processi in base a una certa chiave come per esempio in base al più piccolo valore di CPU burst successivo, anziché in una semplice FIFO. Questo algoritmo può essere con prelazione o senza prelazione.Con prelazione: L’algoritmo interviene anche quando, nel mentre che, un processo è in esecuzione sulla CPU, nel sistema si presenta un processo, in stato di Ready, con CPU burst successivo inferiore al CPU burst del processo attualmente in stato i Running, quindi l’algoritmo prelaziona la CPU al processo corrente in favore di quello nuovo (valgono i discorsi sulla sincronizzazione dei processi cooperanti prelazionati fatti precedentemente).Senza prelazione: Quando l’algoritmo lascia comunque finire il CPU burst del processo corrente, anche se più lungo del CPU burst di un processo nuovo entrato.Un inconveniente di questo algoritmo è la starvation.La starvation, o attesa indefinita, si ha quando un processo non viene mai eseguito perché altri processi riescono ad ottenere per primi la CPU, per esempio perché hanno una priorità più alta. Si verifica questo caso quando, nella readyQueue ordinata in base al CPU burst più breve, un processo che ha il CPU burst più alto di tutti i nuovi processi non verrà mai selezionato come processo da eseguire, perché finirà, ad ogni ordinamento, sempre in ultima posizione.Nell’Applet seguente provate a creare i seguenti processi:P1 cpu-burst=100 io-burt=a piacereP2 cpu-burst=10  io-burt=10P3 cpu-burst=10  io-burt=10P4 cpu-burst=10  io-burt=10Ciò che accade è che P1 sarà sempre in ultima posizione nella readyQueue ordinata e non verrà mai eseguito se non dopo che tutti i processi con CPU burst brevi saranno terminati. Se nel sistema continuassero ad entrare nuovi processi I/O bound, P1 resterebbe per sempre in Ready.Lancia AppletPer superare la starvation è possibile implementare un meccanismo di aging o invecchiamento del processo. Con questa tecnica un processo aumenta gradualmente nel tempo la sua priorità, fino ad arrivare ad un certo punto ad essere il processo con priorità massima e quindi sicuramente verrà eseguito.Scheduling round-robinQuesto algoritmo è un algoritmo con prelazione ed è progettato appositamente per i sistemi time sharing, visto che dà l’illusione all’utente che tutti i suoi processi procedano nel lavoro simultaneamente. Questo risultato è ottenuto commutando la CPU tra i vari processi a intervalli regolari di tempo. Tale intervallo, che deve essere di piccola entità, è chiamato quanto di tempo o time slice. La strategia del round robin seleziona il prossimo processo dalla readyQueue che è di tipo FIFO, la stessa usata dal FCFS, e assegna la CPU a tale processo. Se il processo termina il suo CPU burst prima dello scadere del quanto di tempo, lo scheduler lo mette nella waitingQueue o lo dealloca dalla memoria a seconda del motivo per cui il processo ha rilasciato la CPU. Se, invece, allo scadere del quanto di tempo il processo ha ancora lavoro di CPU da fare, lo scheduler interviene, gli prelaziona la CPU, lo inserisce nella readyQueue e dà la CPU al prossimo processo restituito dalla readyQueue. Le prestazioni di questo algoritmo dipendono dalla lunghezza del quanto di tempo, dal quale dipende anche il comportamento che, per quanti di tempo molto lunghi (più lunghi dei CPU burst dei processi), può essere lo stesso dell’algoritmo FCFS. Mentre per quanti di tempo troppo corti, l’algoritmo potrebbe prelazionare talmente frequentemente la CPU tra i processi, che “sprecherebbe” più tempo per il dispatch che per le computazioni del processo stesso, che in questo modo avanzerebbe di una piccolissima quantità di lavoro per volta, dando l’impressione all’utente che invece di un processore potente dedicato ad un solo processo, esistano tanti processori lenti che eseguono ciascuno un processo. Per esempio:Se la maggior parte dei processi hanno CPU burst = 10 e il time slice = 12 (consideriamolo molto lungo) allora l’algoritmo si comporta come il FCFS perché si ha un context switch per processo, e precisamente quando questi lascia la CPU spontaneamente. All’utente non è data l’impressione che i suoi processi siano tutti in esecuzione perché quelli nella readyQueue attenderanno la fine dei processi che di volta in volta usano la CPU.Se, invece, il time slice è per esempio = 6, sempre con processi con CPU burst=10, allora abbiamo due context switch per processo, uno che lo prelaziona all’incirca alla metà del lavoro e un altro quando il processo termina. In questo caso più processi progrediscono con il lavoro un po’ per volta (ad una velocità accettabile) è l’obbiettivo del time slice è ottenuto.Se invece il quanto è troppo breve, per esempio = 1, allora avremo talmente tanti context switch che il sistema dedicherà alle computazioni dei processi utente meno tempo di quanto è costretto a dedicarne alla gestione dei context switch, e questa è una situazione inaccettabile.L’applet seguente simula un sistema con scheduling RR, provate a variare il time slice per vedere come può diventare simile al FCFS (dopo aver creato un po’ di processi selezionate il time slice per esempio a 1000, me non dimenticate di deselezionare la pausa).

Lancia Applet

Appare evidente che la scelta del quanto di tempo deve essere attenta.