Sistemas Distribuídos
Walfredo Cirne
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
(processamento e 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
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;
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
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