Progetto di una architettura per Progetto di una architettura per l’esecuzione distribuita e coordinata l’esecuzione distribuita e coordinata

di azionidi azioni

Progetto per l’esame di

Reti di Calcolatori L-SProf. Antonio Corradi

Finistauri Matteo

L’idea del progetto: coordinazione

Pronto per Stato

A

Pronto per

Stato A

Pronto per Stato

A

Pronto per

Stato A

Stato A

Pronto per Stato

B

Pronto per

Stato B

Pronto per Stato

B

Pronto per

Stato B

Stato B

Il gruppo di computer Il gruppo di computer si coordina per si coordina per passare allo stato passare allo stato concordato concordato contemporaneamentcontemporaneamentee

L’esecuzione procede L’esecuzione procede passo-passo passo-passo sincronizzatasincronizzata

L’idea del progetto: controllo remoto

Computer A

Computer B

Computer D

Computer C

Configuratore

Computer A, devi fare

operazione A

Ok! Eseguo l’operazione

richiesta

Operazione AOk! Eseguo l’operazione

richiesta

Operazione D

Computer D, devi fare

operazione D

Caratteristiche del sistema

Funzionalità del sistema:• Controllo remoto dei componenti da una

posizione definita (configuratore)• Esecuzione di operazioni sui componenti• Coordinazione delle operazioni in determinati

momenti dell’esecuzione

Problemi da risolvere:• Dinamicità del gruppo (caduta, etc.)• Comunicazioni reliable• Algoritmo per la sincronizzazione dei componenti

Applicazioni: mostra virtuale

Ci aoTipico paesaggio

di Perugia

Foto realizzata da ...

Split di un contenuto della mostra su più monitor

Contenuto con un commento

Il contenuto dei due schermi cambia in maniera sincrona

Descrizione del sistemaDescrizione del sistema

Architettura del sistema

Componente del

gruppo

Componente del gruppo

Componente del

gruppo

Controllo della

disponibilità

Gestione dei gruppi

Gestione dei

componenti

Configuratore Servizi

Il configuratore

• Rappresenta l’interfaccia verso il sistema per l’amministratore.

• Fornisce le seguenti funzionalità:– Visualizzazione dello stato del sistema

(componenti, esecutori, gruppi)– Gestione dei gruppi (compreso inizio

esecuzione e fine esecuzione)– Gestione degli esecutori

Il componente di gruppo

• E’ il componente che esegue fisicamente le operazioni.

• Non è controllabile in maniera diretta ma solo attraverso il configuratore.

• Fornisce le seguenti funzionalità:– Ricezione delle istruzioni da parte del

configuratore (gruppo, esecutore, start e stop del gruppo)

– Sincronizzazione con gli altri componenti in corrispondenza di un checkpoint

– Esecuzione delle operazioni locali stabilite dall’esecutore

Servizi di sistema

• La gestione dei componenti tiene conto dei componenti presenti all’interno del sistema.

• La gestione dei gruppi tiene conto della composizione dei gruppi

• Il controllo della disponibilità si occupa della disponibilità dei vari componenti del sistema– I componenti di gruppo e il configuratore non sono

replicati– Viene utilizzato un meccanismo di lease per

riconoscere i componenti caduti. Pro: meccanismo semplice ed efficace. Contro: overhead per il rinnovo del lease.

Disponibilità dei componenti

• Sia i componenti di gruppo che il configuratore vengono gestiti attraverso il lease: – I componenti di gruppo non sono replicati per

questioni applicative.– Il configuratore non è replicato perché costituisce

l’interfaccia per l’utente-amministratore.

• I servizi di sistema devono essere necessariamente attivi durante tutta la vita dell’applicazione:– I servizi di sistema possono essere replicati senza

alcun problema.

L’infrastruttura di L’infrastruttura di comunicazionecomunicazione

Infrastruttura di comunicazione

• Basata su meccanismi simili a chiamate a procedura remota.

• Permette di:– effettuare il controllo remoto dei componenti– comunicare con i servizi di sistema

• Si basa su:– TCP: nel caso di comandi con passaggio di

parametri o risposta – semantica sincrona.– UDP (versione at-most-once): nel caso di

comandi senza passaggio di parametri o risposte – semantica asincrona di tipo catch & return.

Infrastruttura di comunicazione

Server Request manager

Request acceptor Request

Service• Attende un messaggio in ingresso

• Gestisce la singola richiesta

• Provvede a inviare la risposta al cliente

• Crea l’oggetto request associato alla richiesta

• Incapsula la richiesta, conoscendone i dettagli

• Può eseguire la richiesta localmente

• Rappresenta il servizio fornito dal sistema

• Fornisce l’interfaccia per le operazioni che possono essere fatte su un componente del sistema

Cliente

Execute()

Method()

UDP versione at-most-once

• Obiettivo: ottenere la sicurezza che un comando con UDP arrivi a destinazione

• Passo 1: aggiunta di un messaggio di acknowledgement

P1 P2 P1 P2 P1 P2

1a possibilità 2a possibilità 3a possibilità

Se il messaggio di acknowledgement arriva a destinazione abbiamo la certezza che il messaggio è stato ricevuto dal

destinatario

OK

UDP versione at-most-once

• Obiettivo: ottenere la sicurezza che un comando con UDP arrivi a destinazione

• Passo 2: ritrasmissione del messaggio in caso di scadenza di un timeout

P1 P2 P1 P2

2a possibilità 3a possibilità

La ritrasmissione può essere fatta un numero N di volte definito a priori per evitare tentativi all’infinito. Dopodiché si considera il nodo destinazione caduto.

UDP versione at-most-once

• Obiettivo: ottenere la sicurezza che un comando con UDP arrivi a destinazione P1 P2

2a possibilità

• Passo 3: aggiungere una numerazione per evitare la ricezione di uno stesso messaggio due volte.

• Il messaggio non viene passato alla parte applicativa se è ripetuto.

K

K

K

KSolo

ack

UDP versione at-most-once

• Obiettivo: ottenere la sicurezza che un comando con UDP arrivi a destinazione P1 P2

2a possibilità

• Passo 4: aggiunta di un livello per gestire gli acknowledgement

• Il processo P3 (di livello applicativo) può andarsene dopo aver ricevuto il messaggio.

• Altrimenti il processo P3 dovrebbe restare per vedere se il mittente ha ricevuto l’acknowledgement

K

K

K

KSolo

ack

P3

Receive()

return

Un altro protocollo…

• Il TCP transazionale può essere utilizzato per realizzare una chiamata a procedura remota.

• Prevede tre pacchetti per implementare tutta la logica di TCP e di ottenere i relativi vantaggi. Risulta quindi essere di poco più pesante rispetto al protocollo utilizzato.

• L’utilizzo di questo protocollo permetterebbe di superare i problemi riconosciuti dell’algoritmo sviluppato: – Non riconoscimento dei messaggi precedenti all’ultimo

ricevuto.

Algoritmi di sincronizzazioneAlgoritmi di sincronizzazione

Algoritmi di sincronizzazione

• Basato sulla relazione di Lamport

Componente 1: Ta

To:Po

Componente 2: Tb

Componente 3: Tc

Ta:P1 Ta:P1

Tb:P2 Tb:P2

Tc:P3 Tc:P3

Ta:P1

Tb:P2

Tc:P3

To:Po To:Po

Il componente 1 arriva al checkpointIl componente 2 arriva al checkpointIl componente 3 arriva al checkpointI componenti sono tutti arrivati al checkpoint: si può proseguire

Costo algoritmo: N(N – 1) = O(N2)

Algoritmi di sincronizzazione

Servizio dei gruppi

pronto

pronto

pronto

prossimo

prossimo

prossimo

Servizi troppo carichi di lavoro

Costo algoritmo:

N + N = 2 N = O(N)

Algoritmi di sincronizzazione

Servizio dei gruppi

pronto

pronto

pronto

prossimo

coordinator

prossimo

Scarica la responsabilità del secondo messaggio su uno dei componenti

Costo algoritmo:

N + 1 + (N – 1) =

2 N = O(N)

Altri possibili algoritmi…

• Estensioni a gruppi di oggetti per risorse fault-tolerant (modello a copie attive)– Le copie rappresentano i componenti di gruppo– Pro: modello studiato, sperimentato e approfondito– Contro: mancanza del concetto di minimizzazione dei

tempi di contatto fra le “copie attive”

• L’utilizzo del protocollo multicast di basso livello (IGMP) permetterebbe di semplificare alcune delle fasi degli algoritmi (messaggi di “prossimo” attraverso un multicast)– semantica: ricezione di un acknowledgement da tutti i

componenti del gruppo. Conferma positiva e sollecito selettivo (utilizzando la parte di infrastruttura già realizzata)

Progetto di una architettura per Progetto di una architettura per l’esecuzione distribuita e coordinata l’esecuzione distribuita e coordinata

di azionidi azioni

Progetto per l’esame di

Reti di Calcolatori L-SProf. Antonio Corradi

Finistauri Matteo