Mutua Esclusione Distribuita

 Metodologie tipiche per algoritmi distribuiti
 Mutua esclusione in ambiente distribuito
      1. Algoritmo centralizzato
      2. Token passing: struttura a ring
 Clock Logico
       3. Algoritmo Interamente Distribuito
       4. Token passing senza strutturazione di Ring
 Sistema di AZIONI
       Algoritmi di Mutua Esclusione Distribuita
 Algoritmi di elezione
        Bully algorithm
 
 

Metodologie tipiche per
Algoritmi Distributi (Indice)

Algoritmi Centralizzati
Esiste un particolare processo, chiamato coordinatore, che gestisce l'interazione fra processi.

Algoritmi Distribuiti
Tutti i processi cooperano, comunicando fra di loro, per risolvere un dato problema. Metodologie piu' usate:

Aspetto importante degli algoritmi, sia distribuiti che centralizzati, e' la tolleranza ai guasti.

I sistemi distribuiti non hanno clock  globale. In alcuni casi e' pero' necessario considerare un ordinamento globale degli eventi del sistema ==> utilizzo di :
Clock Logico mantenuto da ogni processo per mezzo di:
Time stamp associati ad ogni messaggio.

Algoritmi totali: per risolvere un problema e' necessaria la collaborazione di tutti i processi. Si deve quindi avere la possibilita' di contattarli tutti.

Barriera: in un certo punto un processo puo' avere bisogno di una sincronizzazione globale (barriera) con tutti igli altri processi prima di procedere.

Mutua esclusione in ambiente distribuito (Indice)

Molti dei metodi visti nei sistemi monoprocessore  non funzionano. Ad esempio per implemntare i semafori occorre avere una memoria comune.

Vediamo alcuni metodi per realizzare la mutua esclusione in ambienti distribuiti.
Si suppone sempre che il processo che ottiene la risorsa prima o poi (eventually) la restituisca, a meno di fallimento del processo stesso.

1. Algoritmo centralizzato

Simula cio' che si fa in ambiente monoprocessore con i monitor.
Il processo coordinatore controlla l'accesso alla sezione critica. Un processo chiede con un messaggio l'autorizzazione ad usare una risorsa e si blocca finche' non l'ottiene.
 
 

 Quando puo' essere assegnata (e' libera), riceve un reply dal coordinatore, l'accede e quindi invia un altro messaggio al coordinatore per segnalare la fine dell'accesso.

Problemi:

Per ovviare al secondo inconveniente bisogna:

Per questo problema, vedere algoritmo di elezione.

Puo' anche fallire un client. Se e' quello che detiene la risorsa, questa rimane sempre occupata e non piu' utilizzabile. Unico metodo "generale" per sapere se un processo e' ancora vivo  o se e' in failure, e' inviargli un messaggio periodico AYA (Are You Alive) a cui il processo risponde con il messaggio IAA (I Am Alive).
Il coordinatore controlla il client che ha la risorsa inviando un AYA, In  aggiunta si utilizza un time-out, scaduto il quale, se non e' stato ancora ricevuto il messaggio IAA, il coordinatore considera in failure il client.

Nell'algoritmo centralizzato non c'e' possibilita' di starvation se il trattamento della coda da parte del coordinatore e' fair.

2. Token passing: struttura a Ring

I processi formano un ring logico: ogni processo conosce l'indirizzo del processo che segue.

  1. Un token circola nel ring
  2. Il processo che acquisisce il token puo' utilizzare la risorsa e usarla.
  3. Dopo averla usata, o se non ne ha bisogno, passa il token al processo successivo.

Caratteristiche:

Prima di vedere un terzo algoritmo, e' necessario definire cos'e' un

Clock Logico

In un sistema distribuito si definiscono:

Ogni processo ha un clock fisico (che segna l'avanzamento del tempo) personale, cioe' non esiste un clock fisico globale. I clock locali possono non essere perfettamente sincronizzati. Assegnando ad ogni evento il valore del clock fisico locale al momento in cui succede, potrebbero verificarsi discrepanze, ad esempio un messaggio potrebbe essere inviato in un tempo precedente a quello in cui viene ricevuto (perche' il processo serder e' generalmente diverso dal receiver).

Se esiste la necessita' di ordinare gli eventi, il clock fisico non e' accettabile per quanto riguarda gli eventi esterni (per avere un esempio, vedere l'algoritmo  interamente distribuito).
In realta', spesso e' sufficiente ordinare gli eventi non in modo globale, come se esistesse un tempo assoluto, ma solo in modo relativo, mantenendo unicamente le relazioni causali fra gli eventi.

Relazione happens-before (Lamport)
aYb (oppure aQb) indica che a happens-before b.
Tale relazione puo' essere osservata in due casi:

Considerando la chiusura della relazione, due eventi si dicono concorrenti se non hanno relazioni happens-before (ossia non e' possibile/utile definire se a precede o segue b).
Si tratta quindi di una relazione che stabilisce un ordinamento parziale sugli eventi.

Clock Logico: Funzione monotona crescente. Ogni evento send e receive e' associato al valore del clock logico in cui e' accaduto (detto Time Stamp TS).
 
 

Il clock logico di un processo viene incrementato ogni volta che avviene un evento. In piu', quando arriva un messaggio, se (il suo) TS > Clock, il valore di Clock e' riassegnato in modo che TS < Clock.
Per evitare che nel sistema ci siano 2 eventi con lo stesso TS, si considera come TS il valore del clock logico esteso (concatenato) cn l'identificatore del processo (parte meno significativa del valore).
L'ordinamento indotto dal TS e' globale.

3. Algoritmo Interamente Distribuito

Si vuole evitare di avere un unico coordinatore.

Algoritmo di Lamport (78): e' uno dei primi schemi. Utilizza un ordinamento completo degli eventi. Richiede 3(n-1) messaggi per ogni entry in una sezione critica, per n processi.

Algoritmo di Ricart e Agrawala (81) con 2(n-1) messaggi (richiede sempre l'ordinamento degli eventi).

Per il secondo punto,  la scelta fra le 2 azioni viene effettuata secondo questo criterio:

  1. se il processo q e' gia' nella sezione critica, differisce l'invio del reply,
  2. se q non vuole entrare in una sezione critica (e quindi non ha inviato nessun messaggio request), invia subito il reply,
  3. se q vorrebbe entrare nella sezione critica (ha gia' inviato un request), ma non ha ancora ricevuto tutti i reply necessari, si confrontano i due TS delle rispettive richieste: se TSp < TSq, allora q invia reply a p (la sua richiesta e' avvenuta in precedenza, secondo l'ordinamento indotto dal Clock Logico), altrimenti lo sospende.

Le richieste a cui non e' inviato immediatamente un reply sono memorizzate.

Esempio

Caratteristiche dell'algoritmo:

  1. si ottiene la mutua esclusione,
  2. non c'e' starvation (per via dei TS trattati in modo FIFO, e dell'ordinamento globale),
  3. non c'e' possibilita' di deadlock.

Svantaggi dell'algoritmo:

  1. Richiede la partecipazione di tutti i processi del sistema,
  2. ogni processo deve conoscere l'identita' degli altri ==> problema aggiuntivo dell'inserimento e uscita  di un processo, in modo sincrono (gestione di un gruppo di processi),
  3. se un processo fallisce durante il protocollo, l'intero schema fallisce. Occorre allora monitorare lo stato di tutti i processi: quando un processo e' riconosciuto in failure, tutti i processi ne sono notificati.

Vantaggi rispetto all'algoritmo di Token Passing: non si inviano messaggi se non c'e' almeno un processo che vuole entrare nella sezione critica.

4. Token Passing senza strutturazione di Ring

E' una situazione intermedia fra l'algoritmo "token passing su ring" e  quello "distribuito". Il token consente l'accesso alla risorsa, ma viene trsmesso solo a chi ne ha effettivamente bisogno.

Algoritmo di Chandy (82).
Garantisce che ogni processo che richiede una risorsa, vi acceda in un tempo finito. Supponiamo di avere n processi. Il token ha associato un vettore T = (T1, T2, ..., Tn) dove Tj indica quante volte il processo pj ha ottenuto l'accesso alla risorsa. Indichiamo ora con pi un generico processo e definiamo le sue azioni:

Per la descrizione di questo algoritmo e' stato usato un metodo diverso da quello (poco formale) visto per gli altri algoritmi precedenti, e meglio descritto nella parte successiva.

Anche in questo algoritmo e' necessaria la conoscenza dell'identita' di tutti i processi del sistema. Per ogni richiesta di uso della risorsa si inviano n-1 messaggi.
Problemi: perdita del token. In questo caso c'e' una difficolta' maggiore nella verifica rispetto all'algoritmo su ring.

Confronto fra gli algoritmi.
 
 

Algoritmi   numero messaggi 
 entry-exit risorsa 
 Problemi
1. Centralizzato  3  Crash coordinatore
 Crash processo dentro risorsa 
2. Token Ring da 1 a infiniti  Crash processo
 Token perso
3. Completamente 
    Distribuito
2(n-1)  Crash processo
4. Token distribuito  (n-1)  Crash processo
 Perdita Token


 

Sistema di AZIONI

Per il kernel dei S.O. abbiamo gia' visto che il metodo di programmazione e' asincrono, cioe' ad ogni interruzione corrisponde un'azione. Le interruzioni fisiche arrivano ad esempio al chip i8259, vengono serializzate e quindi inviate una per una alla CPU.

In modo analogo si possono trattare eventi "software", che non sono interruzioni, ma:

In questo caso un processo puo' essere modellato (in modo molto intuitivo) in questo modo:

Lo schedulatore e' un programma software che seleziona quale evento deve essere considerato fra quelli presenti e provvede ad attivare l'azione corrispondente.
Poiche' le scelte possibili sono molte, il programmatore si limita a implementare un insieme di azioni, ciascuna collegata ad un evento, e definisce a parte le caratteristiche cui deve soddisfare lo scheduler (ad esempio che debba essere "fair", cioe' garantire che in un tempo finito se e' presente un evento, allora l'azione corrispondente sara' attivata, oppure definisce un criterio di priorita' ...). Le azioni  sono quindi svincolate dalla succesione temporale di esecuzione, perche'  ognuna e' abilitata da una condizione iniziale: il ricevimento di un messaggio o il verificarsi di una condizione logica su variabili interne.

Un'azione, una volta iniziata, non puo' essere interrotta, cioe' lo schedulatore puo' controllare lo stato del sistema ed attivare di conseguenza un'azione solo quando nessuna azione e' gia' in esecuzione. L'azione e' detta "atomica".

Negli algoritmi che seguono ogni condizione per l'abilitazione di un'azione, una volta diventata vera, lo rimane almeno finche' l'azione corrispondente non e' eseguita. Si suppone l'agente fair. Un processo e' quindi descritto da un insieme di variabili e da un insieme di azioni. Ogni azione ha un identificatore, e la sua condizione di abilitazione
e' scritta sulla prima riga (ricevimento di un messaggio o condizione logica su variabili interne del processo).
 

Algoritmi di mutua esclusione distribuita

1. Algoritmo Centralizzato

E' un'algoritmo asimmetrico, con un solo processo coordinatore.

Processo Coordinatore  (Coord)

Variabili

  state in {free, busy}   /*  stato della risorsa.
                              Inizialmente state=free         */
  queue                   /*  coda di attesa per le richieste.
                              Inizialmente queue=empty        */

Azioni

    C1: receive (request) from p;
          enqueue p;
   C2: receive (term);
       state:=free;
   C3: { (state=free) and (queue<>empty)}
       dequeue p;
       send reply to p;
       state=busy;

Processo Richiedente

Variabili

   coord            /*    processo coordinatore   */
   WillCR           /* variabile=true se il processo vuole usare
                       la risorsa. Inizialmente WillCR=false  */
   R1: { WillCR }
       send request to coord
       WillCR:=false;
   R2: receive (reply);
       usa la risorsa;
       send term to coord;

2. Algoritmo Distribuito di Rickard - Agrawala

Ogni processo esegue le stesse azioni (algoritmo simmetrico) e possiede le seguenti

Variabili:

   WillCR   =true se il processo vuole usare la risorsa
   eng      =true se il processo ha fatto richiesta per usare la
             risorsa,
   max      numero dei processi del sistema,
   clock    valore del clock logico,
   num      contatore reply,
   set      insieme dei processi da cui si e' ricevuta una request,
   myreq    valore del clock al momento della richiesta,
   myid     identificatore unico del processo.

Inizialmente

WillCR=false, eng=false, num=0, clock=1, set=empty.

Azioni

   A1: { WillCr }
       broadcast (request, clock||myid);
       myreq:=clock||myid;
       clock:=clock+1;
       eng:=true;
       WillCR:=false;
   A2: receive (reply);
       num:=num+1;
   A3: { num=max }
       use resource;
       eng:=false;
       num:=0;
   A4: { (eng=false) and (set<>empty) }
       for every p in set do
          send reply to p;
       set=empty;
   A5: receive (request, TS) from p;
       if (eng=false) or (myreq=TS) then
          send reply to p
       else insert p in set;
       clock:=max(clock, TS)+1;

NOTA: la funzione broadcast invia un messaggio a tutti i processi (compreso il sender) del sistema. Il mantenimento del clock logico puo' essere limitato ai soli messaggi di request.
 

3. Algoritmo di Token Passing senza struttura di Ring (Chandy)

Ogni processo esegue le stesse azioni e possiede le seguenti variabili:

Variabili

   WillCR   variabile=true se il processo vuole usare la risorsa,
   queue    coda dei processi da cui si e' ricevuta una request
   token    array di interi di dimensione =numero processi,
   M        numero di richieste di ingresso nella CR
   myp      processo corrente
   owner    =true se il processo possiede il token
   Inizialmente WillCR=false, queue=empty, token=[0], M=0;
   owner=false per tutti i processi escluso 1 (iniziatore).

Azioni

   A1: { WillCr }
       M:=M+1;
       broadcast (request, M);
       WillCR:=false;
   A2: receive (token);
       token[myp]:= M;
       usa la risorsa;
       owner:=true;
   A3: { owner and (queue<>empty) }
       dequeue (p, m);
       if m > token[p] then  begin
          send token to p;
          owner:=false     end;
   A4. receive (request, m) from p;
       enqueue p in queue;

Algoritmi di elezione

Nei casi in cui si usa un coordinatore centralizzato questo puo' fallire. E' allora necessario:

Nei casi in cui si usa il token invece di attivare un altro coordinatore occorre rigenerare uno e un solo token.

Vediamo come si puo' risolvere il primo problema, cioe' ricreare un coordinatore. Occorre passare da una situazione simmetrica (tutti i processi sono uguali) ad una asimmetrica (esiste un leader che sara' il coordinatore, o lo ricreera').

Si puo' effettuare una "elezione". Gli algoritmi di elezione richiedono normalmente:

Il coordinatore e' sempre il processo con il maggiore numero di priorita' non faulty. La sua identita' e' resa nota a tutti i processi del sistema.
 

Bully algorithm (Garcia-Molina 82)

Supponiamo che un qualunque processo pi invii una richiesta al coordinatore. Se dopo un tempo TM la richiesta non e' ancora stata soddisfatta, pi suppone che il coordinatore sia fallito.

pi allora cerca di eleggere se stesso come coordinatore:

  1. pi invia un messaggio di elezione a tutti i processi con maggior numero di priorita' (sono gli unici che potrebbero eventualmente contrastarlo)
  2. pi aspetta un tempo T per avere risposta.
  3. se non arrivano risposte nel tempo T, pi suppone che tutti i processi (con priorita' maggiore della sua) siano falliti. quindi pi si autoelegge nuovo coordinatore. Attiva una copia di coord e notifica i processi con minore priorita' del cambiamento (la coda e le richieste precedenti sono perse).
  4. se riceve almeno una risposta entro il tempo T, aspetta un tempo T' la comunicazione che un altro processo e' stato eletto. Se pero' entro un tempo T' non arriva la comunicazione del nuovo coordinatore, vuol dire che i processi che avevano risposto sono falliti e pi ricomincia l'algoritmo da capo (punto 1).

Messaggi che possono essere ricevuti da un processo pi:

  1. pj si annuncia come nuovo coordinatore: pj aveva rilevato il crash del vecchio coordinatore, aveva iniziato l'algoritmo di elezione e ne e' risultato vincitore. pi azzera la sua eventuale richiesta di risorsa, e memorizza l'identita' del nuovo coordinatore.
  2. messaggio di inizio tentativo di elezione da parte di pj (vedi punto 1 caso precedente). Deve essere j<i. pi ha dunque un numero di  priorita' maggiore di pj. quindi inizia anche lui la sua procedura di elezione, se gia' non l'ha fatto.
    pi invia una risposta (richiesta di attesa) a pj, per fermarlo.

Risultato: piu' di un processo puo' avviare l'algoritmo, ma un solo processo  completa il suo algoritmo di elezione: quello che ha il piu' alto numero di priorita' fra quelli funzionanti.

Quando un processo ex-failed effettua un recovery (oppure un nuovo processo si inserisce), inizia immediatamente il suo algoritmo di elezione. se ha la piu' alta priorita' ottiene comunque il controllo, in modo che il coordinatore abbia sempre la priorita' maggiore.

Esempio
4 processi p1, p2, p3, p4.   Il loro identificatore e' la priorita', quindi p4 e' il coordinatore.

In pratica con questo algoritmo si riesce a spezzare la simmetria dei processi.