La tecnica della Mutua esclusione nei sistemi operativi e distribuiti

Si parla di concetto di mutua esclusione in sistemi che si servono dell’utilizzo di processi concorrenti, i quali, volendo accedere ad una risorsa condivisa, necessitano di una sorta di politica di gestione degli accessi. Per evitare, quindi, danni come l’inconsistenza dei dati, si sceglie di applicare la politica di mutua esclusione.

Ogni algoritmo di mutua esclusione comprende tre zone principali:
1. una serie di istruzioni chiamate trying protocol (TP) che precedono la sezione principale, ovvero la sezione critica;
2. la sezione critica (CS) -> l’esecuzione della sezione critica coincide con l’accesso alla risorsa condivisa;
3. la exit protocol (EP) -> si tratta delle istruzioni che seguono la sezione critica
La sequenza dei processi che avranno accesso alla risorsa si dice schedule, e viene costruita da un componente, detto di conseguenza scheduler.
E’ necessario quindi definire degli accorgimenti che aiutino ad evitare problemi nella gestione delle risorse condivise.

Questi sono i principali:
1. Mutua Esclusione -> al massimo un processo alla volta è in grado di accedere alla sezione critica (CS)
2. No Deadlock -> se un processo è bloccato nella trying section (TS), esiste almeno un processo in grado di entrare ed uscire dalla sezione critica (CS)
3. No Starvation -> nessun processo può rimanere bloccato per sempre nella trying section

N.B. E’ utile notare che implementando la No Starvation di conseguenza si otterrà anche la No Deadlock.

Algoritmi di mutua esclusione

Algoritmo Centralizzato

Un processo invia la richiesta di accesso “enter”, per la risorsa condivisa, ad un processo coordinatore.
Se la risorsa è libera, quest’ultimo risponde con un messaggio “granted”; altrimenti con “denied”, avendo l’accortezza di memorizzare la richiesta in una coda FIFO, affinchè venga servita quando la risorsa torna disponibile.
Quando un processo rilascia la risorsa invia un messaggio “released” al coordinatore.

Algoritmo Decentralizzato Basato su DHT

Si parte dal presupposto che invece di un solo coordinatore, ne esistano molteplici, così come esistono molteplici repliche della risorsa, una per ogni coordinatore assegnatole.
In tal caso, un processo che vuole accedere alla risorsa deve ottenere la maggioranza delle autorizzazioni da parte dei coordinatori.
D’altra parte se un coordinatore ha già dato autorizzazione ad un altro processo, per la stessa risorsa, esso invierà un parere sfavorevole.
Algoritmo basato su Token Centralizzato

Viene introdotto un coordinatore che gestisce la distribuzione di un token (gettone).
Questo token è unico, perché la risorsa condivisa è unica; di conseguenza, chi possiede il token ha accesso alla risorsa, gli altri si mettono in attesa.

Algoritmo basato su Token Decentralizzato: token ring

Il token, in questo caso, viaggia da un processo all’altro, in una struttura topologica ad anello.
Quando un processo riceve un token, ma non è interessato ad accedere alla risorsa, passa oltre il token, viceversa lo mantiene fino al rilascio della risorsa e del token stesso.

Algoritmo Distribuito di Ricart e Agrawala

Quando un processo P vuole accedere alla risorsa, invia agli N-1 processi un messagio di “request”.
I processi che ricevono il messaggio di “request”, rispondo con un “reply” al processo P; a meno che uno di questi processi non si trovi esso stesso nella sezione critica, o non abbia autorizzato già un altro processo ad accedervi. In quest’ultimo caso, la “request” viene messa in una coda FIFO e servita al momento opportuno.
Quando un processo vuole lasciare la sezione critica invia a tutti gli altri processi un messaggio di “release”.
Quando un processo riceve un messaggio di “release”, esso elimina la prima entry nella coda, e risponde immediatamente alla successiva “request” con un “reply”.
N.B. Quando due processi vogliono accedere contemporaneamente alla sezione critica, viene data precedenza a quello con timestamp più basso. (cfr. Lamport).

Algoritmi di elezione di un coordinatore

Prima di elencare e spiegare gli algoritmi di elezione di un coordinatore è importante sottolineare che:
– ogni processo viene identificato da un ID
– ogni processo conosce l’ID di tutti gli altri processi
– ogni processo non conosce lo stato di attività o inattività degli altri processi

Algoritmo di elezione Bully

1. Il processo P inizia l’algoritmo, quindi invia un messaggio “election” a tutti i processi con ID maggiore del suo;
2. Se nessuno risponde a P, esso viene eletto COORDINATORE
3. Se un processo con ID maggiore risponde a P con “ok”, esso stesso continua l’elezione
4. L’algoritmo continua fino all’elezione del coordinatore.
5. Quando il coordinatore viene eletto, esso comunica con “coordinator”, a tutti gli altri processi, l’avvenuta elezione

Algoritmo di elezione ad Anello

Innanzitutto, ogni processo conosce l’ID del suo successore.
1. Un processo inizia l’algoritmo inviando al suo successore il messaggio “election” affiancato dal suo ID
2. Via via che l’algoritmo continua, al messaggio, contenente il comando “election” e gli ID dei processi precedenti, viene aggiunto l’ID del processo attuale
3. Quando il messaggio torna al processo che aveva iniziato l’algoritmo, esso valuta gli ID, ne sceglie il maggiore, ed invia sull’anello il messaggio “coordinator” aggiungendo in coda l’ID del processo eletto.