Exclusão Mutua

Página Web para Ensino-Aprendizagem de Algoritmos de Exclusão Mútua Utilizando Explorable Explanations para Sistemas Distribuídos



Exclusão Mútua

Em um sistema distríbuido é necessário a coordenação das atividades dos processos, através da troca de mensagens, devido a existência de recursos compartilhados.

A Exclusão Mútua garante que os processos acessem a Seção Crítica (recursos compartilhados), efetuem suas operações e saiam da mesma de forma a não compremeter dados ou recursos comuns ao sistema, liberando-a para acesso de outros processos. A Exclusão Mútua deve respeitar 3 propriedades fundamentais:

  • Segurança: No máximo um processo por vez pode ser executado na sessão crítica;
  • Subsistência: As requisições para entrar e sair da seção crítica devem ter sucesso;
  • Ordenação: Se uma requisição para entrar na seção aconteceu antes de outra, então a entrada na seção crítica é garantida nessa ordem;

Algoritmos de Exclusão Mútua usam técnicas de trocas de mensagens para efetuar a coordenação desses acessos obedecendo as propriedades descritas.



Servidor Central

Todo processo P que quiser acessar a seção crítica deverá solicitar um token ao servidor central. O gerenciamento desse token é feito pelo servidor central através da troca de mensagens com os processos.

Servidor Central


Anel

Este algoritmo é o mais simples para garantir a exclusão mútua em um sistema distríbuido. Ele utiliza a topologia em Anel, onde cada processo P participante da computação precisa somente de um canal de
comunicação com o processo seguinte.
Deste modo, os processos formam um "laço" circular de comunicação, onde as mensagens são transmitidas de maneira unidirecional.

Anel


Ricart e Agrawala

Este algoritmo é usado para garantir exclusão mútua entre N processos pares em um sistema distríbuido. Muito similar aos algoritmos de eleição de líder, um vez que um processo P que deseje entrar na seção crítica
deve enviar uma mensagem para todos os processos, um Multicast.
Para isso presume-se que cada processo tenha um canal de comunicação com os outros processos. Tendo todas as respostas do multicast ele poderá acessar a seção crítica. Ou seja, um processo só acessa a
seção crítica quando todos "permitirem", respondendo a mensagem do requisitante.

Ricart e Agrawala


Maekawa

Maekawa propõe que é necessário uma quantidade k de permisões, onde k < N e N é o número total de processos, de um subconjunto dos processos para ingressar na seção crítica. Esse subconjunto dos processos
deve conter o processos requisitante, ou seja, nas k permisões necessárias, uma é a resposta dele mesmo. Neste algoritmo o processo que deseja acesso á seção crítica é chamado de "candidato" e precisa de k
"votos" para acessá-la.

Maekawa

Sobre

Explorable Explanations (EEs) foram forjadas por um grupo de pessoas com o intuito de reunir textos, imagens, simulações, animações, etc., de forma que um aprendiz possa ler um texto e interagir ao mesmo tempo. Nosso projeto contém um conjunto de EEs abordando conceitos/algoritmos relacionados à disciplinas de Sistemas Distribuídos, nessa pagina só está os algoritmos de exclusão mútua.