Algoritmo de Ricart & 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.
Seja P, um conjunto de processos Pi, com 0 ≤ i < n, onde n é o número de processos participantes da computação, cada processo Pi deve possuir um de Lamport para anexar na mensagem, uma local para armazenar mensagem recebidas e uma . Toda enviada pelos processos segue o formato < T,Pi> , onde T é o valor do relógio lógico do processo e Pi é o identificador do processo. Na imagem abaixo é possível conferir os componentes deste algoritmo e onde foram alocados para a prototipação.
Um fator importante nesse algoritmo é a váriavel de estado, pois ela é o primeiro fator que vai orientar as decisões do processo. A variável diz sua intenção em relação a seção crítica, sendo de 3 tipos:
- RELEASED, o processo está fora dela e não deseja acessá-la.
- WANTED, o processo deseja acesso.
- HELD, o processo está acessando.
Como previamente descrito, quando um processo Pi deseja entrar na seção crítica ele muda sua variável de estado para WANTED e envia um multicast para os demais processos, e se obtiver as resposta de todos os processos, ele receberá acesso e passará seu estado para HELD. A lógica de resposta dos processos é descrita abaixo.
- Se o processo que receber a mensagem estiver com seu estado RELEASED, então ele responderá a mensagem de Pi.
- Se o processo que receber a mensagem estiver com o estado WANTED, ele vai comparar o seu relógio lógico local, com aquele que veio marcado na mensagem. Se for maior, Tlocal > T mensagem, então ele responderá a mensagem. Se for menor, Tlocal < T mensagem, então ele enfileirará a mensagem na sua fila, para responder mais tarde.
- Se o processo que receber a mensagem estiver com o estado HELD, ele enfileirará a mensagem.
Todo processo que terminar de acessar a seção crítica muda o estado de HELD para RELEASED e irá responder todas as mensagens que tem em sua fila. Essa fila de mensagem, usa a lógica FIFO (First in - First out), então as mensagens mais antigas serão respondidas primeiro. Desta forma, se dois ou mais processos solicitarem acesso a seção crítica simultaneamente, aquele que tiver o menor tempo lógico receberá as N-1 respostas e acessará antes.
Teste o algoritmo na animação abaixo, escolha um dos dois cenários iniciais para executar.
- Cenário 1: Pelo menos 1 processo com estado WANTED e o restante com RELEASED;
- Cenário 2: Pelo menos 1 processo com estado HELD e o restante, ou com WANTED, ou com RELEASED;
Para executar iterativamente aperte AVANÇAR e para resetar aperte RESET. Para seguir à próxima animação, veja mais abaixo.