Sistemas Distribuídos
Capítulo 02 – Algoritmos Distribuídos
Aula Passada
2.1 – Relógios Físicos e Lógicos
Aula de Hoje
2.3 Exclusão Mútua
2.4 Eleição
Prof. Paulo Fernando da Silva
Roteiro
• Revisão da aula passada
• Plano de Aula (conteúdos e objetivos)
• Conteúdo:
– Exclusão Mútua
– Eleição
• Revisão do conteúdo
• Próxima Aula
• Exercícios
Prof. Paulo Fernando da Silva
Revisão da Aula Passada
2.1 Relógios Físicos e Lógicos
• Relógios Físicos:
– Cristian
– Berkeley
– NTP
• Relógios Lógicos
– Algoritmo de Lamport
– Ordenação Total
Prof. Paulo Fernando da Silva
Já entregaram a
lista da aula
passada?
Plano de Aula – Conteúdo
2.2 Exclusão Mútua Distribuída
– Algoritmo centralizado
– Algoritmo em anel
– Algoritmo distribuído
2.3 Eleição
– Algoritmo de bully
– Algoritmo em anel
Prof. Paulo Fernando da Silva
Plano de Aula – Objetivos
• Compreender o funcionamento dos
algoritmos distribuídos de:
– exclusão mútua e eleição;
• Conhecer as principais características dos
algoritmos:
– Centralizado, anel e distribuído (exclusão)
– Bully e anel (eleição)
Prof. Paulo Fernando da Silva
2.2 Exclusão Mútua
Algoritmo Centralizado
Algoritmo em Anel
Algoritmo Distribuído
Prof. Paulo Fernando da Silva
Exclusão Mútua Distribuída
• Sistemas distribuídos são Concorrentes
– E compartilham recursos
– Acesso exclusivo garante a consistência
Prof. Paulo Fernando da Silva
Exclusão Mútua Distribuída
Algoritmo Centralizado
Quais são as características?
Prof. Paulo Fernando da Silva
Exclusão Mútua Distribuída
Algoritmo em Anel
p
1
p
2
p
n
p
3
p
4
T oken
Prof. Paulo Fernando da Silva
Quais são as
características?
Exclusão Mútua Distribuída
Algoritmo Distribuído
Quais são as características?
Prof. Paulo Fernando da Silva
2.3 Eleição
Algoritmo de Bully
Algoritmo em Anel
Prof. Paulo Fernando da Silva
Algoritmos de Eleição
• Alguns algoritmos dependem de coordenador
• O que fazer caso o coordenador saia do ar?
Prof. Paulo Fernando da Silva
Algoritmos de Eleição
• Regras Gerais:
– O maior ID será o novo coordenador
– Inicia a eleição quem percebe a falta do
coordenador
• Algoritmos:
– Bully e Anel
Prof. Paulo Fernando da Silva
Eleição - Algoritmo Bully
Prof. Paulo Fernando da Silva
Eleição - Algoritmo Bully
Prof. Paulo Fernando da Silva
Eleição - Algoritmo Ring
Prof. Paulo Fernando da Silva
Eleição - Algoritmo Ring
Prof. Paulo Fernando da Silva
Características
• Algoritmo em Anel:
– Determinístico – quantidade de mensagens fixa
– Depende da formação do anel
• Algoritmo de Bully:
– Pode ser muito bom (ex. 4 percebe falta de 5)
– Ou muito ruim (ex. 1 percebe a falta de 5)
– Não depende de estrutura prévia (anel)
Prof. Paulo Fernando da Silva
Resumo da Aula
• Exclusão Mútua Distribuída
– Algoritmo centralizado
• Fila em um servidor centralizado
– Algoritmo em anel
• Passagem de token em um anel lógico
– Algoritmo distribuído
• Uso de relógio lógico de Lamport
Prof. Paulo Fernando da Silva
Resumo da Aula
• Eleição
– Algoritmo de Bully
• Tenta se eleger em todos os superiores
– Algoritmo em Anel
• Passa mensagem por um anel lógico
Prof. Paulo Fernando da Silva
Plano de Aula – Objetivos
• Compreender o funcionamento dos
algoritmos distribuídos de:
– exclusão mútua e eleição;
• Conhecer as principais características dos
algoritmos:
– Centralizado, anel e distribuído (exclusão)
– Bully e anel (eleição)
Prof. Paulo Fernando da Silva
Próxima Aula...
• Aula de laboratório;
• Exercícios de algoritmos distribuídos:
– Exclusão Mútua
– Eleição
• A descrição do exercício está no AVA
• O material da aula de hoje também está no AVA.
Prof. Paulo Fernando da Silva
Material de Apoio
•
COULOURIS, George F; DOLLIMORE, Jean;
KINDBERG,Tim, et al. . Distributed systems : concepts
and design. 3.ed. Harlow : Addison-Wesley, 2001. xiii,
772p.
•
TANENBAUM, Andrew S; STEEN, Maarten van.
Distributed systems : principles and paradigms. Upper
Saddle River, N.J : Prentice Hall, 2002. xxii, 803p.
•
GARG, Vijay Kumar. Concurrent and distributed
computing in Java. [Piscataway, N.J.?] : IEEE Press;
Hoboken, N.J : Wiley-Interscience, 2004. xx, 309 p, il.
•
APOIO NA INTERNET
•
http://users.ece.utexas.edu/~garg/jbk.html
Prof. Paulo Fernando da Silva
Exercício
• Três processos P1, P2 e P3 solicitando
seção crítica em 5, 1 e 4 respectivamente
– Apresente a exclusão mútua distribuída
• Processos de 1 à 5, onde o processo 2
percebe que o coordenador 5 saiu do ar.
– Apresente a eleição por bully
Prof. Paulo Fernando da Silva