I sistemi che hanno a che fare con processi multipli possono spesso essere programmati più semplicemente usando le regioni critiche.
Quando un processo deve leggere o aggiornare certi valori appartenenti a strutture dati condivise entra in una sezione critica per assicurarsi la mutua esclusione e che nessun altro processo usi quelle strutture dati nello stesso istante.
2.2 CONSISTENZA ATTRAVERSO LA MUTUA ESCLUSIONE
In un sistema distribuito la mutua esclusione è spesso usata per mantenere la consistenza quando vengono eseguite operazioni ristrette. Per esempio, per migliorare la disponibilità, i dati possono essere replicati in più siti. Tuttavia, quando cadute del sistema rendono impossibile la comunicazione tra due o più gruppi di copie, gli aggiornamenti concorrenti a copie di diversi gruppi possono causare una situazione di inconsistenza. In questo caso, l'inconsistenza può essere evitata con la mutua esclusione che inibisce l'aggiornamento di tutte le copie eccetto una.
I meccanismi che garantiscono la mutua esclusione dovrebbero essere sia efficienti che elastici. L'elasticità implica la disponibilità di elevate risorse nell'affrontare i fallimenti, mentre l'efficienza implica basse spese generali incorse dall'esecuzione di operazioni ristrette.
2.3 ALCUNI ALGORITMI
Nei prossimi tre paragrafi verranno presentati 3 tipi di algoritmi ,che sono stati studiati anche a lezione, che illustrano un modo per ottenere la mutua esclusione.
Questo algoritmo si ottiene simulando un sistema uniprocessor. Tra tutti i processi se ne elegge uno a coordinatore, a questo punto se un processo vuole entrare in una regione critica chiede il permesso spedendo un messaggio, nel quale viene specificata la regione critica alla quale vuole accedere, al coordinatore. A questo punto si hanno tre differenti situazioni :
(1) Se nessun altro ha richiesto quella regione critica allora il coordinatore invia un messaggio di OK al processo che ne aveva fatto richiesta (figura a).
(2) Se la regione critica è occupata il coordinatore può :
A) non fornire risposta al processo richiedente, cioè ignorare la richiesta
B) bloccare il processo richiedente mettendolo in coda alla lista dei processi che hanno richiesto l’utilizzo di quella regione critica. Nel momento in qui la regione in questione viene rilasciata allora viene risvegliato il processo in testa alla coda e gli viene dato l’OK (figura c ).
Dal momento che avere un punto di fallimento singolo non è una condizione accettabile, sono stati presentati algoritmi distribuiti per il problema della mutua esclusione. Lamport fu il primo ,nel 1978, a presentare un algoritmo sulla sincronizzazione dei clock, successivamente ,nel 1981, lo stesso algoritmo è stato migliorato da Ricard e Agrawala.
Tale algoritmo richiede che ci sia un ordinamento totale fra tutti gli eventi di un sistema, cioè che fra ogni coppia di eventi, ad esempio messaggi, si possa stabilire in maniera non ambigua quale evento si è verificato per primo. Quando un processo vuole entrare in una regione critica, spedisce un messaggio a tutti i processi. Il messaggio contiene il nome della sezione critica nella quale vuole entrare, il proprio numero di processo ed il proprio tempo corrente. La comunicazione è assunta essere affidabile.
Un processo che riceve tale messaggio si può comportare i tre modi differenti :
(1) se non è nella sezione critica e non vi vuole entrare, spedisce un messaggio di OK al mittente;
(2) se è già all'interno della sezione critica, non spedisce alcuna risposta, ma mette in coda la richiesta;
(3) se vuole entrare nella regione critica, ma non l'ha ancora fatto, confronta il suo tempo corrente con quello incluso nel messaggio ricevuto, quello di valore più basso ha la precedenza (guarda figura ).
Dopo aver spedito la richiesta di entrare in una sezione critica, un processo si mette in attesa di ricevere da tutti gli altri processi il permesso di entrare. Appena sono arrivati tutti i permessi, può entrare nella regione critica; quando poi uscirà dalla regione critica, spedirà un messaggio di OK a tutti i processi che sono nella coda associata a quella regione e sblocca il processo in testa.
Supponiamo di avere una rete a bus, priva di ordinamento fra i processi come in figura a. Costruiamo con un software un anello logico nel quale a ciascun processo viene assegnata una posizione come in figura b; l'ordinamento scelto non ha importanza, importa solo che ogni processo sappia chi lo precede e chi lo segue nell'ordinamento.
In fase di inizializzazione dell'anello, si dà al processo 0 un token che successivamente viene fatto circolare attraverso l'anello, passando dal processo k al processo k+1 . Quando un processo riceve il token dal proprio vicino, effettua un controllo :
(1) se deve entrare in una regione critica, vi entra, svolge tutto il lavoro che deve fare e lascia la regione. Dopo essere uscito trasmette il token sull'anello e non gli è permesso di entrare in una seconda regione critica usando lo stesso token.
(2) se non è interessato ad entrare in alcuna regione critica, il token viene ritrasmesso;