Sistemas Distribuídos
Walfredo Cirne & Fubica Brasileiro
http://walfredo.dsc.ufcg.edu.br/cursos/2005/distsis20052
Aula 4: Mais Conceitos Básicos
As figuras que aparecem nesses slides são de Veríssimo&Rodrigues, reproduzidas com o
consentimento dos mesmos.
Sincronia
• O que significa sincronia?
– envio de mensagens blocking  non-blocking
– iteração same-time  different-time
– hardware clock-driven
– limite superior para execução de ações
Graus de Sincronia
• Assíncrono
– sem limites de tempo para ações
• Síncrono
– ações têm limites de tempo conhecidos
• Parcialmente síncrono
– ações têm limites de tempo para acontecer,
mas estes são desconhecidos e/ou válidos
somente parte do tempo
Qual a gente escolhe?
• Assíncrono
– fácil de implementar, mas pouco útil
• Síncrono
– muito poderoso, mas conflita com escala,
abertura, interatividade, bom uso dos recursos
– usado em sistemas embarcados
• Parcialmente síncrono
– muito usado em computação de uso geral
– semântica tipicamente não é claramente definida
Ordenação
• Fundamental para que se possa raciocinar
sobre sistemas distribuídos
• A priori  A posteriori
Precedência [Lamport]
• Se a e b são eventos no mesmo processo e
a precede b, então a  b
• Se a é o envio da mensagem m e b é a
recepção da mensagem m, então a  b
• Se a  b e b  c, então a  c
Ordenação de Mensagens
• FIFO: entre quaisquer dois processos, as
mensagens são entregues em ordem
• Causal: se envio(m)  envio(n), então
entrega(m)  entrega(n)
• Total: Quaisquer duas mensagens entregues a
quaisquer dois processos são entregues na
mesma ordem
– Fundamental para replicação ativa
• Causal e total são ortogonais!?!
Implementando FIFO
Limitações do FIFO
Implementando Ordenação Causal
• Toda mensagem enviada é armazenada em
past
• Toda mensagem recebida é armazenada em
past
• Toda mensagem m vai acompanhada de past
• Na recepção de m, checa-se primeiro past e
caso haja mensagens que ainda não foram
entregues, estas são entregues antes que m
Implementação por
Relógios Lógicos
•
•
•
•
•
Cada processo mantém o inteiro lclock
Toda mensagem enviada carrega lclock
O envio de uma mensagem incrementa lclock
Mensagens são enviadas usando canais FIFO
Quando a mensagem m, com lclockm, é entregue,
fazemos lclock = max(lclock, lclockm)
• Mensagens só são entregues quando se recebe
mensagens de todos os outros processos com
lclock maior
Refinamento: Relógios Vetoriais
• Assumindo que todas as mensagens são broadcast
• Se unicast ou multicast são permitidos, necessita-se
de uma matriz no lugar do vetor
Canais Ocultos
Relembrando: Exclusão Mútua
• Semáforo S: variável não-negativa inteira
que só pode se modificada pelos
procedimentos up() e down()
• down(S)
se S > 0: decremente S
senão: bloqueia esperando up(S)
• up(S)
se há alguém bloqueado: desbloqueie
senão: incremente S
Usando Semáforos
(* exclusão mútua *)
var mutex: semaphore := 1;
thread P1;
statement X
down(mutex);
statement Y
up(mutex);
statement Z
end P1;
thread P2;
statement A;
down(mutex);
statement B;
up(mutex);
statement C;
end P2;
Exclusão Mútua via
Servidor de Lock
• Necessário para coordenar processos e evitar
“colisões”
• Servidor de lock
– Interessados em entrar na região crítica mandam
mensagem LOCK para o servidor
– O servidor só responde com LOCK-GRANTED para um
processo
– Processo envia UNLOCK ao sair da região
• Servidor é ponto único de falhas e possível
gargalo de performance
• Falha no cliente também é problema
Exclusão Mútua Distribuída
• Usando um protocolo que garante entrega
ordenada total, podemos replicar o servidor
de lock em todos os processos do sistema
• Podemos também eleger dinamicamente
um líder para função de servidor de lock
– Precisamos também pensar em como passar
estado entre lideres, ou então resetar o sistema
quando há troca de líder
Eleição de Líder
• Note a necessidade de sincronia para
detecção da falha do líder!!
Deadlock
• Deadlock ocorre quando um processo fica
esperando por outro
• Para deadlock é necessário ter exclusão
mútua, espera circular, obtém-e-espera,
não-preempção
• Tudo que você conhece deadlock em
sistemas concorrentes vale para sistemas
distribuídos, com a complicação que você
não tem uma visão global do sistema
Consistência
• Como garantir que alguma propriedade
sistêmica é válida?
• Ou seja, como garantir que (ou checar se)
a execução do sistema é consistente?
• Para checar, podemos parar o sistema e
montar um estado global
– Naturalmente, isso é dispendioso
– Protocolos de snapshot distribuído são uma
solução bem mais eficiente para o problema
Consenso
• Problema básico para coordenação de
processos
• No consenso, cada processo p propõe um
valor vp e decide por um valor final fp
• As propriedades de consenso são:
– Acordo:  p,q que decidem: fp = fq
– Validade:  p: fp = vp
– Terminação: Todo processo correto
eventualmente decide
Consenso em um
Sistema sem Falhas
Acordo sobre Participantes
• Muitas vezes é importante saber quais
processos constituem o sistema
– Por exemplo, rank e size viabilizam a
computação determinística de uma propriedade
por todos os processos
• Conjunto de participantes = Visão
• É fundamental que cada mensagem seja
entregue a todos os seus destinatários na
mesma visão
Troca de Visão Desincronizada
Atomic Broadcast
• Atomic Broadcast =
View Synchrony + Total Order
• Atomic Broadcast =
Mudança de visão via entrega de mensagem
+ Total Order
Determinismo de Replicas
• Atomic broadcast permite implementarmos
replicação, desde que as replicas sejam
totalmente determinísticas
• Mas, como construir replicas perfeitamente
determinísticas?
• Será que um malloc() é determinístico?
Partição do Grupo
• Note que detecção de partição precisa ser
entregue como uma mensagem!!
Concorrência
• “A good understanding of the memory
consistency model is paramount to building
correct programs”
• Consistência atômica
– todos os acessos são a mesma memória
• Consistência seqüencial
– equivalente a consistência atômica de alguma
execução
– indistinguível da consistência atômica se
comunicação é somente via memória
Exemplo:
Double-Checked Locking
class Foo {
private Helper helper = null;
public Helper getHelper() {
if (helper == null)
synchronized(this) {
if (helper == null)
helper = new Helper();
}
return helper;
}
}
Modelo de Memória de Java
• Cada thread de Java tem memória local
• Dados inexistentes na memória local são
copiados da memória global
• Eventualmente, dados gravados na memória
local são refletidos na memória global
• Ao entrar num synchronized, todos os dados
da memória local são invalidados
• Ao sair de um synchronized, todos os dados
gravados são refletidos globalmente
Outro Exemplo:
Objetos Ativos
public class DataRace extends Thread {
int a = 0;
public DataRace() {
this.start();
a = 1;
}
public void run() {
System.out.println(a);
}
}
Objetos Ativos:
O problema é sutil
public class DataRace extends Thread {
protected int a = 0;
public DataRace() {
a = 1;
this.start();
}
}
public class ExtendRace extends DataRace {
public ExtendRace() {
super();
a = 2;
}
}
Suporte a Transações
• Transações são uma abstração muito
poderosa tipicamente implementadas por
banco de dados
• Transações são ACID
– Atomicity: tudo ou nada
– Consistency: atualizações levam os dados de um
estado consistente para outro estado consistente
– Isolation: transações executadas em paralelo não
vêem uma a outra
– Durability: é um banco de dados, né?
Transações Distribuídas:
Two-phase Commit