Sistemas Distribuídos
Walfredo Cirne & Fubica Brasileiro
Aula 4: Mais Conceitos Básicos
As figuras que aparecem nesses slides são de Veríssimo&Rodrigues, reproduzidas com o
consentimento dos mesmos.
Na aula passada...
•
•
•
•
•
Nomes e Endereços;
Troca de Mensagens;
Operações Remotas;
Comunicação em Grupo;
Tempo e relógios;
Na aula de hoje... Mais paradigmas
de Sistemas Distribuídos!
•
•
•
•
•
•
Sincronia;
Ordem;
Coordenação;
Consistência;
Concorrência;
Atomicidade.
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
(Processamento, troca de mensagens)
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
• A primeira noção que temos é a de “ordem
física” (ordem em relação a tempo);
• Se não considerarmos tempo, temos
apenas uma seqüência de eventos;
• Fundamental para que se possa raciocinar
sobre sistemas distribuídos (determinar
causas e efeitos);
• A priori (garantir política)  A posteriori (log
& debug)
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: Quaisquer duas mensagens enviadas
pelo mesmo participante e entregue a
qualquer participante são entregues na
mesma ordem de envio.
Ordenação de Mensagens
• Causal: Permite ordenar mensagens
enviadas por processos diferentes.
• Obedece “Entrega Causal”:
– se enviop(m)  envioq(n), então
entregar(m)  entregar(n)
• Implementação: protocolos que asseguram
“ordem lógica”;
Ordenação de Mensagens
• Ordem lógica: uma mensagem m1 precede
logicamente m2 se e somente se:
– m1 é enviada antes de m2 pelo mesmo
participante; ou
– m1 é entregue ao sender de m2 antes deste
enviar m2; ou
– existe m3, tal que m1 precede logicamente m3 e
m3 precede logicamente m2.
• Mas ordem causal também possui
limitações...
Limitações da ordenação causal
Ordenação de Mensagens
• Total: Quaisquer duas mensagens
entregues a quaisquer dois processos são
entregues na mesma ordem
– Fundamental para replicação ativa
Canais Ocultos
• Ordem Temporal: m1 precede
temporalmente m2 se e somente se
t(send(m2) – t(send(m1)) > δt
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
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
Relógios Lógicos [Lamport]
• Objetivo de Lamport: ordenar eventos em um
sistema;
• Se o modelo considera tempo físico, então o
sistema deve conter relógios reais;
• Problema:
– Relógios têm que estar sincronizados;
– Relógios têm que possuir precisão muito próxima;
• Decisão: definir o sistema em termos de
relógios lógicos
Modelo de Lamport
• Um evento pode ser:
sistema
é composto
por uma coleção
de
• O
Cada
processo
é uma sequência
de eventos
– uma sub-rotina, uma instrução...
processos;
– O envio de uma mensagem;
– O recebimento de uma mensagem
p
q
r
Modelo de Lamport
• Neste modelo, Lamport definiu relação de
precedência ();
– Se a e b são eventos no mesmo processo e a
aconteceu antes de 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
• Se a não precede b e b não precede a, a e
b são concorrentes;
Relação de precedência
• a  b se é
possível ir de a
até b seguindo a
linha de
processos e
mensagens;
• Relação de
causalidade;
• Eventos concorrentes não afetam
um ao outro
Relógios Lógicos
• Visão inicial: associar um número a um
evento;
• Cada processo Pi tem um relógio Ci;
• Um relógio associa um número Ci[a] a cada
evento a no processo i;
• O sistema formado por todos os relógios é
representado por C;
– C[b] = Ci[b], se b aconteceu no processo i;
• Os valores de C são apenas contadores;
Clock Condition
• Para ordenar eventos, Lamport definiu clock
condition:
• Clock Condition: Para quaisquer dois
eventos a e b: se a  b, então C[a] < C[b]
Clock Condition
• Para garantir clock condition é preciso que
C1 e C2 sejam verdade:
• C1: Se a e b são eventos em um mesmo
processo Pi e a  b, então Ci[a] < Ci[b];
• C2: Se a é o envio de uma mensagem por
Pi, e b é o recebimento por Pj, então
Ci[a] < Cj[b];
Clock Condition
• É possível garantir C1 e C2 através das
regras de implementação IR1 e IR2,
respectivamente;
• IR1: Cada processo Pi incrementa Ci entre
dois eventos sucessivos;
• IR2: Se a é o envio de uma mensagem m
por Pi, então m carrega o valor Tm de Ci[a].
Ao receber m, Pj ajusta seu relógio Cj para
um valor maior do que Tm, que pode ser o
seu valor atual;
Clock Condition
Coordenação: 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;
Outras construções para
sincronização
•
•
•
•
Conditional regions;
Sequencers;
Event counters;
Barriers;
• Poucas linguagens suportam estas
construções explicitamente;
• Java 1.5 já suporta!!!
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 via
Servidor de Lock
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
Exclusão Mútua Distribuída
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, obtém-e-espera, não-preempção,
espera circular
• 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 decide em
algum momento no futuro;
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
• Como resolver? View Synchrony
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?
Partição do Grupo
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
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
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;
}
}
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;
}
Atomicidade: 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