Sincronização em
Sistemas
Distribuídos
Sistemas distribuídos
Prof. Diovani Milhorim
Conteúdo
Relógios lógicos
 Relógios físicos
 Exclusão mútua
 Algoritmos de eleição

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 terá uma frequência própria,
fazendo com que os n relógios percam seu
sincronismo gradualmente.
Relógios lógicos

Princípios:
1.
Somente processos que interagem precisam
sincronizar seus relógios.
» Ordenação parcial de eventos
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.
» Ordenação causal potencial
Relógios lógicos (cont.)

Relação acontece-antes ( -» ):
1. Sejam x e y eventos num mesmo processo tal
que x ocorre antes de y. Então x -» y é
verdadeiro.
2. Seja x o evento de uma mensagem a ser enviada
por um processo, e y o evento dessa mensagem
ser recebida por outro processo. Então x -» y é
verdadeiro.
3. Sejam x, y e z eventos tal que x -» y e y -» z.
Então x -» z é verdadeiro.
Relógios lógicos (cont.)
Ev ent os oc orrendo em t rês proc es s os :
p1
a
b
m1
p2
c
d
m2
T empo
F í sico
p3
e
f
a -» b, c -» d, e -» f , b -» c , d -» f
a -» f
Os proc es s os "a" e "e" s ão c onc orrent
Relógios lógicos (cont.)

Implementação: Cada processo p mantém seu próprio
relógio lógico (um contador, por software), Cp, usado
para fazer timestamp de eventos. Cp(x) denota o
timestamp do evento x no processo p, e C(x) denota o
timestamp do evento x em qualquer processo.
LC1: Cp é incrementado antes de cada evento em p.
LC2: (a) Quando um processo p envia uma mensagem m,
ele
concatena a informação t=Cp a m, enviando (m,t).
(b) Quando um processo q recebe a mensagem (m,t), ele
computa Cq := max(Cq, t) e aplica LC1 antes de fazer
timestamp do evento de recebimento da mensagem.
Exemplo de aplicação do
algoritmo de relógios lógicos
P1
0
6
12
18
24
30
36
42
48
54
60
A
D
P2
0
8
16
24
32
40
48
56
64
72
80
B
C
P3
0
10
20
30
40
50
60
70
80
90
100
Exemplo de aplicação do
algoritmo de relógios lógicos
P1
0
6
12
18
24
30
36
42
48
70
76
A,0
D,69
P2
0
8
16
24
32
40
48
61
69
77
85
B,24
C,60
P3
0
10
20
30
40
50
60
70
80
90
100
Relógios lógicos (cont.)

Ordenação total de eventos: dois eventos nunca
ocorrem exatamente no mesmo instante de tempo.
1. Se x ocorre antes de y no mesmo processo,
então C(x) é menor que C(y).
2. Se x e y correspondem ao envio e ao
recebimento de uma mensagem, então C(x) é
menor que C(y).
3. Para todos os eventos x e y, C(x) é diferente de
C(y).
Implementação: concatenar o número do processo ao timestamp.
Relógios físicos







GMT: Greenwich Mean Time
BIH: Bureau Internacional de l’Heure
TAI: International Atomic 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
Relógios físicos (cont.)

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.

NTC: Network Time Protocol
 Sub-rede
hierárquica de sincronização
 Servidores primários (WWV) e secundários
Relógios físicos (cont.)

Algoritmo de Cristian:
 A rede
dispõe de um time server (receptor WWV)
 Uma máquina cliente envia uma mensagem pedindo
a hora certa ao time server
 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.
Algoritmo de Cristian
Máquina M
Timer Server
R?
T0
I
d
d
T1
d = ( T1 – T0 – I ) / 2
R
T=R+d
Exclusão mútua

Controle de acesso a regiões críticas

Algoritmo centralizado:
 Um
processo é eleito o coordenador
 Os processos concorrentes devem requisitar
permissão de acesso ao coordenador
 Um processo que termina de fazer acesso a uma
região crítica deve comunicar a liberação da
região ao coordenador
 Processos que tentam entrar em uma região
crítica ocupada devem aguardar em uma fila
controlada pelo coordenador
Alg. Centralizado - Exemplo
Alg. Centralizado - Exemplo
Alg. Centralizado - Exemplo
Exclusão mútua (cont.)

Algoritmo distribuído:



Baseado em ordenação total de eventos e comunicação
confiável em grupo (multicast ou broadcast).
Um processo que deseja entrar em uma região crítica
constrói uma mensagem com o nome da região, o número
do processo e a hora, e a envia a todos os demais
processos concorrentes.
Um processo que recebe a mensagem:
 Caso não esteja na região crítica e não intencione entrar
nela, retorna OK.
 Caso já esteja na região crítica, não responde e enfileira
a requisição.
 Caso também intencione entrar na região crítica,
determina o processo que tentou primeiro (comparando
timestamps) e responde OK ou enfileira a requisição,
apropriadamente.
Alg. Distribuído - Exemplo
Alg. Distribuído - Exemplo
Alg. Distribuído - Exemplo
Exclusão mútua (cont.)

Algoritmo de Token Ring:




Os processos são conectados por um anel e numerados
sequencialmente a partir de 0.
Na iniciação do anel, uma token é dada ao processo 0.
A token é passada do processo k para o processo k+1.
Ao receber a token, um processo pode retê-la ou passá-la
imediatamente para o próximo processo, dependendo se
deseja ou não, respectivamente, entrar na região crítica.
Enquanto o processo estiver na região crítica, a token fica
retida, e somente ao sair da região crítica é repassada
adiante.
Alg. Token Ring - Exemplo
Algoritmos de eleição


Eleição de um processo coordenador em
algoritmos distribuídos
Algoritmo Bully:
1. Um processo P envia uma mensagem
ELECTION para todos os processos de maior
número.
2. Se nenhum processo responde, P vence a
eleição e se torna o coordenador.
3. Se um dos processos responde este inicia sua
participação na eleição a partir do passo 1. O
trabalho de P está feito.
Algoritmos de eleição (cont.)

Algoritmo de Anel:
 Um
processo constrói uma mensagem
ELECTION contendo seu número e envia ao seu
sucessor. Se o sucessor estiver parado, a
mensagem é enviado ao sucessor do sucessor.
 O processo que recebe a mensagem insere seu
próprio número na mensagem e passa para o seu
sucessor.
 Quando a mensagem retorna ao processo que
originou a eleição, este descobre quem é novo
coordenador (o processo com número maior) e,
em seguida, envia uma mensagem
COORDINATOR comunicando o fato.