Comunicazione - LIAComunicazione 2 Quando parliamo di comunicazione punto-punto, parliamo di...

Comunicazione

2

Quando parliamo di comunicazione punto-punto, parliamo di comunicazione a diversi livelli: ad

esempio l'ambito internet con TCP/IP e OSI.

Sicuramente si ha comunicazione quando si parla di scambio di messaggi, con primitive di lavoro

sincrone/asincrone, bloccanti/non bloccanti, asimmetriche/simmetriche, dirette/indirette.

Sicuramente lo scambio di messaggi è una comunicazione più di sistema, mentre il c/s si propone

di più a livello applicativo.

In generale, quando focalizziamo il protocollo bisogna tener ben presente che ci sono delle

semantiche ben diverse (May-be, At-least-once, At-most-once, Exactly-once -quest'ultima molto

molto di alto livello-).

NOTA: TCP ha una semantica at-most-once con caratteristiche molto precise.

3

Tutto questo discorso tende a dimenticare il fatto che nei sistemi, se c'è replicazione, è molto

importante avere degli strumenti di comunicazione di gruppo, ossia la possibilità di comunicare con

più destinatari.

Pertanto potremmo lavorare:

• broadcast: se tutti i partecipanti sono interessati all'informazione

• multicast: se abbiamo determinato un gruppo di riceventi che rappresenta un sottoinsieme

dei possibili destinatari.

4

Tutto ciò è incluso nei protocolli di internet, ad esempio,

nella versione IP4 si hanno degli indirizzi di broadcast.

In questo protocollo il broadcast può essere:

-) limitato perché relativo ad una rete locale (non posso

assolutamente spostarmi su di un'altra rete). (indirizzo

costituito da tutti uni).

-) diretto, ossia un broadcast che passa da una rete e viene

inviato su tutti i nodi di un' altra rete. (indirizzo costituito da

indirizzo rete e tutti uni).

Allo stesso tempo, internet ha previsto la possibilità di avere del multicast. In particolare in IP4, ci

sono degli indirizzi di classe D, con i quali posso raggiungere tutti i destinatari che sono registrati

per quel particolare indirizzo di classe D. In particolare si può inviare il messaggio a tutti gli iscritti

della stessa rete locale, ma non si può minimamente pensare di inviare il messaggio a tutti gli iscritti

dell'intero web.

5

A differenza di un punto-punto, in cui si può ragionare sulla qualità parlando di affidabilità nella

ricezione della risposta (ad esempio con qualche ack), lavorare in un sistema di gruppo e parlare di

garanzia della ricezione, e quindi di qualità, è un po' più complicato.

In un multicast, o peggio ancora in un broadcast, riuscire a capire se la comunicazione è andata a

56 Stefano Di Monte

buon fine è complicato!

Vi sono pertanto dei protocolli di gestione.

In particolare sin dai primi anni di esistenza di internet (primi anni '90), ragionando per il multicast

esiste IGMP: un protocollo che definisce come si lavora in ambito locale per indirizzi di classe D

multicast. Purtroppo, IGMP non può dire nulla di ciò che succede nel caso interrete.

In generale il multicast è stato gestito spesso con un idea molto approssimativa di qualità, difatti

finché sono a livello locale la propagazione dell'informazione avviene in maniera molto semplice a

tutti i possibili sottoscrittori locali, il problema nasce quando voglio comunicare ad una rete diversa

da quella locale.

Una soluzione potrebbe essere: avere dei router istruiti per consentire il passaggio dell'informazione.

Si ricordi però, che la rete non ha una struttura lineare e semplice, bensì ha una serie di maglie.

Quindi ciò prevede anche una serie di router ed un possibile caso di arrivo multiplo (in un router)

dello stresso messaggio...ciò si chiama: multicast realizzato attraverso flooding tra reti, ossia ogni

rete propaga a suon di router il messaggio. Il flooding è molto costoso ed ha un' idea molto forte di

ripetizione: numero di messaggi ricevuti da una singola rete (router) potrebbe essere anche elevato.

Quindi, in questi casi, o gli lasciamo passare tutti i messaggi oppure facciamo in modo che un router

abbia memoria dei messaggi che riceve così da non accettarne più di uguali: ciò richiede stato e lo

stato costa!

Questa è la ragione per cui i protocolli inter-rete non sono mai stati sviluppati in modo univoco.

Per limitare i costi, quindi per ovviare al problema della presenza di stato, si decide di lavorare

senza qualità, ad esempio stabilire che sia presente un TTL (Time To Live): numero di hop (passi)

entro il quale un router scarta il messaggio

6

IGMP è un protocollo semplice perché basato su ipotesi di architettura molto semplice: nell'ambito

di una rete se c'è interesse per un indirizzo di classe D ciò prevede la presenza di un router di

gestione.

Il router è pertanto qualcosa che ha funzionalità di controllo e di gestione della rete, e che deve

garantire di avere un' idea precisa, deve quindi sapere quali sono i nodi interessati alla

comunicazione multicast, quindi iscritti precedentemente ad un indirizzo di classe D. In particolare

lo fa con un messaggio che invia periodicamente e che si chiama IGMPQUERY. D' altro canto i

nodi si sono iscritti all'indirizzo di classe D attraverso un messaggio dal nome IGMPREPORT,

attraverso il quale un nodo avvisa il router di un suo cambiamento di stato (si dice che il nodo ha

fatto join/leave).

Ciò che succede, è che di tanto in tanto il router deve/può controllare che i nodi iscritti siano ancora

presenti ed anche ancora iscritti al multicast (controllo periodico).

NOTA: Se la rete è abbastanza grande, il router è

dovuto ad effettuare un numero anche elevato di

controlli, quindi di invio di messaggi IGMPQUERY: il

che prospetta una possibile condizione di congestione

Reti di Calcolatori LM 57

del router stesso.

7

In prima battuta, tale protocollo lasciava molto spazio al router che spesso e volentieri si

congestionava (si cercava di risolvere tale situazione sgradevole con l'utilizzo di più router che

quindi si dividevano il lavoro). Difatti tutta la gestione era a carico del router: i nodi non

effettuavano il leave, quindi toccava unicamente al router di gestione controllare e sapere di volta in

volta quali fossero i router ancora iscritti ad un determinato indirizzo D multicast.

Nella seconda versione (presente tutt'ora su qualunque macchina) invece, i nodi “sono” obbligati a

fare delle leave, con le quali avvertono il router della loro de-sottoiscrizione al servizio multicast: si

rovescia la responsabilità tra il router e il sottoiscrittore: il router di gestione, pertanto, ha meno

lavoro da fare e si congestiona meno facilmente.

Questa finora citata è la parte semplice del multicast; la parte complicata, più difficile, è la parte di

propagazione globale (inizialmente mai risolta il che comporta, nella maggior parte dei casi, alla

non creazione di uno standard e ad una situazione di incompatibilità futura tra le soluzioni trovate e

non capaci di arrivare alla composizione di un 'unica soluzione -tutt'ora, dopo trent'anni, non si ha

una soluzione unica!-).

8 - 9

Tale problema è stato affrontato in tempi abbastanza recenti.

Il principio alla base dei protocolli creati è molto semplice.

Supponendo di voler/dover raggiungere una serie di riceventi (in realtà si parla di reti di riceventi),

in generale una soluzione per fare multicast è quella di trasmettere l'informazione punto-punto, con

una serie di intermediari presenti: in questo caso vi sono diversi path (che raggiungono i diversi

destinatari) con nessuna condivisione. Questo modo di lavorare è assolutamente inefficiente perché

prevede l'invio di un messaggio differente per ogni singolo ricevente.

Si potrebbe quindi pensare di non partire direttamente con questa mancanza assoluta di

condivisione, ma magari, si potrebbe partire con il messaggio che inizialmente prosegue per un

unico cammino e poi si dirama, attraverso un bus, su tutti i riceventi: in questo caso abbiamo una

fortissima condivisione ed un unico messaggio che parte dal mittente, il che consente una versione

multicast molto efficiente.

Maggiore è la condivisione di cammini, minore è il numero di messaggi che il router deve inviare!

La soluzione quindi, è quella di trovare una struttura dinamica di propagazione che consente di

avere dal sender ai riceventi (e si parla sempre di reti di destinatari -almeno uno-), la situazione di

maggior condivisione dei cammini possibili: al limite migliore vi è un unico messaggio.

Si potrebbe passare anche da reti che non sono interessati al messaggio ma che sono di passaggio

per il cammino a maggior condivisione creato dinamicamente: l'albero è anche in continua

58 Stefano Di Monte

organizzazione, vista la dinamicità dei riceventi che si possono aggiungere e togliere.

10

L'obbiettivo quindi è quello di creare una struttura ad albero (uno spanning tree) con la maggior

condivisione possibile in modo da impegnare meno risorse possibili nella trasmissione dei dati da

inviare ai riceventi.

I protocolli per l'identificazione di tale albero sul grafo di connessione sono un po' diversi tra loro e

ce ne sono parecchi, in quanto non vi è compatibilità. In realtà, in linea di principio, ci sono alcune

cose rispettate più o meno da tutti i protocolli, le quali si identificano in due fasi:

Prima fase

Si parte dalla radice che eroga i messaggi, i quali tendono a raggiungere tutte le foglie: broadcast

effettuato in flooding (quindi molo pesante e costoso), limitato da alcuni protocolli con l'utilizzo di

stub per evitare la ricezione multipla di messaggi. Quello che si vuole fare è creare una struttura,

spanning tree, che permetterà il raggiungimento di tutte le foglie del suddetto albero, con eventuale

passaggio attraverso reti intermedie. Queste reti non sono quindi interessate alla comunicazione, ma

sono invece a conoscenza che i loro figli (in termini di albero), se fossero delle foglie, vogliono il

messaggio inviato in multicast. Pertanto potrebbe succedere che, come si nota in figura, una foglia

potrebbe ricevere da più genitori/reti attraverso percorsi differenti e magari in tempi altrettanto

differenti.

11

Seconda fase.

É presente in quasi tutti i protocolli, e va dalle foglie alla radice.

In questa fase, le foglie dichiarano il proprio interesse alla radice: si potrebbe quindi percorrere il

percorso della prima fase a ritroso...In realtà, le foglie, dopo aver ricevuto un messaggio, effettuano

reverse path, tendono quindi a rimandare il messaggio al mittente, attraverso percorsi diversi (anche

in questo caso si fa broadcast/multicast). Tutto ciò perché, supponendo che alcuni percorsi siano

stati esplorati ed altri no, ripercorrere sempre lo stesso percorso potrebbe far perdere l'occasione di

ottimizzare la struttura dello spanning tree.

12

Il multicast è sicuramente una operazione significativa ma comunque meno significativa della

normale operatività: le reti, durante la fase di identificazione dell'albero, devono continuare a

funzionare per il punto-punto!

Pertanto si hanno due algoritmi di routing:

Distance Vector

Si ha solo un'idea della distanza dei vicini, quindi del vicinato, e della distanza dalle altre reti:

conosco tutte le reti e la distanza da loro, ma per raggiungerle conosco solo il mio vicino.

Tipicamente le reti in locale lavorano con questo protocollo perché a basso costo, mentre nelle

interconnessioni più di alto livello lavoro con link state.


Link state

Protocollo più evoluto, di seconda generazione, in cui tutti hanno un idea del grafo completo di

interconnessione: tutti hanno un idea del come raggiungere gli altri.

Concludendo, il multicast deve dare una minima interferenza alla normale operatività, quindi alla

comunicazione punto-punto.

13

Reverse Path Broadcast

Come abbiamo detto, la seconda fase è quella che va dalle foglie alla radice.

Si chiama Reverse Path, tra il multicast ed il broadcast cambia poco, e tipicamente e quella fase che

consente, a chi arriva dopo in rete, quindi a chi dopo intende partecipare alla comunicazione di

gruppo, di inserirsi correttamente.

Tutti i protocolli, anche se in modo diverso, prevedono questo broadcast a ritroso, il quale permette,

come già accennato, di fare delle ottimizzazioni: ad esempio, come è mostrato in figura, non usiamo

due path disgiunti per raggiungere RB e RE bensì ne utilizziamo uno solo (passando solo per RC)

ottimizzando lo spanning tree.

Fare ciò non è affatto banale.

14

Quello che succede in caso di uscita dalla rete di un nodo è fare pruning dell'albero: aumentiamo la

condivisione ed ottimizziamo l'albero: da a) a b).

Un altro caso è quello in sui, vi è un nodo che vuole entrare nella rete, allora in questo caso si fa un

innesto (grafting) di nuovi cammini perché i nodi riceventi interessati alla comunicazione sono

maggiori di quanto non lo erano originariamente: da b) ad a).

15

Una cosa importante è che tutti questi protocolli sono legati ad un'idea di stato, dello stato

dell'albero, il quale è mantenuto da tutti i singoli nodi partecipanti (compresi i nodi intermedi).

Questo stato, in particolare, non è mai uno stato persistente bensì è uno stato soft: viene mantenuto

per un certo intervallo oltre il quale viene perso. Ciò garantisce che le strutture di base non siano

permanenti, il che prevede un costo dipendente dall'uso e quindi fortemente limitato.

16

Ovviamente vi sono molti protocolli diversi e che lavorano in modo molto diverso, e tristemente non

sono compatibili. I primi due sono:

Distance Vector Multicast Routing Protocol -DVMRP-

é un distance vector multicast, ed è un protocollo capace di ottenere un albero compatibilmente con

un distance vector. Si tende a limitare il costo, facendo dove è possibile, in alcuni momenti, del

tunneling: un cammino viene utilizzato in modo isolato senza entrare troppo nel dettaglio della rete

60 Stefano Di Monte

partecipante (si parla di multicast backbone)

Multicast Open Shortest Path First Protocol -MOSPF-

è l'implementazione più diffusa del link state che estende quest'ultimo al multicast.

NOTA:

Il problema di tali protocolli è che scelto uno, sicuramente non si è compatibili con l'altro.

17

Si è cercato di risolvere tale problema creando dei nuovi standard.

Protocol Indipendetn Multicast

Un primo tentativo fu il PIM, il quale venne creato per essere dipendente dal protocollo punto-

punto; è un protocollo abbastanza complesso perché ragiona su:

• aree dense, in cui molte reti partecipano alla sottoscrizione; in questo caso usa il flooding ed

ha un prune semplificato rispetto al DVMRP

• aree sparse, ossia aree in cui le reti interessate sono molto distanti; in questo caso lavora

eliminando il maggior numero di router intermedi così da semplificare la struttura

dell'albero.

Il PIM è stato molto acclamato inizialmente ma che in realtà non è stato mai adoperato e non si è mai

diffuso.

Core Based Trees

Altro tentativo fu il CBT, che è un protocollo in cui vi è un bone già fatto, quindi che presenta un

albero principale già abbastanza predeterminato. Purtroppo questo protocollo può convivere con gli

altri (ed è quello che succede) con i quali però non è compatibile...ad esempio, si utilizza CBT per

arrivare all'interno di una certa area, all'interno della quale però si lavora con Distance Vector...

18

E' molto importante quindi, a livello scientifico, che gli standard siano determinati il prima possibile

eliminando completamente il rischio di arrivare ad una situazione in cui le applicazioni sono

fortemente dipendenti da certi protocolli esistenti, che però sono tra loro completamente

incompatibili.

19

Ragionando, con una serie di possibili riceventi (ad esempio 4), che devono ricevere come gruppo il

messaggio, riscontriamo un problema più forte nel multicast che nella comunicazione punto-punto.

Difatti, in quest’ultima chi riceve risponde direttamente, mentre in una comunicazione di gruppo,

sicuramente il messaggio viene inviato a tutti i riceventi ma non è detto che la risposta di tutti, arrivi

realmente. Pertanto, come mostrato nello schema in figura, potrebbe succedere che riceviamo 3 ack

come segno di “messaggio inviato con successo”, ma dato che il gruppo è composto da 4 riceventi è

evidente che è successo qualcosa che non va.


Quello che si potrebbe fare, ad esempio, è rimandare (come succede in figura) la richiesta solo al

ricevente che non ha restituito una risposta (sollecito selettivo). Se invece il messaggio originario

inviato a tutti sia un multicast, saremmo costretti ad inviare nuovamente un multicast raggiungendo

tutti i riceventi (sollecito globale) i quali, ad esempio, potrebbero aver capito l’inconveniente e chi

ha già inviato la risposta al primo multicast, potrebbe non rispondere nuovamente.

Potrebbe anche essere che una risorsa sia stata interessata da un guasto, quindi sicuramente non

invierà una conferma positiva (come succede normalmente) bensì una conferma negativa (un

esempio potrebbe essere nel caso di invio di una sequenza di risposte positivo, positivo, negativo

(quindi nessuna risposta), positivo...).

In particolare, i gruppi sono stati studiati perché le operazioni, spesso, non sono singoli bensì sono

organizzate in una sequenza, il più possibile strutturata, di azioni, e su tale sequenza si ragiona.

20

Tutti i protocolli di multicast, anche quelli multi-rete visti precedentemente, prevedono molto spesso

di avere un sender che manda delle richieste ad una serie di reicever, ossia dei server , i quali si

devono coordinare per creare un concetto di gruppo.

Questo modello fa venire in mente il concetto di gruppo, ad esempio con copie replicate che

potrebbero essere di tutti i tipi visti precedentemente (copie attive, passive...).

L’idea di cominciare a lavorare sui gruppi nasce dalla necessità di dover rispondere a delle

operazioni dall’esterno, le quali rappresentavano delle esecuzioni che dovevano essere fatte in modo

più o meno coordinato dalle copie che risiedevano sul nodo di interesse, in prima battuta copie di

database.

L’idea di gruppo comincia ad avere senso, comincia a diventare necessario, quando un sender non

esegue un operazione sola, con la quale non vale la pena avere un gruppo, quindi quando le

operazioni solo molteplici, come ad esempio uno streaming di informazioni, il quale prevede una

serie di operazioni ripetute dal sender ai mittenti, quindi ai componenti del gruppo.

Il concetto di gruppo si articola maggiormente dal punto di vista semantico quando pensiamo di

62 Stefano Di Monte

avere più di un sender, più mittenti che fanno operazioni in contemporanea sul gruppo stesso.

Ovviamente il coordinamento del gruppo ha maggior senso se le operazioni da eseguire non sono

operazioni di lettura (il che comporta poco o nessun coordinamento) bensì di cambiamento di stato

delle copie.

21

Ci son due aspetti semantici fondamentali del multicast:

Affidabilità (Reliability): la correttezza delle operazioni di consegna delle richieste, v'è garanzia che

arrivano dal mittente ai destinatari (qualità).

Ordinamento/Atomicità: come e se, le richieste si manifestano sul gruppo dopo che sono state

inviate ai diversi riceventi. Si chiama ordinamento perché, effettivamente, riguarda l’ordine con cui

le cose si manifestano. Ad esempio se avessimo due sender, alle diverse copie le richieste

arriverebbero con ordine diverso...

NOTA: questi due aspetti possono e devono essere considerati in isolamento.

Il primo aspetto (affidabilità) quindi, è legato ad una correttezza del sistema, garantisce cioè che il

messaggio non si perda; d’altronde non sempre vogliamo essere sicuri di ciò: alcuni sistemi

prescrivono di avere un supporto per la comunicazione di gruppo che non sia così affidabile, in

quanto tollerano che potrebbero esserci delle perdite, prevedendo che i messaggi vengano inviati una

ed una sola vota. Pertanto, le omissioni di qualche messaggio sono tollerate perché è presente un

buon protocollo di coordinamento di gruppo.

D’altra parte un sistema reliable, è un sistema che garantisce la consegna della richiesta/risposta ma

che, proprio per questo motivo, costa di più.

L’altro aspetto è quello dell’ordinamento, ma ne parleremo in seguito.

22

Parlando di reliability multicast, siamo quindi interessati ai possibili fault che possono manifestarsi,

facendo in modo di essere tollerabili a questi e di ricorrere al recovery.

Un primo possibile fault è ad esempio quello dovuto per omissione di un messaggio: un messaggio

si perde e non arriva al destinatario corretto/corrente. Quello che si fa è usare replicazione in tempo:

rimandiamo il messaggio allungando il protocollo in termini di tempo di trasmissione.

Altro possibile fault, potrebbe essere il manifestarsi di un guasto su di un ricevente, abbiamo quindi

un crash del ricevente interessato: ostacolo forte per il multicast di quel gruppo, perché finché

quella copia è giù, gli altri dovranno tenere conto della sua assenza.

Infine, potrebbe essere che è il mittente che si guasta, abbiamo quindi un crash del mittente, che

quindi non riesce ad inviare tutti i messaggi.

Tutti questi tipi di fault sono tutti stati trattati da protocolli ad-hoc molto spesso non standardizzati.

23

Sicuramente, se vogliamo avere dei buoni sistemi reliable, sarebbe opportuno che questi


implementino dei protocolli di gestione. Quest’ultimi hanno dei costi, limitati se le cose a regime

vanno bene, ma che cominciano ad incidere non appena i guasti si presentano (dovuti a recovery,

sostituzione copie, reinserimento copie...).

In generale tutto ciò richiede qualcuno che controlla la gestione: in un sistema in cui c’è un gruppo,

se vogliamo reliability, innanzitutto dobbiamo accettare i costi di gestione, ed in secondo luogo

bisogna introdurre una responsabilità di gestione, qualcuno che controlla l’operatività e che porti

avanti in maniera corretta il tutto.

Se questo qualcuno è “fisso”, se ci troviamo quindi in uno schema a farm molto centralizzato, vi è,

quindi, una copia determinata per fungere da controllore degli altri, potrebbe succedere che questa si

guasti. Tutti gli schemi statici di gestione, sono pertanto, schemi molto rigidi; a tal proposito, in

alcuni sistemi per ovviare a questo problema si usano supporti diversi: macchine più affidabili per la

funzione di gestione e macchine di minore qualità per la normale operatività (progetto ad-hoc,

quindi con un costo molto spesso intollerabile).

Pertanto, se si guasta il controllore, vi sono alcuni sistemi più safe, che prevedono una sostituzione

(anche momentanea) e quindi un passaggio di responsabilità di gestione, altri invece prevedono un

controllo reciproco .

Chi custodisce il custode? –Giovenale-.

Il ruolo del controllore è fondamentale, perché se ben fatto introduce nel sistema dei costi

abbastanza tollerabili, altrimenti se fatto male, potrebbe portare il sistema ad ingolfarsi: ad esempio

un controllore che controlla molto frequentemente potrebbe occupare la banda in maniera troppo

invadente: sempre applicare il principio di minima intrusione!

Bisogna ricordare comunque, che la parte di gestione richiede di dimensionamenti dipendenti dal

sistema che stiamo controllando. Pertanto, quando stiamo sul sistema bisogna capire quali possono

essere questi dimensionamenti: ad esempio, un time out dipendente dal sistema: se le copie son

vicine, allora il time out potrebbe essere piccolo, grande per delle copie lontane.

Due strategie, molto banali per aumentare l’efficienza e che sono soluzioni di multicast (atomico

ed) affidabile sono:

hold-black: dice che il supporto di comunicazione non deve dare subito all’applicazione i messaggi

che stanno arrivando, ma in alcuni casi deve ritardarli se vuole ottenere un certo ordinamento.

Supponendo che arrivino i messaggi 1,2,3,5,6,7, potrebbe essere che vale la pena aspettare il 4°

messaggio e trattenere in memoria, o, come si dice, tenere in hold-black tutti gli altri per poi darli

tutti in ordine. Quello che fa questa strategia è una gestione per il livello applicativo, e viene usata

nel protocollo TCP: si restituisce solo l’intero flusso, aspettando nel caso, i segmenti mancanti (in

realtà non è sempre detto: politica at-most-once!).

negative ack: quando facciamo delle richieste le copie del gruppo devono dare delle conferme; se

statisticamente le omissioni risultano rare, potremmo risparmiare banda lavorando in negativo:

anziché mandare delle conferme usiamo un tacito assenso, in cui i riceventi non dicono niente. Un

esempio è il caso in cui un certo mittente comincia ad inviare il messaggio 1, il messaggio 2,

messaggio 3 ecc ecc, supponiamo sia uno streaming, ed il ricevente riceve una risposta 1, 2 e 3 e

finché riceve in ordine tutto è ok. Quando non riceve un messaggio nell’ordine giusto, ad esempio

1,3,2, allora in questo caso c’è sicuramente qualcosa che non va ed invia un NACK. Un protocollo

di questo genere è molto usato nel TCP. Quindi è ovvio che il negative ack deve prevedere

correttamente la sequenza: mittente e destinatari devono avere la storia dei messaggi.

Se avessimo più mittenti, quindi più stream, è chiaro che la numerazione dev’essere fatta

64 Stefano Di Monte

nell’ambito del mittente specifico.

NOTA: vi possono essere possibili ack positivi (con # messaggio ricevuto) in piggybacking per

indicare eventuali perdite. Alcuni sistemi, comunque, potrebbero tollerare la perdita di uno o più

(comunque pochi) messaggi.

Queste due strategie sono spesso usate e bastano queste per ottenere la corretta affidabilità.

24

Sicuramente quando abbiamo un gruppo, si deve ragionare in termini di ordinamento del gruppo.

Importante ricordare che: quando si parla di gruppo tipicamente ci si riferisce al distribuito, in cui le

copie del gruppo sono presenti su locazioni geografiche separate ed hanno una bassa probabilità di

errore congiunto (se una copia fallisce è molto probabile che le altre sopravvivano al guasto e

continuino il loro operato).

Il primo ordinamento che potrebbe saltare alla mente, quando si lavora nel distribuito, è

l’ordinamento FIFO : è un First In First Out, pensato per un unico mittente e si ragiona nei termini

di quest’unico mittente che manda una sequenza di messaggi (o di operazioni) ad un gruppo. Quindi

se il mittente manda i massaggi in un certo ordine,ad esempio m1 e poi m2, tutti i riceventi vedono i

messaggi nello steso medesimo ordine (m1 e poi m2); se per caso una copia dovesse per qualche

ragione ricevere i messaggi in ordine diverso da quello di invio ci sarà un supportino di hold-black,

che garantisce che l’ordine sia preservato.

In particolare, si possono avere anche più di un mittente! Quindi è possibile che il mittente S1

manda i messaggi m1 ed m2, mentre il mittente S2 manda i messaggi m3 ed m4: ciò vuol dire che

questi messaggi arrivano a tutti rispettando l’ordine dei destinatari: prima m1 poi m2 e prima m3 e

poi m4, il che vuol dire che i messaggi potrebbero anche mescolarsi (m1m3m2m4, m1m2m3m4,

m3m4m1m2, m3m1m2m4 ...), l’importante è che si rispetti il FIFO per ogni mittente.

In generale, supportare il FIFO è abbastanza facile: per implementare un FIFO è sufficiente avere

una numerazione dei messaggi per mittente.

Ovviamente ogni copia deve avere uno stato, e se le copie arrivano fuori ordine allora hold-black.

25

Il FIFO molto spesso è incorporato nei supporti di multicast.

Un altro ordinamento provato con internet è quello sulle news. Essendo un servizio caratterizzato

dalla presenza di server non consistenti, in alcuni casi succede che, quando qualcuno fa una richiesta

di news, ad un certo punto riceverà una risposta su quel certo topic, ma essendoci diversi osservatori

interessati a quel topic, alcuni di questi ricevevano prima la risposta e solo in un secondo momento

la richiesta originaria. Questo è dovuto al fatto che molto spesso le news sono etichettate con il

tempo macchina di chi le ha inviate, e il tempo macchina di chi risponde potrebbe essere sfasato

rispetto agli altri tempi macchina, ed inoltre il sistema di news è scarsamente interconnesso.

Per ciò, s’intende per quale motivo l’ordinamento FIFO venne pensato per un unico mittente.

Nel caso di due o più mittenti, quello che si può e/o deve fare è considerare la relazione causa-

effetto tra i vari mittenti.

26

Da ciò, l’ordinamento CAUSALE: tutte le copie che hanno una relazione di causa ed effetto, nel

sistema compariranno prima le cause e poi gli effetti, mai il contrario.

Se nel caso, considerando i messaggi m1, m2, m3 ed m4, se m3 fosse l’ effetto di m1 che quindi


risulta esserne la causa, allora tutti devono vedere nello scheduling, prima m1 e poi m3.

Questo tipo di ordinamento è più complicato di quello FIFO da gestire.

Ovviamente, esistono dei supporti che garantiscono l’ordinamento causale (sicuramente non per il

concentrato che va quasi sempre con l’ordinamento FIFO).

27

<<Come si potrebbe garantire un rapporto di causa/effetto?>>

Potrebbe essere che la dipendenza dei messaggi sia scritta nel messaggio stesso, ad esempio in m3

si potrebbe scrivere che dipende da m1. Ma non solo questo, si dovrebbe scrivere in m3 anche chi

deve inviare m1 cosicché si possa stimolarlo nell’invio del messaggio suddetto, nel caso in cui non

lo faccia per una qualsiasi ragione.

Ciò comporta, nel caso in cui i messaggi siano dipendenti da una serie di cause, ad avere dei

messaggi molto più cresciuti...inoltre richiede al ricevente di tracciare la storia del messaggio stesso,

il che potrebbe comportare, nel complesso, una complessità molto maggiore.

Sicuramente ci sono dei rapporti di causa/effetto che vanno tracciati, altri invece meno importanti,

questo perché ci si è accorti che non vale la pena utilizzarlo su tutti gli eventi del sistema...

Quello che in realtà succede in molti casi nel distribuito, utilizzando un ordinamento causale, è che:

supponendo di avere due entità (A e B) che seguono due operazioni (Na e Nb) sul gruppo, e

supponiamo che queste due operazioni non siano correlate tra loro; potrebbe succedere che le

operazioni arrivino in ordine diverso a due entità del gruppo (C e D) e, di conseguenza, questi due

potrebbero eseguirle nello stesso ordine diverso di arrivo...la cosa importante in un gruppo è che,

nonostante la non correlazione delle operazioni tutti eseguano le operazione allo stesso ordine, non

importa se prima Na e poi Nb o viceversa.

28

Soluzione: ordinamento ATOMICO: garantisce che le operazioni fatte dal gruppo siano decise dal

gruppo come ordine e siano fatte tutte nell’ordine deciso dal gruppo, secondo le sue esigenze,

politiche o necessità.

Questo tipo di ordinamento è molto importante in alcune operazioni, ad esempio in quelle

operazioni spesso invertibili, che potrebbero dare un risultato diverso perché eseguite in un ordine

diverso da diverse copie del gruppo.

L’ordinamento atomico, a differenza dell’ ordinamento causale che si applica solo alle operazioni in

relazione causa/effetto, e dell’ordinamento FIFO che si applica solo alle operazioni provenienti da

un unico utente, quindi in entrambi i casi non a tutte, quello atomico si applica a tutte le operazioni

che il gruppo esegue.

<<Come potrebbe essere fatto un ordinamento atomico?>>

Ad esempio, un modo potrebbe essere quello di avere un front

end che dia ad ogni operazione un numero (come succede ad

esempio in fila al banco dei salumi, in posta ...) rispettato da

tutti. Si tratta di uno schema fortemente centrale con tutte le

problematiche che esso si porta dietro (di affidabilità, e se si guasta il front end?) ma che comporta

altresì un costo molto basso. Inoltre, tale schema, dal punto di vista dei mittenti non preserva il

FIFO né tanto meno relazioni di causa/effetto.

Si potrebbe rendere tale schema più robusto, ad esempio replicando il front end, molto

semplicemente con copie passive (soluzione più semplice), e se facessimo delle ipotesi di guasto

singolo si potrebbe usare una sola copia.

66 Stefano Di Monte

Altri tipi di ordinamenti atomici potrebbero rispettare il FIFO o il causale, o anche entrambi.

29 – 30 - 31

L‘importante è ricordare che:

l’ordinamento atomico è un ordinamento globale, che quindi riguarda tutte le operazioni del gruppo,

mentre gli ordinamenti FIFO e causale sono solo ordinamenti parziali che quindi riguardano un

sottoinsieme delle operazioni del gruppo.

Naturalmente, potrebbe essere che un sistema non abbia nessuna necessità di ordinamento: le

operazioni arrivano sulle copie e vengono eseguite nell’ordine in cui arrivano. Non avere alcun

ordinamento prevede il costo più basso possibile ed in alcuni casi potrebbe essere proprio ciò che

vogliamo avere, se ad esempio le specifiche non prevedono alcun ordinamento (si va sempre verso

la SEMPLICITA’ quando è possibile!).

<<Quanti tipi di ordinamenti atomici ci sono?>>

Parecchi! Alcuni di questi rispettano il FIFO per tutti i mittenti, altri solo per alcuni, altri ancora

rispettano il causale, ed altri non rispettano nessuno dei due: per tale motivo i costi dell’atomico

sono molto diversi per casi diversi.

32

Come già accennato precedentemente, avere un coordinatore centrale comporta un problema nel

caso in cui questo si guasti, risolvibile con la replicazione, unfairness della gestione: alcuni vicini al

coordinatore o favoriti dallo stesso, possono piazzarsi continuamente prima di altri (che hanno fatto

la richiesta prima).

Quello che si fa è utilizzare un coordinatore mobile, a token circolante, in cui è l’intero sistema che

controlla se stesso: la responsabilità non è più di uno solo.

33

Quando parliamo di ordinamenti si parla sempre di SINCRONIZZAZIONE.

Tale concetto molto spesso è limitato alla mutua esclusione, ma in realtà fare ordinamenti vuol dire

fare in modo che certi eventi accadano in un certo ordine quindi vuol dire sincronizzare tali eventi

affinché rispettino l’ordine stabilito.

Nel distribuito, una prima cosa che è stata fatta a livello storico, è cercare di riportare il concetto di

sincronizzazione com’era presente nel concentrato, ossia con un unico clock.

Concetto molto efficace nel concentrato ma che risultò poco efficiente nel distribuito, proprio per la

mancanza di un clock globale da poter riportare a tutti i partecipanti della comunicazione, i quali

hanno un loro clock personale che non è sincronizzato con quello degli altri.

34

Il primo tentativo fu quello di riuscire ad aver una funzione di clock fisico nei sistemi distribuiti che

sia sincrona quanto basta.

Di fatto si è definito Universal Coordinated Time (UTC), che si basa sull’idea di avere un orologio

(un valore) che viene distribuito ad una serie di partecipanti; in altri casi potrebbe essere che viene

richiesto il clock di una serie di partecipanti, viene portato allo stesso valore e distribuito

nuovamente a tutti (Berkeley time).

Questo è un protocollo realizzato solo per un numero di partecipanti molto limitato.

35


Network Time Protocol (NTP): è un protocollo di diffusione di tempo, che distribuisce

effettivamente i clock fisici, e che si basa sul fatto che esista un qualcuno che emette un clock, il

quale viene ricevuto ed installato sui diversi nodi. Bisogna però tenere presente che la propagazione

dei clock comporta la presenza di ritardi...che si sono cercati di superare attraverso politiche di

filtraggio statistiche legate al comportamento storico dei server.

Il tutto avveniva per gerarchie di server: vi era un livello radice che trasmetteva al livello sottostante

e così via fino ai clienti finali, comportando la perdita di accuratezza del clock stesso, man mano

che si scendeva di livello.

Per avere una maggiore precisione naturalmente bisognerebbe avere una frequenza di trasmissione

sempre più elevata.

Per tale motivo tale protocollo è stato sempre utilizzato in alberi molto limitati.

36

In sostanza quindi, lavorare con i clock fisici comportava avere a che fare con molti problemi...di

conseguenza ci si accorse che l’approccio era completamente sbagliato.

La sincronizzazione via clock non era ciò di cui si aveva bisogno: si focalizzò quindi l’attenzione sul

ridurre il campo della sincronizzazione, ossia a ridurlo solo unicamente sugli eventi di maggiore

importanza e non a tutto il sistema.

Questo deriva dal fatto che in un sistema distribuito si hanno degli eventi completamente scoordinati

in cui non importa la sincronizzazione e degli eventi correlati in cui la sincronizzazione è di

particolare importanza: il sistema in generale è libero ma in alcuni casi ci sono degli eventi che

verranno coordinati, tutto ciò comporta un costo intrinseco molto limitato e dei protocolli molto più

semplici.

37

A livello storico, il problema è stato risolto da tre filoni.

Una soluzione è stata trovata nella priorità degli eventi: alcuni lo sono di più altri meno. Questa

forma di ordinamento/sincronizzazione è molto adatta per sistemi a real time in cui i processi

devono rispettare delle deadline. È sostanzialmente un sistema unfair: qualcuno che ha manifestato

la propria esigenza molto prima viene scavalcato da qualcun altro che arriva dopo ma che ha

priorità maggiore.

I due metodi più importanti sono: sincronizzazione dei clock logici di Lamport e quello basato sulla

presenza di un token passante.

68 Stefano Di Monte

38

Ragionando per Lamport, all’interno di uno scenario (piuttosto generale) costituito da processi che

hanno una loro storia interna e che possono esibire un comportamento locale (generando eventi

localmente) e remoto (inviando messaggi ad un altro processo) si pone l’attenzione solo su alcuni

eventi significativi del sistema distribuito.

Ciò che si vuole garantire è che tali processi facciano una corretta sincronizzazione di tali eventi in

modo tale da avere un corretto coordinamento degli eventi che interessano l’intero sistema; e ciò

risulta fattibile solamente se il singolo processo che coordina i suo eventi, lo fa in maniera corretta e

consistente con la sincronizzazione effettuata dagli altri processi del gruppo.

39

La relazione fondamentale sulla quale si basa tutto il modo di Lamport è ->, ossia la relazione di

happened-before (precede) che cerca di ragionare sugli eventi che possono avvenire su un processo e

tra processi.

Ragionando su eventi locali, quindi dello stesso processo, ad esempio a e b, se a precede b,

quindi a viene eseguito prima di b, allora è possibile utilizzare la formula a->b.

Se parliamo di scambio di messaggi, ed a è l’evento di invio mentre b quello di ricezione di

un messaggio, allora vale sempre a->b: relazione chiara di causa(a) /effetto (b)

È possibile applicare anche la proprietà transitiva; quindi se a->b e b->c allora a->c.

Questa relazione consente di ordinare degli eventi, anche di processi diversi, se c’è stata

comunicazione.

Nell’ambito di un processo ci consente di ordinare tutti gli eventi, mentre nell’ambito di più processi

ci consente di ordinare solo alcuni eventi, non tutti: in questo caso si parla di eventi concorrenti, per

tale motivo si parla di relazione PARZIALE di ordinamento.

40

Come si nota in figura, quando scambiamo messaggi facciamo intervenire delle relazioni di

precedenza (derivanti anche dalla proprietà di transitività).

Come si nota però, per i processi a1,c1 o tra a1,c2 non è specificata alcuna relazione di precedenza,

si dice quindi che i due processi (a coppie: a1,c1 e a1,a2) sono concorrenti.

Gli eventi concorrenti, idealmente, potrebbero essere messi in esecuzione dalle componenti del

gruppo in maniera diversa.


41

In generale, quando lavoriamo heppened-before, assumiamo che a livello di processo locale ci sia

una generazione di eventi locali.

Invece si assume che a livello di scambio di messaggi, lo scambio dei messaggi sia asincrono.

pertanto lavorando in tal modo, vi può essere ritardo di trasmissione, e quest'ultimo può essere

grande a piacere, non può essere quindi previsto; si assume comunque che non c’è omissione di

messaggi.

Pertanto lavorando con la relazione heppened-before non esiste un unico orologio globale (quindi un

unico tempo globale) bensì un insieme di clock locali (quindi tempi locali).

42

Quello che si vuole costruire, basandoci su questa relazione happened-before (->), che applichiamo

solo agli eventi di trasmissione + agli aventi locali corrispondenti, è un sistema di tempo non fermo

(che non si basa quindi su orologi fisici) ma logico (pertanto che si basa su orologi logici).

Come già detto non abbiamo quindi bisogno di una trasmissione di clock, o in generale di una

precisione di clock, ma abbiam bisogno di stimare quali sono gli eventi che ci interessano e di

ordinare questi eventi. Ciò ci consente di risparmiare moltissimo sull'esigenza di coordinamento

rispetto all'orologio fisico.

Tale strategia prevede quindi degli orologi logici che ci consentono di lavorare in maniera più

efficiente.

In particolare Lamport, stabilisce che devono esistere dei clock logici di sistema, associati ad ogni

singolo processo, quest'ultimi sono dei generatori di tempo logici e sono in grado di far avere

all'intero sistema un unica idea di tempo logico che tiene conto di tutte le comunicazioni, e lo fa

con un costo molto basso.

In generale, dopo avere definito la relazione “precede” (happened-before) si vuole definire un

timestamp associato ad ogni evento, sopra il quale si possa lavorare in maniera semplice.

Le condizioni di clock (Logical Clock -LC-) di base sono:

se a->b allora ciò che dobbiamo realizzare è LC(a) < LC(b) (ma non viceversa!)

NOTA: la condizione di clock è solo univoca non biunivoca, ciò vuol dire che dati i rispettivi clock

logici non è possibile stabilire la relazione di precedenza di quegli eventi.

43

La condizione di clock si mappa sulla relazione di Lamport per due parti:

C1: (parte locale:) se a e b sono dello stesso processo Pi, e a->b allora LCi(a) < LCi(b)

<<Come si realizza?>>

I1: Ogni processo ha il proprio clock, ed ognuno di questi ha il proprio valore iniziale. Quello che

succede è che a livello locale, ogni qual volta si presenta un evento di interesse, questo clock viene

banalmente incrementato.

Usando questa strategia ogni evento che ne precede un altro ha il clock logico che precede lo stesso

clock logico dell' altro.

C2: se a è l'invio di un messaggio nel processo Pi e b la ricezione del medesimo messaggio in Pj,

70 Stefano Di Monte

allora LCi(a) < LCi(b).


I2 - I3: quando invio un messaggio, in quest'ultimo invio anche il mio clock logico come timestamp,

quindi a conseguenza di ciò, quando uno riceve il messaggio considera il mio timestamp, considera

anche il suo timestamp locale, considera quindi il maggiore dei due e ci aggiunge 1.

LCj = max (TSricevuto, LClocale) + 1

NOTA: i processi potrebbero cominciare da zero, ma anche da qualsiasi altro valore logico.

44

Quello che succede è che se ad esempio, come si nota in figura, vi è un processo (nel caso c1 e c2),

che ha il clock molto indietro, ma che invia dei messaggi a dei processi che hanno il clock molto più

alto del suo, allora il suo timestamp non verrà preso in considerazione: chi ha il clock più alto lo

tende ad imporre su quello più basso .

In altri termini, chi riceve adegua il clock, chi manda invece non adegua il clock: difatti finché il

processo c non riceve, il suo clock rimarrà basso, d'altro canto se sfruttassimo i clock dei processi

per considerare l'ordine delle operazioni, il processo c, in questo caso, sarebbe il favorito (a scapito

del tempo vero di creazione).

Concludendo quindi, in questa relazione di happened-before, i clock vengono adeguati quando

riceviamo delle informazioni non se mandiamo solamente. Quindi sarebbe opportuno che in un

gruppo tutti ricevano: il protocollo potrebbe quindi prevedere dei messaggi aggiunti.

NOTA: si ricordi quindi che la relazione di happened-before realizza un ordinamento parziale.

45

CI potrebbero essere nel sistema eventi concorrenti che quindi non sono in relazione happened-

before. In questa slide, ad esempio, a1 e c1 sono concorrenti, ed il fatto che abbiam dato dei

numerini a tutti gli eventi ci consente di ordinarli (in questo caso a1 < c1) senza che questi siano in

relazione happened-before.

Altro esempio, c2 e b2 hanno entrambi il numerino 10: non si può dire chi dei due venga prima

dell'altro, dato dal fatto che questo modo di ordinare i processi è parziale.


46

Pertanto, la sincronizzazione prevede di fare un ordinamento totale!

Con la relazione happened-before abbiam dato un senso di precedenza a dei processi significativi,

con la creazione dei timestamp abbiam esteso la relazione precedente con dell' ordinamento, ma

restano ancora degli eventi che non sono ordinati: produciamo una nuova relazione d'ordinamento

sempre basata su happened-before ma che è di ordinamento totale e si indica con

Il “precede totale” è una funzione di ordinamento totale ed è derivata dalla relazione di Lamport

estendendo la condizione di clock.

In generale, dato a evento di un processo Pi e b evento di un processo Pj, a b se:

LCi(a) < LCj(b),

OR

se LCi(a) < Lcj(b) e Pi < Pj

così facendo si stabilisce un ordine tra processi, ovviando al problema dello stesso timestamp dando

degli ordini di precedenza ai vari processi interessati.

Questa relazione prevede un costo abbastanza basso, e ci permette di effettuare effettivamente della

sincronizzazione.

47

Vi sono comunque dei problemi:

1. Il primo problema è quello di aggiornare il clock: la relazione di happend-before, lo fa solo

quando si ricevono delle informazioni, con la presenza di processi che ricevono poco quindi, molto

indietro in termini di clock rispetto a processi che ricevono spesso e che quindi avranno il clock

sempre aggiornato.

2. Un secondo problema conseguente al primo è che il processo che non riceve mai però, se

volessimo dare un ordine alle operazioni, il processo con il clock logico più basso verrebbe sempre

favorito su tutti nonostante magari sia stato creato dopo.

3. Un ulteriore problema è quello del canale nascosto: si supponga un processo che invii un certo

tempo, a questo punto, se al di fuori del sistema telefonassi ad un altra località e dicessi di aver

72 Stefano Di Monte

inviato un messaggio creerei una relazione di causa ed effetto su un canale esterno non tracciato nel

sistema il quale, quindi, non può tenere conto della telefona perché al di fuori della capacità

espressiva del sistema stesso. Se si usano dei canali non mappati, quindi hidden, il sistema non può

tenerne conto e quindi i clock non vengono assolutamente aggiornati correttamente.

4. Altro problema è che non riusciamo a capire se due processi che sono per questo protocollo in

relazione tra loro, sono, anche realmente, in una relazione di causa ed effetto.

48

La relazione ordina tutte le coppie di eventi anche quelli non ordinabili, quindi ad esempio

eventi concorrenti che vengono eseguiti in sequenza.

Nonostante ciò, una relazione di ordine totale richiede di avere dei limiti sulla dinamicità del

sistema (ad esempio creazione di nuovi eventi a tempo in corso).

49

Tutto quello appena detto garantisce di lavorare con clock logici e sappiamo e possiamo ordinarlo

per via del loro timestamp, quindi se un evento e1 avesse un LC=5 ed un evento e2 un LC=9, allora

sicuramente e1 < e2.....in realtà sono gli LC degli eventi che si precedono ma non è detto che

realmente i due eventi si precedano: la relazione happened-before non è biunivoca, non si può

passare dal clock logico alla relazione di precedenza.

Con i clock logici studiati precedentemente questa cosa non si può fare.

Pertanto è stato cerato un modo per rendere la cosa biunivoca, non si potranno usare quindi solo gli

LC, bensì si userà un vettore di clock logici: ordinamento vector clock.

Quando si lavora con il vector clock, ogni processo deve avere un vettore di clock, ciò vuol dire che

deve avere il suo clock, del quale ne è responsabile, e la SUA nozione di tutti i clock degli altri, che

viene passata quando scambio le informazioni.

Quindi il vettore di clock viene passato per ogni singola comunicazione: pertanto tutto ciò ha un

costo molto forte in termini di banda e di gestione (!) ma garantisce che la relazione di precedenza

sia BIUNIVOCA con quella di ordinamento dei clock logici.

50 – 51 - 52

Entrando più nel particolare:

-) non vi è più un unico clock bensì un vettore di clock

-) ogni processo è gestore del proprio clock e del proprio timestamp, ed ha conoscenza dei clock

degli altri processi

-) se vi sono n processi vi saranno anche n vettori.

Algoritmo:


Sicuramente il costo di tale protocollo è elevato ma ha un vantaggio intrinseco altrettanto alto:

risolve il problema n° 4, ossia due processi in precedenza con tale algoritmo sono anche realmente

in relazione di causa/effetto, mentre due eventi concorrenti nel mondo reale, con tale algoritmo non

sono messi in relazione.

NOTA: la maggior parte dei sistemi usa i clock logici, né i vector clock e tanto meno le matrici di

clock.

53

La sincronizzazione classica è quella effettuata su una risorsa.

Sicuramente, quando si parla di sincronizzazione, ciò di cui bisogna tener conto è:

safety: correttezza, un solo processo alla volta accede alla risorsa (mutua esclusione).

Liveness: sistemi abbastanza live in cui siamo sicuri che andiamo verso una certa soluzione (la

soluzione è presente sempre): ogni processo che ha fatto una richiesta riceve l'accesso alla risorsa in

un tempo finito.

Fairness: se uno ha fatto una richiesta, questa deve essere risolta con una politica fair (giusta).

Ovviamente ci sono molti modi per realizzarlo.

Una soluzione possibile (la prima che potrebbe venirci in mente), è una soluzione a processo

coordinatore.

Questa è una soluzione molto centralizzata in cui vi è un coordinatore che gestisce la risorsa, ed al

quale bisogna chiedere se sia possibile accedere alla risorsa (modello c/s)..

Questo è un modello di gestione della risorsa, non un modello in cui il coordinatore possiede la

risorsa!

Tale protocollo è un protocollo di request:

• i processi effettuano la richiesta (request)

• i processi ottengono una risposta

• ora il processo può utilizzare la risorsa per tutto il

74 Stefano Di Monte

tempo che vuole ma limitato

• quando il processo ha finito di usare la risorsa rilascia la risorsa (release)

Il coordinatore dovrebbe decidere con politiche fair l'utilizzo della risorsa: sicuramente potrebbe

adottare una politica FIFO, ma potrebbe essere che i nodi più vicini al coordinatore passino prima

degli altri proprio per l'alta vicinanza.

Chiaramente se il coordinatore fallisce la risorsa non è più disponibile.

55

Questo schema viene utilizzato ad esempio nei sistemi operativi, e per ogni richiesta abbiamo uno

scambio di tre messaggi: request, reply e release.

56

Consideriamo N processi che vogliono accedere alla risorsa e che non vogliono assolutamente un

nodo centralizzato per la gestione della risorsa stessa, quindi vogliono lavorare uno in base all'altro

scambiandosi messaggi e vogliono lavorare sul proprio stato per capire se e quando accedere alla

risorsa.

Ovviamente un protocollo del genere si baserà enormemente sullo scambio di messaggi, e la

relazione su cui si lavora è una relazione happened-before totale.

57

Quindi ogni processo deve avere una propria coda di messaggi ricevuti in cui i messaggi sono

accodati in modo FIFO secondo il proprio timestamp, e in generale, quando un processo manda un

processo ad un altro non è mai possibile che il processo mittente abbia mandato i messaggi in un

ordine e al ricevente arrivino in un ordine diverso; inoltre, i messaggi non si perdono.

Quello che si assume quindi, è che tutti i processi siano in visibilità diretta l'uno con l'altro; si

potrebbe pensare ad una funzionalità di routing che però non deve permettere omissioni e

scavalcamenti di messaggi, i quali quindi, sono affidabili da questi due punti di vista.

Con queste assunzioni possiamo fare un protocollo che garantisce la mutua esclusione.

58 – 59 – 60

Protocollo M.E.

<<Come si lavora su ogni singolo processo?>>

Ogni singolo processo parte con una coda in cui vi è una sorta di “tappo”: un tempo T0 ed un

processo P0 iniziali ed inesistenti, inferiori di ogni clock del sistema;

Ogni singolo processo sa che esistono N processi;

Ragionando per P1:

Fase1: supponiamo che questi voglia entrare sulla risorsa, quello che quindi fa P1, mette il suo

timestamp T1 ed il suo “nome” P1 sulla sua coda dei messaggi e la manda a tutti gli altri: quindi su

ogni singola coda degli altri processi ci sarà la coppia (T1, P1), quindi manderà N-1 messaggi.

Fase2: Ogni singolo processo che riceve una richiesta di entrare su quella risorsa, risponde con un

ack (con il proprio timestamp aggiornato -in realtà con la coppia (Pm, Tm)-) alla richiesta. Così

facendo il suo clock viene aggiornato e sarà quindi successivo alla richiesta. (N-1 risposte).


Fase3: A questo punto il processo che ha fatto la richiesta vede le N-1 risposte, vede se la sua

richiesta è prima in coda per tutte le possibili richieste che hanno risposte corrispondenti; se questo

è vero, ed è quindi la prima in coda, allora può accedere alla risorsa.

Fase4: Quando ha finito con la risorsa, la rilascia in modo corretto, estrae dalla sua coda tutto quello

che è necessario e poi la fa estrarre a tutti gli altri inviando N-1 messaggi. A questo punto ha finito

il suo operato ed ha la coda pulita se non piena delle richieste degli altri.

Costo totale del protocollo: 3 x (N – 1) messaggi; (costo elevato se il valore di N è elevato).

Alcuni casi di studio:

Caso1: supponiamo che P1 riceva tutti gli N-1 ack di conferma per accedere alla risorsa.

A questo punto, P1 avrà in coda tutti gli N-1 timestamp degli altri processi e saranno tutti superiori

al suo timestamp, quindi, essendone N-1 (tutti gli altri processi), P1 accede alla risorsa, ci sta sopra

quanto tempo vuole (sempre tempo limitato) e quando ha finito, tira via la sua richiesta e tutte le

risposte dalla sua coda ed invia a tutti gli altri il messaggio che dice di togliere la sua richiesta dalle

loro code.

Caso2: due processi contemporaneamente (Pi e Pm) vogliono accedere alla risorsa.

Siamo nella situazione in cui P1 e Pm abbiano inviato la richiesta di accedere alla risorsa e tutte e

due abbiano ricevuto le N-1 risposte. Sicuramente, nelle N-1 risposte di Pi vi è quella di Pm e

viceversa, ma certamente una delle due sarà precedente all'altra. Quelle delle due che è prima

dev'essere anche prima nella richiesta all'altro.

Supponendo che Pi l'abbia inviata prima, sarà quindi Pi ad accedere alla risorsa perché la sua

richiesta è con timestamp inferiore.

Una volta che Pi è acceduto alla risorsa, allora potrà toccare a Pm accedere alla medesima risorsa.

Tale protocollo ha il vantaggio di non avere un punto di centralizzazione, sono loro, tutti processi

del sistema (rete), a decidere chi accede alla risorsa; ovviamente l'ordine di accesso alla risorsa

dipenderà dai loro clock.

Importante è ricordare che in questo protocollo non c'è mai un clock che rimane indietro perché ci è

sempre un ricezione di messaggi ogni qual volta si vuole accedere ad una risorsa.

Inoltre non c'è possibilità di interferenza, anche se tutti volessero accedere contemporaneamente alla

risorsa!

76 Stefano Di Monte

61 - 62

Uua proposta di ottimizzazione, altro protocollo M.E.:

Protocollo Rigart & Agrawala

Molto usato ed implementato.

Con tale protocollo si limita il costo a 2 x (N-1) messaggi.

In sostanza il funzionamento è il seguente:

in generale, si differenzia da Lamport in cui ad ogni invio da parte di un qualsiasi processo di

richiesta per accedere ad una risorsa, io invio sempre una risposta di conferma in qualsiasi caso,

anche se non sono interessato alla risorsa o sto utilizzando quella risorsa.

Pertanto, quello che si fa, è sfruttare quindi, l'essere già su quella risorsa o essere più prioritario del

processo che ha inviato la richiesta per ritardare la mia risposta!

In altre parole, in tale protocollo, quello che succede è che un processo non invia la risposta se è già

su quella risorsa o se è più prioritario del processo che ha inviato la richiesta: la ricezione di tutte le

N-1 risposte è ritardata, non avviene, come nel caso precedente, in un “unico momento”, non

arrivano tutte insieme.

Con tale protocollo si risparmia la fase di rilascio, perché appena la mia coda riceve N-1 risposte

ciò vuol dire che posso accedere alla risorsa.

Comunemente al protocollo di Lamport, quando un processo vuole accedere ad una risorsa invia il

suo timestamp di accesso agli altri; la variazione sta nel fatto che gli altri rispondono a tale richiesta

se e solo se sono meno prioritari e se sono interessati alla risorsa medesima. Se siamo più prioritari

ma vogliamo accedere rispondiamo ugualmente. Invece se siamo già all'interno della risorsa non

rispondiamo. Quindi, se mi trovo dalla parte del mittente, accedo alla risorsa se e solo se ho N-1

risposte nella mia coda; se non le ho tutte, aspetto le altre risposte mancanti (solo un processo può

avere N-1 risposte).

Riassumendo, NON rispondo alla richiesta di voler accedere ad una determinata risorsa se:

• sono PIU' prioritario ma sono ugualmente interessato alla medesima risorsa.

d'altro canto rispondo se:

• sono MENO prioritario

• sono interessato alla medesima risorsa

• non sono interessato alla medesima risorsa

Questo è un modello, (e quindi anche quello di Lamport), su bisogno, nel senso che se si vuole

accedere ad una risorsa allora c'è scambio di messaggi altrimenti non succede niente.

Con questi modelli assolutamente non centralizzati, otteniamo la sincronizzazione lavorando nel

locale: ogni processo lavora solo sulla propria coda.

Sicuramente dietro tutti questi algoritmi, c'è l'idea molto forte che i messaggi non si perdono e

soprattutto che il numero dei processi è statico, il che vuol dire che è quello stabilito, e nel caso

qualcuno faccia richiesta di entrare allora la conoscenza viene trasferita a tutto il gruppo: chiunque

voglia entrare sa che può entrare se e solo se riceve N-1 consensi (stesso discorso ma all'inverso se

qualcuno del gruppo voglia uscirne).

63


Nel corso degli anni si son sviluppati tutta una serie di sistemi che vanno sotto l'acronimo di

CATOCS: si lavora con sistemi causali (quindi con riconoscimento delle relazioni di causa/effetto)

ed in cui si lavora con operazioni totalmente coordinate, quindi in modo atomico.

Si trascura completamente l'idea di un gestore unico, a tutto vantaggio di un tipo di gestione

completamente decentralizzato, a scambio di messaggi.

64

ISIS

Sistema che nasce dall'idea di gestire delle risorse replicate (replicazione attiva) (ovviamente ce ne

saranno altre non replicate) in maniera totalmente trasparente.

Inoltre prevede la coesistenza nel sistema di differenti azioni multicast, ossia di azioni di gruppo che

hanno una semantica differenziata.

(NOTA: dal punto di vista di ISIS, il multicast viene chiamato broadcast).

Queste azioni di comunicazioni di gruppo sono capaci di ordinamento, ovviamente in modo diverso,

ma l'azione di base (quella che avviene se non specifico nulla) resta comunque l'azione senza

ordinamento; ve ne sono comunque 3 che incarnano quelle dette precedentemente:

FIFOBroadcast: prescrive cosa succede quando si va da un certo mittente per quel certo mittente sul

gruppo.

CausalBroadcast: si lavora con rapporto causa/effetto in particolare si confrontano tutti gli altri

causali.

AtomicBroadcast.

Questi broadcast si possono mettere insieme sulla stessa risorsa, quindi per lo stesso gruppo, di

conseguenza le copie corrisponderanno con una semantica per il tipo di broadcast adottato.

Esplorando ISIS, ci si è resi conto che queste tre forme di ordinamento non erano abbastanza: difatti

tutti gli algoritmi visti finora prevedono che non ci sia omissione di messaggi e soprattutto che i

processi non falliscano, cosa che in realtà in genere non accade...

pertanto ISIS introduce una nuova forma di broadcast e la chiama:

GroupBroadcast: vi sono dei momenti, in realtà, in cui il gruppo deve essere gestito: una copia

fallisce, una copia entra in questo momento nel gruppo piuttosto di un'altra che invece va via: il

gruppo diventa DINAMICO.

65 – 66

ISIS Atomic Bcast

Ragionando sull'atomico, in ISIS si lavora in modo simile al protocollo di Lamport: non con la

versione di Ricart&Agrawala perché, permettere alle copie di non poter inviare la risposta nei casi

prima citati, non ci consente di capire se una copia non ha risposto perché guasta o perché non

interessata all'operazione (nel caso di copia guasta ad esempio replicazione in tempo e conseguente

recovery).

In particolare, supponiamo di avere un gruppo, e che arrivi un messaggio dall'esterno (ma non è

78 Stefano Di Monte

detto che debba arrivare per forza dall'esterno), chi riceve tale messaggio diventa il coordinatore del

messaggio stesso.

Il gestore si alloca dinamicamente in base a dove si manifesta il messaggio!

Funzionamento:

Chi riceve il messaggio, ad esempio Pi, lo propaga a tutti gli altri marcandolo con il suo timestamp

(N-1 messaggi). A questo punto, il messaggio non può ancora produrre operatività su alcun

processo, dato che si trova ancora in uno stato intermedio, e gli altri inviano a Pi una risposta

marcandola con il proprio timestamp (N-1 messaggi). Il responsabile del messaggio (quindi Pi),

guarda tutti i timestamp ricevuti e marca il messaggio con quello più alto (timestamp definitivo) e lo

rimanda nuovamente a tutti gli altri con un operazione di multicast. (N-1 messaggi).

<<Scegliere il timestamp massimo è necessario? O si potrebbe scegliere qualcos'altro?>>

La cosa importante in questo protocollo, è la propagazione dell' informazione del messaggio che

dev'essere nota a tutti, e tutti devono averlo collocato nella propria coda, il valore del timestamp,

purché questo sia unico (ed in genere lo è sempre) non ha importanza: andava benissimo un

qualsiasi valore di timestamp, ad esempio quello di inizio o quello del processo ricevente per primo

o ….

La complessità di tale protocollo è 3 x (N – 1) messaggi, che può essere elevata per N elevato ma

che ottiene una semplice marcatura del messaggio: in particolare il costo complessivo non era mai

elevato.

Il protocollo, quindi, prescrive che le risposte siano tutte ricevute, in realtà qualcuno potrebbe

guastarsi e non poter inviare la sua risposta.

67

L'altra forma importante di multicast è il causale, ossia:

l'ISIS CBCast.

Dati due messaggi provenienti dall'esterno, questo protocollo prevede il riconoscimento della

relazione causa/effetto che li contraddistingue.

Quello che si fa, è fare degli ordinamenti interni al gruppo in cui il timestamp che ci guida è quello

del mittente.

Pertanto, tale protocollo ha la stessa complessità del multicast atomico:

• chi riceve invia il messaggio a tutti (N-1 messaggi)

• gli altri mi rispondono che l'hanno ricevuto (N-1 messaggi)

• e il messaggio viene rinviato a tutti gli altri “marcato con l'ordinamento” (N-1 messaggi).

Quindi, supponiamo che arrivino due messaggi in contemporanea: naturalmente chi ha il timestamp

inferiore sarà la causa e l'altro sarà sicuramente l'effetto.

NOTA:

Mentre l'atomico ragiona su degli eventi che sono interni al gruppo dei riceventi, il casuale invece

ragiona con degli eventi che sono esterni al gruppo; pertanto potrebbe però succedere che dati i due

messaggi uno la causa (m1) e l'altro l'effetto (m2) (quindi timestamp di m1 < timestamp di m2), m2

arrivi prima di m1, e m1 arrivi con un ritardo molto maggiore al tempo di coordinamento del


gruppo, quando oramai il gruppo ha già dato un suo verdetto al messaggio m2.

Un multicast casuale quindi, richiede un forte coordinamento dei mittenti, e tale coordinamento non

è responsabilità del gruppo.

Pertanto in alcuni casi, potenzialmente, per un sistema molto globale, e che ad esempio mostra degli

eventi che sono correlati con dei ritardi che rendono molto difficile avvertire la correlazione, forse

in questi casi non sarebbe opportuno lavorare con un multicast di questo tipo, con un multicast

quindi, casuale.

Non è detto che gli strumenti siano sempre corretti!

68

ISIS Group Bcast

In generale è un azione di gruppo, e avviene perché:

-) vi è un cambiamento del numero delle copie del gruppo

-) vi è una copia che si è guastata, e che non è più in grado di lavorare.

Supponiamo un gruppo con determinate copie e con una sua consistenza. Supponiamo ora che il

gruppo, ad un certo punto, potrebbe cambiare di numero di componenti (introduzione di nuove

risorse, o una di queste si guasta ecc ecc). In contemporanea, ricordiamo che su questo gruppo

stanno avvenendo delle azioni multicast FIFO, causale e atomico.

Potrebbe succedere, ad esempio, che mentre stiamo coordinando un messaggio in atomico, un

componente del gruppo non risponda più, quindi non invii più la sua risposta. Al ché potrebbe

essere sollecitato con replicazione in tempo, 1, 2, 3 volte....ma se non risponde si passa ad un'azione

di configurazione di gruppo: si dice a tutto il gruppo che da quel momento in poi la tabella di

appartenenza deve distruggere il riferimento alla copia che non risponde più e deve altresì dire al

gruppo che il numero delle copie è sceso di uno.

Un' azione di gruppo è un broadcast che idealmente dev'essere compatibile e deve lavorare bene con

tutti i broadcast che sono in atto nel gruppo stesso. Naturalmente si parlerà di situazioni critiche

quando si avrà a che fare non con il FIFO bensì con multicast atomico o causale.

Il GroupBroadcast, si comporta come una specie di parentesi per i broadcast già in atto, ad esempio:

per tutte quelle copie che han cominciato a lavorare prima che succedesse il guasto e che il numero

delle copie del gruppo scendesse di uno o il caso contrario (cioè aggiunta di uno), pertanto, se

queste copie fossero in attesa di risposte, è cioè nella fase critica, tali copie sarebbero spostate dopo

il broadcast, dopo quindi che il cambiamento sia avvenuto, dopo cioè che il gruppo è stato avvertito

del cambiamento. Viceversa, per tutte quelle copie che han passato la fase critica, ovviamente queste

saranno prima del GroupBCast.

Il GroupBCast ha un effetto di spostare in tempo tutti gli ordinamenti che non possono essere

completati prima della variazione, anche se avessero già cominciato.

La gestione del gruppo è una cosa molto importante.

69

JGroup

80 Stefano Di Monte

70

Ring Logico

Sincronizzazione fatta in modo dinamico:

In sostanza, se abbiamo un gruppo di partecipanti, questo potrebbe

essere organizzato in un ring logico, anello che consente a ciascuno di

conoscere solamente i suoi due vicini.

Questo è un sistema sicuramente scalabile, perché non devo conoscere

tutti ma solo chi mi segue e chi mi precede.

Tipicamente, l'anello viene usto per far circolare un'autorizzazione, un

token, che nel caso della sincronizzazione rappresenta la possibilità di

fare sincronizzazione, quindi chi lo ha in un certo istante potrebbe essere

quello in grado di accedere alla risorsa (parlando degli ordinamenti precedenti, chi ha il token, ad

esempio, potrebbe essere quella copia responsabile della marcatura finale del messaggio).

L'atomicità di tale modello, sta nel fatto che il token circola: un nodo, quindi un processo, può

tenere il token solo per un certo tempo, dopodiché è obbligato a passarlo al successivo (ogni nodo

quindi ha il suo slot di responsabilità). Naturalmente, se ad un nodo arriva il token, e questi non

deve fare niente, può sicuramente passarlo più velocemente al prossimo.

Inoltre il token ha un tempo massimo di circolazione.

Trovandoci nel distribuito, potrebbe comunque essere che vi siano dei ritardi, che quindi un nodo

trattenga il token per un periodo maggiore al consentito, al previsto, quindi il tempo di circolazione

del token potrebbe essere superiore a quello previsto.

Questa è una soluzione proattiva: si impegna banda anche se non si fa nulla! In altre parole il token

deve circolare anche senza richieste!

D'altra parte la trasmissione del token non è poi molto pesante.

71

Dunque, come già accennato, il token circola, un singolo nodo lo riceve ad un certo punto, lo usa se

necessario e quando ha terminato è costretto a passarlo al successivo.

Pertanto l'anello potrebbe sembrare una struttura molto decentralizzata, in realtà è molto importante

che tutti sappiano quanti sono i partecipanti in numero perché è molto importante che si sappia il

tempo di circolazione del token stesso.

Il token è la struttura fondamentale: per fare sincronizzazione, per accedere alle risorse, per ordinare

l'accesso risorse... ...senza il quale non è possibile lavorare.

Bisogna garantire pertanto che il token sia sempre presente.

Ovviamente, se un nodo dell'anello fallisse, ed è quello che detiene il token, allora il token non vi

sarebbe più: bisogna avere una qualche gestione dei guasti e del sistema in generale, che in questo

caso, ad esempio, rigenerasse il token nuovamente e magari non ne generasse più di uno, in poche

parole che funzioni correttamente.

In caso di fallimento è quindi indispensabile un piccolo supporto: se qualcuno fallisce, qualcun'

altro deve accorgersene ed avviare la fase di recovery del nodo caduto per chiudere l'anello (ad


esempio i nodi vicini...).

72

La parte di supporto è di solito implementata a basso livello e viene tenuta separata dalla parte di

gestione e di controllo del token la quale è gestita dai nodi stessi.

Ogni singolo nodo, quando passa il token al suo successivo fa scattare un time-out,che dipende dal

numero di nodi e quindi dal tempo di permanenza massimo del token su ogni singolo nodo del ring.

A questo punto, se il time out scatta e il token non è ancora ritornato al nodo che ha lanciato il time

out, allora molto probabilmente vorrà dire che il token si è perso.

La procedura di recovery quindi, è pensata per ogni singolo nodo che ha un proprio time out, e parte

se il token non ritorna prima che quest'ultimo termini il countdown: nel caso in cui ritorni in tempo,

il timeout viene azzerato e fatto ripartire al prossimo passaggio del token al nodo successivo.

73 - 74

Nel caso in cui il time out scatti, questo potrebbe scattare su una serie di nodi e non solo su un unico

nodo, quindi bisogna stare attenti a generare un solo token.

La procedura di creazione del nuovo token viene tipicamente chiamata protocollo di elezione

nell'anello.

Il funzionamento è il seguente:

quando scatta il time out, parte la procedura di recovery, quindi il

protocollo di elezione del nuovo token;

si fa partire un token falso, un token di elezione (ET), destinato a

diventare, se tutto va bene, un token vero. Questo, quindi, viene

mandato a tutti i nodi dell'anello, i quali al suo passaggio

capiscono che è in atto una azione di elezione del nuovo token, e

ci aspettiamo ritorni al punto di partenza.

In particolare, ponendoci al posto del nodo che ha avviato

l'elezione del nuovo token:

1. se quest'ultimo vedesse ritornare l' election token da lui inviato, allora quest'ultimo diverrebbe il

nuovo token e da questo momento in poi sarà l'unico token sul ring.

2.se quest'ultimo vedesse passare il vecchio vero token, allora sicuramente nell'anello vi è una

situazione di ritardo, nessun guasto, quindi il recovery non è più necessario e di conseguenza l' ET

viene distrutto.

3.se quest'ultimo vedesse passare un altro election token (due nodi han generato l'ET), allora

sicuramente quello che dovrebbe succedere che uno ed uno solo dei token che stanno girando

nell'anello possa realizzarsi in vero token. Quello che conta in questo caso è la priorità statica dei

nodi generatori dell' ET e facenti parte dell'anello: si può dire che l' ET eredità la priorità del suo

nodo generatore (un nodo 5 avrà sicuramente più priorità del nodo 3). L'ET con priorità maggiore è

destinato a diventare il nuovo token del ring.

Tipicamente nei protocolli di elezione, non si può prevedere quale sarà il numero delle fasi

dell'elezione, non si può prevedere in sostanza quale sarà il numero dei token che si genereranno,

quindi non si può prevedere quanto durerà il tempo dell'elezione (breve se l'ET sarà generato dal

82 Stefano Di Monte

nodo più prioritario, massimo se l'ET sarà generato dal nodo con priorità più bassa).

NOTA: l'architettura dell'anello qui presente è stata pensata per un guasto singolo ma ne sono state

create anche per guasti multipli.

75 - 76

Quando si parla di protocolli di elezione non si può non citare un algoritmo molto usato, non per

forza su di un anello, ma a qualsiasi architettura: algoritmo BULLY: dal nome “bullo” ne deriva la

logica dell'algoritmo che fa stare zitti tutti gli altri (nodi).

Data una serie di possibili partecipanti, ossia di nodi che possono intervenire

e gestire una situazione di quelle citate prima, in sostanza bisogna stabilire in

modo dinamico chi deve farlo; i nodi hanno tra loro un ordine a priorità

statica: se c'è il nodo1 e lui che deve gestire il tutto, altrimenti il nodo2, o il

nodo3 e così via...

Se tutto ciò non è stato determinato a priori, se quindi non vi è un

coordinatore, bisogna stabilirlo dinamicamente: chi si accorge della

mancanza di ciò cerca lui stesso di diventare il coordinatore del gruppo.

Avverte il gruppo del suo volere, inviando un messaggio verso l'alto ossia

verso i nodi più prioritari, fa quindi partire verso questi un elezione

(Election).

Se sono presenti altri nodi più prioritari, questi lo rispondono con un

messaggio di Answer, con il quale lo azzittiscono dicendogli che non può diventare lui il

coordinatore.

Viceversa, se non sono presenti nodi più prioritari, e comunque entro un certo tempo non dovesse

ricevere alcun messaggio di answer, allora potrà essere senz'altro il nuovo coordinatore: invierà un

messaggio, verso il basso a tutti i nodi meno prioritari, chiamato IAmCoordinator.

Se siamo fortunati il tutto dura due fasi, altrimenti questo algoritmo constaterà di tre o più fasi: nel

caso in cui il nodo che comincia sia a priorità minima, ciò comporterà un numero di fasi elevato.

Questi protocolli consentono di lavorare a fronte di guasti molteplici.

77

Ci stiamo muovendo quindi in un campo in cui si parla di sincronizzazione in maniera molto

decentralizzata, senza introdurre punti di guasto singolo: quelli che possono fallire possono essere

anche più partecipanti.

A tal proposito, quello che si manifesta in un sistema, è determinare uno STATO GLOBALE.

Determinare uno stato globale in un sistema fortemente distribuito, quindi in cui vi sono molti

processori che lavorano e che si coordinano tramite scambio di messaggi, può avvenire per varie

ragioni, ad esempio se il sistema è soggetto ad un fallimento si potrebbe salvare tutto lo stato per

capire cosa sia successo, oppure in alcuni casi si vuole fare un checkpoint di tutto il sistema per

capire quale sia la situazione totale del sistema, per poi far ripartire il sistema stesso dall'istante di

“pausa”.

Supponiamo di avere dei processi su dei processori.


Per salvare lo stato del sistema, si potrebbero prendere tutti gli stati dei partecipanti al sistema e

anche i messaggi scambiati (in atto) tra i diversi processi: ma ciò potrebbe portare ad avere più parti

dello stato globale magari non compatibili tra loro, mandando in frantumi l'idea che vorremmo

avere di stato globale “sensato”.

Bisogna fare in modo che il salvataggio dello stato avvenga in momenti giusti e consistenti!

78 - 79

Si consideri la linea tratteggiata della figura come il momento in cui i processi salvano lo stato;

come si nota dalla figura di sinistra, la quale rappresenta un taglio consistente:

-) P1 salva il suo stato dopo aver mandato il messaggio m3, quindi quando P1 ripartirà non invierà

nuovamente il messaggio m3.

-) il salvataggio di P2 e P3 non incorporano il messaggio m2; in particolare P2 deve tener conto che

a lui arriverà il messaggio m3, che quindi si presenterà su di un suo canale d'ingresso. Se non

tenesse conto di questo, quel messaggio m3 andrebbe perso; per evitare ciò dovrà quindi far parte

del suo stato!

Guardando la figura di destra, rappresentante un taglio inconsistente:

-) m3 non viene incorporato ma non provoca alcuna situazione critica

-) P2 salva prima dell'invio di un messaggio, in questo caso di m2 che quindi non risulta incorporato

nello stato, mentre P3 fa un salvataggio dopo la ricezione del messaggio m2. In questo caso si

incorpora nello stato globale la ricezione del messaggio ma non l'invio, portando ad una situazione

di inconsistenza del salvataggio. Risulta inconsistente perché, così facendo, alla ripartenza, P2

risulta non aver inviato nessun messaggio, mentre a P3 risulta aver ricevuto il messaggio. A questo

punto se facessimo un replay, avremmo che il messaggio m2 verrebbe inviato 2 volte!

Pertanto, si è stabilito che tutti gli algoritmi di salvataggio dello stato globale debbano ragionare

sull'effettuare tagli consistenti: tutti i nodi salvano il proprio stato e quindi, saltano i messaggi che

stanno arrivando sui loro ingressi

80 – 81 – 82 – 83 – 84

Per fare un sistema di salvataggio di stato bisogna introdurre una composizione dello stato che si

84 Stefano Di Monte

chiama snapshot (fotografia) di tutti i nodi in un certo momento, e che siano consistenti. Tale

fotografia potrebbe partire da uno qualsiasi dei nodi del sistema, la cosa risulta indifferente solo se il

sistema è completamente connesso.

In linea di principio, la strategia funziona in questo modo:

Battezziamo pertanto che sia avviata tale procedura: un nodo fa partire lo snapshot.

Quello che deve accadere ora, è che venga propagata l'idea dello stato che va salvato: chi lo salva

dovrà dire agli altri, attraverso i suoi canali d'uscita, che dovrà a sua volta salvare lo stato. Si parla

quindi di “onda di salvataggio dello stato” che si propaga tra i nodi del sistema: chi riceve l'onda

deve salvare il suo stato e propagare a sua volta.

Quando tutti hanno salvato, il lavoro è terminato e ciò che avremo sarà lo stato globale del sistema.


Ogni nodo è caratterizzato da due colori che rappresentano lo stato:

bianco: devono effettuare il salvataggio, non sono stati interessati dall'onda di propagazione del

salvataggio

rosso: hanno fatto/stanno per fare il salvataggio

Pertanto il primo nodo che parte è il primo che da bianco diventa rosso; per cambiare colore deve

fare due cose:

(a) salvare il proprio stato (sulla sua memoria di sistema, a livello locale, sul proprio HD...

(b) deve mandare, attraverso tutti i suoi canali d'uscita, l'idea della propagazione dello snapshot

a tutti i suoi vicini: in generale esiste un messaggio ad-hoc che si chiama marker, il quale per

l'appunto propaga l'onda verso i vicini.

Di conseguenza ogni nodo ripete queste due fasi: riceve un marker ed effettua i punti (a) e (b)

precedenti.

Una volta che tutti i processi han salvato in locale il loro stato, si ricordi che lo stato globale è fatto

anche di messaggi (stato del canale) e non solo dello stato locale di tutti i processi, quindi dobbiamo

tenere in conto anche di tutti i canali d'ingresso: dal momento in cui un processo diventa rosso

continua a registrare ciò che gli viene in ingresso, su tutti i canali, fino a che questi non si

chiudono, ossia finché su ogni singolo canale non arriva un messaggio di marker.

Con:


NOTA: si ricordi che il marker è comunque un messaggio come gli altri e viene accodato, se ce ne

fosse bisogno, come vengono accodati tutti gli altri messaggi.

Quindi ci sono due casi di arrivo del marker:

(a) se arriva quando il processo è bianco, allora questi diventa rosso

(c) - (d) se arriva quando il processo è rosso, allora questi chiude il canale d'ingresso dove è arrivato

il marker e lo stato di un processo, salvato per far parte dello stato globale, comincia dal momento in

cui quel processo diventa rosso al momento in cui arriva il marker che mi chiude tutti i canali

d'ingresso.

A questo punto avremo lo stato globale quando tutti i nodi son diventati rossi e han chiuso i loro

canali d'ingresso.

85

Una volta effettuato lo snapshot globale sarebbe opportuno che:

-) tutti ritornano ad essere bianchi.

-) magari esiste un nodo dedicato alla raccolta di tutti gli stati salvati dai diversi nodi del sistema.

Supponiamo che ci sia un' interferenza: che ad esempio due processi facciano partire lo snapshot

contemporaneamente. Sicuramente, le due cose non sono compatibili, in quanto ci sarebbero alcuni

processi diventati rossi per un certo marker ed altri per l'altro marker...

86 Stefano Di Monte

<<E' possibile pensare ad una situazione in cui coesistono due snapshot contemporaneamente?>>

Certo, basta identificare i diversi snapshot! Distinguere ad esempio gli stati dei rispettivi processi:

per ogni tipo di marker vi è un colore dello stato, due rossi differenti per i due diversi marker: uno

stato potrebbe essere rosso per il marker del mittente A e ancora bianco per il marker del mittente B.

<<E se gli snapshot arrivassero dallo stesso mittente?>>

Potremmo identificare negli snapshot oltre al mittente, il tempo di invio o l'ordine d'invio.


Comunicazione - LIAComunicazione 2 Quando parliamo di comunicazione punto-punto, parliamo di...

Documents

Transcript of Comunicazione - LIAComunicazione 2 Quando parliamo di comunicazione punto-punto, parliamo di...