Appunti Sistemi operativi - parte 4

Lezione 15

Modello ad ambiente globale

Nel modello ad ambiente globale abbiamo che le risorse sono risorse condivise, la risorsa vedremo essere la memoria e quindi questa memoria risulterà essere condivisa tra più processi. Questo ci porta a dover disciplinare e quindi programmare e sincronizzare in modo da evitare problemi di cooperazione e disincronizzazione.

Nel modello a scambio di messaggi abbiamo che le risorse sono locali ai processi. Per locali si intende che solo il processo che possiede la risorsa può accedervi. In questo secondo modello non si hanno problemi di competizione in quanto un solo processo potrà accedere alla risorsa che è locale ad esso, questo modello risulterà essere più semplice in quanto bisognerà focalizzarsi solo su problemi di cooperazione.

Cominciamo con il vedere il modello ad ambiente globale, in questo caso abbiamo che più processi competono nell’uso di una risorsa e quindi le risorse sono condivise e il loro utilizzo deve essere disciplinato al fine di una buona programmazione.

Nel controllo delle risorse si hanno principalmente 3 tipi di problemi.

Mutua esclusione

Per la mutua esclusione bisogna garantire che più processi che competano nell’utilizzo di una risorsa accedano uno alla volta ed utilizzino la risorsa in modo che non ci siano conflitti nell’uso.

Per una regione critica dobbiamo capire come disciplinarne l’accesso e quindi come accedere in questa regione e come rilasciarla. Una regione critica deve essere caratterizzata con una serie di istruzioni per l’accesso e da due entry point che chiameremo enter_region e leave_region. Questi due entry point specificano l’ingresso e l’uscita di un processo. Un processo che vuole entrare in una regione critica chiama enter_region, esegue le istruzioni della sezione critica e quando lascia dovrà chiamare una leave_region.

Abbiamo bisogno di un ingresso e di un’uscita in quanto un processo alla volta deve entrare in questa regione critica.

In pratica, quello che stiamo dicendo è che un processo per eseguire una regione critica deve eseguire una procedura che prende il nome di enter_region. Questa procedura, se il processo che la invoca è l’unico processo che vuole accedere alla risorsa, gli lascia il controllo e lo lascia accedere. A questo punto il processo accede, esegue il comando che nell'esempio considerato è I ed invoca la leave_region per lasciare la sezione in modo da lasciare spazio ad altri processi che vogliono eseguire questa regione critica.

Deadlock e Starvation

Un esempio di deadlock lo si ha quando si hanno due processi che attendono vicendevolmente una risorsa che hanno ma sostanzialmente questa risorsa non viene mai rilasciata perché si attende l’altro. È come se, ad esempio, ci sono due persone, una che ha un foglio e l’altra la penna, ed uno aspetta che l’altro rilasci la carta per poter scrivere mentre l’altro aspetta che l’altro rilasci la penna. Le due persone in questo modo resteranno in attesa indefinita che prende il nome di Deadlock.

La starvation, invece, è uno di quei problemi che abbiamo già indagato e che si viene a manifestare in quei sistemi a priorità. Sostanzialmente possiamo definire un fenomeno di Starvation quando, ad esempio, si ha un processo a bassa priorità che ha un’attesa indefinita per l’assegnazione della risorsa e questo accade perché se arriva un flusso di processi ad alta priorità il processo a bassa priorità ha il rischio di non vedersi mai assegnata la risorsa.

Nel corso dello scheduling abbiamo visto come questo problema viene ad essere risolto andando ad aumentare la priorità. Anche in questo contesto cercheremo di indagare nel profondo questa problematica.

N.B: Il Deadlock possiamo dire che è uno stallo che non si sbloccherà mai fino a quando non ci sarà un intervento esterno. Per quanto riguarda invece la Starvation abbiamo che lo stallo è indefinito e sussisterà fino a quando continueranno ad arrivare processi ad alta priorità.

Requisiti e soluzioni

Consideriamo ad esempio l’ultimo requisito e supponiamo il caso in cui abbiamo che la sezione critica del nostro programma sia la stampa di una lista a puntatori. Quello che facciamo è qualcosa del tipo: abbiamo che non possiamo dire che il tempo di permanenza di un processo nella regione critica è sempre finito in quanto se supponiamo, ad esempio, che a questo programma venga passata una lista toroidale o una lista con il problema dei puntatori, abbiamo che questo while non finirebbe mai di eseguire.

Questo esempio banale mette in luce che questo tipo di cicli sono poco robusti a differenza delle strutture dati. Per soddisfare il requisito di mutua esclusione si usano ad esempio delle guardie che vengono ad essere usate per fare delle Static Analysis.

Se nell’esempio in questione mettiamo un contatore (CONT) e all’esecuzione del while aggiungiamo un’altra condizione (CONT > N_MAX_ITERAZIONI) ed aggiungiamo alla fine del ciclo while l’incremento del contatore (CONT++), abbiamo che il contatore rappresenterà una guardia in quanto in questo caso questa variabile contatore ci assicura che il ciclo while, anche se ha degli errori, anche se gli passiamo una struttura dati diversa da una struttura toroidale, da questo ciclo riusciremo sempre ad uscire.

Implementazione delle funzioni enter_region e leave_region

Vediamo ora come devono essere implementati la enter_region e la leave_region. Dobbiamo ricordarci che siamo in un ambiente multiprocesso e quindi più processi possono richiedere l’accesso a questa sezione critica.

Per garantire la mutua esclusione dobbiamo andare a disabilitare l’interrupt. Per quanto riguarda un sistema multiprocessore disabilitare l’interrupt non basta in quanto sarà possibile fare accesso in memoria oppure andare ad abilitare altri processori e quindi deve essere sostanzialmente disabilitato l’accesso al bus di memoria di modo da essere sicuri che un processo all’interno di un processore non venga ad essere mai interrotto e quindi è possibile essere sicuri che quando si entra nella sezione critica non ci sia mai un’interruzione.

Una prima soluzione semplice che ci può far risolvere il problema della mutua esclusione è quella di utilizzare la variabile lock.

Possiamo considerare una variabile lock=0 e questo ci indica che la sezione critica è libera. Possiamo poi porre una condizione con l’if che ci dice che nel caso la variabile lock è proprio 0, allora poni lock=1 ed esegui la sezione critica. Una volta eseguita la sezione critica, facciamo porre lock=0 e facciamo abbandonare la sezione critica.

In questo modo abbiamo che se un processo P1 entra, questo trova lock=0, pone lock=1 ed esegue la sezione critica, ma se nel frattempo un altro processo P2 cerca di accedere alla sezione critica trova lock=1 e non può accedere e dovrà aspettare e quindi farà un goto A.

Una variabile lock potrebbe sembrare una soluzione al problema, ma abbiamo che questa soluzione non funziona in quanto l’accesso alla sezione critica è fatto da due istruzioni: una valutazione e un’assegnazione che sono istruzioni divisibili, e quindi può capitare quanto rappresentato nella slide sotto.

Abbiamo un processo P1, x=lock, se x==0 abbiamo che la sezione critica è libera e quindi il processo può andare avanti nella sua esecuzione. A questo punto viene ad essere schedulato il processo P1 ed arriva il processo P2 che fa la stessa cosa e quindi abbiamo che x=lock, se x==0 va avanti ed esegue la sezione critica ponendo lock=1 e quando finisce pone lock=0.

Quello che accade è che se viene schedulato il processo P2 a favore di P1, P1 si trova già nella sezione critica e quindi pone lock=1 e quindi in questo caso verremmo ad avere due processi che sono entrambi nella sezione critica e quindi viene ad essere violato uno dei principi della mutua esclusione.

Facendo queste operazioni indivisibili si viene ad attuare una variazione della sezione critica. Questo programma può o meno funzionare a seconda di quella che risulta essere la velocità relativa dei due processi P1 e P2.

Per risolvere questo problema già negli anni '60-'70 Nicholas Swirt, Daixtra proposero soluzioni software al problema che però risultarono essere molto laboriose ed onerose computazionalmente. Per fare sistemi multiprogrammati e quindi per risolvere problemi di competizione c’è bisogno di un supporto hardware.

Istruzione TSL

TSL è un’istruzione macchina il cui acronimo indica Test And Set Lock. Con questa istruzione TSL, che non è interrompibile in quanto viene ad essere eseguita in un solo ciclo di clock, viene ad essere risolto il problema. Poiché il problema era la divisibilità di una valutazione e di un’assegnazione, in questo caso con il TSL risolvo il problema in quanto queste due operazioni non saranno più divisibili e quindi non si potrà più avere Starvation. Nei sistemi multiprocessore e quindi nei processori multicore il TSL inibisce l’accesso anche al BUS e quindi risulta essere indivisibile a tutti gli effetti.

La enter_region con la prima istruzione fa un’operazione di assegnamento leggendo il valore di LOCK e trasferendolo in RX in un solo ciclo. Se il LOCK=0 allora viene fatta una RETURN altrimenti (JUMP NOTEQUAL) cicla e torna a enter_region attendendo che il lock diventi 0. Quando si fa return, si viene ad entrare nella regione critica. Il programma quindi esegue secondo il seguente schema in figura.

Un processo fa enter_region e quando esce dalla enter_region esegue la sezione critica. Quando viene restituito il controllo viene quindi ad essere eseguita la sezione critica S1. Se il processo rimane nella enter_region invece aspetta. Quello che accade è quindi che si hanno due funzioni in cui abbiamo che quando sono eseguite o si rimane dentro in quanto la sezione critica è già bloccata oppure il controllo viene restituito e viene ad essere eseguita la sezione critica. La sezione critica è quindi protetta da due funzioni enter_region che serve per entrare nella sezione critica e leave_region che invece serve per uscire. Con il TSL se abbiamo che il lock=1 abbiamo che viene ad essere copiato 1 su RX e viene messo 1 su LOCK, viene poi ad essere comparato RX con 0, non è uguale a 0 e quindi il processo ciclerà su enter_region. Quindi fino a quando lock=1 il processo non uscirà mai dalla enter_region. Quando il lock=0, JNE non è vero e quindi va avanti, fa il return (RET) ed esce dalla funzione enter_region e comincerà ad eseguire la sezione critica.

La leave_region è molto semplice e si traduce sostanzialmente con un MOVE del valore 0 in LOCK e poi si fa una return (RET). Questa sopra è una prima soluzione al problema della mutua esclusione.

Questa soluzione è caratterizzata però da un’attesa attiva. Il processo P che trova la variabile LOCK occupata non viene ad essere sospeso ma risulterà essere sempre attivo sul processore perché cicla e quindi verrà ad essere sempre schedulato.

Problema della priority inversion

Il processo P2 quando fa “tsl x, lock” sostanzialmente ripete un ciclo e quindi il processo P2 viene ad essere schedulato alternando le fasi di running-ready e quindi occupa il processore e questo crea un problema più critico della busy wait che è il problema della priority inversion.

Questo problema della priority inversion fu un problema che portò al fallimento della prima missione su Marte la Mars Rover Robot. In questa missione funzionò tutto in quanto fu lanciata la capsula dopodiché questa venne agganciata dall’orbita di Marte, dalla capsula si staccò il robottino, il robottino attraverso un sistema di comunicazione comunicava con il satellite che era intorno all’orbita di Marte. Accadde che il robottino aveva un SO Wind River che è un SO certificato, questo SO aveva tre categorie di priorità alta, media e bassa poiché il robot aveva fatto una patch e doveva fare il reboot, ciò che accadde fu che entrò in un loop in cui si inizializzava in quanto il SO vedeva una variabile che indicava il reboot e doveva fare prima l’aggiornamento e poi il reboot e poiché il reboot aveva una priorità maggiore dell’aggiornamento accadeva che il robot non andava mai a fare l’aggiornamento ma finiva in un ciclo di reboot perenne.

La NASA è il pioniere per quanto riguarda i sistemi critici, la sicurezza e l’affidabilità dei sistemi. Oggi tutti gli standard di sicurezza ed affidabilità che esistono al mondo hanno radice nella NASA e nel JPL.

Se consideriamo l’esempio precedente e supponiamo che P2 sia a priorità alta e P1 a priorità bassa, abbiamo che P1 starà in attesa che P2 gli metta il lock=0 e quindi essendo P2 a priorità più alta avremo che verrà sempre ad essere schedulato e quindi lo scheduler non andrà mai a schedulare P1.

Questa attesa attiva sostanzialmente farà in modo che questo processo a priorità alta non cederà mai la CPU per far mettere lock=0 e quindi andare nella sezione critica, questo problema prende il nome di Priority Inversion. Nei SO il problema della Priority Inversion che si ha quando due processi che accedono alla stessa risorsa critica hanno priorità diverse viene risolto andando ad assegnare la stessa priorità ad ambo i processi, cioè il processo a priorità bassa eredita la priorità più alta del processo che sta nella sezione critica proprio per evitare questa attesa indefinita e di stallo dei sistemi.

L’Priority Inevitance non ci va bene in quanto l’attesa attiva ci dà fastidio in quanto nei SO si vuole andare ad aumentare il livello di multiprogrammazione e non si vuole andare ad aumentare il livello di utilizzo della CPU, nei SO general purpose si cerca quindi di evitare l’attesa attiva in quanto si consuma CPU ed un consumo di CPU non necessario si cerca sempre di evitarlo per problemi di efficienza.

Soluzione con attesa passiva

Per risolvere il problema c’è bisogno quindi di un’attesa passiva di modo da far transitare il processo dallo stato di esecuzione allo stato di sospeso; per fare questo occorrono due system call che provocano la sospensione del processo, il SO mette a disposizione la system call suspend(processo). La suspend è una funzione che prende come parametro un processo e non fa altro che provocare la sospensione di un processo che era running. Abbiamo poi un’altra funzione che è la funzione wake-up che è un segnale di risveglio per il processo sospeso.

Quando viene chiamata una suspend() il kernel si alloca una coda dei processi sospesi che è un array di code e ci sposta i processi che devono essere sospesi, quando viene fatta una wake-up il processo viene preso e viene spostato in uno stato di running, in questo modo si riesce ad evitare l’attesa attiva e quindi il processo viene sospeso e dà adito ad altri processi di utilizzare il processore.

La suspend e la wait devono essere incasellate in un meccanismo che ci consenta di far cooperare o competere dei processi, la struttura dati che incastra queste primitive prende il nome di semaforo. Il nome che viene dato a questa struttura dati deriva dalla metafora dei semafori agli incroci che gestiscono le code di auto.

Ogni volta che creiamo un’istanza di un semaforo il SO alloca una coda agli array di code dei processi sospesi, in questa coda andranno tutti i processi che aspettano un segnale su un semaforo S, avremo tante code per quanti sono i semafori istanziati sul SO. In definitiva abbiamo un’operazione di signal, un’operazione di wait, una struttura dati fatta da una coda che viene gestita dal SO e da un valore che è un puntatore.

N.B: Non dire mai all’orale che la coda è gestita dal semaforo perché quando un processo si sospende colui che gestisce la sospensione e l’attivazione del processo è lo scheduler che è una parte del SO, quindi il fatto che il semaforo sottintenda la creazione di una coda non vuol dire che la gestisce ma appunto come indica il termine sotto intende vuol dire che crea una coda che viene poi gestita dallo scheduler in base alle transizioni di stato dei processi che fanno uso del semaforo.

Possiamo osservare dalla figura sopra come il semaforo abbia una coda gestita dal SO, la wait abbiamo detto che decrementa il semaforo e se il valore del semaforo diventa minore di 0 inserisce il processo nella coda dei processi sospesi e lo sospende. Queste due operazioni possono essere incorporate in una sola operazione della suspend, questo dipende dal livello di astrazione a cui vogliamo descrivere il processo.

Per spiegare il funzionamento preferiamo separare le operazioni di modo da far capire che quando il semaforo diventa negativo il processo viene ad essere sospeso e dire che un processo viene sospeso vuol dire che viene inserito nella coda dei processi sospesi e questa è proprio la coda che sottintende il semaforo (s.queue) e poi viene sospeso il semaforo.

La procedura di signal incrementa il valore del semaforo e se il suo valore è minore o uguale a zero allora rimuove il processo dalla coda dei processi sospesi e lo risveglia mettendolo nella coda dei processi pronti. Nel caso in esame nella figura il valore del semaforo è uguale a 1, nel processore abbiamo il processo D, se D fa una wait il valore del semaforo passa da 1 a 0 e D non viene sospeso e viene poi rischedulato nella coda dei processi pronti. Se arriva il processo A che fa una wait abbiamo che valore del semaforo va da 0 a -1 e A viene ad essere sospeso.

Semaforo binario

Il semaforo binario è la tipologia di semaforo più semplice, abbiamo che il valore del suo contatore non è un intero ma è una variabile booleana. In questo caso abbiamo che il semaforo può assumere solo due valori che possiamo considerare corrispondere proprio al rosso e al verde di un tradizionale semaforo; abbiamo che se il valore è uguale a 1, il valore è posto uguale a 0; se il valore è uguale a 0 abbiamo che il processo viene ad essere sospeso. Se la coda è vuota e quindi non abbiamo nessun processo sospeso allora il valore è uguale a 1.