Comunicazione: primitive. Comunicazione rendez-vous

(1)

Comunicazione II S.Balsamo - A. 2007 R13.1

Reti di calcolatori Reti di calcolatori

Prof.ssa Simonetta Balsamo Dipartimento di Informatica Università Ca’ Foscari di Venezia balsamo@dsi.unive.it http://www.dsi.unive.it/~reti

Comunicazione II

Comunicazione: primitive

Comunicazione: sincrona/asincrona - Primitive bloccanti/non bloccanti Ritardo nell’invocazione della primitiva:

non bloccante nessun ritardo bloccante comunicazione sincrona Primitive non bloccanti

send termina appena il messaggio è stato accodato o copiato localmente per la trasmissione

receive segnala la disponibilità a ricevere e predispone un’area di ricezione

uso di interruzioni per segnalare il completamento dell’operazione Primitive bloccanti

send non termina finché il messaggio non è stato trasmesso (anche ricevuto per comunicazione affidabile) receive non termina finché il messaggio non è nel buffer di ricezione

Comunicazione: primitive

Vantaggi e limiti Primitive non bloccanti

+ flessibilità

+ possibilità di prevedere la durata (e.g. comunicazione real-time) - possibile accesso multiplo all’area messaggi

- impredicibilità dello stato dell’altro: possibile difficoltà di programmazione - testing dei programmi più complesso

Primitive bloccanti + sicurezza

- impossibilità di prevedere la durata - limite al grado di parallelismo esplicitabile

Comunicazione: primitive e buffer

Buffer: spazio di memorizzazione coda di messaggi fra mittente e destinatario

Dimensione del buffer zero

finita infinita Buffer pieno send ritardata

send che provoca errore nel mittente Buffer vuoto receive ritardata

receive che provoca eccezione nel destinatario Buffer infinito la send non è mai ritardata

-> send asincrona

il mittente può continuare indipendentemente dal destinatario Buffer zero send e receive sincronizzate

-> send e receive sincrone - bloccanti

Comunicazione rendez-vous

Buffer zero: primitive bloccanti

Comunicazione rendez-vous (es. CSP, Occam,…) cliente e serventi hanno spazi di indirizzamento diversi deve essere resa visibile una interfaccia di ciascuno deve essere nota l’identità di ciascuno Uso del servizio di denominazione Pacchetti trasmessi dal supporto (trasporto)

send

Cliente ^ack

ack

Servente risposta

fase di rendez-vous Comunicazione II S.Balsamo - A. 2007 R13.6

Comunicazione con buffer finito

Buffer finito

il destinatario può specificare la dimensione massima del buffer il mittente può avanzare rispetto al destinatario di tale dimensione Gestione del buffer, maggiore complessità di implementazione del protocollo di comunicazione

Gestione degli oggetti (buffer e messaggi)

Primitive: sincrone bloccanti sincronizzazione mittente-destinatario sincrone non bloccanti sincronizzazione del messaggio successivo recupero del messaggio asincrone non bloccanti

asincrone bloccanti

quanto tempo aspettare?

Introduzione del time-out cliente e servente

(2)

Comunicazione con buffer finito

Comunicazione con primitive sincrone e buffer finito:

possibile deadlock

send

Cliente _send Servente

In caso di assenza di memoria i due processi si bloccano vicendevolmente Possibile deadlock dovuto ad un ciclo di comunicazioni bloccate

Comunicazione e affidabilità

 Tolleranza ai guasti e agli errori

perdita di messaggi

duplicazione di messaggi

nodi non raggiungibili

ordinamento di messaggi

 Primitive affidabili / non affidabili (con / senza ack)

garanzia di consegna (uso di ack)

time-out e ritrasmissione

Quante ritrasmissioni?

Quale durata di time-out?

 Progettazione della comunicazione: a che livello introdurre la affidabilità della comunicazione?

prestazioni

costo

flessibilità

Comunicazione e affidabilità

Affidabilità e semantica della comunicazione

 may be non si sa se la comunicazione è avvenuta

at least once la comunicazione può essere avvenuta più volte possibili messaggi duplicati

at most once la comunicazione è avvenuta al più una volta può non essere avvenuta

il mittente può non sapere dell’esito -> ritrasmissione

->numerazione da parte del destinatario

exacly once la comunicazione è avvenuta esattamente una volta oppure non è avvenuta e il mittente conosce l’esito il destinatario traccia le comunicazioni e scarta i

duplicati

quanto deve essere lunga la storia delle comunicazioni?

-> semantica con conoscenza dello stato dell’altro e durata del protocollo

Comunicazione tipi di primitive

Primitive

 simmetriche

send(nome_destinatario, messaggio) receive(nome_mittente, messaggio)

asimmetriche

send(nome_destinatario, messaggio) receive(qualsiasi_mittente, messaggio)

 lascia libertà ai processi

 minore leggibilità

 minore modularità

 non si possono avere più clienti contemporaneamente

indiretteuso di link, porte o altre entità intermedie link: canale di comunicazione unidirezionale

il mittente conosce il destinatario e non viceversa send(link, buffer) receive(link, buffer) il cliente conosce il link del servente e invia un link al servente per avere la risposta

migliore dinamicità - migrazione

uso di aree dedicate alla trasmissione anche di grandi dimensioni

maggior overhead Comunicazione II S.Balsamo - A. 2007 R13.11

Comunicazione tipi di primitive

Porte

oggetto protetto dal nucleo con operazioni specifiche:

invio, ricezione, priorità send(porta, buffer) receive(porta, buffer) solo un processo per volta può effettuare le operazioni consentite alla porta è associata una coda FIFO

il processo proprietario della porta può distribuire i diritti e passare anche la porta quando il processo termina la porta termina (può provocare eccezioni agli altri) mailbox

nome globale per la comunicazione indiretta send(mailbox, buffer) receive(mailbox, buffer) overhead

Comunicazione a gruppi

Comunicazione uno - a - tutti: broadcast Comunicazione uno - a - molti: multicast

messaggio multicast inviato da uno ad un gruppo utile per tolleranza ai guasti in applicazioni distribuite Multicast

Motivazioni per il multicast

• Tolleranza ai guasti - replicazione servizi - stessa richiesta a più serventi in parallelo; tollera guasti dei serventi

•ricerca e localizzazione di oggetti distribuiti - es. File system distribuito: il server appropriato risponde

•replicazione dei dati - migliori prestazioni - ad una modifica il gestore delle copie invia messaggio multicast

•aggiornamento multiplo

(3)

Protocolli multicast

Come si trattano le risposte?

senza attesa attesa di una sola risposta attesa di alcune risposte - quante?

attesa di tutte le risposte

Mittente

Destinatario 1

Destinatario 2

Destinatario 3 richiesta

multicast

risposta 1

risposta 2

risposta 3 richiesta ripetuta per 3

Protocolli multicast

Sollecito selettivo globale Conferma positiva (ack)

negativa (nack) Numero di conferme attese Semantica del multicast Implementazione del multicast

indirizzi di gruppo classe D nel protocollo IP (livello 3) supporto di broadcast es. Ethernet

supporto punto-a-punto

lista con uso di attributi: invio di messaggi con predicato il destinatario che soddisfa il predicato può ricevere il messaggio

Multicast: atomicità e affidabilità

Multicast atomico

garanzia di consegna a tutti i componenti del gruppo ricevuto da tutti o da nessuno

Multicast affidabile garanzia di consegna Multicast non affidabile

spedisce una sola volta

Ordinamento dei messaggi ai destinatari?

Singoli multicast atomici mantengono l’ordine FIFO dei messaggi - per un mittente e un destinatario

ma per più mittenti di multicast si può avere disordine

Protocolli multicast

Multicast totalmente ordinato per trasmettere da più clienti I messaggi trasmessi ad un gruppo in multicast arrivano ad ogni membro del gruppo in ordine

mitt 1 mitt 2 mitt 3 mitt 4

A

B

A B B A

Protocolli multicast: ordinamento

Multicast FIFO

ordinamento solo dallo stesso mittente allo stesso destinatario Multicast causale

ordinamento logico (causale)

consegna in un ordine che rispetta una regola di causalità se un evento A precede un evento B

allora i messaggi sono consegnati rispettando tale ordine algoritmi di ordinamento (Lamport)

Multicast totalmente ordinato

se atomico, consegna ad ogni membro del gruppo nello stesso ordine

Differenza fra multicast causale ed atomico

Protocollo multicast:

implementazione

Diverse implementazioni del multicast

* semplice ma non efficiente: tramite send potenzialmente inaffidabile

procedure multicast (dest: array of PortId; m: messaggio);

var i: cardinal;

begin

for i:=0 to Max (dest) do Send (dest(i),m);

end;

* per multicast affidabile:

- controllo di perdita di messaggi - crash del mittente attesa della risposta time-out e ritrasmissione

(4)

Protocollo multicast affidabile:

implementazione

* gestione dei guasti - omissione di messaggi - failure del mittente occorre effettuare un monitoraggio

- controllo della trasmissione corrente - eventuale ritrasmissione - rimozione dei processi falliti - gestione del gruppo implementazione:

- invio del messaggio a tutto il gruppo - attesa della risposta - time-out e ritrasmissione problema: guasto del monitor

- attesa, quanto?

Protocollo multicast atomico e affidabile

1 mittente invia un messaggio al gruppo e aspetta ack da ognuno 2 se arrivano tutti gli ack OK

altrimenti se non arrivano entro un timeout: ritrasmissione ripetendo l’attesa un dato numero di volte, oltre le quali si elimina dal gruppo chi non risponde

Quando un processo aspetta la risposta da un altro processo del gruppo, lo monitorizza (mittente) per identificare possibili eventuali guasti (richiede la trasmissione della risposta)

Possibile esclusione da un gruppo.

Muticast atomico e affidabile - costoso

Protocollo multicast atomico e affidabile

Problema: guasto mittente Per atomicità

ogni destinatario invia un ack e monitorizza il mittente per attesa di conferma il mittente completato il multicast, manda conferma a tutti (in m. atomico) Con un multicast per volta il successivo è la conferma dal mittente del m.

precedente - soluzioni inefficienti -

Hold-back queue

Altre soluzioni al multicast atomico e affidabile Hold-back queue

Il messaggio a destinazione viene tenuto in sospeso prima di essere consegnato, fino all’arrivo del messaggio di consegna

Per garantire l’ordinamento e l’atomicità i messaggi sono numerati e ogni messaggio è ritardato finché non arrivano i precedenti

Atomicità e ordine

Mittente

Destinatario Hold back queue

Coda di destinazione

Negative ack

Altre soluzioni al multicast atomico e affidabile Negative ack

I messaggi sono numerati ordinatamente dal mittente

Il destinatario invia un segnale di NACK se il numero di messaggio arrivato non è in sequenza

Il destinatario non invia ACK

Il mittente ha copia (storia) dei messaggi inviati Gestione possibili guasti del mittente recuperabili dal destinatario Anche i destinatari devono avere la storia dei messaggi Problema della lunghezza della storia

Possibili occasionali ack positivi (con # messaggio ricevuto) in piggyback

Multicast atomico e totalmente ordinato

Si associa ad ogni messaggio un identificatore unico totalmente ordinato Un messaggio è stabile a destinazione se non possono arrivare altri messaggi con id. più basso.

Si passano ai livelli superiori (applicazione) solo i messaggi stabili

Semplice da realizzare se ogni mittente usa il # in sequenza con riferimento ad un ordinamento totale

Ogni destinatario è sicuro del messaggio solo se non esiste un gap con il successivo

Sequenza condivisa di identificatori

(5)

Multicast atomico e totalmente ordinato

Soluzioni:

a) usare una marca temporale (timestamp) da orologi logici o fisici b) usare un processo sequenziatore

c) usare un protocollo fra i membri del gruppo per la generazione di un identificatore

Soluzioni b e c integrano il calcolo dell’identificatore con il multicast Problemi aperti

Multicast atomico e totalmente ordinato

Implementazione:

- centralizzata

unico gestore che ordina collo di bottiglia - distribuita

coordinamento fra i riceventi che concordano l’ordine diverse implementazioni

es. un gestore per ogni richiesta soluzione inefficiente e poco scalabile es. uso di broadcast

solo per casi particolari algoritmi distribuiti per sistemi distribuiti

Multicast in Java

Implementazione in Java

Java fornisce un insieme di classi primitive per il multicast

MulticastSocket sottoclasse di DatagramSocket Invio di messaggi in multicast è simile all’invio su un socket UDP

- creare un datagram - specificare il TTL (numero di hop) Operazioni:

- creazione un socket multicast - iscrizione ad un gruppo multicast - invio dati al gruppo - ricezione dal gruppo - abbandono del gruppo