Tópicos em redes e
sistemas distribuídos
Carlos Oberdan Rolim
Ciência da Computação
Sistemas de Informação
Sincronização em Sistemas
Distribuídos
[C10,C13, T3]
Conteúdo
Relógios lógicos
Relógicos 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: 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.
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 parcial de eventos
» 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.)
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
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,
concatena a informação t=Cp a m, enviando (m,t).
ele
(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.
NTP: 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
Processo 3
aguardando
na fila pela
liberação do
recurso
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
Após algum tempo 1 responde a 3
OK e então este entra na Região
crítica pois já possuía OK do 2
anteriormente
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
Algoritmo de Bully
O algoritmo de Bully serve para eleger um líder
(processo coordenador) em algoritmos distribuídos
Processos são identificados por um identificador
numérico, único, fixo e atribuído antes do início da
eleição.
A topologia não é limitada a um anel e cada um dos
processos pode se comunicar com qualquer outro no
sistema.
Novamente a execução do algoritmo busca eleger o
processo de maior identificador e fazer com que todos
reconheçam o novo líder.
Algoritmos de eleição
Algoritmo Bully:
Se um dos processos identifica a perda de contato com o líder,
inicia uma nova eleição enviando a todos os outros uma
mensagem contendo seu identificador.
Todos os nós respondem ao processo que iniciou a eleição com
os seus próprios identificadores.
Se o processo que iniciou a eleição possui o maior identificador
entre todos os outros, proclama-se líder e avisa todos os outros.
Senão aguarda que o processo de maior identificador inicie uma
eleição e se torne líder.
Este algoritmo possui este nome justamente por seu
comportamento de bully. (Bullying é um termo em inglês utilizado
para descrever atos de violência física ou psicológica, intencionais e
repetidos)
O processo de maior identificador predomina sobre os
de menor número e mesmo que um destes ganhe uma
eleição, rapidamente toma o posto do eleito propondo
uma nova eleição.
Algoritmos de eleição (cont.)
Algoritmo de Anel:
O algoritmo em anel ou LCR, iniciais de Le Lann, Chang e
Roberts, serve para eleger um líder se os processos estiverem
dispostos em um anel.
Cada processo deve conhecer seu vizinho à direita e à esquerda
e deve ter um identificador numérico, único, fixo e atribuído
antes do início da eleição.
Originalmente este algoritmo visava a recuperação de um token
perdido em uma rede com topologia em forma de anel, elegendo
um nó da rede que servisse como ponto de partida para o novo
token.
Algoritmos de eleição (cont.)
Algoritmo de Anel:
Se um dos processos identifica a perda de contato com o líder,
inicia uma nova eleição enviando a todos os outros uma
mensagem contendo seu identificador.
Esse 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.