Appunti Sistemi operativi - parte 2

Lezione 6

Riallacciandoci a quanto detto nella scorsa lezione, possiamo dire che l’algoritmo FCFS ha un vantaggio fondamentale in quanto è l’algoritmo a minimo overhead e quindi, anche se soffre dell’effetto convoglio e quindi i processi I/O vengono ad essere ritardati a causa dei processi CPU bound, l’algoritmo di scheduling è molto leggero e l’overhead è minimo. Tale tipologia di algoritmo risulta funzionare bene lì dove il carico del sistema è uniforme e quindi se non ci sono processi che hanno tempi di CPU molto diversi tra di loro, questo algoritmo costituisce una buona scelta.

Gli algoritmi di tipo Round Robin privilegiano invece i tempi di risposta e quindi l’interattività e quei parametri user oriented visti nella lezione precedente; per questa tipologia di algoritmo, abbiamo che il quanto di tempo deve essere scelto in modo che q non sia né troppo grande né troppo piccolo. Se q dovesse essere troppo grande, l’algoritmo tenderà ad essere di tipo FCFS, mentre se è troppo piccolo, si ha un aumento dell’overhead ma diminuisce il tempo di risposta. Abbiamo visto che il tempo q non deve essere mai minore del tipico tempo di servizio che ha un processo, altrimenti si avrebbe un overhead ancora maggiore in quanto anche i processi di I/O non riuscirebbero a sfruttare il quanto di tempo per fare le proprie operazioni e continuerebbero a ciclare sulla CPU. Il quanto di tempo va quindi dimensionato sul tempo di servizio di un singolo processo.

Shortest Process Next (SPN)

Lo Shortest Process Next è un primo esempio non preemptive di algoritmo che tende a massimizzare dei parametri system oriented. Nella fattispecie, tale tipologia di algoritmo cerca di minimizzare il tempo di esecuzione di tutti i processi e quindi minimizza il tempo di Timearound dei processi. Questa tipologia di scheduler privilegia molto i processi di I/O. Vedremo nel seguito che la versione preemptive di questo algoritmo non penalizza affatto i processi di I/O e quindi è molto utilizzata lì dove ci sono carichi prettamente di I/O.

Vediamo ora come si calcolano i tempi di servizio. L’algoritmo SPN richiede la conoscenza del tempo di servizio in un processo. Consideriamo ad esempio di avere gli stessi processi considerati precedentemente e quindi supponiamo di considerare l’esecuzione del processo A. Il fatto che tale processo abbia un tempo di esecuzione pari a 3 vuol dire che A comincia la propria esecuzione e va in READY; tale processo occuperà la CPU per 3 quanti di tempo e poi si sospenderà; dopo l’esecuzione di A si sospenderà, per poi rieseguire ed occupare nuovamente la CPU per 3 quanti di tempo. Intendiamo quindi per tempo di servizio il tempo che il processo prende alla CPU per la sua esecuzione. Nell’esempio considerato avremo allora che il processo B occuperà la CPU per 6 quanti di tempo e così via per gli altri processi. I tempi di CPU dei processi considerati fino ad ora sono tutti tempi uguali; in realtà non è sempre così, ma restiamo in queste ipotesi.

Se volessimo capire all’istante i+1, quando viene schedulato il processo, qual è il suo tempo di CPU, possiamo dire che il tempo di CPU all’istante i+1 sia uguale alla media dei tempi Tj diviso il numero di campioni i. Si considera quindi la media esponenziale dei tempi di CPU. In generale, abbiamo che i tempi che fino ad ora abbiamo considerato costanti nella realtà non lo siano, e questo dipende dal tipo di operazioni che vengono ad essere svolte.

Supponiamo ad esempio che un processo P abbia fatto K esecuzioni e supponiamo di conoscere tutti i suoi tempi di CPU per prevedere il tempo di CPU del processo al passo K+1, che serve all’algoritmo SPN per sapere quale processo andare a schedulare, in quanto il processo che verrà ad essere schedulato sarà quello con il tempo di servizio minore e quindi gli occorre avere stima dei tempi di servizio per i vari processi. Per stimare tale tempo di servizio, come abbiamo visto sopra, quello che viene ad essere fatto altro non è che una media aritmetica. La prima esecuzione viene ad essere stimata staticamente, ad esempio andando a vedere quelle che sono le linee di codice.

La media aritmetica può anche essere scritta come possiamo quindi andarci a conservare le medie e conservandoci le medie possiamo in qualche modo trovare la media k+1.

Il problema è che la media aritmetica va bene fino a quando i tempi sono tutti uniformi, ma tipicamente i tempi di servizio di un processo non sono costanti ma hanno una certa variazione iniziale. Per seguire queste curve non si usa mai una media aritmetica, ma una media esponenziale. La media esponenziale ci dice che il tempo di CPU al passo n+1 sarà uguale a:

La rapidità con cui le stime seguono la curva dipendono da come si sceglie il parametro α. Se α = 0, i tempi sono costanti; altrimenti, se α = 1, la stima al passo n+1 sarà uguale al tempo di CPU al passo precedente. Quindi più α è grande, tende a 1, più contano gli ultimi campioni; più α è piccolo, più terremo a mente gli altri campioni nella stima. Ecco perché si considera questa media esponenziale.

I processi di qualunque tipo di sistema variano e non hanno gli stessi tempi di CPU, quindi i programmi tipicamente hanno dei tempi di CPU iniziali che sono abbastanza bassi in quanto fanno I/O, hanno poi delle parti centrali dove usano la CPU e infine hanno delle parti finali dove usano di nuovo I/O. Per tale ragione, come abbiamo detto prima, abbiamo che la media aritmetica non va bene e viene per tanto utilizzata la media esponenziale che basa il suo utilizzo sul parametro α che è un parametro compreso tra 0 ed 1 ed indica quanti campioni bisogna tenere in considerazione nella predizione.

Media esponenziale e stima dei tempi di CPU

Nel primo caso (α = 0) scritto in rosso, abbiamo che la stima fatta per il passo n+1 sarà uguale alla stima fatta al passo n e quindi abbiamo che i tempi di CPU risulteranno essere costanti. Nel secondo caso (α = 1), vengono ad essere completamente scartati i valori vecchi e si prende come stima l’ultimo valore della CPU. Se sviluppiamo in serie l’esponenziale, otteniamo il peso dato ad ogni processo di CPU che è rappresentato nella serie scritta sopra come (1-α).

Se andiamo a plottare questi pesi per i diversi valori di α, possiamo andare a vedere come pesano i valori passati. Se consideriamo ad esempio un valore di α alto, nel caso in esame ad esempio consideriamo α = 0.8, possiamo osservare come conterà moltissimo il primo campione, poco il secondo mentre il terzo sarà quasi trascurabile. Per α = 0.8 possiamo dire che sono importantissimi gli ultimi due campioni. Per quanto riguarda invece α = 0.2, possiamo osservare che il primo campione vale 0.2, il secondo 0.18 e si procede fino ad arrivare al 10° campione. Per quanto riguarda invece α = 0.5, ci troviamo in una via di mezzo dove si vanno a prendere fino ai primi 5 campioni. La scelta di un α viene ad essere fatta dall’ingegnere a partire dalla variabilità e dai tempi di CPU studiando bene quelli che sono i processi ed i tempi di carico.

Questo tipo di algoritmo viene ad essere utilizzato in sistemi embedded come ad esempio per lo scheduling di alcuni sensori, come può essere quello dell’apertura delle porte, e non in sistemi general purpose, perché se abbiamo un task aperiodico e quindi un task dove non è possibile predire quando un processo verrà ad essere schedulato, risulterà difficile andare a fare una predizione accurata di α.

Nell’esempio considerato, abbiamo che la curva in nero sono i valori dei processi osservati, la media esponenziale è la prima curva a quadrati in bianco che non risulta essere un granché in quanto non andrà mai a convergere. Se scegliamo un α = 0.8, possiamo osservare che per tale valore la nuova curva che otteniamo segue bene la curva di partenza e appena la curva si stabilizza e quindi i tempi di CPU si stabilizzano, abbiamo che si andrà a stabilizzare anche la media aritmetica. Possiamo allora dire che l’α grande va bene per quelle curve che hanno poi una situazione di regime.

Nella figura sopra, possiamo osservare come la curva con rombo bianco rappresenti l’errore che si commette. Possiamo allora dire che l’errore che si commette quando i punti variano, essendo nell’esempio considerato la pendenza del grafico costante, l’errore che si andrà a commettere risulterà essere un errore importante. Se usiamo invece un α più piccolo, ad esempio α = 0.5, abbiamo che la curva che dà origine alla media risulterà essere meno sensibile all’andamento della curva che si intende seguire e comunque garantisce una certa convergenza.

Nella pratica, per fare il tuning del parametro α, quello che si fa oltre all’analisi di sensibilità è una caratterizzazione del carico della macchina.

Versione preemptive e feedback

La versione preemptive del SPN prende il nome di Shortest Remaining Time. Nella versione preemptive, non appena arriva un processo che ha un tempo di esecuzione minore rispetto al tempo di servizio del processo in esecuzione, quest’ultimo viene sospeso a favore del primo. Ad esempio, nel nostro caso abbiamo che il processo A è in esecuzione ma appena arriva il processo B che è più lungo, A continua la sua esecuzione e quando finisce viene ad essere eseguito B. Rispetto al caso precedente, quando arriva C, avendo C un tempo di esecuzione minore di B, la CPU viene ad essere prelazionata a favore di C e B viene ad essere ritardato. Mentre C è in esecuzione, arriva D che ha un tempo di esecuzione pari a 5; a C mancano 2 e quindi continua ad eseguire mentre D viene ad essere ritardato. Quando C termina, la CPU viene ad essere assegnata ad E che nel frattempo è sopraggiunto ed ha un tempo di servizio minore rispetto a B e D che si trovano nella coda dei processi pronti. Quando E termina, il controllo della CPU viene ad essere passato a B che può finalmente terminare il suo processo. Infine, il controllo passa a D che viene eseguito e termina.

Possiamo osservare in questo esempio come il processo E non venga mai ad essere ritardato e questo ci consente di dire come questo algoritmo favorisce tremendamente i processi di I/O non ritardandoli affatto. Questi due algoritmi di cui abbiamo parlato proprio per l’impossibilità di predire il tempo di esecuzione con sufficiente accuratezza non possono essere adoperati per scopi general purpose.

Per i sistemi general purpose che devono predire i processi di I/O, se non si conosce il futuro, è possibile però conoscere il passato e per tale categoria di problemi esiste la seguente tipologia di algoritmi. Per gli algoritmi Feedback si prende appunto il feedback sul tempo di esecuzione speso per i processi del sistema e quindi è possibile dire che il tempo speso è correlato al tempo di CPU e quindi è possibile incominciare a fare delle scelte che sono similari a quelle fatte per gli algoritmi precedenti. L’obiettivo per gli algoritmi SPN ed SRT è lo stesso ed è quello di andare a favorire in qualche modo i processi di I/O.

L’obiettivo degli algoritmi di Feedback è quello di avere più code, ogni coda ha una sua priorità. Quando arriva un processo a priorità P questo processo viene ad essere messo nella coda a priorità 0. P viene ad essere poi schedulato ed accade che o P finisce e quindi se ne va dal sistema, se P se ne va invece per via di un timer o perché sono state fatte operazioni di I/O, abbiamo che P non viene più messo nella coda a priorità 0 ma verrà messo nella coda a priorità 1. La coda a priorità 1 verrà ad essere schedulata quando la coda a priorità 0 risulterà essere vuota, quando tutti gli altri processi di priorità 0 sono terminati verrà quindi ad essere data una seconda chance a P che verrà nuovamente ad essere schedulato. Questa volta, abbiamo che se P finisce, bene; altrimenti, come descritto prima, P verrà ad essere messo in un’altra coda con priorità 2 e così via fino ad arrivare alla priorità n.

Possiamo osservare come questo scheduler tenti sempre di favorire i processi di I/O perché tali processi utilizzano poco il processore e quindi di norma seguono come percorso quello di entrare nella coda, arrivare al processore e poi si sospendono. I processi di CPU, invece, sono quelli che come il processo P descritto nell’esempio tenderanno a farsi tutto il giro delle code.

Questa è una classe di algoritmi di scheduler, tipicamente ogni coda avrà poi un suo scheduler. La coda più utilizzata adopererà il Round Robin con quanti di tempo diversi che vanno da un quanto di tempo pari a 2^n-1 per la coda 1, 2 per la coda 2 fino ad arrivare ad un quanto di tempo pari a 2 per la coda n. Il problema risulterà essere la coda a priorità n e questo accade perché ad ogni coda si aumenta il quanto di tempo per dare più chance al processo che sta già da molto tempo all’interno del sistema di finire. Quando si arriva però all’ultima coda, si trovano tutti quei processi che sono molto CPU bound e che si sono fatti il giro completo. Per tale ragione, abbiamo che questi processi possono essere schedulati o con il quanto di tempo pari a 2^n-1 oppure con un algoritmo di tipo FCFS in modo che una volta arrivati a questa coda siamo sicuri che i processi li andiamo ad esaurire.

Questo algoritmo soffre di Starvation in quanto se abbiamo un processo in una coda ma arrivano sempre processi più veloci del processo in coda, tale processo non verrà mai ad essere servito. Per tale ragione si può considerare una variante di tale algoritmo che consente di tenere conto dell’aging o meglio del cambiamento della priorità dei processi; questo meccanismo consente ai processi che si trovano nel sistema da molto tempo di essere rimessi in circolo per avere più chance di finire. Ogni coda ha un proprio algoritmo di scheduler; quello più adoperato è che per ogni coda vi è un algoritmo di scheduling Round Robin con quanto tempo 2 dove n è l’ennesima coda. L’ultima coda ha invece uno scheduler FCFS per fare in modo che i processi che arrivano in questa coda vengano poi finiti. In questo algoritmo i processi di I/O sono favoriti mentre rispetto agli algoritmi SRT abbiamo che questo algoritmo è migliore o peggiore a seconda di come andiamo a configurare il quanto di tempo all’interno della coda 0. In un algoritmo SRT abbiamo che il processo non viene ritardato; possiamo avere lo stesso effetto se e soltanto se il quanto di tempo della coda 0 è sufficiente a far concludere il processo e quindi nell’esempio in considerazione risulti essere maggiore di 1.

Lezione 7

Parliamo di SO time sharing e quindi a partizione di tempo. In questa tipologia di sistemi, abbiamo che negli algoritmi a condivisione di tempo di solito è implementata una tipologia di algoritmo Round Robin, dove abbiamo che ad ogni processo è associato un quanto di tempo ed il tempo di CPU è condiviso tra i vari processi. Quello che si ottiene rispetto alle metriche di troughput, tempi di latenza, tempi di risposta o tempi di timearound è qualcosa da capire perché il favorire una tipologia di algoritmo rispetto ad un’altra andrà ad incidere in positivo o in negativo su una metrica rispetto ad un’altra. Come vedremo più avanti, Linux non usa l’algoritmo di Round Robin in quanto tale tipologia di algoritmo va a svantaggio di alcuni processi come ad esempio i processi di I/O bound che sono una tipologia di processi rispetto ai CPU bound che utilizzano poco la CPU.

UNIX introduce quello che è il concetto vero e proprio di SO, anche se nella slide sopra la shell-oriented viene ad essere introdotto come contro. Abbiamo che UNIX è stato uno dei primi SO ad introdurre un terminale e questo poi è diventato lo standard. L’immagine sopra presenta la genealogia dei vari sistemi basati su UNIX e possiamo vedere come la creazione di Linux si aggiri intorno agli anni 90. Dopo, in parallelo, possiamo osservare che ci sono stati diversi SO basati su UNIX; infatti, già a partire dagli anni 70 ne sono stati implementati diversi. Possiamo osservare che nella slide sopra mancano alcuni SO come ad esempio Android e VMWhere che viene ad essere usato per la virtualizzazione.

Il sistema MULTICS era scritto completamente in linguaggio Assembly e questo rendeva difficile portarlo in altre architetture hardware, essendo il linguaggio Assembly fortemente collegato all’architettura hardware dove è eseguito. Quanto sviluppato alla Berkeley University fu uno dei precursori del sistema MAC OS o anche di Solaris.

Lo standard Posix fu uno standard molto importante per l’epoca che diede il via a tutta una serie di standardizzazioni per sviluppare applicazioni. Questo standard Posix permise quindi di favorire la portabilità degli applicativi permettendo di avere un’interfaccia comune che poteva essere adoperata da tutti gli sviluppatori di applicativi multi processo e tutti gli sviluppatori dovevano adoperare quel setting di librerie, ad esempio, che erano messe a disposizione. Dopo gli anni 90 si comincia ad avere quella che è la vera e propria infanzia per il sistema Linux.

Nei sistemi basati su UNIX abbiamo un’architettura a livelli, come possiamo osservare dall’immagine sopra presenta due modalità di esecuzione, la modalità Kernel e la modalità Utente. Per passare dall’esecuzione in una modalità piuttosto che un’altra, bisogna fare tutta una serie di chiamate verso l’hardware e per arrivare all’amp;rs