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.
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.
Caratteristiche:
Prima di vedere un terzo algoritmo, e' necessario definire cos'e' un
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:
Le richieste a cui non e' inviato immediatamente un reply sono memorizzate.
Esempio
Caratteristiche dell'algoritmo:
Svantaggi dell'algoritmo:
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 |
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;
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:
Messaggi che possono essere ricevuti da un processo pi:
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.