Algoritmo de Maekawa
Para Maekawa, assim como para Ricart & Agrawala, um processo que deseja entrar na seção crítica deve obter permissão dos outros processos, mas não todos, através da troca de mensagem. 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.
Dado um conjunto com N processos, é construído N subconjuntos com √N processos em cada. O ideal é que cada subconjunto tenha o máximo de diversificade posível e que um processo esteja em pelo menos 2, ou idealmente em √N, subconjuntos. A interseção entre 2 subconjutos de processos não pode ser vazia. Cada processo tem um voto e só pode votar uma vez para um processo candidato acessar a seção crítica. O estado do voto é vísivel a todos os processos de seus subconjutos, o voto é reiniciado segundo uma lógica descrita mais a baixo. Deste modo todas as propriedades de exclusão mútua são atendida.
Na imagem abaixo é ilustrado um cenário para exemplificar como funciona a construção dos grupos. Existem 6 processos que participam da computação distribuída e são possíveis candidatos a acessar a seção crítica. O número de subgrupos N vai ser igual ao total de processos existentes, ou seja, serão 6 grupos. Para a quantidade de processo em cada grupo é utilizado o teto de √N, que vai ser 3. Com intuito de manter os grupos o mais diversificado possível, de forma que sempre a interseção entre quaisquer 2 grupos seja 1 processo, foi contruídos os grupos que aparecem na tabela da imagem.
Na imagem, o processo 4 quer acessar a sesão crítica, então ele vai selecionar um dos 6 subgrupos que tenha ele como participante. O grupo selecionado para exemplo foi o G4(0, 2, 4). Logo, o Processo 4 deve mandar mensagem para os processos 0 e 2 para ganhar permisão de acesso a seção crítica. A lógica de resposta e manutenção do voto, é explicada numa seção mais abaixo.
Cada processo possui a seguinte estrutura:
- Um de lamport que vai fixado ao identificador de processo no envio de mensagem, na forma < Pi, T>;
- Uma , que diz a ação do processo com relação a seção crítica;
- Um para guardar mensagens de acesso, que segue a lógica FIFO (First-in First-out);
- Uma variável de voto, que pode ser: TRUE(já votou) ou FALSE(não votou);
Passe o indicador do mouse sobre cada botão acima para verificar na imagem seu respectivo componente;
| Grupos | Processos |
|---|---|
| G1 | {1,2,3} |
| G2 | {0,3,4} |
| G3 | {0,5,6} |
| G4 | {0,2,4} |
| G5 | {1,4,6} |
| G6 | {2,5,6} |
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 que deseje entrar na seção crítica deve enviar k mensagens, um multicast, para os processos de um dos subconjuntos que ele pertença, para isso presume-se que cada processo tenha um canal de comunicação com os outros processos. Tendo todas as k respostas do multicast, todos os votos dos processos pertencentes àquele subconjunto, ele poderá acessar a seção crítica.
Um fator importante nesse algoritmo é a váriavel de estado do processo e seu voto, pois eles são os fatores que vão orientar as decisões do processo. A variável de estado 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.
O processo Pi que deseja entrar na seção crítica vai mudar sua variável de estado para WANTED e enviar k mensagens para um subgrupo que ele pertença, e se obtiver todas as k respostas, ele receberá acesso. A lógica de resposta dos processos é descrita abaixo.
- Se o processo que receber a mensagem estiver com seu estado HELD ou seu voto como TRUE, então a mensagem de Pi será enfileirada.
- Se se estado for WANTED e seu voto FALSE, ele responde e muda seu voto para TRUE se seu relógio lógico for maior que o relógio lógico de Pi. Se for menor, ele enfileirará a mensagem.
- Se um processo receber mensagem de liberação da seção crítica, ele remove o nó mais superior da sua fila, muda seu voto para TRUE e envia seu voto para o processo destino.
- Quando um processo liberar a seção crítica, ele envia uma mensagem de liberação para os processo votantes de seu subgrupo.
No algoritmo abaixo os processos PO, P1, P2 e P3 possuem os seguintes subgrupos: G1[P0, P1], G2[P1, P2] e G3[P1, P3]. Para testar escolha um dos dois cenários iniciais para executar o algoritmo e depois aperte PLAY, para executar iterativamente, para avançar no algoritmo aperte AVANÇAR e para reiniciar aperte RESET.
- 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;