Appunti Sistemi Operativi

Implementazione di un algoritmo di mutua esclusione

Psoddisfatta, così che questo deve aspettare. Solo dopo che il processo ha abbandonato la sezioneflag0 false Qcritica diventa , e il processo può accede alla sua sezione critica.P turn 1Se il processo viene nel frattempo riavviato, imposterà a , e dovrà aspettare che ilQprocesso abbia abbandonato la sua sezione critica.

• La mutua esclusione è garantita dal fatto che il controllo flag e di turn viene fatto in modo atomico
• L’assenza di deadlock viene garantita dal fatto che solamente una delle due condizioni while può essere vera nello stesso momento
• Il progresso dell’elaborazione è garantito dal fatto che se uno dei due processi tenta di entrare e l’altro non è in sezione critica può tranquillamente entrare

//'' dichiarazione delle variabili globali comuni''//

//'' array di lunghezza n con tutti i valori a 0''

int in[1:n] = ([n] 0);

array di lunghezza n con tutti i valori a 0
int turno[1:n] = ([n] 0);

Process CS[i = 1 to n] {
    for(;;) {
        // protocollo di ingresso per la sezione critica
        for[j = 1 to n] {
            // turno[j] = i;
            in[i] = j;
            for[k = 1 to n st i != k] {
                // aspetta se il processo k ha il numero di in più grande
                while(in[k] >= in[i] & turno[j] == i);
            }
        }
        <sezione critica>
        in[i]=0;
        <sezione non critica>
    }
}

Funzionamento: la generalizzazione che è stata fatta dell'algoritmo per n processi è piuttosto complessa. Il protocollo di ingresso, per ciascuno degli n processi, consiste, in un ciclo for turno[j] che itera in n-1 fasi. Il valore indica quale sia l'ultimo processo che è arrivato nella j-esima fase; mentre il valore di in rappresenta la fase in cui il processo si trova.

Soluzioni Hardware
Nei sistemi uniprocessore, i processi concorrenti vengono alternati tramite il meccanismo degli interrupt, l'idea sarebbe

quella di farne a meno. Il problema è che il Sistema Operativo dovrebbe lasciare ai processi la responsabilità di riattivare gli interrupt, cosa che è altamente pericolosa ed allo stesso tempo riduce il grado di parallelismo ottenibile dal processore. Inoltre, questa idea non funzionerebbe su sistemi multiprocessore!

test_and_set()

L'istruzione viene usata per scrivere in una locazione di memoria e restituire il suo vecchio valore come una singola operazione atomica. Se diversi processi possono accedere alla stessa area di memoria, e se un processo sta eseguendo un test_and_set(), nessun altro processo può iniziare un altro finché il primo processo non ha terminato la propria. La CPU può utilizzare l'istruzione test and set offerta da altre componenti elettroniche, oppure può fornire una propria istruzione test_and_set(). L'istruzione test_and_set() si può definire come:

bool test_and_set(bool *obiettivo){bool

valore = obiettivo; obiettivo = true; return valore;

Sezione 6 – Semafori

Principio base: due o più processi possono cooperare attraverso semplici segnali, in modo tale che un processo possa essere bloccato in specifici punti del suo programma finché non riceve un segnale da un altro processo.

Definizione: Un semaforo è una variabile intera cui si può accedere, escludendo l'inizializzazione, solo tramite due operazioni atomiche predefinite: wait() e signal().

• wait() P, definita anche come P(): viene invocata per attendere il segnale (ovvero, per attendere un evento o il rilascio di un programma)
• signal() V, definita anche come V(): viene invocata per inviare un segnale, quale il verificarsi di un evento o il rilascio di un programma.

Il semaforo è inizialmente impostato al numero di risorse disponibili. I processi che desiderino utilizzare una risorsa invocano wait() sul semaforo, decrementandone così il valore; i processi che

restituiscono una risorsa, invece, invocano sul semaforo incrementandone il valore. Quando il semaforo vale 0, tutte le risorse sono occupate, e i processi che ne richiedono l'uso dovranno bloccarsi fino a quando il valore del semaforo non ritorna positivo.

Per ogni semaforo, il sistema operativo deve mantenere una struttura dati contenente l'insieme dei processi sospesi. Quando un processo deve essere svegliato, è necessario selezionare uno dei processi sospesi. La struttura dati che solitamente si usa è la FIFO, in modo tale da svegliare per primo il processo che è stato più a lungo sospeso. Questa è una politica fair, che garantisce l'assenza di starvation.

wait() e signal() sono primitive fornite dal sistema operativo. L'implementazione fornita però non è completa in quanto i due metodi devono essere eseguiti in modo atomico.

In un sistema uniprocessore è possibile disabilitare/riabilitare gli interrupt.

all'inizio/fine dei metodi. Questo perché questi metodi sono direttamente implementati dal sistema operativo. L'intervallo temporale in cui gli interrupt sono disabilitati è molto breve. In un sistema multiprocessore è necessario utilizzare una delle tecniche di CS viste in precedenza (Dekker, Peterson, test_and_set(), ...). Utilizzando queste tecniche, non abbiamo eliminato il busy-waiting, ma lo abbiamo limitato alle sezioni critiche, e queste CS sono molto brevi. Semafori Binari Questi sono una variante del semaforo intero dove il suo valore può assumere i valori 0 e 1. Servono a garantire la mutua esclusione ed hanno lo stesso potere espressivo dei semafori interi. Problemi Classici Rappresentano le interazioni tipiche dei processi concorrenti. 1. Producer/Consumer Producer Esiste un processo produttore (P) che genera valori e vuole trasferirli ad un processo consumatore (C) che prende i valori generati e li consuma. Tra di essiLa comunicazione avviene attraverso una singola variabile condivisa. Le proprietà da garantire sono: - Producer Consumer non deve scrivere nuovamente l'area di memoria condivisa prima che abbia effettivamente utilizzato il valore precedente - Consumer Producer non deve leggere due volte lo stesso valore, ma deve attendere che abbia generato il valore successivo - Assenza di deadlock 2. Buffer limitato Producer Consumer Producer E' simile al problema / , in questo caso però, lo scambio tra e Consumer non avviene tramite un singolo elemento, ma tramite un buffer di dimensione limitata (vettore di elementi). Le proprietà da garantire sono: - Producer Consumer non deve sovrascrivere elementi del buffer prima che abbia effettivamente utilizzato i relativi valori - Consumer Producer non deve leggere due volte lo stesso valore, ma deve attendere che abbia generato il valore successivo - Assenza di deadlock - Assenza di starvation Per la strutturadei buffer si utilizza un array circolare che possiede due indici, front e rear, che indicano rispettivamente il prossimo elemento da scrivere e il prossimo elemento da leggere. Gli indici vengono utilizzati in modo ciclico. Implementazione:

1. Filosofi a cena

Si considerino cinque filosofi che trascorrono la loro esistenza pensando e mangiando. I filosofi condividono un tavolo rotondo circondato da cinque sedie, una per ciascun filosofo. Al centro del tavolo si trova una zuppiera colma di riso, e la tavola è apparecchiata con cinque bacchette. Quando un filosofo pensa, non interagisce con i colleghi; quando gli viene fame, tenta di prendere le bacchette più vicine: quelle che si trovano tra lui e i commensali alla sua destra e alla sua sinistra. Un filosofo può prendere una bacchetta alla volta e non può prendere una bacchetta che si trova già nelle mani di un suo vicino. Quando un filosofo affamato tiene in mano due bacchette contemporaneamente, mangia senza interruzioni.

lasciare le bacchette. Terminato il pasto, le posa eriprende a pensare. Il problema dei cinque filosofi è considerato un classico problema di sincronizzazione: rappresenta una vasta classe di problemi di controllo della concorrenza, in particolare i problemi caratterizzati dalla necessità di assegnare varie risorse a diversi processi evitando situazioni di stallo e di attesa infinita. Una semplice soluzione consiste nel rappresentare ogni bacchetta con un semaforo: un filosofo tenta di afferrare ciascuna bacchetta eseguendo un'operazione wait() su quel semaforo e la posa eseguendo un'operazione signal() sui semafori appropriati. I dati condivisi sono quindi: semaphore chopstick[5]; chopstick 1 dove tutti gli elementi sono inizializzati a 1. La struttura del filosofo i è la seguente: while (true) { wait(chopstick[i]); wait(chopstick[(i + 1) % 5]); /** Mangia **/ signal(chopstick[i]); signal(chopstick[(i + 1) % 5]); /** Pensa **/ } Questa soluzione garantisce che due vicininon mangino contemporaneamente, ma è insufficiente poiché non esclude la possibilità che si abbia una situazione di stallo (deadlock). Se tutti prendono la bacchetta di sinistra, rimarranno tutti in attesa di poter prendere quella destra, cosa che non accadrà mai. Tali situazioni possono essere evitate con i seguenti espedienti:

• Solo quattro filosofi possono stare contemporaneamente a tavola
• Un filosofo può prendere entrambe le sue bacchette solo se sono entrambe disponibili
• Si adotta una soluzione asimmetrica: un filosofo dispari prende prima la bacchetta di sinistra e poi quella destra; invece, un filosofo pari prende prima la bacchetta di destra e poi quella di sinistra.

Tuttavia, una soluzione immune alle situazioni di stallo non esclude necessariamente la possibilità di situazioni di attesa infinita. 4. Lettori e Scrittori Si supponga che una base di dati sia da condividere tra numerosi processi concorrenti. Alcuni processipossono richiedere solo la lettura del contenuto della base dati, mentre altri ne possono richiedere un aggiornamento, vale a dire una lettura e una scrittura. Questi tipi di processi vengono distinti chiamando lettori quelli interessati alla sola lettura e scrittori gli altri. Naturalmente, se due lettori accedono nello stesso momento all'insieme di dati condiviso, non si ha alcun effetto negativo; viceversa, se uno scrittore e un altro processo accedono contemporaneamente alla stessa base di dati, ne può derivare il caos. Per impedire l'insorgere di difficoltà di questo tipo è necessario che gli scrittori abbiano un accesso esclusivo in fase di scrittura alla base di dati condivisa. Il problema