Coordenação e Sincronização em
Sistemas Distribuídos
[C10,C13, T3]
Conteúdo
•
•
•
•
Exclusão mútua
Relógios lógicos
Relógicos físicos
Algoritmos de eleição
Coordenação Distribuída
Exclusão mútua distribuída: Um conjunto de processos
compartilham um
recurso ou um conjunto de recursos administrados por um
servidor.
Eleição distribuída: Dentre um conjunto de processos, é
necessário escolher
um deles para executar uma regra específica, geralmente
privilegiada e com
fins de coordenação, durante um certo tempo.
Detecção de propriedades: terminação, deadlock etc.
Exclusão mútua distribuída
Processos distribuídos requerem acesso às suas regiões críticas.
No caso distribuído, não há variáveis compartilhadas nem
facilidades disponibilizadas por um kernel local único que
possam ser usados na solução deste problema.
Algoritmos:
• algoritmo centralizado;
• algoritmo em anel (token-ring);
• algoritmo distribuído (Ricart & Agrawala).
Exclusão mútua distribuída
Servidor/
Coordenador
Algoritmo centralizado
X1
4
send(P1, permissão A)
P1
Entra RC
Fila de
requisições RecursoStatus
free busy
A
do recurso
free
B
A
C
free
3
send(S, Req. EM, recurso A)
receive(S, permissão A)
P4
Sai RC
send(S, Libera EM, recurso A)
t
P2
*
P3
*
send(S, Req. EM, recurso A)
(*) Bloqueados no recebimento.
Exclusão mútua distribuída
Algoritmo centralizado
• Algoritmo simples de entender e de implementar.
• Requer somente três mensagens para entrar em e sair de região crítica.
• Coordenador central é um ponto único de falha.
Recuperação de uma falha do servidor: um novo servidor deve ser
criado ou, então, um dos processos deve assumir esta função. Neste caso,
um mecanismo de eleição deve ser executado para definir qual dos processos
ativos será o escolhido, já que o servidor tem que ser único.
• Outro problema: Como lidar com a falha de um dos processos clientes,
principalmente, daquele que detém o token?
• Coordenador central pode tornar-se um gargalo!
Exclusão mútua distribuída
Algoritmo em anel (token-ring)
P5
P2
P3
P0
P1
P4
P6
Arranjo físico dos processos
P0
Arranjo lógico dos processos
P1
P2
P6
P3
P5
P4
O processo que detém o token
pode entrar na região crítica.
Exclusão mútua distribuída
Algoritmo em anel (token-ring)
Processo P(k) deseja entrar na região crítica:
TOKEN
P(k-1)
TOKEN
P(k)
P(k+1)
Executa sua
região crítica
Processo P(k) não deseja entrar na região crítica:
TOKEN
P(k-1)
TOKEN
P(k)
P(k+1)
Exclusão mútua distribuída
Algoritmo em anel (token-ring)
• O token não é, necessariamente, obtido em ordem “happened-before”
(~temporal). Pode levar de 1 a (n-1) mensagens para se obter o token, desde
o momento em que se torna necessário.
• Mensagens são enviadas no anel mesmo quando nenhum processo requer
o token.
• Tempo máximo de um ciclo = soma dos tempos de execução das regiões
críticas de todos os processos.
Exclusão mútua distribuída
Algoritmo em anel (token-ring)
• Token perdido: recuperação baseada no envio de ACK quando do
recebimento do token.
• Processo que falha: reconfiguração executada para remover o processo
do anel. Enquanto isso, a circulação do token é interrompida.
• Se o processo que falha é quem possui o token: um mecanismo de eleição
é necessário para escolher um único processo que irá regenerar o token e
iniciar a sua circulação.
Sincronização em Sistemas Distribuídos
Propriedades de algoritmos distribuídos
• As informações relevantes estão espalhadas entre diversas
máquinas.
• Deve ser evitada a qualquer custo a existência de um ponto
único de falha.
• Os processos tomam decisões baseados, exclusivamente, nas
informações
disponíveis no local onde eles estão rodando.
• Não existe uma fonte de clock comum ou qualquer outra
fonte precisa de
tempo global.
Sincronização de relógios
Nos sistemas centralizados, o tempo é um conceito não-ambíguo. Quando um
processo deseja saber a hora, basta que ele execute uma chamada de sistema,
que o kernel lhe dá as informações a respeito.
Se o processo A pergunta pela hora e, pouco depois, o processo B também
faz a mesma pergunta, o valor que B obtém será maior (ou, eventualmente, igual)
que o valor obtido por A. Com certeza, o valor que B recebe não será
menor que o obtido por A.
Já no caso dos sistemas distribuídos, a conformidade em relação à questão do
tempo não é obtida de forma trivial.
Sincronização de relógios
12
12
3
9
Nó A
Nó C
3
9
6
6
Rede
12
12
3
9
6
Nó B
Nó D
3
9
6
Sincronização de relógios
Apesar da freqüência de cada oscilador ser bastante estável, não é
possível garantir que os cristais de todos os processadores estejam
oscilando exatamente na mesma freqüência.
Na prática, quando um sistema tem n processadores, todos os n cristais
estarão oscilando em freqüências ligeiramente diferentes uns dos outros,
fazendo que os clocks (software) pouco a pouco percam o sincronismo e
forneçam valores diferentes quando lidos pelos processos.
Esta diferença nos valores de tempo é denominada escorregamento
do clock (clock skew).
Sincronização de relógios
Computador no qual
o compilador está
2144
rodando
X
2145
2146
2147
tempo de acordo com
o clock local
2145
tempo de acordo com
o clock local
Arquivo output.o criado
Computador no qual
o editor está
2142
rodando
2143
X
2144
Arquivo output.c criado
t1
t2
Um evento ocorrido depois de um outro evento pode ter associado
a ele um valor de tempo local que nos faça concluir que ele ocorreu
antes do outro.
Tempo
Sincronização de relógios
Para muitos propósitos é suficiente que todas as máquinas estejam de acordo
sobre uma determinada marcação de tempo, não sendo porém importante
que este tempo coincida com o tempo real.
Para certas classes de algoritmos, o que vale é a consistência interna dos clocks
e não o quanto eles estão próximos do tempo real.
No âmbito de tais algoritmos, é usual referir-se aos clocks como clocks lógicos.
Sincronização de relógios
Pode haver uma restrição adicional (sistemas de tempo real, por exemplo) que
exija que os clocks não somente sejam os mesmos, mas que também não possam
diferir do tempo real mais do que um certo valor.
Neste caso, os clocks são chamados de clocks físicos.
Sincronização de relógios
Sincronização de relógios lógicos:
Objetivo: ordenação de eventos em ambiente distribuído.
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.
Sincronização de relógios
Relação “acontecer-antes” (happens-before):
Fornece uma ordenação parcial de eventos
Não especifica a exata ordem dos eventos, mas somente define a
ordem de certos elementos que dependem de outros
A expressão ab (a acontece antes de b) significa que todos os processos
concordam com o fato de que primeiro acontece o evento a e depois
ocorre o evento b.
Exemplo:
If you have three events {A, B, C}, then they are totally ordered if they
always have to happen in the order A  B  C. However, if A must
happen before C, but you don't care when B happens, then they are
partially ordered. In this case we would say that the sequences A  B 
C, A  C  B, and B  A  C all satisfy the partial ordering
Sincronização de relógios
Propriedades da relação  :
1. Se dois eventos E1 e E2 acontecem no mesmo processo P, a ordem deles é a
ordem observada em P, ou seja, se E1 e E2 são eventos no mesmo processo
e se E1ocorre antes de E2, então E1E2 é verdadeira.
2. Se o processo A envia uma mensagem para o processo B, o evento envio de
mensagem “acontece antes” do evento recebimento, ou seja, uma mensagem
não pode ser recebida antes de ter sido enviada, pois ela demora um tempo
finito para chegar ao destino
send(msg) recv(msg)
Regras:
1. Transitividade: se ab e bc, então ac.
2. Concorrência de eventos: Se os eventos E1 e E2 acontecem em dois processos
diferentes que não trocam mensagens então E1E2
e E2E1.
/
/
Os eventos E1 e E2 são denominados eventos concorrentes (E1 E2).
P1
Sincronização de relógios
•a
•b m1
•c
P2
•d
m2
P3
•e
•
f
Tempo
Prop.1
Prop.2
Regra 1
ab
bc
ac
ad
cd
df
b d
bf
ef
cf
af
Regra 2
a  e
Sincronização de relógios
• Ordenação causal de eventos garantia que mensagens enviadas por
processos diferentes são entregues pela ordem correta no receptor
• Não garante que as mensagens dos processos concorrentes sejam
ordenadas
• Ordenação total de eventos  garante que quaisquer duas mensagens
entregas a qualquer par de receptores são entregues na mesma ordem
em ambos
• Ordenação temporal de eventos  Uma mensagem m1 precede
temporalmente m2 e será recebida por essa ordem por todos os
membros do grupo e se só se m1 for enviada antes de m2 com um
certo intervalo de tempo (Δt)
Sincronização de relógios
Implementação de relógio lógico (Solução de Lamport):
O sincronismo do clock não precisa ser absoluto.
Os processos devem estar de acordo sobre a ordem na qual eventos ocorrem.
• Um valor de clock C(a) é associado a cada evento a .
• Se a e b são eventos dentro do mesmo processo e a ocorre antes de b, então
C(a) deve ser menor que C(b).
• Se a é o evento de envio de mensagem para o processo X e b é o evento de
recebimento da mensagem no processo X, então C(a) e C(b) devem ser
associados de tal forma que C(a) < C(b).
O tempo medido pelo clock C( ) deve ser sempre crescente, nunca decrescente.
Correções nos valores do clock podem ser feitas adicionando-se um valor
positivo ao valor corrente do clock, nunca subtraindo-se.
Sincronização de relógios
Algoritmo:
• Cada processo P mantém um relógio Cp inicializado com 0 e incrementado
a cada evento interno a P.
• Ao enviar uma mensagem m, o processo envia (m, t) onde t = Cp.
• Ao receber uma mensagem (m, t), o processo Q faz CQ=max (CQ, t) + 1
Sincronização de relógios
a
P
b
• •
0
c
•
1
X3
2
(M1,1)
Q
e
f
g
1
2
3
h
i
4 7
8
X
(M2,3)
R
•
0
•
k
1
• •
9
10
Clock em P
M4
• • • •
0
d
m
2 4
5
• •
•
9
Clock em Q
(M3,6)
•
•
•
X
l
j
n
6
CR= max (CR , t) + 1
CR = max (1, 3) + 1
•
o
7
Clock em R
Tempo real
Sincronização de relógios
Este algoritmo fornece somente uma forma de ordenação parcial de todos os
eventos do sistema, já que alguns pares de distintos eventos, gerados por
diferentes processos, têm idênticos timestamps.
Entretanto, pode-se estender este algoritmo para ordenação total, acrescentando-se
ao timestamp a identificação do processo no qual o evento ocorreu. Desta forma,
um evento a ocorrido no processo pa com timestamp local Ta e um evento b
ocorrido no processo pb com timestamp local Tb, receberiam timestamps globais
(Ta, pa) e (Tb, pb), respectivamente.
Define-se, então, que (Ta, pa) < (Tb, pb) se e somente se Ta < Tb ou
Ta = Tb e pa < pb.
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
*WWV = sinal que o United States National Institute of Standards and Technology (NIST)
transmite continuamente com frequência e tempo controlado por um relógio atômico. São
emitias frequências padrões para calibrar dispositivos
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 distribuída (cont.)
Algoritmo distribuído (Ricart & Agrawala):
•Agora que já foi falado sobre ordenação total de eventos podemos falar desse
algoritmo
• Apresentado pela primeira vez no artigo de Lamport sobre sincronização de
clocks (1978).
• Ricart & Agrawala (1981) tornaram este algoritmo mais eficiente.
• Premissas:
• Ordenação total de todos os eventos.
• Assume-se que o envio de mensagens é confiável, ou seja, toda mensagem
é reconhecida pelo receptor.
• Comunicação de mensagens em grupo, se disponível, deve ser usada em
vez de mensagens individuais.
Exclusão mútua distribuída (cont.)
Na inicialização:
state := RELEASED
Para obter EM(token):
state:= WANTED
envia Req.EM para todos os processos (multicast)
T := timestamp da requisição
wait( (n-1) respostas recebidas)
state := HELD
Ao receber Req.EM (Ti, pi) em pj (i j):
if ((state = HELD) or (state = WANTED and (T,pj) < (Ti, pi)))
coloca Req. de pi na fila e não responde
else
responde OK imediatamente a pi
Para liberar EM(token):
state := RELEASED
responde OK a todas as Req. que estão na fila
Exclusão mútua distribuída (cont.)
Entrar na região crítica
P1
send(Req.EM, pid, timestamp local)
P2
•
•
•
Pn
Processo que recebe mensagem solicitando EM:
1. não quer entrar na RC: envia OK para o emissor
2. está na RC: não responde
3. quer entrar na RC:
• timestamp do receptor < timestamp do emissor: enfileirar pedido e
não responder
• timestamp do receptor > timestamp do emissor: envia OK para emissor
Exclusão mútua distribuída (cont.)
state:=HELD
coloca P3 na fila
state:=RELEASED
state:=WANTED
send(EM,P1,10)
OK
P2
P1
P1
send(EM,P3,12)
Entra na
região
crítica
P3
state:=WANTED
OK
P1
Sai da
região
crítica
P3
OK
P3
state:=RELEASED
envia OK para todos da fila
Entra na
região
crítica
state:=HELD
P2
Exclusão mútua distribuída (cont.)
• Número de mensagens necessárias por entrada na RC: 2(n-1)
• n pontos de falha. Se qualquer dos processos tiver um problema e não responder,
a ausência de resposta será interpretada incorretamente como uma negativa para
execução da região crítica. Bloqueio de todos os processos.
 Receptor deverá sempre enviar uma resposta, aceitando ou negando a
permissão solicitada.
• Comunicação em grupo é desejável ou cada processo deve manter sua própria
lista de membros do grupo.
• Todos os processos estão, igualmente, envolvidos em todas as decisões relativas
às entradas nas regiões críticas X gargalo de desempenho do algoritmo centralizado.
Eleição
• A maioria dos algoritmos distribuídos precisa de um processo para agir como
coordenador, inicializador, seqüenciador ...
• Uma eleição é um procedimento para escolha de um processo dentre um
grupo de processos (tipicamente, para assumir a função de coordenador).
• A escolha deve ser única, apesar de vários processos se candidatarem e
executarem algoritmos de eleição, concorrentemente.
•O processo coordenador pode falhar  um novo coordenador deve ser eleito.
• Em geral, os algoritmos eletivos tendem a designar como coordenador o processo
com o número de identificação mais alto. Esta identificação consiste de um
número único, por exemplo, seu endereço na rede (por simplicidade, considere
um processo por máquina).
• Qualquer número de falhas pode ocorrer durante o processo de eleição.
Eleição
Algoritmo do tirano (bully algorithm):
• Garcia-Molina (1982)
•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. Cada processo sabe os números de
identificação de cada um dos demais processos. Os processos não sabem é quais
processos estão ativos e quais estão inativos.
•A topologia não é limitada a um anel e cada um dos processos pode se
comunicar com qualquer outro no sistema.
•A execução do algoritmo busca eleger o processo de maior identificador e fazer
com que todos reconheçam o novo líder.
Eleição
• Algoritmo do tirano (bully algorithm):
– 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.
Eleição
Algoritmo do tirano (bully algorithm):
Processo pi, ao verificar falha:
Envia mensagem indicativa de eleição para todos os processos pj,
tal que i < j.
Depois de um tempo t
Se não recebeu nenhuma resposta , pi se elege e envia mensagem
indicativa de novo coordenador para todos os demais.
Senão
desiste da eleição.
Processo pi, ao receber mensagem indicativa de eleição de pj:
Responde a pj e inicia sua própria eleição.
Eleição
0
7
X7
1
Eleição
6
2
1
6
2
E
OK
5
3
E
0
4
Processo 4 verifica que o processo
coordenador (7) falhou e convoca
eleições.
5
3
OK
4
Processos 5 e 6 respondem,
informando ao processo 4 que
seu trabalho terminou.
Eleição
E
7
X
0
Eleição
6
X7
1
2
0
1
6
2
OK
E
5
3
4
Processos 5 e 6 convocam eleições.
5
3
4
Processos 6 responde, informando
ao processo 5 que seu trabalho
terminou.
Eleição
X7
0
C
1
C
Coordenador
6
C
5
2
C
C
3
4
O processo 6 anuncia a todos os
demais processos que é o novo
coordenador.
Eleição
Coordenador
0
C
7
C
1
C
6
C
C
2
C
5
3
4
O processo 7, ao ser reinicializado, verifica que possui
número de identificação maior do que o coordenador
atual e assume a coordenação de forma tirânica, ditatorial
(daí a origem do nome do algoritmo).
Eleição
Algoritmo em anel (ring-based election algorithm):
• Ao contrário do algoritmo em anel para exclusão mútua, este algoritmo não
usa o conceito de token.
•Processos são organizados em um anél lógico sendo que cada um possui um
identificador.
•Valores são únicos e completamente ordenados
• Identificadores podem ser dinâmicos. Por exemplo (identificador da
máquina/ load)
•Cada processo sabe exatamente quem é seu sucessor.
•Todas as mensagens são passadas no sentido horário
•O objetivo é escolher como coordenador aquele que possui maior identificaro
•Cada processo pode iniciar a eleição colocando seu identificador em uma
mensagem de eleição e mandando ao seu vizinho. Ele vai alterar então seu
estado de não participante para participante
Eleição
Algoritmo em anel (ring-based election algorithm):
• Quando recebe uma mensagem de eleição compara seu id com o da mensagem
• Se id da mensagem > que o seu id e seu estado é participante,
simplesmente passa mensagem adiante.
• Se id da mensagem > que o seu id e seu estado é não participante.
Muda seu estado para participante e passa mensagem intocada
• Se seu id > que o id da mensagem e estado não participante, muda seu
estado para participante e repassa uma nova mensagem de eleição com
seu id inserido
•Quando recebe uma mensagem de eleição contendo seu próprio identificador
venceu a eleição. Muda seu estado para não participante e envia uma
mensagem com eleito contendo seu identificador
•Quando recebe uma mensagem eleito cada processo muda seu estado para não
participante e muda suas variaveis internas para refletir o novo coordenador
Eleição
0
E(6)
7
Não responde
1
E(6)
E(6)
6
2
E(5)
E(6)
3
5
E(6)
4
E(6)
Processo 5 detecta a falha do coordenador (7)
e convoca eleições circulando uma mensagem
identificativa de eleição (E).
Eleição
C
0
X7
1
C
C
C = Eleito(6)
6
2
C
C
3
5
C
4
C
A mensagem muda para uma outra, informando que há um novo
coordenador, cuja identificação consta da mensagem. Esta mensagem
indica também quem são os novos membros do anel.
Eleição
0
7
X
Não responde
E(6)
1
E(6)
E(6)
6
2
E(2)
E(5)
3
5
E(4)
4
E(3)
Os processos 2 e 5 descobrem, simultaneamente, falha do coordenador
anterior (7). Observe que o fato de haver a circulação de mensagens extras
não traz nenhum problema, exceto um pouco de desperdício da banda passante.