Aula 3 - Sistemas Distribuídos

Sistemas Distribuídos - Sincronização

Sistemas distribuídos em geral contém muitos processos que colaboram para alcançar uma meta comum. Eventos em um nodo do sistema distribuído depende de eventos de outros nodos. Determinar a ordem em que estes eventos ocorrem é muito difícil devido aos atrasos imprevisíveis que ocorrem em uma rede distribuída.

Os fatores que contribuem para que este atraso ocorra são:

• Número de processadores desconhecido;
• Topologia de rede desconhecida;
• Entradas independentes em diferentes locais;
• Vários programas executados de uma só vez, começando em tempo diferente e operando a velocidade diferente;

Fatores que dificultam a sincronização:

• Não determinismo dos processadores;
• Tempos de envio de mensagem incertos;
• Desconhecimento da ordenação das mensagens;
• Falhas de processadores e comunicação;

Exclusão Mutua em Sistemas Distribuídos

Um processo é escolhido como coordenador, ele é responsável por controlar entrada de processos em regiões críticas. Quando um processo deseja acessar uma região crítica, ele envia uma mensagem ao coordenador, que por sua vez, irá verificar se a região está desocupada e pode ser acessada.

Se a região crítica está ocupada com outro processo, o coordenador não responde ao pedido. Caso o contrário o coordenador permite o acesso a região crítica.

Características

• Garante exclusão mútua;
• Nenhum processo espera indefinidamente (Não há starvation – situação a qual alguns processos são repetidamente preteridos, enquanto outros ficam com acesso ao recurso desejado)
• É fácil de ser implementado;
• Coordenador é um ponto único de falha;
• Coordenador pode representar um gargalo em termos de desempenho.

Algoritmo distribuído para Exclusão Mútua

Para evitar os gargalos de um coordenador temos o algoritmo de exclusão mútua que funciona da seguinte forma:

Quando um processo quer entrar em uma região crítica, ele constrói uma mensagem contendo o nome da região crítica que ele quer acessar, seu número de processo e o tempo corrente. Ele envia essa mensagem para todos os outros processos.

Quando a mensagem chega ao destino processo destino ele pode tomar uma das seguintes decisões

Se o receptor não está na região crítica e não quer acessá-la, ele devolve a mensagem OK para o emissor.

Se o receptor está na região crítica, ele não responde e enfileira o pedido.

Características

• Garante exclusão mútua;
• Não há Starvation;
• Gera mais tráfego na rede;
• Não há um ponto único de falha e sim N pontos de falha ( onde N é o número de processos);
• Gerência do grupo é mais difícil;
• Todos os processos estão envolvidos em todas as decisões e cada processo representa um gargalo em potencial;

Algoritmo de Exclusão Mútua – Anel

Através de software, um anel lógico é construído onde a cada processo é atribuído um número no anel, onde cada processo conhece o processo sucessor.

Quando a rede é inicializada, o processo 0 recebe um token. Este token circula pela rede onde é passado de um processo ao outro em mensagens ponto a ponto.

Quando um processo recebe o token, ele verifica se está querendo acessar alguma região crítica. Se ele necessita, ele acessa e passa o token para o processo vizinho assim que ele finalizar o acesso a região crítica.

Se um processo recebe um token mas ele não deseja acessar nenhuma região crítica, ele libera o token imediatamente ao processo vizinho.

Problema com este algoritmo

Falha dos processos: Se um dos componentes do anel falhar causa sua quebra.

Perda do token: O tempo entre os aparecimentos do token é limitado, sendo difícil determinar sua perda.

 

Deadlock

“Um conjunto de processos está em Deadlock se cada processo no conjunto  está esperando por um evento que apenas outro processo do conjunto pode gerar” (Tanenbaum)

Um conjunto de processos fica bloqueado, cada um a espera de um recurso que o outro detém.

Nos sistemas distribuídos podem ocorrer dois tipos de Deadlocks:

Deadlock de comunicação: Quando um processo A está tentando acessar uma mensagem para o processo B que está tentando uma mensagem para o processo C que está tentando uma mensagem para o processo A.

Deadlock de Recursos: Ocorre quando os processos estão lutando para uso exclusivo de dispositivos de I/O, arquivos ou outros recursos.

Condição de Exclusão Mútua: Para os recursos e processos envolvidos, apenas um processo pode acessar um determinado recurso em um dado momento.

Condição de Obtenção e Espera: Para os recursos e processos envolvidos, cada vez que um processo tenta acessar um recurso, ele, ou obtém o recurso ou entra em estado de espera até que o mesmo seja liberado pelo processo que obteve anteriormente.

Condição de Recursos Não Preemptivos: Para os recursos e processos envolvidos, quando um processo requisita um recurso já possuído por outro processo, o processo que o possui não pode perder a posse do recurso para aquele que requisitou o recurso sem que ele o libere espontaneamente.

Condição de Espera Circular: Para um conjunto de processos, cada processo no conjunto está esperando por um evento que apenas outro processo do conjunto pode gerar.

As quatro estratégias para tratamento de Deadlock

Quanto a escolha das estratégias deve ser feita baseada nos requisitos do sistema, isto é, naquele que o sistema suporta em termos de custos ou restrições.

As estratégias são as seguintes:

Ignorar o problema: Como em alguns sistemas a ocorrência de Deadlocks acarreta apenas problemas toleráveis, ou a freqüência em que este evento ocorre torna mais barato uma recuperação manual do sistema a um estado funcional. Estratégia utilizada na maioria dos Sistemas Operacionais, incluindo UNIX.

Detectar e Recuperar: Esta estratégia consiste em detectar a ocorrência de um Deadlock e uma vez que se tenha atingido este estado, tomar alguma medida para recuperar o sistema.

Tipicamente a solução de recuperação do sistema é matar um dos processos pertencentes ao conjunto ao conjunto de processos Deadlock.

Muitas vezes essa solução não é muito desejável e a detecção dos Deadlocks pode envolver um custo adicional considerável ao sistema.

Evitar: Detectar dinamicamente se algum conjunto de requisições por recursos levará a um Deadlock, e caso isso venha a ocorrer, mudar a ordem das requisições de forma que não ocorra o Deadlock.

Prevenção: Construir um sistema de forma que não seja possível atingir o estado de Deadlock.

A maneira mais simples de fazer isso é obrigar que cada processo adquira todos os recursos necessários antes de iniciar o processamento, assim eliminando a condição de espera circular. Outra forma de evitar o Deadlock é causar a preempção de recursos, de forma a quebrar o requisito de não preempção.