Scheduling

Scheduling

Con Scheduler o Schedulatore si intende generalmente il componente fondamentale di un SO Multitasking (in grado cioè di eseguire concorrentemente più processi o task) che si occupa di definire la sequenza con cui i processi si avvicendano nell'uso di una risorsa, in particolare della CPU (il reale avvicendamento, con il cambio di contesto, è comunque operato dal Dispatcher). Ogni processo sospeso ha il suo PCB linkato ad una specifica coda di scheduling, i processi in attesa della liberazione di una qualunque risorsa che non sia la CPU (o altro evento correlato) sono Waiting, tutti gli altri in attesa della risorsa CPU sono Ready: un generico scheduler agisce su una coda di scheduling selezionando il prossimo processo che deve operare una transizione di stato, Waiting  Ready oppure Ready  Running.

I tre tipi fondamentali di schedulatore sono lo scheduler a breve termine (o di CPU), lo scheduler a medio termine (o di Swap) e lo schedulatore a lungo termine (o di Job): il primo, quello attivato più frequentemente, svolge la funzione descritta all'inizio e si attiva tipicamente quando un processo passa nello stato Running, quando termina oppure in occasione del prerilascio nei sistemi time-sharing; il secondo opera nell'ambito della schedulazione della memoria, gestendo un'area particolare della memoria di massa - indipendente dal File System, definita Area di Swap - nella quale con operazioni di Swap-In (o dalla quale con operazioni di Swap-Out) viene trasferita all'occorrenza una certa quantità di processi Ready di cui si prevede l'imminente transizione allo stato Running; il terzo, presente soprattuto nei vecchi sistemi batch (si tenga presente che il Job è per un sistema batch l'equivalente di un Processo per un sistema time-sharing) ha la funzione di pianificare l'esecuzione di job secondari sostanzialmente quando il sistema risulta libero da processi conversazionali, tipicamente scegliendo il prossimo job da processare sulla base del banale criterio per cui la maggiore priorità va ai processi che impegnano la CPU per minor tempo. In realtà quando si parla di algoritmi di scheduling, ci si può riferire ad una generica risorsa, non necessariamente in modo esclusivo alla CPU (per esempio è stato già analizzato il funzionamento di un possibile scheduler di accessi ad un disco

Gli algoritmi di scheduling della CPU hanno l'obiettivo di garantire l'imparzialità o fairness (processi dello stesso tipo devono avere trattamenti simili) e l'efficienza (garantire che tutte le risorse siano sfruttate al massimo, compresa la CPU), e di migliorare il Throughput (numero di lavori processati nell'unità di tempo), il Turnaround o Tempo di Completamento (tempo di attesa relativo ai lavori batch, trascorso il quale il sistema restituisce i risultati), il Tempo di Attesa (che un processo deve attendere in una coda pendente per una certa risorsa, nella coda dei processi Ready se la risorsa in questione è proprio la CPU) e il Tempo di Risposta (il tempo intercorrente tra il completamento dell'inserimento dei dati di input e l'istante in cui compare il primo carattere di output), dove tipicamente tempo di risposta e throughput sono in contrasto tra loro (eseguendo in parallelo più task si aumenta lo sfruttamento globale del sistema ma diminuisce il grado di soddisfazione del singolo utente). Tra gli algoritmi di scheduling della CPU si distinguono quelli che implementano uno scheduling preemptive (o con diritto di prelazione) e scheduling non preemptive (o senza diritto di prelazione): nel primo caso lo scheduler può sottrarre il possesso della risorsa CPU al processo in ogni momento, anche quando questo potrebbe proseguire nella sua esecuzione; nel secondo caso invece lo scheduler deve attendere che il processo termini oppure cambi il suo stato di esecuzione in Ready o Waiting a seguito di una richiesta I/O o di una interruzione; gli algoritmi di scheduling della CPU possono inoltre prevedere una priorità (statica o dinamica) o essere senza priorità e le caratteristiche Sì/No preemptive e Con/Senza priorità sono tra loro combinabili. Ha senso infine classificare i processi come CPU Bound, cioè a prevalente utilizzo della CPU, oppure come I/O Bound, cioè a prevalente utilizzo di periferiche. I principali algoritmi di scheduling sono elencati di seguito

FCFS - First Come First Served

Il più semplice algoritmo di scheduling batch di tipo FIFO, non preemptive e per questo incompatibile con il time-sharing, esegue cioè i processi nell'ordine esatto in cui essi vengono sottomessi al sistema senza interromperli se non in caso di terminazione, richiesta di I/O o interrupt (in questi casi ci sarà invece una commutazione di processo attivo). In genere il suo utilizzo non risulta vantaggioso perchè produce tempi di attesa medi (che si calcola come 0 + Tempo di Utilizzo continuativo della CPU da parte del 1° processo in coda + somma dei TUC dei primi 2 processi + TUC dei primi 3 processi il tutto diviso per gli N processi in attesa) non ottimali (svantaggiosi in particolare per i processi corti) e tanto più elevati quanto più i processi che richiedono la CPU per un tempo maggiore sono ai primi posti della coda d'attesa: il caso limite negativo è quello in cui i processi vengono sottomessi al sistema esattamente in ordine decrescente rispetto al tempo di occupazione previsto della CPU (il caso ottimale si ottiene contrordinando la coda dei processi del caso peggiore). Inoltre, nell'ipotesi in cui in attesa vi siano più processi I/O bound e un unico processo CPU bound, indipendentemente dall'ordine con cui vengano inizialmente sottomessi al sistema, non appena i processi I/O bound vengono sospesi alla prima richiesta I/O, il processo CPU bound prende possesso della CPU e tutti gli altri sono costretti ad accodarsi (effetto convoy), con la conseguenza che i dispositivi I/O rimangono nel frattempo inutilizzati durante tutto il tempo continuativo che la CPU è da esso occupata (laddove questo finalmente sospenda la sua esecuzione, i processi I/O bound si riattiveranno ma avendo essi un tempo di utilizzo medio della CPU basso, la situazione precedente si ripresenterà alla successiva richiesta I/O ed essi dovranno nuovamente attendere a lungo prima di recuperare il possesso della CPU): il sistema da multiprogrammato diventa monoprogrammato de facto (un solo processo che monopolizza l'uso della CPU

RR - Round Robin

Il più semplice algoritmo di scheduling preemptive di tipo FIFO, specificamente adatto al time-sharing, che esegue i processi nell'ordine esatto in cui essi vengono sottomessi al sistema, interrompendoli (con relativa commutazione di processo attivo) ciclicamente (la coda è da intendersi qui circolare) dopo un quanto di tempo massimo prestabilito - slice (fetta) di tempo - di utilizzo continuativo della CPU, scandito da un timer (nella sua formulazione più banale si ottiene dal FCFS aggiungendo il timer); il tempo medio di attesa dipende dall'ampiezza della slice e garantisce comunque l'assenza di starvation (attesa indefinita), visto che l'ultimo processo in coda attenderà comunque un tempo minimo pari a circa (N-1)xSlice; va infine considerato l'impatto dovuto ai frequenti cambi di contesto, che aumentano l'overhead (sovraccarico) introdotto dal sistema e che impongono vincoli sull'ampiezza della slice: per mantenere prestazioni ottimali, la durata del context_switch dovrebbe essere notevolmente più breve del quanto di tempo stabilito in almeno l'80% dei casi.

SJF - Shortest Job First (detto anche SPF - Shortest Process First)

Costituisce un miglioramento del FCFS, introducendo per ogni processo una priorità inversamente proporzionale al tempo totale d'esecuzione, ed è tra gli algoritmi di scheduling batch quello che ottimizza al massimo il tempo medio di attesa: tra i processi pronti viene eseguito prima quello con il tempo d'esecuzione totale più breve e, naturalmente, il problema fondamentale da risolvere è proprio conoscere in anticipo tale informazione. Il tempo totale d'uso della CPU può essere fornito (nei vecchi sistemi era così) direttamente dall'utente e lo schedulatore accetta sulla fiducia questa previsione, inserendo il nuovo processo nella lista di quelli pronti in una posizione consona alla sua priorità presunta: una volta concessa la CPU ad un processo, se il tempo dichiarato d'uso scade prima che il lavoro sia terminato, il processo viene abortito multando in questo modo l'utente con la mancata consegna dei risultati (all'utente conviene quindi stimare sempre per eccesso il tempo richiesto). Più frequentemente, il tempo d'esecuzione di un processo viene predetto direttamente dallo schedulatore, sulla base di una stima dinamica della CPU burst (fiammata): quando un processo viene sottomesso al sistema, si vede assegnare inizialmente un tempo stimato di esecuzione totale To (in teoria arbitrariamente fissato) in base al quale viene inserito nella coda dei processi pronti in una opportuna posizione; una volta ottenuto il possesso della CPU, tale processo resta in esecuzione fino a che non termina oppure fino a che non rimane in attesa su qualche semaforo (richiesta di I/O, interrupt): in questa seconda ipotesi lo schedulatore memorizza il tempo effettivo Vo d'uso continuativo della CPU da parte del processo, ovvero la sua CPU burst effettiva, esegue la commutazione di contesto schedulando il prossimo processo pronto ed, infine, assegna al processo testè sospeso una nuova posizione nella coda, sulla base della prossima CPU burst presunta, stimata tipicamente mediante lo strumento della cosiddetta media esponenziale

T = a Vo + (1-a) To con 0 < a < 1

ovvero una media pesata della CPU burst inizialmente prevista e della CPU burst effettiva, espressione che diventa alla schedulazione N-esima

Tn = a Vn + (1-a) Tn

e che è possibie eventualmente sviluppare nella

a Vn + a (1-a) Vn-1 + .. .. + a (1-a)^n Vo + (1-a)^(n+1) To

in cui tutti i precedenti CPU burst effettivi compaiono esplicitamente: all'aumentare di a assumono maggiore peso nella stima le CPU burst effettive, in particolare quelle più recenti hanno maggior peso delle pregresse e al limite per a  1 il prossimo CPU burst stimato tende a coincidere con quello precedente (il processo tende a conservare nella coda la priorità che aveva prima dell'ultima sospensione); al diminuire di a assumono invece maggiore peso la CPU burst stimata in origine To e le CPU burst effettive pregresse, ovvero contano sempre meno quelle via via più recenti, e al limite per a  0 il prossimo CPU burst stimato tende a coincidere con quello originario To (il processo tende a conservare sempre la stessa priorità che aveva all'inizio). In pratica, si può immaginare che un generico processo sia sostanzialmente di tipo CPU bound (CPU burst lunghi) oppure di tipo I/O bound (CPU burst corti) e che quindi, rispettivamente, l'algoritmo tenda ad associargli un priorità più bassa (all'aumentare del tempo stimato d'uso la priorità scende) o più alta (al diminuire del tempo stimato d'uso la priorità sale); più realisticamente, durante la sua esecuzione, un processo può alternare fasi più o meno lunghe in cui è CPU bound e fasi in cui è I/O bound: all'aumentare di a la CPU burst stimata tiene conto maggiormente della storia recente, quindi tenderà a conservarsi lunga (minore priorità) se il processo è attualmente CPU bound, breve (maggiore priorità) se invece è I/O bound, fornendo daltronde una stima tipicamente inadeguata del CPU burst in corrispondenza di transizioni del tipo di "bound" del processo; al diminuire di a invece la CPU burst stimata tiene conto maggiormente della storia pregressa, per cui varierà lentamente tendendo a discostarsi poco dal valore di To, il che è utile se il processo effettua molte transizioni tra CPU bound e I/O bound (la sua priorità non oscilla troppo) ma non se si mantiene sostanzialmente CPU bound oppure I/O bound (in tal caso sarebbe opportuno assegnargli rispettivamente una priorità tendenzialmente bassa o alta

SRTF (SRN) - Shortest Remaining Time First/Next (detto anche preemptive SJF)

L'algoritmo SJF classico non ammette prelazione per cui se, durante l'esecuzione (quindi in piena CPU burst) di un processo, viene aggiunto alla coda dei Ready un nuovo processo con una CPU burst stimata inferiore (quindi maggiore priorità) rispetto al processo attualmente in esecuzione, quest'ultimo non viene comunque interrotto e il nuovo processo pronto è costretto ad attendere (un possibile scenario è B in esecuzione, B esegue una richiesta I/O e viene sospeso, A sopraggiunge in esecuzione, il semaforo su cui B è in attesa viene sbloccato ma A è ancora in esecuzione e B non può tornare Running prima che A non sia terminato o sospeso a sua volta). Il SRTF al contrario ammette la prelazione, per cui in generale l'inserimento nella coda dei processi pronti di un processo a priorità più elevata di quello in esecuzione produce la sospensione di quest'ultimo (nello scenario precedente, se a B appena sbloccato viene associata una priorità elevata, A viene sospeso a vantaggio di B). Una variante del SRTF è caratterizzata da un preemptive sincrono, anzichè asincrono, e prevede un timer che, trascorso un tempo massimo T di esecuzione continuativa di un processo (per esempio CPU bound, quindi tendente ad avere CPU burst lunghi), sospende forzatamente il processo in esecuzione, aggiorna il suo CPU burst semplicemente decurtandolo di T e schedula il prossimo processo a più basso CPU burst (più alta priorità) nella coda dei processi pronti (naturalmente, in linea di principio, nulla vieta se il processo sospeso è quasi terminato, che sia ancora esso quello a massima priorità e che quindi venga immediatamente ripreso): in questo modo la verifica dell'esistenza di un processo più prioritario non avviene ad ogni nuovo inserimento in coda Ready ma periodicamente.

Code multiple

Un algoritmo di scheduling a code multiple prevede la creazione di N code a diversa priorità (tali che tutti i processi di una stessa coda si assumono aventi la stessa priorità), la definizione di un criterio di allocazione del generico processo ad una specifica coda e l'assegnazione di un algoritmo di scheduling a ciascuna di esse; ad ogni nuovo processo viene inizialmente associato un valore discretizzato di priorità, viene allocato come processo pronto in via permanente ad una specifica coda e viene gestito secondo le strategie previste dallo scheduler attivo su quella coda. Caso particolare è quello in cui ci siano soltanto due code, una per i processi conversazionali (gestita con algoritmo RR) e una meno prioritaria per i job batch (gestita con algoritmo FCFS): quando è in esecuzione un job batch ma un nuovo processo conversazionale è pronto, il primo subisce il prerilascio e la CPU viene automaticamente assegnata al secondo in quanto più prioritario; per evitarne lo starvation, laddove non vengano eseguiti per troppo tempo, si può operare una promozione a RR dei job batch ripartendo il tempo totale di CPU tra le due code, per esempio assicurando l'80% di esso alla coda foreground ma almeno il 20% anche alla coda background.

Multilevel Feedback o Code multiple con feedback

Un algoritmo di scheduling a code multiple con feedback, rispetto al caso precedente, definisce ulteriormente un criterio per variare nel tempo la priorità di un processo e quindi la sua coda di appartenenza. Un criterio spesso adottato prevede di associare un quanto di tempo o slice costante a ciascuna coda, crescente al variare della coda, ed in particolare assegnando una slice più corta ad una coda a maggiore priorità e una slice più lunga ad una coda a minore priorità: un processo che una volta in esecuzione usi la CPU senza sospendersi (richiesta di I/O, interrupt e in generale attesa su semaforo) per l'intera slice di tempo che gli è stata assegnata verrà declassato nella adiacente coda a minore priorità ma a slice di tempo più ampia, viceversa laddove impegni la CPU solo per una parte (tipicamente meno della metà) della slice assegnata verrà promosso nella adiacente coda a maggiore priorità ma a slice di tempo meno ampia; nel primo caso il processo viene interrotto dal timer quando sta usando la CPU quindi è presumibilmente un processo CPU bound: declassandolo esso attenderà più tempo prima di ripartire ma rimarrà in esecuzione più a lungo (in assenza di sospensioni), avendo dunque maggiore probabilità di terminare e liberare un posto nella coda; nel secondo caso il processo si sospende prima che intervenga la prelazione dello scheduler quindi è presumibilmente un processo I/O bound: promuovendolo esso potrà riprendere più presto la sua esecuzione ma per un tempo più limitato in coerenza col suo status di processo soggetto a sospendersi con frequenza; in generale un processo naviga tra le code, aumentando la sua priorità quando diventa I/O bound e diminuendola quando diventa CPU bound.

Altri approcci allo scheduling sono lo scheduling garantito e lo scheduling a lotteria. Nello scheduling garantito, lo scheduler divide il tempo d'utilizzo della risorsa tra gli N processi in competizione e la priorità di un processo in attesa dipende dal tempo d'uso precedente (del singolo processo) confrontato col tempo complessivo d'uso (da parte di tutti i processi) della risorsa diviso per N. Nello scheduling a lotteria, ad ogni processo viene assegnato un certo numero di tickets, lo scheduler estrae un ticket e seleziona quindi del tutto casualmente un processo in attesa.

In un sistema real-time il tempo di risposta è un fattore determinante per la correttezza della risposta stessa. Ogni processo o task ha una deadline che rappresenta l'istante massimo in cui la sua elaborazione deve essere completata, e si parla di hard task se il mancare la deadline produce effetti catastrofici, di soft task se invece si ha solo un degrado delle prestazioni: un sistema capace di gestire hard task è detto hard real-time. Si possono distinguere task periodici o time driven attivati automaticamente dal kernel a intervalli regolari, e task aperiodici o event driven attivati al verificarsi di un evento o attraverso una esplicita invocazione della primitiva di attivazione. Con un algoritmo Rate Monotonic (RM) ciascun task ha una priorità inversamente proporzionale alla sua frequenza. Con un algoritmo Earliest Deadline First (EDF) lo scheduler sceglie dinamicamente il processo la cui deadline assoluta è più vicina nel tempo. Con un algoritmo Laxity lo scheduler sceglie dinamicamente il processo la cui elaborazione termina più vicina alla deadline. In tutti i casi, assegnati M eventi periodici, ciascuno di periodo Ti e tempo d'uso massimo (worst case) di CPU per gestirlo Ci, si considera la deadline relativa Di massimo intervallo di tempo che intercorre tra la richiesta di attivazione e la deadline assoluta) pari a Ti e una stima del carico della CPU è data da U = somma dei rapporti Ci / Ti al variare di M: se U>1 si assume che il sistema sia sovraccaricato  e quindi non schedulabile.