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 » 24.Esercitazione - Algoritmo snapshot di Chandy-Lamport


Sistema bancario

Si consideri un programma distribuito che simuli il comportamento di un sistema bancario in cui:

  • ogni processo del sistema ha un deposito di denaro
  • ogni processo può prelevare una certa somma dal proprio deposito ed inviarla ad un processo vicino, che a sua volta lo deposita sul proprio conto.

Il sistema è caratterizzato da un system value dato da somma di denaro dei vari conti e di quello in transito tra i conti.

Il programma deve essere in grado di determinare il system value in ogni processo del sistema senza interrompere la normale esecuzione del programma.
Il programma termina quando il system value è noto a tutti i processi del sistema.

Il sistema

Il deposito di ciascun processo è scelto in maniera casuale.

Allo stato iniziale tutti i processi sono nello stato RUNNING.

Le somme di denaro scambiate tra i processi sono scelte in maniera casuale.

Ad un certo istante (random) occorre determinare il system value.

Ciò può essere fatto utilizzando l’algoritmo di Chandy-Lamport.

Lo snapshot

Il processo 0 avvia l’algoritmo
Lo stato del processo 0 passa da RUNNING a SNAPPING
Gli altri processi cambiano stato da RUNNING a SNAPPING quando ricevono un messaggio snap

Quando un processo cambia il suo stato in SNAPPING:

  • determina il valore corrente del proprio deposito e lo memorizza in una variabile snapValue
  • invia un messaggio marker (snap) a tutti i processi vicini (quindi su tutti i canali di uscita)
  • continua le operazioni in maniera normale ma aggiunge il valore della somma ricevuta da ciascun vicino (quindi da tutti i canali di ingresso) allo snapValue fino alla ricezione di un messaggio snap dallo specifico vicino (sul canale di ingresso)
  • se il processo ha ricevuto messaggi snap da tutti i vicini (cioè da tutti i canali di ingresso) il valore di snapValue rappresenta la componente del processo al system value.

Confronto con Chandy-Lamport


Broadcasting

Il programma continua finché ciascun processo non abbia determinato il valore finale di totalValue.
Ciascun processo controlla il numero di messaggi snap che deve ancora ricevere (missingSnaps) dai processi vicini (cioè su tutti i canali di ingresso).
Quando un processo ha determinato il proprio valore finale di snapValue si porta nello stato BROADCASTING ed invia tale valore (ed il suo id) in broadcast e continua le operazioni.
Alla ricezione dello snapValue di un altro processo, se questo non è già stato ricevuto, il valore contenuto viene sommato al totalValue e inoltrato ai vicini.
Ciascun processo attende di ricevere gli snapValue da tutti gli altri processi del sistema (missingValues), determina il valore definitivo di totalValue (che rappresenta il system value) e si porta nello stato TERMINATED.

Tutti i processi devono avere lo stesso totalValue:

  • un’assertion controlla che ciò sia verificato
  • in caso contrario viene visualizzato il messaggio “Assertion failed”.

Main.java

Mostra codice

ValueMessage.java

Mostra codice

SnapMessage.java

Mostra codice

ResultMessage.java

Mostra codice

Prog.java

Mostra codice

TotalValue.java

Mostra codice

Implementazione con programmazione multithread e concorrente in Java

Si consideri una implementazione dell’algoritmo Snaphot di Chandy-Lamport in Java.
Si utilizzano più thread per

  • invio e
  • ricezione dei messaggi.

L’accesso ai canali ed alle variabili rappresentanti lo stato locale di ciascun processo avviene in maniera concorrente:

  • deve quindi essere sincronizzato.

Ciascun processo può sia inviare che ricevere messaggi, funge quindi sia da client che da server:

  • occorre un thread che gestisca le connessioni in ingresso (per evitare che il processo resti in attesa di una richiesta di connessione sulla server socket).

Process.java

Mostra codice

SocketListener.java

Mostra codice

Sender.java

Mostra codice

Receiver.java

Mostra codice

Main.java

Mostra codice

I materiali di supporto della lezione

Codice DAJ

Codice Java MT

  • 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