Sincronização em Sistemas Distribuídos

1
Sincronização em Sistemas
Distribuídos
2
Roteiro
Sincronização através do clock
 Relógios Lógicos

– Solução de Lamport (1978, 1990)

Relógios Físicos
– Algoritmo de Cristian
– Algoritmo de Berkeley
3
Sincronização de Relógio

Ambigüidade de Tempo
Processo A envia msg1
msg1 = dobre o valor de x
Processo B envia a msg2
msg2 = adicione 100 a x
C
1
2
A
4
5
B
D
3
x tem valor 1000
Processo C executa msg1 e msg2
x = 2100
Processo D executa msg2, msg1
x = 2200
GRUPO I
GRUPO II
4
Sincronização de Relógio

Ambigüidade de Tempo
– Inexistente entre processos em Sistemas
Centralizados
» Informação direcionada pelo Kernel
» Se P1 pergunta pelo tempo antes de P2

TP1 <= TP2
– Solução “não trivial” em Sistemas Distribuídos
5
Sincronização de Relógio


Processo B questiona a hora a S no instante T0
Processo A questiona a hora a S no instante T0 + 1
– Tempo de B deveria ser <= ao tempo de A
A
S
– O request (requisição) de A chega primeiro a S
– Conclusão
» TA <= TB
B
6
Sincronização de Relógio

Exemplo de ambigüidade do Tempo Global
– Programa make do UNIX
– Conclusões
» São divididos em vários arquivos fonte.
» Alteração no código (fonte) só exige a recompilação no
arquivo específico, em vez de todo o programa. Como ?
» Examina arquivos fonte e objeto.
» Compara data e hora de alteração.
» Se o tempo do fonte é maior que o do objeto, cria um novo
objeto (deve ser recompilado).
7
Sincronização de Relógio

Exemplo de ambigüidade do Tempo Global
– Programa make do UNIX
» Se input.c tem tempo 1000 e input.obj tem tempo 900

cria um novo arquivo input.obj
» Se input.c tem tempo 1000 e input.obj tem tempo 1010



NÃO cria um novo arquivo input.obj
Não há necessidade de recompilação
Nesse caso, o executável não reflete as alterações feitas
8
Sincronização de Relógio

Exemplo de ambigüidade do Tempo Global
– Supondo um ambiente distribuído com a edição na máquina A e a
compilação na máquina B
» O que acontece se o relógio de B adiantar em função de A?
input.obj
criado
1000
1001
1002
1004
990
991
992
993
Máquina B
Máquina A
input.c
alterado
» O programa make não vai chamar o compilador p/ recompilar
o arquivo fonte. Mistura de arquivos objeto e fonte (velhos e
novos). Provavelmente, não vai funcionar a aplicação ...
9
Sincronização de Relógio

Exemplo de ambigüidade do Tempo Global
– Conclusões (ambiente distribuído)
» Pode não haver uma fonte única de informação de
tempo.
» Clocks mais lentos, outros mais rápidos.
» Efeitos “catastróficos” pelo fato de não termos
todos os clocks sincronizados.
» É possível sincronizar todos os clocks de um
sistema distribuído ?

Algoritmo de Lamport (mostrou em 1978)
10
Eventos e Relógios


A ordem de eventos que ocorrem em processos
distintos pode ser crítica em uma aplicação
distribuída (ex: make, protocolo de consistência
de réplicas).
Em um sistema com n computadores, cada um dos
n cristais (associado a dois registradores, um
contador e um de armazenamento) terá uma
freqüência própria, fazendo com que os n relógios
percam seu sincronismo gradualmente.
– Multicomputadores
11
Relógios lógicos

Princípios:
1. Somente processos que interagem precisam
sincronizar seus relógios.
2. Não é necessário que todos os processos
observem um único tempo absoluto; eles
somente precisam concordar com relação à
ordem em que os eventos ocorrem.
12
Solução de Lamport

Lamport
– Sincronização de Clock não necessita ser absoluta

Processos sem interação
– Não é necessário que seus clocks estejam sincronizados
– Perda de sincronização não interfere
– Não poderá causar nenhum problema

Tempo real X ordem dos eventos
– O que interessa (importa) aos processos ?
» A ordem na qual os eventos irão ocorrer ...
 Clock Lógico
13
Clock Lógico X Clock Físico

Clock Físico
– Clocks devem ser iguais (multicomputadores) e
não podem derivar num certo valor do tempo
real.
» Tempo Real
14
Solução de Lamport

Relação “happens-before”
– a  b é lida “a acontece antes de b”
– Todos os processos concordam que o evento a
ocorreu antes de b
» Se a e b são eventos num mesmo processo e “a
acontece antes de b”, então a  b é verdadeira
» Se a representa um SEND de P1 e b um RECV de
P2, sendo P1 e P2 processos distintos, então a  b é
verdadeira.
15
Solução de Lamport

Relação “happens-before”
– Transitividade
» a  b e b  c, então a  c

Se os eventos x e y ocorrem em processos
que não trocam mensagens (concorrentes)
– É falso que:
» x  y
e y  x
16
Eventos (exemplo)
Eventos ocorrendo em três processos:
p1
a
b
m1
p2
c
d
m2
Tempo
Físico
p3
e
f
a -» b, c -» d, e -» f, b -» c, d -» f
a -» f
Os processos "a" e "e" são concorrentes: a || e
17
Solução de Lamport

Se a  b, então C(a)  C(b)
– Clock de a é menor que o de b
» Clock como tempo

Clock sempre é incrementado, nunca
decrementado.
18
Solução de Lamport
Processo 1
Processo 2
0
Processo 3
0
0
8
10
12
16
20
18
24
24
32
40
30
40
50
36
48
42
56
70
64
80
54
72
90
60
80
100
6
48
A
D
B
C
30
60
Processos 1, 2 e 3
executam em máquinas
distintas com
diferenças de
velocidade de Clock.
Msg (a,b,c e d)
19
Solução de Lamport
Processo 1
Processo 2
0
Processo 3
0
0
8
10
12
16
20
18
24
24
32
40
30
40
50
36
48
42
61
70
69
80
70
77
90
76
85
100
6
48
A
D
B
C
30
60
20
Solução de Lamport

Requisitos para Tempo Global
– Entre dois eventos deve haver ao menos um
Clock Tick.
» Múltiplos eventos de SEND ou RECV sucessivos

Avançar o Clock
– Dois eventos não devem ocorrer no mesmo
tempo
» ID (identificação) do processo
21
Relógios físicos







BIH: Bureau Internacional de l’Heure
TAI: International Atomic Time
GMT: Greenwich Mean Time
UTC: Universal Coordinated Time
NIST: National Institute of Standard Time
WWV: estação de rádio de ondas curtas
GEOS: Geostationary Environment Operational
Satellite
22
Algoritmo de Cristian

Servidor de Tempo Passivo
– Receptor WWV (time server)
– Sincronização Externa (fonte externa)

Clientes questionam a hora do servidor
– Resposta imediata ...

Problemas
– Ajuste de Clock
» Clock (cliente) pode ser adiantado gradativamente
» Clock (cliente) nunca deve ser atrasado (pode causar sérios
problemas)
» Overhead do Kernel do Servidor
23
Algoritmo de Cristian

Resposta imediata
– Ao receber a mensagem resposta do time
server, o cliente adiciona o tempo médio de
envio de mensagens à hora recebida. Esse
tempo médio é calculado pelo próprio cliente
considerando as horas de envio e recebimento
das mensagens e ainda o tempo gasto pelo time
server para processar o pedido.
24
Algoritmo de Cristian
25
Algoritmo de Cristian
Máquina M
Timer Server
R?
T0
I
d
d
T1
d = ( T1 – T0 – I ) / 2
R
T=R+d
26
Algoritmo de Berkeley
A rede não dispõe de uma máquina com um
receptor WWV.
 A rede dispõe de um time server que faz
polling nas outras máquinas a fim de obter
a hora marcada por cada uma, fazer uma
média entre essas horas e divulgar essa
média para todas as máquinas.

27
Algoritmo de Berkeley

Servidor Ativo
– Sincronização Interna (sincronização entre
relógios)
» Relógios podem não estar sincronizados
externamente
– Questiona todas as máquinas pela hora local
– Ajuste pela média
» Avanço do relógio
» Atraso via mudança de ticks
28
Algoritmo de Berkeley
29
Algoritmo baseado na Média

Solução descentralizada
– Cada máquina transmite, via broadcast, sua
hora corrente
– Cada máquina coleta o envio de todas as
outras.
» Após receber todas as mensagens, computa nova
hora.
» Soluções:


Média.
Média com descarte de extremos.
30
Relógios físicos

NTC: Network Time Protocol
– Sub rede hierárquica de sincronização
– Servidores primários (WWV) e secundários