Sistemas Distribuídos
Professora: Ana Paula Couto
DCC 064
Sincronização - Relógios
Lógicos
Capítulo 6
Agenda
•
Relógios Lógicos
–
–
Relógios de Lamport
Relógios Vetoriais
Algumas definições...
Um sistema distribuído pode ser visto como uma
coleção P de N processos pi, i = 1,2,… N
 Cada processo pi possui um estado consistente si
 Processos se comunicam através de mensagens
 Ações de um processo: enviar e receber mensagens,
mudar o próprio status
 Evento: ocorrência de uma ação associada ao
processo
 Eventos dentro de um processo pi podem ser
totalmente ordenados pela relação “acontece antes”
(“happened before”) → , ou seja, a → b, se e somente
se a ocorre antes de b em pi

Relógios Lógicos
(Lamport,1978)
Ao invés da sincronização de relógios, ordenação
dos eventos:
1) Se dois eventos ocorrem no mesmo processo,
então eles ocorrem na ordem observada pelo
processo pi
2) Quando uma mensagem m é trocada entre dois
processos, e a é o evento de envio e b o de
recebimento, então a → b
3) Relação “acontece antes” é transitiva
Relógios Lógicos
(Lamport,1978)(I)
a → b ( p1) c →d (p2)
b
→ c dado m1
d → f dado m2
Nem todos os eventos podem ser relacionados através da
relação “acontece antes” →
Consideremos a e e (processos diferentes, sem a existência de cadeias de
mensagens entre os processos)
Não estão relacionados através da relação → ; são definidos como processos
concorrentes; a || e
p1
a
b
m1
p2
c
p3
d
m2
Physical
time
Relógios Lógicos
(Lamport,1978) (II)
Um relógio lógico é um contador monotonicamente
crescente. NÃO precisa estar relacionado com o relógio
físico.
COMO FUNCIONA
Cada processo pi tem o seu relógico lógico, Ci que pode ser usado para aplicar
timestamps lógicos aos eventos
1) Ci é incrementado de 1 antes de cada evento no processo pi
2) Quando um processo pi envia mensagem m, o tempo t = Ci é anexado a
mensagem
3) Quando pi recebe (m,t), o relógio é atualizado para Ci:= max(Cj, t) antes
de aplicar 1)
Relógios Lógicos
(Lamport,1978) (III)
Em cada um dos processos p1, p2, p3 o relógio lógico é inicializado com
zero
Os valores dos relógios lógicos são aqueles imediatamente após o
evento, por exemplo, 1 para a, 2 para b.
Juntamente com m1, o valor 2 é enviado e o relógio em p2, após o
evento c, recebe o max(0,2)+1 = 3
a → b implica em C(a)<C (b ) MAS C(a)<C (b ) NÃO implica em a → b
p1
1
2
a
b
p2
p3
1
m1
C(b) > C(e) mas b || e
3
4
c
d
Physical
time
m2
5
Relógios Lógicos (Lamport,1978)
(IV)
Relógios Vetoriais
(Mattern, Figdge,1988) (I)
• Relógios vetoriais - implementados para evitar a limitação
dos relógios de Lamport: C(a) < C(b) não implica a “acontece
antes” de b
• Vetores com marcas de tempo são usados para os eventos
locais em cada processo
• Seja VCi [I] o número de eventos ocorridos em pi até o
instante de tempo em questão
•Seja VCi [j], o número de eventos que ocorreram em pj ,
portanto pi sabe quantos eventos ocorreram em pj
Relógios Vetoriais
(Mattern, Figdge,1988) (II)
Como Funciona
Vetor de relógios VCi no processo pi é um vetor de N
inteiros
1) Inicialmente CVi[j] = 0 for i, j = 1, 2, …N
2)antes de cada evento, pi executa CVi[i] := CVi[i] +1
3) pi envia t = CVi em cada mensagem transmitida
4) quando pi recebe (m,t), o processo ajusta CVi[j] :=
max(CVi[j] , t[j]) j = 1, 2, …N (antes do próximo evento
adiciona 1 ao seu próprio contador de eventos)
Relógios Vetoriais
(Mattern,Figdge,1988) (III)
p1: a(1,0,0); b (2,0,0) envia (2,0,0) juntamente com a mensagem m1
Em p2, no recebimento de m1, o vetor de relógios é modificado para max
((0,0,0), (2,0,0)) = (2, 0, 0) adicionando 1 ao seu próprio relógio = (2,1,0)
Neste caso, o evento c 'sabe' que ocorreram 2 eventos no processo p1
antes da ocorrência do evento c em p2
=,<=, max: devem ser realizadas entre pares de elementos
(1,0,0)
p1
(2,0,0)
a
b
(2,1,0)
p2
p3
m1
c
(0,0,1)
e
(2,2,0)
d
Physical
time
m2
(2,2,2)
f
Algumas considerações...
Algoritmos de Cristian e Berkeley sincroniza relógios
físicos, apesar da defasagem entre relógios e retardos
das mensagens
 Para ordenar eventos em computadores diferentes,
sincronização dos relógios nem sempre pode ser feito
 A relação “acontece antes” resulta em uma ordenação
parcial dos eventos
 Relógios de Lamport são contadores que mudam de
acordo com o relacionamento de “acontece antes”
entre os eventos
 Relógios vetoriais são uma melhora nos relógios de
Lamport, onde dois eventos são ordenados pela
relação “acontece antes” ou são concorrentes através
da comparação dos vetores com marcas de tempo
