.. meta:: :language: it :description language=it: sincronizzazione :description language=en: synchronization :keywords: distributed system, synchronization :author: Luciano De Falco Alfano .. index:: sincronizzazione .. _ref_sincronizzazione: Sincronizzazione ================== .. contents:: :local: *Lezione del 2019-05-08 mer*. Concetti base ---------------- I processi hanno la necessità di sincronizzarsi. La sincronizzazione può essere necessaria per i segenti motivi: * concordare rigaurdo l'accesso esclusivo ad una risorsa; * concordare riguardo l'ordine degli eventi in corso. La sincronizzazione in un singolo sistema centralizzato è facile da ottenere. Ma quando si ha a che fare con più sistemi autonomi, può essere un requisito molto difficile da perseguire. In alcuni casi un gruppo di processi ha necessità di concordare un coordinatore (*leader*). Consideriamo il problema dell'ordinamento di eventi tra sistemi autonomi, che è alla base anche della gestione dell'accesso a risorse condivise tra sistemi distribuiti. Il concetto di ordinare eventi è relazionabile al concetto di tempo. Possiamo associare agli eventi una coordinata temporale, e ordinarli secondo il valore di questa coordinata. Ad esempio. Supponiamo vi sia un *general clock* valido per tutti i processi. Il processo *A* rileva il tempo dal clock ottenendo *t(A)*. Dopo di che fa la stessa cosa il *processo *B*, ottenendo *t(B)*. Varrà *t(A) <= t(B)*, e possiamo affermare che l'evento del processo *A* avviene prima dell'evento del processo *B*. Però l'uso di una coordinata temporale non semplifica il problema. Anche questa è semplice da gestire in un sistema centralizzato, ma non lo è in un sistema distribuito. Per capire questo concetto osserviamo il seguente diagramma temporale. .. image:: ./images/22_clock_distribuito.svg :align: center Questo diagramma illustra una possibile situazione anomala che si può creare in un sistema formato da due computer: uno (il superiore) demandato alla compilazione del programma *out.c* in *out.o*, e l'altro (coordinata centrale) in cui si effettua l'editing di *out.c*. Un programma *make* [#]_ che confronti l'ora di creazione di *out.o* (le 2020, secondo il clock locale del computer di compilazione) lo troverebbe successivo all'orario di modifica di *out.c* (le 2010, secondo il clock locale del computer di editing). In queste condizioni *make* **non** ricompila *out.o*. Invece, usando la coordinata in basso, (che ci mostra il *general clock*, ovvero il tempo oggettivo) possiamo osservare che *out.o* è stato creato alle 2010, precedente alle 2020 che è l'orario di editing di *out.c*. Un *make* in grado di valutare gli eventi secondo il *general clock* ricompilerebbe correttamente *out.o*. Questo problema è generale. Ad esempio si supponga di voler monitorare un ponte, tramite sensori che inviano i dati a diversi computer. Per confrontare i dati ricevuti da computer diversi, è necessario che i clock locali dei due computer siano confrontabili. Non solo. Se voglio sapere a che ora è accaduto un evento di particolare interesse (ad es. una sollecitazione sismica), devo avere sincronizzazione con un orario valido in generale. Analogamente se vogliano controllare il movimento di un robot, con sensori di posizione e movimento che inviano i relativi dati a computer diversi. Anche in questo caso, dovendo confrontare i dati collezionati da computer diversi, è necessario sincronizzare i relativi clock. Non tutti i problemi di sincronizzazione sono uguali. In un determinato contesto è possibile sia sufficiente determinare se un evento è avvenuto prima o dopo un altro evento. In questi casi "*basta*" avere una temporizzazione logica (si veda oltre). Nell'esempio precedente sarebbe sufficiente sapere se la generazione di *out.o* è avvenuta prima o dopo la modifica di *out.c*. Ma vi sono casi in cui questo non basta. Supponiamo di poter accedere ad una risorsa solo in un determinato intervallo temporale. In questo caso è necessario che il computer che richiede l'accesso sia sincronizzato con il clock del controllore secondo la misura fisica del tempo. Il problema della sincronizzazione dei clock ---------------------------------------------- Quindi: come si possono sincronizzare i clock di computer diversi? Generalità ^^^^^^^^^^^^^^ Il clock locale di un computer viene usualmente realizzato utilizzando cristalli di quarzo fatti oscillare a determinate frequenza. La frequenza di oscillazione del quarzo dipende, in modo molto sensibile, dalla tensione applicata al suo circuito. Al quarzo sono associati un contatore a una cella di inizializzazione (*holding register*). Ad ogni oscillazione del quarzo, il contatore decrementa di uno. Quando arriva a zero viene generato un interrupt e il contatore viene ricaricato con il contenuto del registro di inizializzazione. L'interrupt viene ricevuto dal sistema operativo, che aggiorna di conseguenza il proprio contatore temporale (ovvero il clock fisico del computer). La sincronizzazione del tempo fisico richiede la sincronizzazione dei clock delle cpu coinvolte nel sistema distribuito. Garantire che la frequenza di oscillazione dei cristalli che pilotano i diversi clock sia uguale per tutti è impossibile. Di conseguenza, gradualmente i clock derivano uno rispetto l'altro. La differenza di valori tra due diversi orologi è detta *clock skew*. In alcuni sistemi, ad es. nei sistemi real-time, il valore fisico del clock è importante. Da qui la necessità di capire come sincronizzare i clock fisici con gli orologi del modo reale, e come sincronizzare i clock fisici tra loro. Quindi è necessario capire come viene misurato il tempo nel mondo reale. Il tempo è un concetto complesso. Nel 17° secolo l'invenzione dell'orologio meccanico ha permesso la misura oggettiva del tempo, inizialmente riferendosi al tempo solare medio. Il tempo solare medio si riferiva all'intervallo temporare che passa tra due **transiti** [#]_ consecutivi del sole: il *giorno solare*. Da questo derivava il *secondo solare*, definito come 1/86400 di un giorno solare medio. Nel 1967/68, nell'ambito del *Sistema internazionale di unità di misura* (*SI*) il secondo è stato definito come: "The second is the duration of 9 192 631 770 periods of the radiation corresponding to the transition between the two hyperfine levels of the ground state of the caesium 133 atom." 13th CGPM (1967/68, Resolution 1; CR, 103) "This definition refers to a caesium atom at rest at a temperature of 0 K." (Added by CIPM in 1997) In pratica il tempo atomico (TAI) è dato dal numero medio di transioni di vari orologi al cesio 133, misurati dal 1 gennaio 1958 e divisi per 9,192,631,770. Con questa definizione si è resa indipendente l'unità di misura del secondo dalle misurazioni astronomiche, che dipendono da caratteristiche fisiche variabili. Ad es. perché il periodo di rotazione della Terra è in estensione, per questo attualmente il giorno calcolato con 86400 secondi TAI è più breve del giorno solare medio di 3 msec. Lo sfasamento tra TAI e lunghezza del giorno solare medio viene risolto introducendo un intervallo di sfasamento (*leap seconds*) quando la differenza osservata tra le due misure supera gli 800 msec. Questa coordinata temporale viene detta **Coordinated Universal Time** (UTC). UTC tramite stazioni radio e satelliti ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Esistono stazioni radio che trasmettono il tempo UTC, ad es. in USA la WWV, e in UK la MSF. Così come molti satelliti dispongono del servizio di comunicazione del tempo UTC. Quindi è possibile utilizzare ricevitori radio ad onde corte, o da servizi satellitari, per ricevere le trasmissioni predette ottenendo un segnale UTC di riferimento. Eventualmente modificndo il segnale con il calcolo delle posizioni relative tra trasmettitore e ricevitore per correggere l'errore dovuto al ritardo della propagazione dell'onda radio. UTC tramite GPS ^^^^^^^^^^^^^^^^^ Un'altra possibilità consiste nell'utilizzare il sistema GPS. Questo è un sistema distribuito di satelliti che permettono di determinare la posizione geografica di un punto della superficie terrestre. I satelliti GPS sono posizionati ad una altitudine di 20,350 km [#]_. Ognuno è dotato di 4 orologi atomici, e trasmettono in continuzione la loro posizione. Ogni messaggio è marcato con il local time del satellite stesso. Ed essendo un local time ottenuto dalla media di 4 orologi atomici, è molto accurato. Ogni device dotato di ricevitore GPS è in grado di sincronizzare con il local time dei satelliti GPS. La localizzazione di un punto geografico sulla superficie terrestre può avvenire confrontando i segnali di tre satelliti GPS. Se si ricevono più segnali dei tre necssari, il ricevitore può calcolare le medie, ottenendo una misura più precisa del punto. Quando si calcola la posizione tramite GPS è neessario considerare due aspetti importanti: * la ricezione del segnale non è immediata [#]_; * il clock del ricevitore in generale non è sincronizzato con quello del satellite. Se si indica con: * :math:`\Delta_r` la deviazione (incognita) dell'orologio del ricevitore rispetto quello del satellite, * :math:`T_{now}` il tempo del ricevitore, * :math:`T_{i}` il tempo del satellite (questo è dichiarato dal satellite); allora l'intervallo temporale per la ricezione del segnale è dato da: .. math:: \Delta_i = (T_{now} - T_i) - \Delta_r E la distanza reale dal satellite è (*c* è la velocità della luce): .. math:: d_i = \Delta_i \cdot c = (T_{now} - T_i) \cdot c + \Delta_r \cdot c Da questa si capisce che per rimuovere le incognite è necessario impostare un sistema di equazioni in cui maggiore è la quantità di satelliti, più accurato sarà il calcolo. UTC tramite Network Time Protocol ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Esistono processi che possono comunicare il tempo corrente. Server che implementano questo servizio sono detti **time server**. Però anche in questo caso è necessario considerare i ritardi dovuti al processo di invio della richiesta, la sua elaborazione nel server, e per la ricezione della risposta. È necessario effettuare una buona stima di questi ritardi. Cosa difficile, perché dipendono da fattori che sono al di fuori del nostro controllo. Il tempo di risposta della rete, dipendente dal traffico corrente. Il tempo di risposta del server, dipendente dal suo carico di lavoro. E così via. L'algoritmo di Berkeley ------------------------- Questo algoritmo si utilizza in LAN per sincronizzare gli orologi rispetto un time daemon di riferimento, usando però un algoritmo di calcolo della media dei clock delle diverse macchine coinvolte. Quindi qui lo scopo non è quello di avere una sincronizzazione con il tempo UTC. In pratica il time daemon chiede a tutte le altre macchine i valori dei loro clock. Queste rispondono con il delta rispetto il tempo dichiarato dal server. Il server calcola di conseguenza la variazione necessaria per allineare ogni macchina, incluso se stesso, e la comunica di conseguenza. Ad esempio come nella seguente tabella. ============ ===== ==== ================================= ============== computer time Δ time deamon correction correction ============ ===== ==== ================================= ============== WS A 2:50 -10 3:05-2:50=+15 WS B 3:25 +25 3:05-3:25=-20 Time daemon 3:00 0 (-10+25+0)/3=+5 => 3:00+5 = 3:05 3:05-3:00=+05 ============ ===== ==== ================================= ============== Orologi logici ----------------- (*Logical clocks*) Il concetto di orologio logico è stato proposto da Leslie Lamport [#]_ nel 1978 (vedi [LAMP1978]_) per gestire i casi in cui è necessario concordare la sequenza di eventi, senza dover per forza sincronizzare gli orologi fisici. Il precedente esempio della *make* ricade in questo contesto: basta sapere che *out.o* è stato prodotto *prima* della modifica di *out.c*. Tra l'altro Lamport ha osservato: * che se due processi non interagiscono, non è necessario sincronizzare i loro orologi; * spesso non è necessario sincronizzare il valore degli orologi, ma concordare riguardo come si sono succeduti gli eventi. Detto con maggiore enfasi: mi serve sempre il tempo? No, in alcuni casi non mi serve. L'orologio logico di Lamport non è un orologio: è un contatore di eventi. Lamport si basa sul concetto di ordinamento parziale, e definisce una relazione **happens-before**, indicabile come :math:`a \rightarrow b` (*a happens-before b*); questa significa che: avviene *a*, e poi avviene *b*. La relazione *happens-before* può essere osservata direttamente: * se *a* e *b* sono eventi che hanno luogo nello stesso processo, e *a* avviene prima di *b*, allora :math:`a \rightarrow b` è *vero*; * se *a* è l'invio di un messaggio da parte di un processo, e *b* è la ricezione dello stesso messaggio da parte del processo destinatario, allora :math:`a \rightarrow b` è *vero* [#]_. Per la relazione *happens-before* vale la relazione transitiva: :math:`if \: a \rightarrow b \: and \: b \rightarrow c \: then \: a \rightarrow c`. Se due eventi *a* e *b* avvengono in processi diversi, che non si scambiano messaggi, riguardo la relazione :math:`a \rightarrow b` *non possiamo* affermare sia vera, ma nulla possiamo affermare neanche riguardo :math:`b \rightarrow a`. In un sistema complesso, formato da più macchine, utilizzando i logical clock di Lamport, e la relativa proprietà transitiva, è possibile ordinare gli eventi nell'ambito di uno stesso processo e quelli che avvengono tra processi diversi. Tutti i processi possono concordare su un tempo *C(a)* tale che se è vero :math:`a \rightarrow b`, allora è vero *C(a) < C(b)*. Il tempo *C* (*Clock Time*) non può essere decrescente. Le sue variazioni devono avvenire sempre sommando valori positivi, mai sottraendo. L'implementazione dei logical clock prevede che il messaggio di sincronizzazione tra processi diversi trasporti anche il valore del logical clock della macchina che ha generato l'evento [#]_ Lamport ha proposto il meccanismo illustrato qui di seguito, considerando la presenza di tre diversi processi, ognuno con il suo logical clock, dotati di velocità diverse (ovvero da sx a dx incrementi di 6, di 8 e di 10). .. image:: ./images/23_logical_clock.svg :align: center Nel disegno a sinistra osserviamo che *m1* ed *m2* sono congruenti, in quanto il tempo di arrivo é superiore a quello di partenza del messaggio. Invece *m3* ci pone un problema: il suo arrivo al tempo 56 non è compatibile con quello di partenza, che vale 60. Quindi il processo *P2* porrà il suo orologio logico al valore di 60+1. Analogamente *m4* parte a 69, ma arriverebbe a 54. Al suo arrivo il processo *P1* porrà il suo orologio logico a 69+1. L'implementazione del logical clock avviene nel middleware layer tra il livello applicativo e quello di network che trasporta il messaggio. E tipicamente: * prima di inviare un evento, il processo |Pi| aggiorna il logical clock eseguendo :math:`C_i \leftarrow C_i + 1`; * quando il processo |Pi| invia il messaggio *m* al processo |Pj| pone il timestamp di m (*ts(m)*) pari a |Ci|; * alla ricezione di un messaggio *m*, il processo |Pj| aggiusta il suo logical clock al valore :math:`C_j \leftarrow max\{C_j, ts(m)\}`, quindi esegue :math:`C_j \leftarrow C_j + 1` e passa il messaggio *m* all'applicazione. Multicasting completamente ordinato -------------------------------------- (*Totally ordered multicasting*) La necessità che i messaggi di multicasting inviati tra diversi componenti di un sistema distribuito debbano essere ordinati può essere compresa analizzando il seguente scenario. Supponiamo di avere due processi (*User1* e *User2*), che possono inviare comandi di modifica (*Upd1* e *Upd2*) ai due server *Replica1* e *Replica2*. Essendo repliche, i comandi sono inviati due volte: una per ogni server, al fine di mantenerli allineati. Ora, supponiamo che la sequenza temporale con cui sono inviati i comandi, sia quella illustrata nella seguente figura, in cui la coordinata temporale fisica è orientata secondo le frecce orizzontali. Inoltre si ipotizza che il messaggio *udp1* sia inviato ai due processo *replica1* e *replica2* in multicast, quindi le due "copie" partono nello stesso momento. Analogamente per il messaggio *udp2*. .. image:: ./images/24_ordered_multicasting.svg :align: center In questo scenario, confrontando *user1* rispetto *user2*, osserviamo che *Upd1* è generato prima di *upd2*. Ma, mentre *replica1* riceve i due comandi nell'ordine corretto, *replica2* li riceve rovesciati: prima *upd2* e poi *upd1*. Consideriamo il fatto che *upd1* può modificare un dato il cui valore viene successivamente usato da *upd2*. Si capisce che in questo caso l'ordine in cui arrivano i comandi è significativo, ed è necessario siano eseguiti in entrambi i sistemi con la stessa sequenza. Quindi in alcuni casi abbiamo necessità che la **sequenza di esecuzione** di una serie di messaggi su più processi sia rigorosamente la stessa. Si noti che parliamo di sequenza di esecuzione, non di tempo fisico. Per questo motivo i *logical clocks* di Lamport sono buoni candidati per governare questo tipo di scenari. Osservando che i *logical clocks* vengono regolati quando due processi interagiscono, e considerando il fatto che in un sistema formato da più processi, ogni processo interagisce con qualunque altro processo cui richiede/fornisce servizi, ne deduciamo che i *logical times* di tutti i processi che hanno interesse l'uno con l'altro sono mutuamente sincronizzati. Di conseguenza la relazione di Lamport può essere utilizzata per dimostrare il concetto di *totally ordered multicast*, di cui abbiamo bisogno, in contesti in cui vi è un numero limitato di processi. Qui di seguito si riporta un esempio di uso della relazione di Lamport per mostrare un ordinamento di eventi in due processi *P1* e *P2*. La colonna del processo indica il csuo lock logico, seuito dalla colonna che indica il contenuto del messagio in uscita, quello del messaggio in entrata, la coda dei messaggi orinati secondo l'orologio logico, ed infine l'azione dell'applicazione. La prima colonna a sx è un Global clock di riscontro per il lettore: identifica la riga. .. image:: ./images/total_ordered_multicast.png :align: center In sintesi *P1* invia il messaggio di update *M1* a se stesso e a *P2*. Mentre *P2* invia il messaggio di update *M2* a se stesso e a *P1*. Alla ricezione dei rispettivi messaggi, questi vengono messi in coda, ordinata secondo l'orologio logico: lo osserviamo alla riga 2, e alla riga 3, nelle colonne *queue* dei rispettivi processi. Dopo di che le applicazioni inviano le conferme di ricezione: alla riga 3 partono *AM1P1* (ack di *M1*, processo *P1*) e *AM2P2* (ack di *M2* processo *2*) [#]_. Questi ack sono ricevuti alla riga 4 e al tick successivo (riga 5) sono registrati nelle code per svincolare i relativi messaggi. Questo accade per *M1* in *P2*, in quanto è in testa alla coda, ma non ad *M2* in *P1*; infatti *M2* viene dopo *M1*, che *P1* ancora non può eseguire perché non ha ricevuto il relativo ack da *P2*. Alla riga 4 partono gli ack *AM2P1* da *P1* e *AM1P2* da *P2*, che sono ricevuti alla riga 5e registrati in coda alla riga 6. Si noti che alla riga 5, i valore dell'orologio logico di *P1* passa da 24 a 25, in quanto riceve un valore 24 nel timestamp di *AM1P2*, e per la regola di Lamport viene incrementato per non andare in conflitto. Finalmete, alla riga 6 *P1* può eseguire *M1*, avendo ricevuto il repatvo ack da *P2*, mentre *P2* conclude le attività eseguendo *M2* perché ha ricevuto il relativo ack da *P1*. All riga 7 anche *P1* conclude le attività eseguendo *M2*. Si osserva come entrambi i processi hanno rispettato l'ordinamento dei messaggi grazie all'uso degli orologi logici di Lamport. Si noti che se abbiamo una rete di processi di grandi dimensioni [#]_, la relazione di Lamport non è più sufficiente. È necessario ricorrere ad altre soluzioni. Conclusione ------------------- La sicronizzazione è importante nel caso di esistenza di repliche. Perché si deve assicurare che le operazioni siano esguite con lo stesso ordine nelle diverse repliche. In questi casi i logical clock di Lamport possono essere usati per assicurare che venga rispettato l'ordine dei comandi nelle diverse repliche. Usare l'ordine per mantenere allineate le repliche è detto *State Machine Replication Approach* (SMRA). ------------------- .. |Pi| replace:: P\ :sub:`i` .. |Pj| replace:: P\ :sub:`j` .. |Ci| replace:: C\ :sub:`i` .. [#] Si ricorda il comportamento del *make*. Un file viene trattato (compilato) se il suo sorgente ha un timestamp successivo a quello del file prodotto. Ad esempio, nel caso di compilazione con *linguaggio c*, abbiamo questo processo: source-file -> object-file -> executable-file, che nell'esempio è: out.c -> out.o -> out. Se t(out.c) > t(out.o), *make* lancia la compilazione di out.c per produrre un nuovo out.o. .. [#] Un *transito* solare è il momento del passaggio del sole per il suo punto più alto nell'arco della giornata. .. [#] la distanza di un satellite dalla Terra viene classificata in: LEO (<=2000 km), MEO ( >2000, <= 35786 km) e HEO zone (>35786 km). La frontiera MEO/HEO zones definisce l'orbita sincrona (GEO e GSO). Un satellite GSO appare fisso rispetto la superficie terrestre. I satelliti GPS sono in orbita semisincrona (SSO), ovvero completano la circumnavigazione della terra in esattamente 12 ore. .. [#] Servono *t = s / v* secondi per ricevere il segnale. Se *s = 20000 km* e *v = 300000 km/sec*, allora vale circa *t = 0.0066... sec*, ovvero circa 6.7 msec. .. [#] Computer scientist molto conosciuto. Tra l'altro, ideatore del LaTex, dei protocolli Paxos, del concetto di Bizantine Failure, e del linguaggio formale TLA+. I protocolli Paxos servono decidere il consenso riguardo risultati ottenuti da un gruppo di processori non affidabili (ovvero, che possono fallire). Il `TLA+ `_ (Temporal Logic of Actions) è un linguaggio formale per progettare e modellare sistemi concorrenti. .. [#] In quanto un messaggio non può arrivare prima di quando inviato. .. [#] Questo è un comportamento simile al timestamp associato ad un messaggio. Solo che, invece di far viaggiare il timestamp, viaggia il valore dell'orologio logico. .. [#] L'emissione quasi immediata di *AM1P1* e *AM2P2* è logica: sono i riscontri della ricezione dei propri messaggi di update, quindi sono generati localmente al processo dal middleware di implementazione del sistema, non c'è impegno di rete. .. [#] Come nel caso del calcolo di bitcoin.