In molte applicazioni distribuite è utile conoscere lo stato globale in cui si trova correntemente il sistema.
Intuitivamente, lo stato globale di un sistema distribuito consiste di:
La determinazione dello stato globale è complessa per via della mancanza di un tempo globale in un sistema distribuito, né d’altra parte è possibile una sincronizzazione perfetta dei clock locali.
L’esigenza di determinare lo stato globale si presenta in molti problemi pratici, quali:
Garbage collection: se nessuno dei processi di un sistema possiede un riferimento a un oggetto X, non è detto che esso possa essere considerato garbage: se nella rete è in transito un messaggio con un riferimento a X, il processo ricevente potrà accedervi in futuro.
Deadlock detection: è il classico problema di attesa reciproca tra due processi (o in generale, attesa di tipo circolare tra n processi)
Termination detection: è il problema di determinare se una computazione distribuita è terminata. Ad esempio, in un sistema con due soli processi, se entrambi sono in uno stato di attesa passiva non si può concludere che l’elaborazione sia terminata: se nella rete è in transito un messaggio dall’uno all’altro dei processi, con una richiesta di attivazione, l’elaborazione riprenderà.
L’occorrenza di una singola azione in pi è un evento e.
Gli eventi sono di due tipi:
L’insieme degli eventi di un processo pi può essere ordinato totalmente in base alla relazione di precedenza temporale:
La storia (locale) di un processo pi è la successione di eventi che ha luogo in pi, ordinata in base alla relazione di precedenza temporale:
La storia (locale) iniziale di pi fino all’evento k è:
Un taglio dell’esecuzione di un sistema distribuito è un sottoinsieme della sua storia globale, costituito dall’unione di storie iniziali dei processi:
taglio C = h1c1∪h2c2 ∪ … ∪ hNcN
La frontiera del taglio è l’insieme di tutti gli ultimi eventi verificatisi negli N processi pi prima del taglio:
frontiera F = { eici } i = 1, …, N
Un taglio C è consistente se, per ogni evento e contenuto, contiene anche tutti gli eventi “happened-before” e:
CC = h1c1 ∪ h2c2 ∪ … ∪ hNcN / ∀ e ∈ CC, f → e ⇒ f ∈ CC
Uno stato globale S di un sistema distribuito è una unione di stati dei singoli processi:
S0 = (S1, , S2…, SN)
Non tutti i possibili stati globali sono significativi.
Uno stato globale consistente CS di un sistema distribuito è uno stato globale corrispondente ad un taglio consistente.
L’evoluzione di un sistema distribuito è una successione di transizioni tra stati globali consistenti:
S0 → S1 → S2 → …
Una esecuzione (run) di un sistema distribuito è un ordinamento totale degli eventi in una storia globale H, consistente con l’ordinamento di ogni storia locale.
Non tutte le esecuzioni attraversano solo stati globali consistenti.
Una esecuzione consistente (consistent run) o linearizzazione di un sistema distribuito è un ordinamento totale degli eventi in una storia globale H, consistente con tutte le relazioni HB (happened-before) tra gli eventi.
Una linearizzazione è una esecuzione.
Una linearizzazione attraversa solo stati globali consistenti.
Uno stato globale S’ si dice raggiungibile da S se esiste una linearizzazione che passa per S e poi per S’.
Ipotesi:
Caratteristiche dell’algoritmo:
L’algoritmo fa uso di messaggi marker, che svolgono un doppio ruolo:
Nella figura è riportata l’ganizzazione di un processo (canali entranti, uscenti, stato locale, file system locale, marker) per l’algoritmo di Chandy e Lamport
Regola di ricezione per il processo pi
Alla ricezione di un marker sul canale entrante c:
if (pi non ha ancora salvato lo stato) then
registra lo stato del processo;
registra come vuoto lo stato del canale c;
avvia la registrazione dei messsaggi sugli altri canali entranti;
else
registra lo stato di c come insieme dei messaggi registrati
end if
Regola di invio per il processo pi
Dopo aver salvato lo stato, invia un marker su ogni canale uscente c prima dell’invio di ogni altro messaggio su c
Dinamica:
A) Il processo pi: (1) riceve un marker per la prima volta, (2) registra il suo stato, e (3) invia un marker su ogni canale di uscita.
B) pi registra tutti i messaggi entranti;
pi riceve un marker sul canale i1 e termina la registrazione dello stato di quel canale.
Il processo p1 compra dal processo p2 oggetti del costo di 1 € cad.
Il processo p1 avvia lo snapshot: salva il proprio stato; avvia la registrazione sul canale entrante c2; invia un marker M sul canale c1.
Stato iniziale S0: (p1: 10 €, 0 oggetti), (p2: 50 €, 20 oggetti), canali vuoti.
p1 ordina due oggetti (dopo il marker, vedi regola di invio); il sistema si trova nello stato S1:
(p1: 8 €, 0 oggetti), (p2: 50 €, 20 oggetti), (c1: 2 €, c2 vuoto)
p2 evade l’ordine di 5 oggetti; il sistema transita nello stato S2:
(p1: 8 €, 0 oggetti), (p2: 50 €, 15 oggetti), (c1: 2 €, c2: 5 oggetti)
p1 riceve i 5 oggetti; p2 riceve M, salva il proprio stato (50 €, 15 ogg.) e salva lo stato di c1 come vuoto; nuovo stato S3:
(p1: 8 €, 5 oggetti), (p2: 50 €, 15 oggetti), (c1: 2 €, c2: 5 oggetti)
Stato calcolato dall’algoritmo di snapshot:
Ssnapshot:
p1: 10 €, 0 oggetti p2: 50 €, 15 oggetti
c2: 5 oggetti c1: vuoto
Questo stato differisce dagli stati So, S1, S2, S3 effettivamente attraversati dal sistema; tuttavia è uno stato consistente (anche in Ssnapshot ci sono in tutto 50 € e 20 oggetti).
Stato calcolato dall’algoritmo di snapshot:
Ssnapshot:
p1: 10 €, 0 oggetti
c1: vuoto
p2: 50 €, 15 oggetti
c2: 5 oggetti
Questo stato differisce dagli stati So, S1, S2, S3 effettivamente attraversati dal sistema; tuttavia è uno stato consistente (anche in Ssnapshot ci sono in tutto 50 € e 20 oggetti).
L’algoritmo di snapshot distribuito termina certamente, se si assume che un processo che riceve un marker:
In tali ipotesi, se esiste un percorso tra un processo pi e un processo pj, allora pj registrerà il suo stato in un tempo finito dopo che pi ha registrato il suo stato.
Poiché per ipotesi il grafo di processi e canali è strettamente connesso, tutti i processi registreranno il proprio stato entro un tempo finito dopo che qualche processo ha dato inizio all’algoritmo, registrando il proprio stato.
Siano ei, ej due generici eventi rispettivamente in pi, pj, con ei → ej, i ≠ j.
Lo stato globale è consistente se, qualora ej appartenga al taglio, anche ei appartiene al taglio (nel caso i = j ciò è ovvio).
Lo stato globale selezionato dall’algoritmo di snapshot è consistente.
Dimostrazione: se ej appartiene al taglio, allora si è verificato prima che pj registrasse il suo stato, e non è possibile che ei si sia verificato dopo che pi aveva registrato il suo stato.
Infatti, poiché ei → ej, esiste una sequenza di messaggi m1, …, mh (h ≥ 1) che contribuisce a determinare la relazione ei → ej. Se per assurdo pi avesse registrato il suo stato prima del verificarsi di ei, per via delle due regole dell’algoritmo e poiché i canali sono FIFO, un marker avrebbe dovuto raggiungere pj prima di ej. Per la regola di ricezione, pj avrebbe allora registrato il suo stato prima di ej; ciò contraddice l’ipotesi che ej non sia nel taglio.
Siniziale: stato globale del sistema, immediatamente prima che il primo processo registri il suo stato;
Ssnaphot: stato globale osservato dall’algoritmo;
Sfinale: stato globale del sistema alla terminazione dell’algoritmo, immediatamente dopo l’ultima azione di registrazione di uno stato.
La proprietà di raggiungibilità dello stato Ssnaphot osservato con l’algoritmo distribuito è utile per determinare la validità di predicati stabili.
Infatti, se un predicato stabile P è vero nello stato Ssnaphot, allora è vero anche nello stato finale Sfinale, poiché per definizione un predicato stabile vero in uno stato S resta vero in ogni stato raggiungibile da S.
Analogamente, se un predicato stabile P è falso nello stato Ssnaphot, allora deve essere falso anche nello stato Siniziale.
Problema:
Determinare se una computazione distribuita è terminata.
Una computazione distribuita può ritenersi terminata quando:
Si suppone che lo scambio di messaggi nel sistema sia affidabile, cioè i messaggi sono consegnati:
Soluzione – Versione modificata del Distributed Snapshot di Chandy e Lamport (1985)
Un processo P invia il MARKER ad un processo Q; Q annota P come suo predecessore (Q è successore di P).
Come previsto dall’algoritmo di C&L, Q inoltra il MARKER su tutti i canali in uscita, ed avvia la registrazione dei canali in ingresso.
Appena Q termina la sua parte di snapshot, invia uno dei seguenti messaggi a P:
DONE ⇔ Tutti i successori di Q hanno restituito DONE, ovvero se Q non ha ricevuto alcun messaggio nell’intervallo [t0-tn]
CONTINUE in tutti gli altri casi
Il processo che ha avviato lo snapshot riceve un messaggio DONE se e solo se tutti i processi nel sistema distribuito hanno inviato un messaggio DONE.
In tal caso nessun messaggio è in circolazione nel sistema e la computazione può ritenersi terminata.
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software
G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. XI §5), IV ed., 2005