Notas de Aula - MAC 5755 - Sistemas Operacionais Distribuídos

Aula 11 - 19/9/2001

Impasses (deadlocks)

• Fig. 5.5. Galli
• Só ocorre impasse se 3 coisas acontecem:
1. Exclusão mútua
2. Alocação não-interrompível dos recursos (non-preemptive allocation)
3. Espera cíclica, i.e., um ciclo no grafo de processos e recursos
• Como lidar com impasses?
1. Previnir
1. Permitir um único recurso simultâneo por processo (não realista)
2. Pré-alocação de todos os recursos (ineficiente)
3. Numerar recursos e solicitá-los sempre em ordem (evita ciclos mas é difícil de implementar na prática)
4. Dar prioridades aos processos. Se um processo de prioridade mais alta pede acesso a um recurso reservado para um processo de prioridade mais baixa, o último é obrigado a liberar os recursos
2. Evitar
• Processos apresentam todas as suas necessidades a priori; algoritmos NP-completos determinam se é possível alocar todos os recursos sem impasse
• Problemas:
• muito ineficiente
• processos nem sempre sabem determinar a priori todos os recursos de que necessitarão
3. Ignorar
• Não se faz nada, ignora-se o problema
• É a solução adotada pela maior parte dos sistemas tradicionais (UNIX, Windows)
• Usuários detectam um problema e começam a matar os processos problemáticos manualmente até que o sistema volte a funcionar
4. Detecção
• Algoritmo centralizado ou
• algoritmo de Chandy, Misra, Haas
• Usa mensagens sonda (probing messages) sempre que um processo não consegue receber um recurso ou quando ocorre um timeout no seu pedido do recurso.
• sonda contém:
  1. identificação do processo bloqueado
  2. identificação do processo emissor da mensagem
  3. identificação do processo receptor da mensagem
• Descrição: livro da Galli, pag. 123. Explicação através de desenho.

Algoritmos de Eleição em Sistemas Distribuídos

• (referência: seção 3.3 do Tanenbaum)
• Muitos sistemas distribuídos precisam de um coordenador, iniciador ou seqüenciador.
• Exemplo: coordenador no algoritmo de exclusão mútua.
• Critério arbitrário: escolhemos o processo de número mais alto (onde número do processo inclui o endereço da máquina na qual ele está sendo executado).
• Supomos que:
• todos processos do grupo fazendo a eleição conhecem o número de todos os participantes da eleição
• não sabemos quais dos processos estão ativos e quais estão fora do ar
• Objetivo: ao término da eleição, todos os processos ativos escolhem um único processo para ser o coordenador.
• Algoritmo do Manda-chuva (Bully Algorithm)
• Garcia-Molina (1982)
• quando um processo P detecta que o coordenador não está mais respondendo, ele convoca uma nova eleição:
• P manda uma mensagem ELEIÇÃO para todos os processos com número mais alto que o seu
• se ninguém responde, P ganha e se torna o novo coordenador
• se algum processo responde, o processo que respondeu assume a eleição e o trabalho de P acabou
• a qualquer momento, um processo Q pode receber uma mensagem ELEIÇÃO de um de seus nós mais baixos P
• Q responde com uma mensagem OK para P
• Q inicia uma nova eleição (a não ser que já esteja organizando uma)
• em um certo instante, todos os processos desistem de concorrer com exceção de um deles que se nomeia coordenador
• o vitorioso manda uma mensagem COORDENADOR para todos os participantes anunciando que ele é o vitorioso
• se um processo que estava fora do ar volta a funcionar, ele inicia uma nova eleição
• Figura 3.12, pag. 142 do Tanenbaum
• Problemas:
• muitas mensagens
• como identificar se um processo está fora do ar?
• se um processo demora prá responder, ele está fora do ar ou está ocupado?
• e se eu considero que um processo está fora do ar e daí recebo uma resposta dele?
• Algoritmo em Anel
• (não usa bastão)
• processos são ordenados (fisicamente ou) logicamente; cada nó conhece o anel todo
• quando um processo P detecta que o coordenador não está mais respondendo:
• P manda uma mensagem ELEIÇÃO (contendo o seu número de processo) para o seu sucessor
• se o sucessor estiver fora do ar, manda para o sucessor do sucessor e assim por diante
• em cada passo do anel, cada processo adiciona o seu número na mensagem que está circulando
• em um certo instante, a mensagem volta para o nó P que a criou
• esse nó verifica a lista de processos e identifica o novo coordenador
• P coloca uma mensagem COORDENADOR no anel contendo o número do coordenador e os membros do novo anel
• quando a mensagem percorre todo o anel, ela é retirada do mesmo
• Fig. 3.13, pag. 143 do Tanenbaum
• Problemas:
• obriga todos os nós a conhecerem todo o anel -> não é muito escalável
• se alguém que estava fora do ar volta a ativa, como reintegrá-lo?
• se dois nós iniciam a eleição simultaneamente -> não é um grande problema pois, provavelmente, ambas eleições terão o mesmo resultado

Referências

Capítulo 5 do Galli, seções 3.3 e 3.5 do Tanenbaum e capítulo 6 do Sinha