Aula 4 Sistemas Distribuidos

Prévia do material em texto

Sistemas Distribuídos
Prof. Carlos Viana
Exclusão Mútua
• Uma questão fundamental em sistemas 
distribuídos é a concorrência entre vários 
processos;
• Em muitos casos, isso também significa que 
processos precisar acessar simultaneamente 
os mesmos recursos.
Exclusão Mútua
• Algoritmos distribuídos de exclusão mútua 
podem ser classificados em duas categorias 
diferentes:
– Soluções baseadas em ficha: consegue-se a 
exclusão mútua com a passagem de uma 
mensagem especial entre os processos, conhecida 
como ficha;
– Solução baseada em permissão: um processo que 
quiser acessar o recurso em primeiro lugar solicita 
a permissão de outros processos;
Exclusão Mútua Distribuída
• Problema:
– Como assegurar acesso concorrente a recursos 
distribuídos?
– Necessário prevenir competição em zonas críticas;
• Requisitos:
– Apenas um processo de cada vez pode executar na 
zona crítica;
– Eventualmente os pedidos para entrar ou sair da zona 
crítica sucedem;
– Os pedidos são processados por ordem de acordo 
com a relação happens-before;
Exclusão Mútua Distribuída
• Soluções básicas para assegurar acesso 
exclusivo a recursos distribuídos:
– Centralizando o acesso num servidor;
– Completamente descentralizado, usando um 
sistema peer-to-peer;
– Completamente distribuído, sem se impor uma 
topologia;
– Completamente distribuído através de um anel 
lógico;
Exclusão Mútua Centralizada
• A solução centralizada é muito simples:
• A solução centralizada é muito simples:
– (a) P1 pede ao coordenador para aceder ao recurso; permissão 
concedida.
– (b) P2 pede acesso ao mesmo recurso; o coordenador não responde.
– (c) Quando P1 liberta o recurso, o coordenador responde ao P2.
Exclusão Mútua Centralizada
• Propriedades:
– Fácil de implementar;
–Não escala bem;
–O servidor central pode falhar;
Exclusão Mútua Descentralizada
• Princípio:
– Assumir que cada recurso está replicado n vezes; 
– Cada réplica tem o seu coordenador o acesso a 
um recurso é garantido quando se tem a maioria 
dos votos de m > n/2 coordenadores;
– Um coordenador responde sempre e de imediato;
– Quando o coordenador avaria (crash), recupera 
rápido mas pode dar permissões incorretas;
Exclusão Mútua Descentralizada
• Quanto robusta é a estratégia?
– Seja p = ∆t / T a probabilidade de um coordenador 
avariar e recuperar num período ∆ t quando o seu 
tempo de vida é T;
– A probabilidade de k dos m coordenadores façam 
reset:
Exclusão Mútua Descentralizada
• Requer ordem total de todos os eventos 
no sistema (Lamport) o processo que 
quer aceder ao recurso envia pedido 
para todos processos com indicação do 
recurso e o seu timestamp. 
• O processo que recebe um pedido, atua 
do seguinte modo:
Continuação...
• Se não está e não pretende aceder ao recurso, 
responde com OK;
• Se está a aceder ao recurso, não responde, 
deixa o pedido em fila;
• Se também pretende aceder ao recurso, 
compara o timestamp que recebeu com o que 
ele tinha enviado para os outros quando 
marcou o seu interesse. O timestamp menor 
ganha;
Exclusão Mútua Descentralizada
• Um processo ganha acesso quando receber o 
OK de todos os outros;
• Quando termina o acesso envia OK para todos 
os outros;
Exclusão Mútua Descentralizada
• Sobre o algoritmo:
– É distribuído e assegura exclusão mútua 
sem deadlock ou starvation requer 2(n−1) 
mensagens, em que n é o número de 
processos. 
– Em vez de 1 ponto de falha, tem n;
Continuação...
–Se qualquer dos processos não 
responder, o seu silêncio é 
interpretado como não permissão de 
acesso e todas tentativas de acesso a 
zonas críticas serão bloqueadas. 
–Este algoritmo mostra que envolver 
todos os processos numa decisão é 
excessivo;
Exclusão Mútua: 
Anel de Tokens (token ring)
• Algoritmo:
–Todos os processos estão organizados 
num anel lógico;
–Um token é passado pelo anel;
–Antes de entrar na zona crítica, um 
processo espera até que tenha o token. 
Só passa o token quando sair.
Continuação...
Exclusão Mútua: 
Anel de Tokens (token ring)
• Propriedades:
–Tempo médio de espera pelo token n/2 
(limita expansibilidade);
–Passagem do token gasta largura de 
banda;
–Falha de nós quebra a estrutura do 
anel (detecção difícil);
Exclusão Mútua: 
Comparação dos 4 Métodos
Algoritmo Mensagens por 
entrada/saída
Atraso antes da entrada 
(em números de tempos de 
mensagens)
Problemas
Centralizado 3 2 Queda do coordenador
Descentralizado 3mk, k = 1,2... 2 m Inanição, baixa eficiência
Distribuídos 2 (n – 1) 2 (n – 1) Queda de qualquer processo
Token Ring 1 a ∞ 0 a n - 1 Ficha perdida; processo cai
Algoritmos de Eleição de Líder
• Muitos Sistemas Distribuídos têm 
por base o modelo cliente-servidor, 
com um servidor/coordenador (líder) 
e muitos clientes.
• Questão:
–Como selecionar o líder 
dinamicamente?
Algoritmos de Eleição de Líder
• Outras questões/observações:
– Se o líder for fixo, indicado manualmente, temos uma 
solução centralizada, com um único ponto de falha.
– Falhando um líder, se tivermos um método para eleger 
dinamicamente um novo líder, será esta solução 
centralizada ou distribuída?
– Será que uma solução inteiramente distribuída, i.e. sem 
coordenador,
– sempre mais robusta que qualquer solução 
centralizada/coordenada?
• Para determinar o coordenador:
–Assumir que todos os nós têm um ID único;
–Necessário concordar qual dos processos 
ativos tem o maior ID;
Algoritmo do Valentão
• Ideia base:
–Inventado por Garcia-Molina (1982). 
Quando qualquer processo nota que o 
coordenador não esta mais 
respondendo às requisições, ele inicia 
uma eleição.
Continuação...
• Existem três tipos de mensagens:
– ELECTION: anúncio de eleição;
–ANSWER: resposta à eleição;
–COORDINATOR: anúncio do coordenador 
eleito;
Algoritmo do Valentão
• Algoritmo:
– Verificando por timeout que o coordenador falhou, P 
inicia uma eleição enviando uma mensagem ELECTION 
para os processos com identificadores maiores que o 
seu;
– Se ninguém responde (msg ANSWER), então P ganha a 
eleição e anuncia-se como líder (envia msg
COORDINATOR a todos processos);
– Se pelo menos um processo responder, esse inicia 
nova eleição. A tarefa de P termina;
Algoritmo do Valentão
a) O processo 4 convoca uma 
eleição;
b) Os processos 5 e 6 
respondem e mandam 4 parar;
c) Agora, cada um, 5 e 6, 
convoca uma eleição;
d) O processo 6 manda 5 
parar;
e) O processo 6 vence e 
informa a todos;
Algoritmo de Eleição em Anel
• Ideia base:
–Processos organizados num anel lógico. O 
processo com maior identificador deve ser 
eleito coordenador;
• Existem dois tipos de mensagens:
– ELECTION: anúncio de eleição;
–COORDINATOR: anúncio do coordenador 
eleito;
Algoritmo de Eleição em Anel
• Algoritmo:
– Verificando por timeout que o coordenador falhou, P inicia 
uma eleição enviando uma mensagem ELECTION, com o 
seu ID, para o seu sucessor. Se o sucessor estiver em baixo, 
envia ao seguinte;
– Cada processo adiciona o seu ID à mensagem ELECTION e 
encaminha-a para o processo seguinte do anel;
– A eleição termina quando a mensagem chega novamente a 
P. Este envia de seguida uma mensagem CORDINATOR 
através do anel com informação sobre todos processos 
activos. O coordenador é o processo com maior 
identificador.
Algoritmo de Eleição em Anel
• O algoritmo funciona mesmo se dois processos 
iniciarem a eleição quase em simultâneo:
Algoritmo de Eleição em Anel
• Ideia base:
–Orientado para sistemas de grande escala 
com base em redes peer-to-peer;
–A ideia é ter vários superpares a atuarem 
como coordenadores;
Continuação...• Selecionar superpares tal que:
– Nós normais tenha latência baixa no acesso a 
superpares;
– Os superpares estão distribuídos pela camada de 
rede;
– Os superpares são apenas uma fracção pré-
definida dos pares;
– Cada superpar não deverá precisar de servir mais 
do que um número determinado de nós normais;
Algoritmo de Eleição em Anel
• Solução baseada em DHT:
–Fixar parte do espaço de ID para 
superpares.
–Caso se use identificadores de m-bits, 
reserva-se os. bits mais à 
esquerda para os superpares.
1. Quais as finalidade da exclusão mútua.
2. Explique o método de exclusão mútua centralizado 
3. Explique o método de exclusão mútua distribuído.
4. Explique o funcionamento do algoritmo do 
valentão.
5. Explique o funcionamento do algoritmo Eleição do 
líder.
6. Explique o funcionamento do algoritmo em anel.
Dúvidas