Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 3.Tempo e sincronizzazione nei Sistemi Distribuiti


Sommario

  • Tempo
  • clock, skew, drift, UTC
  • Sincronizzazione degli orologi
    • esterna (algoritmo di Cristian)
    • interna (algoritmo di Berkeley)
    • con server distribuiti (NTP)
  • Relazione happened-before
  • Tempo logico e orologi logici di Lamport

Il tempo nei sistemi distribuiti

In un sistema distribuito, ogni nodo è dotato di un proprio orologio, ed è possibile che ad un evento x, che accade “dopo” un altro evento y, sia associato un istante “antecedente” quello di y.
Ciò comporta problemi in molte applicazioni.
Es.: compilazione con make, utility basata sulla data dei file.


Modello di sistema distribuito

Consiste di un insieme ρ di N processi pi, i=1, 2, …, N:

  • ciascun processo è in esecuzione su un diverso processore;
  • i processori non condividono memoria;
  • ciascun processo pi ha uno stato si, che trasforma nella sua esecuzione;
  • lo stato di un processo include il valore di tutte le sue variabili, nonché di tutti gli oggetti locali (es.: archivi);
  • ciascun processore è dotato di un proprio orologio fisico (clock);
  • non esiste un orologio fisico globale, ma esiste la nozione di un tempo reale “effettivo” in un sistema di riferimento assoluto.

Un processo pi può eseguire le seguenti azioni:

  • send o receive di un messaggio;
  • variazioni del suo stato si.

Eventi e storia di un processo

L’occorrenza di una singola azione in pi è un evento e.
L’insieme degli eventi di un processo pi può essere ordinato totalmente in base alla relazione di precedenza temporale

  • e → e’ se e solo se e si è verificato prima e’ di in pi.

L’ordinamento è ben definito (anche in caso di multithreading) in quanto ciascun processo è in esecuzione su un processore dedicato.
La storia di un processo pi è la successione di eventi che ha luogo in pi, ordinata in base alla relazione →

  • storia(pi) = hi = <ei0, ei1, ei2,…>

Orologi fisici

Un orologio fisico di un computer (computer clock, meglio detto: timer) è un dispositivo tipicamente costituito da:

  • un cristallo di quarzo, che oscilla a una frequenza nota;
  • un registro contatore;
  • un registro di inizializzazione (holding register);
  • un registro di memorizzazione.

Ciascuna oscillazione del cristallo decrementa il contatore di una unità. Quando il contatore raggiunge lo zero, il contatore viene re-impostato al valore indicato dal registro di inizializzazione.
Il clock può dunque essere programmato per generare interruzioni periodiche (clock tick), p.es. 60 volte al secondo. Ad ogni interruzione, il valore del registro di memorizzazione viene aggiornato.

Il risultato è il valore di un clock hardware Hi(t).

Orologi fisici (segue)

Il sistema operativo legge dal registro il valore Hi(t) del clock hardware, lo moltiplica per un fattore di scala ed aggiunge un offset, fornendo il valore di un clock software Ci(t):

  • Ci(t) = α Hi(t)+ β.

Ci(t) rappresenta una misura approssimata del tempo “effettivo” t per il processo pi.
A due eventi successivi possono essere associati valori distinti di Ci(t) solo se la risoluzione del clock (periodo tra gli aggiornamenti del clock) è minore dell’intervallo temporale tra i due eventi.

Attributi di un clock – definizioni

Tempo effettivo o reale t: il tempo “vero” in ciascun istante, in un sistema di riferimento assoluto nominale, indicato da un ideale orologio perfetto.
Clock offset: differenza tra la lettura istantanea del clock locale rispetto a t(o, in generale, rispetto a un altro clock);
Clock frequency: il tasso con cui il clock locale progredisce
(derivata prima rispetto a t);
Clock skew: differenza tra le frequenze del clock locale e reale;
Clock drift: variazione nel tempo della frequenza del clock locale
(derivata seconda del clock locale rispetto a t);
Clock adjustment: variazione subitanea degli attributi di un clock locale, per effetto di un’azione di sistema o d’utente.
In letteratura la differenza tra le letture di due orologi viene spesso indicata con il termine clock skew, anziché offset.

Tempo Atomico Internazionale

I secondi misurati nel tempo solare NON hanno durata costante.
Con l’invenzione dell’orologio atomico nel 1948, il tempo non è più misurato su base astronomica, ma su base fisica, contando le transizioni dell’atomo di cesio 133.
Il secondo è definito come il tempo nel quale l’atomo di cesio 133 effettua esattamente 9.192.631.700 transizioni (valore scelto per rendere il secondo pari alla durata media di un secondo misurato su base solare nel 1958).
Ci sono circa 50 orologi atomici nel mondo, che comunicano la propria ora periodicamente al Bureau International de l’Heure (BIH) a Parigi.
Il BIH calcola il valore medio, che rappresenta il Tempo Atomico Internazionale (TAI).
I secondi TAI hanno durata costante.
Attualmente, 86.400 secondi TAI sono circa 3 ms meno della durata media del giorno solare (che si allunga nel tempo).

Universal Coordinated Time (UTC)

È il sistema basato su orologi atomici, con la correzione di leap seconds, introdotti appena la differenza tra il tempo atomico e quello solare raggiunge la soglia di 800 ms.
È alla base dei moderni sistemi civili.
Ha sostituito il vecchio standard del Greenwich Mean Time (GMT), basato sul tempo astronomico.
Ad oggi, sono stati introdotti circa 50 leap seconds nel tempo UTC.

Relazione tra clock locale e UTC

Idealmente:
Ci(t) = t, per ogni i e per ogni t,
quindi dC/dt = 1.

Nella realtà, si ha dC/dt > 1
(dC/dt < 1) quando il clock procede più rapidamente (lentamente) del tempo effettivo.

In pratica, molti costruttori specificano per il clock una costante ρ  tale che:
1 - ρ ≤ dC/dt ≤ 1 + ρ


Relazione tra clock locale e UTC

Se due clock divergono dal tempo UTC in direzioni opposte, dopo un intervallo Δt dalla sincronizzazione possono differire al più di 2ρ Δt.

Se si vuole che due orologi non differiscano di un valore maggiore di ρ, essi vanno sincronizzati (via software) ogni ρ/2ρ  secondi.

Sincronizzazione dei clock

Per molte applicazioni, l’ora “effettiva” è fondamentale. Per tali sistemi sono spesso necessari orologi fisici esterni.
Per ragioni di efficienza e affidabilità, poi, gli orologi sono tipicamente ridondati.
Si pongono dunque due tipi di problemi:

  • come sincronizzare un orologio locale con un orologio esterno?
  • come sincronizzare più orologi tra loro?

I due problemi sono rispettivamente noti come:
- Sincronizzazione esterna:

  • algoritmo di Cristian (1989).

– Sincronizzazione interna:

  • algoritmo di Berkeley (Gusella e Zatti, 1989).

Algoritmo di Cristian

È un algoritmo di sincronizzazione esterna, che si basa sull’utilizzo di un time server passivo, dotato di un dispositivo che riceve il segnale di una sorgente UTC.
Su richiesta, un processo server invia un messaggio contenente l’ora t, misurata col proprio orologio basato su UTC.


Algoritmo di Cristian

Il processo cliente p misura il round-trip-time TRTT come intervallo temporale tra gli istanti Ti e Ti+1 (misurati con lo stesso clock locale al client). L’accuratezza della misura dipende dal clock drift. Tipicamente si può assumere che p possa poi aggiornare il clock locale al valore t+TRTT/2.


Algoritmo di Cristian

Cristian definisce il suo algoritmo probabilistico: si raggiunge la sincronizzazione solo se il round-trip-time (RTT) dei messaggi è sufficientemente piccolo rispetto all’accuratezza richiesta.
Es.: su una rete LAN, il RTT generalmente non supera i 10 ms.
Un clock con un drift rate di 10-6 secondi/secondo varia di non più di 10-5 millisecondi.

Detto min il tempo minimo di trasmissione dei messaggi, l’ora dell’orologio del server all’istante T1 è compresa in [t+min, t+TRTT-min], intervallo ampio TRTT-2min. L’accuratezza è quindi ±(TRTT/2-min).

Algoritmo di Berkeley

È un algoritmo di sincronizzazione interna ideato principalmente per reti intranet.
Si basa sull’utilizzo di un time server attivo.
Un nodo viene selezionato come master.
Gli altri nodi con cui deve essere effettuata la sincronizzazione fanno da slave.

Algoritmo di Berkeley

Il master:

  • effettua periodicamente il polling dei nodi slave;
  • calcola una stima dell’ora locale di ciascuno slave, in base al round-trip time (analogamente all’algoritmo di Cristian);
  • calcola l’ora media (inclusa la propria);
  • comunica ad ogni slave di quanto variare il clock locale.

L’accuratezza dell’algoritmo dipende dal round-trip time dei messaggi tra il master e gli slave. Per aumentarla, il master:

  • stima un round-trip time massimo nominale;
  • elimina dal calcolo della media le letture dei clock associate a valori del round-trip time maggiori del massimo.

In questo modo si limita l’effetto dei clock con i quali il RTT è troppo variabile.

Algoritmo di Berkeley

Per aumentare ulteriormente la precisione, l’algoritmo prevede di non considerare le letture di eventuali faulty clocks.
A tale scopo, il master considera nel calcolo della media solo il sottoinsieme dei clock locali che non differiscono tra essi più di un valore prestabilito.
Si dice che il master effettua una media tollerante ai guasti (fault tolerant average).
Nel caso in cui il master si guasti, è prevista l’elezione di un nuovo master.

Network Time Protocol

È un protocollo per un time service per nodi di rete Internet.
L’obiettivo di NTP è di offrire ai nodi Internet un servizio di sincronizzazione con l’ora UTC.
NTP si propone di offrire tale servizio in maniera:

  • affidabile, anche in caso di lunghe perdite di connettività;
  • scalabile, adatto all’elevato numero di client e server su Internet;
  • sicura, mediante meccanismi di protezione da interferenze accidentali o maliziose con il time service.

Il servizio NTP è fornito da una rete di server connessi a Internet, secondo una organizzazione logica gerarchica; si distinguono:

  • server primari, direttamente connessi a una sorgente UTC;
  • server secondari, sincronizzati direttamente con server primari.

Network Time Protocol

I server NTP possono sincronizzarsi secondo tre modalità:

  • multicast mode,
  • procedure call mode,
  • symmetric mode.

Tutte le modalità usano messaggi UDP.
Il multicast mode è previsto per reti LAN. Il server effettua periodicamente il multicast dell’ora ai nodi sulla LAN. I nodi regolano la propria ora su quella del server.

Il procedure call mode è analogo all’algoritmo di Cristian: il server accetta richieste e risponde con la lettura corrente del proprio clock.
Questa modalità è usata p.es. dai file server su una LAN o su LAN adiacenti.

Network Time Protocol

Il symmetric mode è usato dai livelli più alti della gerarchia, per raggiungere maggiore precisione.
In procedure call mode e symmetric mode, i server si scambiano coppie di messaggi, che contengono l’ora locale dei due eventi-messaggio più recenti, oltre a quello corrente.


Network Time Protocol

o: offset “vero” del clock di B rispetto a quello di A.
t, t’: tempi di trasmissione effettivi di m, m’.
Ti-2 = Ti-3 + t + o
Ti = Ti-1 + t’ – o
delay di = t + t’ = Ti-2 – Ti-3 + Ti – Ti-1
o = oi + (t’ –t)/2, ove: oi = (Ti-2 – Ti-3+ Ti-1 – Ti)/2 stima dell’offset
oi – di/2 <= o <= oi + di/2 misura dell’accuratezza della stima oi


Relazione happened-before

La relazione tra eventi HB (happened-before, “è accaduto prima di”), indicata con il simbolo →, è definita dalle condizioni:

  • HB1: Se esiste un processo pi tale che e→i e’ (cioè pi osserva che e accade prima di e’), allora e → e’
  • HB2: ν  messaggio m: send(m) receive(m)
  • HB3: Se e → e’ e e’ → e’‘, allora e→ e’‘.

La relazione HB definisce un ordinamento parziale degli eventi in un sistema distribuito.
L’interpretazione è che se e → e’, allora c’è un nesso di potenziale causalità tra gli eventi e → e’.

Eventi in un sistema distribuito


Orologi logici di Lamport

Lamport ha ideato un semplice meccanismo (logical clocks) con cui esprimere numericamente la relazione HB tra eventi in un sistema distribuito.

Un orologio logico di Lamport (LC, o LLC) è un contatore software crescente monotonicamente; i suoi valori (interi) non sono necessariamente in relazione con quelli di un orologio fisico.
Un LC viene tipicamente incrementato di 1, ma si può scegliere qualsiasi valore intero.

Ogni processo ha il suo LC, che usa per marcare temporalmente gli eventi: Li(e) è la marcatura di e da parte del processo pi che lo osserva (Lamport timestamp).

Orologi logici di Lamport

Ogni processo aggiorna il proprio LC, e lo invia assieme ai messaggi che trasmette, in base alle seguenti regole:

LC1:

Li è incrementato prima di ogni evento osservato da pi
Li := Li + 1

LC2:

(a) Quando pi invia un messaggio m, inserisce in m il valore t = Li
(B) Quando pj riceve (m,t), calcola:

Lj := max(Lj, t)

e applica LC1 prima di marcare l’evento receive(m).

Marcatura temporale degli eventi con orologi logici

Esempio

Esempio


Proprietà degli orologi logici

È facile vedere, per induzione, che:
e → e’ e → e’L(e) < L(e’)

NON è vero il contrario:
L(e) <L(e’) →e → e’
Non possiamo quindi inferire l’ordine relativo di due eventi conoscendo le loro marche temporali.

Orologi logici ed eventi concorrenti


Orologi vettore

Un orologio vettore (VC) per un sistema di N processi è un array di N interi. Ogni processo detiene un proprio orologio vettore Vi, e aggiorna il proprio VC, e lo invia assieme ai messaggi che trasmette, in base alle seguenti regole:

  • VC1: Inizialmente, Vi [j] = 0, i, j =1, 2, …, N
  • VC2: Vi [i] è incrementato prima di ogni evento osservato da pi: Vi [i]:= Vi[i] + 1
  • VC3: Quando pi invia un messaggio m, inserisce in m il vettore t = Vi
  • VC4: Quando pi riceve (m,t), calcola: Vi[j] := max(Vi[j], t[j]) j=1, 2, …, N

Orologi vettore

Vi [i] rappresenta il numero di eventi che pi ha marcato.
Vi [j] (j≠i) rappresenta il numero di eventi osservati da pj e dai quali pi è causalmente potenzialmente affetto (pj potrebbe aver marcato più eventi, ma di questi non è pervenuta informazione a pi).

Marcatura degli eventi con orologi-vettore

Esempio

Esempio


I materiali di supporto della lezione

G. Coulouris et al.: Distributed Systems: Concepts and Design

(Cap. XI §1-4), IV ed., 2005.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion