Upload
internet
View
103
Download
0
Embed Size (px)
Citation preview
Sistemas DistribuídosWalfredo Cirne
Aula 3: Conceitos Básicos
As figuras que aparecem nesses slides são de Veríssimo&Rodrigues, reproduzidas com o consentimento dos mesmos.
Propriedades de um sistema
• Safety– Alguma coisa ruim não pode acontecer
• Liveliness– Alguma coisa boa vai acontecer um dia
• Timeliness– Adicionam requisitos de tempo real às
propriedades de liveliness
Nomes e endereços
• Nomes identificam objetos– Nomes únicos globalmente × contexto de nomes– Nomes “puros” × “impuros”
• Endereços são nomes usados por algum sistema de comunicação para entregar mensagens
• Nomes são resolvidos em endereços– “Ciência da Computação é a ciência que resolve
problemas adicionando níveis de indireção”– Quais resoluções temos quando enviamos um email
para [email protected]?– Nomes podem ter seu significado mudado ao longo do
tempo
Mapeamento/resolução de nomes
• Serviços de nomes traduzem nomes em endereços– Binding
• Associa um nome a um endereço
– Lookup• Recupera (resolve) um endereço a partir de um nome
– Unbiding• Desassocia um nome a um endereço
• O servidor de nomes precisa usar um endereço bem conhecido
Servidores de nomes
Troca de mensagens
• Mecanismo básico de interação em sistemas distribuídos• Endereçamento, protocolo e formato das mensagens• Confiabilidade
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.
Semântica de Bloqueio
• O send pode retornar quando:– Se recebe um ack– Quando o dado enviado está bufferizado – Imediatamente
• Cada opção tem impactos de performance e interface
• Respose-and-reply × Notification/events
Operação remota
• Chamada remota de procedimento (ou método)– Marshalling/unmarshalling– Bloqueio durante a execução– Semântica de falhas
• Mecanismo básico usado no paradigma cliente/servidor– Amplamente usada (ex Java RMI)
Usando multiplas threads com operações remotas
Comunicação em grupo
• Difusão de conteúdo– especialmente streaming
• Grupo de servidores– melhor disponibilidade e/ou performance
• 1 multicast ≠ n unicasts
Multicast para difusão de conteúdo
Group membership
• Serviço usado para construção de grupos de replicas– Provê serviço de alto nível– Entrega confiável de mensagens
• Visão do grupo– Os membros do grupo sabem quem está no
grupo
• Ordenação de mensagens– O enviador recebe suas próprias mensagens
Relembrando o modelo de Lamport
• O sistema é composto por uma coleção de processos;
p
q
r
• Cada processo é uma sequência de eventos• Um evento pode ser:
– uma sub-rotina, uma instrução... – O envio de uma mensagem;– O recebimento de uma mensagem
Precedência
• 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 Causal
• 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”
Relógios Lógicos
• A idéia é associar um número a cada 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
Relógios Lógicos
• Clock Condition: Para quaisquer dois eventos a e b: se a b, então C[a] < C[b]
• Implementação– Cada processo Pi incrementa Ci entre dois
eventos sucessivos
– 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
• 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 Vetoriais
Limitações da ordenação causal
Ordenação Total
• Quaisquer duas mensagens entregues a quaisqueis processos são entregues na mesma ordem
• Fundamental para replicação ativa
Canais Ocultos
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?