cap11 Tempo e Estados Globais

Prévia do material em texto

Tempo e Estados 
Globais
Sumário
‣ Relógios, eventos e estados de processos
‣ Sincronização de relógios físicos
‣ Relógios lógicos
Motivação
‣ Monitorar a ocorrência de eventos e o 
estado dos processos
‣ Desafios em relação ao tempo
‣ precisão
‣ alguns algoritmos distribuídos dependem da 
sincronização dos componentes do sistema
Problema
‣ Dados dois eventos, qual deles ocorreu 
primeiro? Ou eles ocorreram 
simultaneamente? 
‣ Limitação na capacidade de indicar, em 
diferentes componentes do sistema, o 
tempo de ocorrência de eventos com 
precisão suficiente
‣ ausência de uma noção global de tempo 
absoluta
Estado de um Processo
‣ Considere um sistema distribuído que 
envolve um conjunto de N processos: p1, 
p2, ... , pn 
‣ O estado si de um processo pi inclui os 
valores de seus atributos e dos recursos 
de seu ambiente operacional
Eventos
‣ Um evento é uma ocorrência de uma 
ação durante a execução de um 
processo:
‣ ação de comunicação
‣ ação de transformação de estado
‣ A seqüência de eventos de um processo 
é uma ordem total única denotada pela 
relação →i :
‣ e →i e’
‣ histórico(pi) = hi = <e1, e2 , ... , em>
Relógios
‣ Cada computador possui seu próprio 
relógio físico
‣ contagem de oscilações de um cristal
‣ clock ticks (interrupções geradas em 
intervalos regulares)
‣ Tempo físico real t no processo i
‣ relógio de hardware: Hi(t)
‣ relógio de software: Ci = αHi(t) + β
Resolução
‣ Resolução de um relógio é o período 
entre as atualizações do valor do relógio.
‣ Simultaneidade
‣ dois eventos são simultâneos se o tempo 
entre suas ocorrências é menor que a 
resolução do relógio
Distorção e Derivação
‣ Distorção (skew): a diferença instantânea 
entre as leituras de dois relógios
‣ Relógios baseados em cristal estão 
sujeitos à derivação de relógio (drift)
‣ suas leituras vão se divergir no futuro, pois 
contam o tempo em velocidades diferentes.
‣ ocorre em função da diferença no período de 
oscilação dos cristais (sujeitos a condições 
físicas) 
Taxa de Derivação
‣ A taxa de derivação (drift rate) é o 
deslocamento entre o relógio local e um 
relógio de referência (perfeito), por 
unidade de tempo
‣ Exemplo
‣ Um relógio baseado em um cristal de quartzo 
possui taxa de derivação de 10-6 segundos por 
segundo (uma diferença de 1 segundo a cada 
1.000.000 de segundos)
Relógios Atômicos
‣ Relógios de computadores podem ser 
sincronizados com fontes externas de 
tempo altamente precisas
‣ Relógios com osciladores atômicos (taxa de 
derivação de uma parte em 10-13)
‣ International Atomic Time - padrão para tempo 
real decorrido (1s = 9.192.631.770 períodos 
de transição entre duas camadas do estado 
fundamental do Césio-133)
Tempo Astronômico
‣ Segundos, anos e unidades correlatas 
têm suas raízes no tempo astronômico
‣ baseado nos períodos de rotação da Terra e 
de sua translação em torno do Sol
‣ sujeito a alterações decorrentes de 
fenômenos físicos (atritos das marés, 
correntes de convecção no interior do 
planeta, efeitos atmosféricos, etc.) 
UTC
‣ Tempo Universal Coordenado (UTC) é 
um padrão internacional para contagem 
de tempo.
‣ Baseado no tempo atômico (ocasionalmente 
adaptado de acordo com o tempo 
astronômico)
‣ Sinais UTC são sincronizados e 
transmitidos regularmente, de estações 
de rádio e satélites, por todo o planeta
‣ receptores próprios (GPS (1μs), rádio (1ms))
Sumário
‣ Relógios, eventos e estados de processos
‣ Sincronização de relógios físicos
‣ Relógios lógicos
Sincronização
‣ Uma alternativa para permitir a 
ordenação dos eventos em uma sistema 
distribuído é a sincronização dos relógios 
dos processos envolvidos no sistema:
‣ Sincronização externa
‣ Sincronização interna
Sincronização Externa
‣ Sincronizar os relógios Ci dos processos 
em um sistema distribuído com uma 
fonte externa de referência.
‣ limite de sincronização D > 0 e fonte S de 
tempo UTC: 
|S(t) - Ci(t)| < D, para todo i 
Sincronização Interna
‣ Os relógios Ci são sincronizados, entre 
si, com um grau de precisão conhecido
‣ Limite de sincronização D > 0: 
|Ci(t) - Cj(t)| < D, para todo par i,j
Sincronização
‣ Relógios sincronizados internamente não 
são necessariamente sincronizados 
externamente
‣ eles podem se desviar coletivamente de uma 
referência externa
‣ Relógios sincronizados externamente, com 
limite D, estão também sincronizados 
internamente, com limite 2D
Relógio Correto
‣ Condições de correção
‣ limite na taxa de derivação
‣ monotonicidade: t’> t ⇒ C(t’) > C(t)
‣ Relógio falho
‣ falha por colapso (deixar de oscilar)
‣ falha arbitrária (ex. aumento da taxa de 
derivação, bug do milênio, etc.) 
Estratégias de Sincronização
‣ Sincronização em um sistema síncrono
‣ Método de Cristian
‣ Algoritmo de Berkeley
‣ O protocolo NTP
Sistema Síncrono
‣ Um processo envia o tempo t de seu 
relógio para outro processo em uma 
mensagem m.
‣ Seja u a incerteza no tempo de 
transmissão de uma mensagem:
 u = Tmax - Tmin
‣ Processo destino configura seu relógio 
como t+((Tmax + Tmin)/2)
Método de Cristian
m!r!
m!t!
p! Time server,S!
Fonte UTC
Servidor de Tempo
‣ Processo p configura seu relógio como t+(RTT/2)
Algoritmo de Berkeley
‣ Sincronização interna para um conjunto 
de computadores
‣ um computador é selecionado como mestre 
(coordenador) e os demais são denominados 
escravos
‣ O mestre recebe os valores dos relógios 
dos escravos e calcula a média. Envia 
para cada escravo seu desvio em relação 
à média.
Protocolo NTP
‣ NTP - Network Time Protocol
‣ Define a arquitetura de um serviço para 
distribuição de informações de tempo 
pela Internet
Princípios de Projeto
‣ Fornecer um serviço para sincronizar 
hosts na Internet com o UTC
‣ técnicas estatísticas para filtragem de dados
‣ Alto grau de confiabilidade e 
escalabilidade
‣ servidores e caminhos redundantes
‣ Sincronizações freqüentes
‣ Técnicas de autenticação
Sub-Rede de Sincronização
Fonte UTC
Servidores Primários (stratum 1)
Servidores Secundários (stratum 2)
.
.
.
Formas de Sincronização
‣ Multicast 
‣ informação de tempo enviada periodicamente 
por multicast na redel local
‣ Chamada de procedimento
‣ servidores respondem mensagens de requisição 
com sua indicação de tempo
‣ Modo simétrico
‣ servidores (em níveis hierárquicos altos) trocam 
mensagens com informações de temporização
Pr
ec
is
ão
Operação
‣ Utiliza protocolo de transporte UDP
‣ Mensagens contém os instantes de envio 
e recepção das mensagens recentes
T!i!
T!i-1!T!i!-2!
T!i!-!3!
Server B!
Server A!
Time!
m! m'!
Time!
‣ Para cada par de mensagens, os 
servidores NTP calculam
‣ atraso (d): tempo de transmissão total das 
duas mensagens
d = Ti-2-Ti-3 + Ti-Ti-1
‣ compensação (o): estimativa da compensação 
real entre os dois relógios
o = ((Ti-2-Ti-3) - (Ti-Ti-1)) /2
‣ Aplicam um algoritmo de filtragem de 
dados em sucessivos pares < o, d> para 
determinar a qualidade das estimativas
‣ Um servidor NTP interage com vários 
pares para determinar as estimativas
‣ Existe um algoritmo próprio para 
seleção de pares
‣ descarte de valores não confiáveis
‣ são favorecidos os servidores mais altos na 
hierarquia e aqueles com menor dispersão de 
sincronização
‣ A freqüência de atualização do relógio de 
um servidor é definida de acordo com 
sua taxa de derivação.
Sumário
‣ Relógios, eventos e estados de processos
‣ Sincronização de relógios físicos
‣ Relógios lógicos
Tempo Lógico
‣ Lamport[1978]: como não podemos 
sincronizar perfeitamente os relógios em 
um sistema distribuído, não podemos 
usar o tempo físico para determinar a 
ordem de qualquer par de eventos 
arbitrários.
‣ Proposta de uma estratégia de 
ordenação análoga à causalidade física.
Tempo Lógico
‣ Esquema de ordenação baseado em 
princípios simples e intuitivos:
‣ Se dois eventos ocorreram em um processo 
pi, então eles ocorreram na ordem em que pi 
os observou (→i)
‣ Quando uma mensagem é transmitida de um 
processo para outro, o evento de envio 
ocorreu antes do evento de recepção.
Ordenação Parcial
‣ Relação “antes do acontecido”, 
denotada por →:
‣ Se e →i e’, então e → e’
‣ para qualquer mensagem m, 
send(m) → receive (m)
‣ Se e → e’ e e’ → e’’, 
então e → e”
p1
p2
p3
a b
c d
e f
m1
m2
Physical
time
a → b
b → c
a → f
a ↛ e
a || e (são concorrentes) 
Relógio Lógico
‣ Mecanismo por meio do qual a 
ordenação “antes do acontecido” é 
capturada numericamente.
‣ O relógio lógico é um contador cujo 
valor não depende de um relógio físico
‣ contagem aumenta monotonicamente
‣ cada processo pi mantém seu próprio relógio 
lógico Li
‣ Li(e) é a indicação de tempo do evento e em pi
Regras de Relógios Lógicos
‣ Li ← 0, para todo i
‣ Quando da ocorrência de um evento, Li é 
incrementado;
‣ Quando um processo pi envia uma 
mensagem m, o valor t = Li é anexado a m.
‣ Quando um processo pj recebe [m, t], ele 
faz Lj ← max(Lj, t) e incrementa Lj antes 
de indicar o tempo do evento receive.
a b
c d
e f
m1
m2
21
3 4
51
p1
p2
p3
Physical 
time
e → e’ ⇒ L(e) < L(e’)
L(b) > L(e), mas b || e
Ordenação Total
‣ Seja e um evento em pi com indicação de 
tempo Ti e e’ um evento em pj com 
indicação de tempo Tj. Define-se as 
indicações de tempo globais como
‣ (Ti, i) e (Tj, j), respectivamente
‣ (Ti, i) < (Tj, j) ⇔ Ti < Tj ou Ti = Tj e i < j
Relógios Vetoriais
‣ Um relógio vetorial para um sistema com 
N processos é um vetor de N inteiros.
‣ Regras:
‣ Vi[j] ← 0, para todo i e j;
‣ pi incrementa Vi[i], antes de ocorrer um evento
‣ pi inclui t = Vi[i] em cada mensagem que envia
‣ quando pi recebe uma mensagem, 
faz Vi[j] ← max(Vi[j], t[j]), para todo j
Relógios Vetoriais
‣ V = V’ ⇔ V[i] = V’[i], para todo i
‣ V ≤ V’ ⇔ V[i] ≤ V’[i], para todo i
‣ V < V’ ⇔ V ≤ V e V ≠ V’, para todo i
a b
c d
e f
m1
m2
(2,0,0)(1,0,0)
(2,1,0) (2,2,0)
(2,2,2)(0,0,1)
p1
p2
p3
Physical 
time
V(a) < V(f) , a → f
c || e
e → e’ ⇒ V(e) < V(e’)
V(e) < V(e’) ⇒ e → e’