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.
Consiste di un insieme ρ di N processi pi, i=1, 2, …, N:
Un processo pi può eseguire le seguenti azioni:
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 →
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 →
Un orologio fisico di un computer (computer clock, meglio detto: timer) è un dispositivo tipicamente costituito da:
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).
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) 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.
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.
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).
È 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.
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 + ρ
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.
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:
I due problemi sono rispettivamente noti come:
- Sincronizzazione esterna:
– Sincronizzazione interna:
È 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.
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.
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).
È 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.
Il master:
L’accuratezza dell’algoritmo dipende dal round-trip time dei messaggi tra il master e gli slave. Per aumentarla, il master:
In questo modo si limita l’effetto dei clock con i quali il RTT è troppo variabile.
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.
È 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:
Il servizio NTP è fornito da una rete di server connessi a Internet, secondo una organizzazione logica gerarchica; si distinguono:
I server NTP possono sincronizzarsi secondo tre modalità:
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.
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.
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
La relazione tra eventi HB (happened-before, “è accaduto prima di”), indicata con il simbolo →, è definita dalle condizioni:
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’.
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).
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).
È 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.
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:
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).
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software
G. Coulouris et al.: Distributed Systems: Concepts and Design
(Cap. XI §1-4), IV ed., 2005.