Sincronizzazione 2

Lezione del 2019-05-22 mer.

La sincronizzazione serve anche al coordinamento delle attività di sistemi distributi, utilizzando: blocchi, mutue esclusioni, elezioni del leader.

In particolare sono fondamentali le mutue esclusioni e le elezioni del leader. I primi per garantire l’accesso esclusivo ad una risorsa. I secondi sono comuni nei sistemi peer-to-peer e dove è presente il raggruppamento per sottoreti.

Mutua esclusione

In molti casi i processi hanno necessità di accedere alla stessa risorsa, e possono tentare di farlo simultaneamente.

Tale accesso contemporaneo può corrompere, o rendere inconsistente, la risorsa. In questi casi è necessario garantire ai processi un accesso mutuamente esclusivo.

Nei sistemi cenralizzati questi problemi si risolvono con l’uso di semafori o di lock. Con i sistemi distribuiti questi strumenti non sono disponibili perché non vi è memoria condivisa.

Quindi vi è la necessità di un protocollo di comunicazione per garantire l’accesso esclusivo ad una risorsa.

In generale vi sono due tipi di algoritmi per mutua esclusione di sistemi distribuiti:

• le soluzioni token ring;

• e gli approcci basati sul permesso.

Nelle soluzioni token ring è facile avere equità 1 ed evitare i deadlock. Ma quando si perde il token, è difficile crearne uno, e solo uno, nuovo 2.

Tra gli approcci basati sul permesso, vi è l’algoritmo centralizzato. Questo algoritmo simula il comportamento che si ha in un sistema monoprocesso:

• un processo viene eletto coordinatore,

• e quando un processo vuole accedere ad una risorsa condivisa invia un messaggio al coordinatore.

In questo modo vi è uguaglianza e viene garantita la mutua esclusione, ed è il più semplice da implementare.

Il seguente diagramma illustra il funzionamento dell’algoritmo in questione.

Nel riquadro (a), il processo 1 richiede la risorsa, il coordinatore la concede perché non la detiene nessun altro. Nel riquadro (b) il processo 2 richiede la risorsa. Il coordinatore mette in coda la richiesta e non risponde, negando in tal modo l’accesso. Quando il processo 1 rilascia la risorsa (riquadro (c)), il coordinatore comunica al processo 2 che può utilizzarla, e rimuove dalla coda delle richieste la relativa annotazione.

Come usuale, quando si ha a che fare con sistemi distribuiti, la dinamica è complessa. Qui abbiamo la scelta che la mancanza di risposta ha un significato: risorsa non concessa.

Possibili problemi sono:

• presenza di un unico punto di guasto;

• mancanza di scalabilità.

Pure, di tipo basato sul consenso è l’algoritmo di Ricart e Agrawala 3. Questo richiede che vi sia un ordinamento totale di tutti gli eventi nel sistema.

Si ricordi che l’algoritmo di Lamport è un possibile modo per ottenere l’ordinamento degli eventi, e si può usare per fornire time-stamps per una mutua esclusione distribuita.

Si hanno i seguenti passi:

• quando un processo deve accedere ad una risorsa condivisa, invia a tutti i processi un messaggio con il nome della risorsa, il proprio identificativo, e il logical time corrente;

• quando un processo riceve una richiesta, agisce in funzione di tre possibilità:

  • se non ha la risorsa e non la vuole avere, risponde con un messaggio di ok al richiedente;

  • se già ha in uso la risorsa, non rispode, ma accoda la richiesta;

  • se anche lui vuole accedere alla stessa risorsa, ma ancora non l’ha fatto, a sua volta ha inviato un mesaggio di richiesta tutti; in questo caso compara il timestamp del messaggio ricevuto con quello del proprio messaggio inviato, chi ha il timestamp inferiore vince.

Il seguente diagramma illustra gli step di funzionamento di Ricart e Agrawala:

Nel riquadro (a) vediamo che i processi 0 e 2 richiedono entrambi la risorsa. Il primo con logical clock 8 e il secondo con logical clock 12. Quindi (riquadro (b)) vince il processo 0 che usa la risorsa e accoda la richiesta del processo 2. Quando il processo 0 rilascia la risorsa (riquadro (c)) invia il suo ok al processo 2, che la prende in carico.

L’algoritmo sembra semplice. Che problemi comporta?

• vi sono più punti di guasto, ma in senso negativo: se un processo non risponde può essere inteso come negazione del permesso, ma potrebbe essere un processo che si è bloccato.

Per mitigare il problema si può utilizzare un messaggio esplicito invece del silenzio.

In generale, se esiste un middleware che implementa il protocollo, vale la pena utilizzarlo.

Algoritmo Token ring. Che nei ricordi del prof. Mostarda è molto difficile da controllare.

Si costruisce un anello logico software che lega tutti i processi del sistema. Dopo di che, si inietta nell’anello un token che viaggia lungo l’anello, un processo dopo l’altro. Il processo che ha il token può utilizzare la risorsa. Quando ha finito di utilizzare la risorsa, passa il token al processo successivo.

C’è il solito problema che quando un nodo cade, la situazione va gestita, o blocca tutto il sistema. Ma, come al solito, come decidere se un processo è caduto o è lento? Questo aspetto è particolarmente critico se si sta parlando del processo che ha il token in carico.

Se un nodo non vede risposta, può decidere di shuntare il processo che non risponde, credendolo caduto, per vederlo rispuntare poco dopo perché era lento. Risultato: nell’anello possono girare due token, dando luogo all’accesso contemporaneo di due processi alla risorsa.

Algoritmi per la elezione di un leader

Molti algoritmi per sistemi distribuiti richiedono che un processo assuma il ruolo di coordinatore. Di fatto la necessità di effettuare leader election è una delle più diffuse nell’ambito dei sistemi distribuiti. A questo fine, è necessario identificare univocamente i processi, con un dato che ne permetta l’ordinamento.

Infatti gli algoritmi di elezione, tentano di localizzare il processo con l’identificatore più elevato per designarlo come coordinatore.

Gli algoritmi di leader election si differenziano per il modo in cui tentano la localizzazione.

Algoritmo del bullo (Bully algorithm). Vince chi ha l’identificativo maggiore. In pratica con i seguenti passaggi:

• un processo P invia una richiesta di elezione a tutti i processi che hanno un identificativo maggiore;

• se non risponde nessuno, P ha vinto l’elezione e diviene il coordinatore;

• se uno dei processi con numero superiore risponde, si assume il ruolo di richiedere l’elezione, e P esce di scena.

Il seguente diagramma illustra il bully algorithm.

Nel riquadro (a) osserviamo che il processo 4 richiede l’elezione, probabilmente perché si è accorto che il coordinatore corrente, il processo 7, non risponde più. I processi 5 e 6 rispondono, e il processo 4, con id minore, si fa da parte (riquadro (b)). A questo punto 5 e 6 chiedono l’elezione (riquadro (c)). Il processo 6 risponde al 5, che si ritira, e vince l’elezione perché non gli risponde nessuno (riquadro (d)). Quindi il processo 6 notifica a tutti di essere il nuovo coordinatore (riquadro (e)).

Tutto ciò funziona se non vi sono problemi di comunicazione. Questo è un assunto generale per gli algoritmi di elezione. In particolare esiste un teorema che dimostra l’impossibilità di leader election in presenza di errori, ad es. di comunicazione per guasto della rete.

Il seguente diagramma mosta un esempio di cosa può succedere a causa di un quasto alla rete.

Il riquadro (a) mostra la situazione a regime. Il nodo 8 è il leader presente in una rete composta da due gruppi di tre nodi, collegati da un link di comunicazione.

Supponiamo vi sia un guasto al link (riquadro (b)). In questo caso il gruppo formato dai nodi {7, 6, 2}, non comunicando con il nodo 8, eleggerebbero il nodo 7 come leader. Ma il gruppo {1, 3, 8} continuerebbe a funzionare utilizzando il nodo 8 come leader. Se successivamente il link risalisse, avremmo un sistema con due leader: il nodo 8 e il 7.

È possibile utilizzare nelle elelzioni algoritmi basati su ring (senza token). In questi casi si forma un anello dei processi che formano il sistema (overlay network). Dopo di che si fa viaggiare nell’anello un messaggio di election che colleziona gli identificativi dei nodi attraversati. Quando il giro è terminato, il messaggio election si trasforma in coordinator comunicando ai nodi attraversati l’elenco dei nodi che hanno risposto (e quindi formano effettivamente l’anello) e l’identificativo del coordinatore (il nodo con id maggiore).

---

1

Equità: tutti i processi hanno l’opportunità di accedere alla risorsa.

2

Solo uno nuovo. È il solito problema: se non mi arriva il token, il processo che lo deteneva è caduto, o è solo lento nel rispondere?

3

L’algoritmo di Ricart e Agrawala è descritto in dettaglio in [RICAG1981].