Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 4.Stato globale nei Sistemi Distribuiti


Sommario

  • Stato globale di un sistema distribuito
  • Tagli
  • Linearizzazione e raggiungibilità
  • Algoritmo di snapshot distribuito di Chandy e Lamport
  • Proprietà dello snapshot
  • Esempio applicativo: termination detection distribuita

Stato globale di un sistema distribuito

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:

  • stato locale di ciascun processo; in cosa consista lo stato locale, dipende da ciò cui si è interessati, può includere p.es. il valore di variabili locali, i record di una base dati, o lo stato di alcuni file;
  • messaggi inviati ma non ancora ricevuti, che si possono dunque pensare come in transito nei canali di comunicazione tra processi.

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.

Stato globale di un sistema distribuito: esempi

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à.

Eventi e storia di un processo

L’occorrenza di una singola azione in pi è un evento e.

Gli eventi sono di due tipi:

  • eventi interni al processo (es.: aggiornamento di una variabile);
  • eventi di invio o ricezione di messaggi.

L’insieme degli eventi di un processo pi può essere ordinato totalmente in base alla relazione di precedenza temporale:

  • e → e’ se e solo se e si è verificato prima e’ di in pi.

Eventi e storia di un processo

La storia (locale) di un processo pi è la successione di eventi che ha luogo in pi, ordinata in base alla relazione di precedenza temporale:

  • storia(pi) = hi = <ei0, ei1, ei2,…>

La storia (locale) iniziale di pi fino all’evento k è:

  • storia(pi,k) = hik = <ei0, ei1, …, eik>

Taglio

Un taglio dell’esecuzione di un sistema distribuito è un sottoinsieme della sua storia globale, costituito dall’unione di storie iniziali dei processi:

taglio C = h1c1h2c2 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


Tagli consistenti

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


Stato globale e stato globale consistente

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 → …

Esecuzione ed esecuzione consistente

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.

Linearizzazione e raggiungibilità

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’.

Algoritmo di snapshot di Chandy e Lamport

Ipotesi:

  • i processi non sono soggetti a fallimenti;
  • i canali non sono soggetti a fallimenti: la comunicazione è affidabile e prima o poi ogni messaggio viene ricevuto una e una sola volta;
  • i canali sono unidirezionali e di tipo FIFO;
  • il grafo dei processi e dei canali è fortemente connesso (c’è un percorso tra ogni coppia di processi).

Algoritmo di snapshot di Chandy e Lamport

Caratteristiche dell’algoritmo:

  • qualunque processo può dar inizio all’algoritmo in un qualsiasi istante;
  • i processi non interrompono le loro elaborazioni e lo scambio messaggi durante lo snapshot;
  • lo stato osservato dall’algoritmo distribuito è consistente;
  • lo stato osservato dall’algoritmo distribuito può non corrispondere a nessuno stato globale effettivamente attraversato dal sistema in un qualche istante.

Algoritmo di snapshot di Chandy e Lamport

L’algoritmo fa uso di messaggi marker, che svolgono un doppio ruolo:

  • obbligano il ricevente a salvare il proprio stato, se ancora non l’ha fatto;
  • servono a discriminare i messaggi da includere nello stato del canale.

Nella figura è riportata l’ganizzazione di un processo (canali entranti, uscenti, stato locale, file system locale, marker) per l’algoritmo di Chandy e Lamport


Algoritmo di snapshot 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

Algoritmo di snapshot di Chandy e Lamport

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.

Esemplificazione dell’algoritmo di snapshot

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.


Esemplificazione dell’algoritmo di snapshot

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)


Esemplificazione dell’algoritmo di snapshot

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).


Esemplificazione dell’algoritmo di snapshot

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).


Terminazione dell’algoritmo di snapshot distribuito

L’algoritmo di snapshot distribuito termina certamente, se si assume che un processo che riceve un marker:

  • salvi il suo stato in un tempo finito;
  • invii i marker sui canali uscenti in un tempo finito.

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.

Proprietà dello snapshot

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.

Proprietà dello snapshot (segue)

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.

Raggiungibilità degli stati nell’algoritmo di snapshot

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.


Stabilità e raggiungibilità dello snapshot

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.

Esempio: Termination Detection

Problema:

Determinare se una computazione distribuita è terminata.

Una computazione distribuita può ritenersi terminata quando:

  • i processi non hanno in corso elaborazioni e sono al più in uno stato passivo;
  • nello stato osservato (snapshot) non ci sono messaggi in transito (inviati ma non ancora ricevuti).

Si suppone che lo scambio di messaggi nel sistema sia affidabile, cioè i messaggi sono consegnati:

  • certamente (prima o poi),
  • inalterati,
  • una e una sola volta (nessuna duplicazione)
  • nell’ordine di spedizione (per ciascun canale –> canali FIFO)

Esempio: Termination Detection

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


Esempio: Termination Detection

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.

Esempio: Termination Detection

Esempio – Computazione non terminata

Esempio – Computazione non terminata


Esempio: Termination Detection

Esempio – Computazione terminata

Esempio – Computazione terminata


I materiali di supporto della lezione

G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. XI §5), IV ed., 2005

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion