Sistemas Distribuídos
Aula 09 – Sincronismo e Deadlock
Prof. Hélio de Sousa Lima Filho
([email protected])
Algoritmos
para Eleição
• Muitos processos distribuídos requerem
um processo para agir como coordenador,
inicializador ou alguma outra atividade em
especial
• O objetivo do algoritmo de eleição é
garantir a democracia.
– Quando uma eleição termina, todos os
processos concordam com a decisão de
quem é o novo coordenador.
Sistemas Distribuídos
2
Algoritmos
para Eleição
• Se todos os processos são exatamente do
mesmo tipo, sem nenhuma característica que
os distingam dos demais, não existe
nenhuma forma de selecionar um deles em
especial.
• Assume-se que cada processo possui um
endereço único (por exemplo seu endereço
de rede), e os algoritmos de eleição tentam
localizar o processo com o maior número e
designá-lo como coordenador
Sistemas Distribuídos
3
Algoritmos para Eleição
Algoritmo Bully
• Quando um processo (P) nota que o
coordenador não está mais respondendo
a uma requisição, ele inicia uma eleição:
– P envia uma mensagem de ELECTION para
todos os processos com números maiores
que o seu;
– Se nenhum responde, P ganha a eleição e se
torna coordenador
– Se um processo com um número maior
responde, ele assume o processo de eleição
Sistemas Distribuídos
4
Algoritmos para Eleição
Algoritmo Bully
• Esse procedimento termina com um
processo vencedor, o qual avisa a todos
os outros que ele é o novo coordenador
• Se o processo que era coordenador e
havia falhado retornar, ele inicia uma nova
eleição.
– Se acontecer de seu número ser maior, ele
irá vencer a eleição e retornará a ser o
coordenador
Sistemas Distribuídos
5
Algoritmos para Eleição
Algoritmo Bully
2
0
7
Election
4
1
5
Sistemas Distribuídos
6
3
6
Algoritmos para Eleição
Algoritmo Bully
2
0
7
6
4
1
5
Sistemas Distribuídos
3
7
Algoritmos para Eleição
Algoritmo Bully
2
0
7
6
4
1
5
Sistemas Distribuídos
3
8
Algoritmos para Eleição
Algoritmo Bully
2
0
7
6
4
1
5
Sistemas Distribuídos
3
9
Algoritmos para Eleição
Algoritmo Bully
2
0
7
6
4
1
5
Sistemas Distribuídos
3
10
Algoritmos para Eleição
Algoritmo em Anel
• Algoritmo baseado na utilização de anel, porém
sem token
• É assumido que os processos estão fisicamente
ou logicamente ordenados, isto é, cada processo
sabe quem é o seu sucessor
• Quando um processo percebe que o coordenador
não está funcionando, ele constrói uma
mensagem ELECTION contendo seu número e
envia essa mensagem para o seu sucessor
• Se o sucessor estiver desativado, o emissor salta
para o próximo sucessor
Sistemas Distribuídos
11
Algoritmos para Eleição
Algoritmo em Anel
• A cada passo o emissor adiciona o número
dos processos na lista de mensagem
• Quando a mensagem dá a volta no anel e
retorna ao processo que iniciou a eleição, o
novo coordenador é determinado (o processo
com mais alto número na lista) e esta
mensagem é retirada do anel
• Uma nova mensagem denominada
COORDINATOR é gerada informando quem
é o novo coordenador
Sistemas Distribuídos
12
Algoritmos para Eleição
Algoritmo em Anel
6
5
7
0
4
3
2
2
Sistemas Distribuídos
1
13
Algoritmos para Eleição
Algoritmo em Anel
6
5
7
0
4
2, 3
3
2
2
Sistemas Distribuídos
1
14
Algoritmos para Eleição
Algoritmo em Anel
6
5
7
2, 3, 4
0
4
2, 3
3
2
2
Sistemas Distribuídos
1
15
Algoritmos para Eleição
Algoritmo em Anel
6
5
7
2, 3, 4, 5
2, 3, 4
0
4
2, 3
3
2
2
Sistemas Distribuídos
1
16
Algoritmos para Eleição
Algoritmo em Anel
6
5
7
2, 3, 4, 5
2, 3, 4
Não
responde
0
4
2, 3
3
2
2
Sistemas Distribuídos
1
17
Algoritmos para Eleição
Algoritmo em Anel
6
5
7
2, 3, 4, 5
2, 3, 4
2, 3, 4, 5, 6
0
4
2, 3
3
2
2
Sistemas Distribuídos
1
18
Algoritmos para Eleição
Algoritmo em Anel
6
5
7
2, 3, 4, 5
2, 3, 4
2, 3, 4, 5, 6
0
4
2, 3, 4, 5, 6, 0
2, 3
3
2
2
Sistemas Distribuídos
1
19
Algoritmos para Eleição
Algoritmo em Anel
6
5
7
2, 3, 4, 5
2, 3, 4
2, 3, 4, 5, 6
0
4
2, 3, 4, 5, 6, 0
2, 3
3
2, 3, 4, 5, 6, 0, 1
2
2
Sistemas Distribuídos
1
20
Algoritmos para Eleição
Algoritmo em Anel
6
5
7
6
6
6
0
4
6
6
3
6
2
6
Sistemas Distribuídos
1
21
Deadlock
• Um conjunto de processos está em
deadlock se cada processo do conjunto
está aguardando por um evento que
somente um outro processo do mesmo
conjunto pode causar
Sistemas Distribuídos
22
Deadlock
• Exemplo:
– dois processos querendo imprimir um arquivo
grande armazenado num DVD
– O processo A requisita permissão para utilizar a
impressora e recebe autorização
– O processo B, em seguida, requisita utilizar o
DVD e também consegue permissão
– O processo A pede para utilizar o DVD mas a
requisição é negada até que B libere
– O processo B pede para utilizar a impressora
mas a requisição é negada até que A libere
Sistemas Distribuídos
23
Deadlock
• Recursos
– Um recurso é qualquer dispositivo de hardware ou
informação que pode ser utilizado por somente um
único processo em um determinado instante de
tempo
– Podem ser:
• Preemptivos
– Podem ser retirados dos processos sem prejuízos
– Exemplo: memória
• Não-preemptivos
– Não pode ser retirado do processo sem causar falhas no
processamento
• Normalmente, tem-se deadlocks com recursos
não-preemptíveis.
Sistemas Distribuídos
24
Deadlocks
Condições de ocorrência
• Exclusão mútua
– Cada recurso só pode estar associado a um
processo em um determinado instante
• Posse e espera
– Processo de posse de recursos podem
requisitar por novos recursos
Sistemas Distribuídos
25
Deadlocks
Condições de ocorrência
• Não-preempção
– Recursos previamente garantidos não podem
ser retirados de um processo
• Espera circular
– Deve existir uma cadeia circular de 2 ou mais
processos, cada um aguardando por recursos
que estão alocados para membros de cada
cadeia
Sistemas Distribuídos
26
Deadlocks
Abordagens para tratamento
•
•
•
•
•
Algoritmo do Avestruz
Prevenção de deadlock
Impedimento de deadlock
Detecção de deadlock
Recuperação de deadlock
Sistemas Distribuídos
27
Deadlocks
Abordagens para tratamento
• O algoritmo do Avestruz é uma boa
abordagem para a maioria dos sistemas
gerais, tais como automação de
escritórios, controle de processos, etc.
• A detecção e recuperação também são
abordagens bastante utilizadas,
principalmente porque prevenir e evitar
são abordagens mais complexas
Sistemas Distribuídos
28
Deadlocks
Abordagens para tratamento
• A prevenção também é possível, embora
mais complexa do que as formas de
prevenção utilizadas em sistemas com um
único processador
• As abordagens de impedimento, em
geral, não são utilizadas em sist.
distribuídos, principalmente porque é
muito difícil saber quais recursos que cada
processo irá eventualmente precisar
Sistemas Distribuídos
29