Relatório
1. Introdução
A garantia da exclusividade de acesso ou de execução de um recurso compartilhado é uma premissa importante em cenários de processos concorrentes. A exclusão mútua visa controlar o compartilhamento de tais recursos, determinando estratégias para que tais recursos possam ser adequadamente controlados. Nesse contexto, um recurso (que, na verdade corresponde a um trecho de código) é designado como Região Crítica (RC). Entretanto, em um cenário distribuído, é imperativo que todos os processos cheguem a um acordo sobre a ordem de acesso à RC. Ou seja, todos os processos precisam interagir e a partir dessa interação sincronizar seus acessos ao recurso que se mantém compartilhado. No entanto, quaisquer soluções de exclusão mútua distribuída precisam considerar, minimanente, três propriedades: Safety (Segurança): no máximo, um processo executa a cada momento na RC, Liveness (Progressão): todo pedido de entrada e/ou saida da RC é atendido em algum momento e Fairness (Justiça): em que todos os processos têm a mesma chance de acessar a RC, incorrendo, dessa forma, em não priorização.
O algoritmo de Ricart-Agrawala é uma categoria de solução baseada em permissões (ou replies), sendo uma simplificação da proposta de Lamport, por eliminar estruturas tais como o vetor de timestamps e a necessidade de lidar o canal de comunicação do processo com base em ordenação FIFO. Além disso, as permissões não necessitam mais ser baseadas em mensagens de release, ou seja, um processo só executa a RC se obtiver as permissões (designadas como replies) de todos os demais.
2. Objetivos
O propósito desse trabalho é a implementação de uma solução de exclusão mútua distribuída baseada no algoritmo de Ricart-Agrawala. Para a implementação é utilizada a biblioteca de recursos de simulação de eventos discretos SmPL. Para a avaliação dos resultados obtidos foram escolhidos dois cenários principais de execução: com 2 e 3 nodos(ou processos). Em cada caso são fornecidos os instantes de requisição de entrada na RC. A partir do registro dessas intenções, eventos de envio e recepção de mensagens (que permitem a construção das permissões) são gerados. As permissões, no entanto, são baseadas em um relógio lógico global, implementado para ordenar as requisições. Tais eventos, de acordo com o requisitado, são programados para ocorrer conforme uma distribuição aleatória de tempo (de 1 a 5 unidades de tempo). Ao final, todos os processos deverão ter obtido permissão para acesso à RC.
3. Sobre a implementação
A implementação dos objetivos traçados anteriormente é baseada nas estruturas de dados apresentadas na Figura 1. O tipo 
é usado tanto para
registrar as mensagens que são enviadas por algum nodo como para facilitar lidar com as respostas. Dessa forma, quaisquer requisições como quaisquer
respostas têm como ser analisadas. Além dessas estruturas que permitem lidar com as atividades de comunicação entre os nodos, tem-se o tipo 
, cujo
objetivo é registrar dados que facilitam as decisões de cada nodo.
Figura 1. Estruturas de dados
No entanto, para lidar com a simulação da execução do algoritmo, um aspecto é vital e norteador para as decisões de implementação: a escolha dos eventos.
Eventos
Como decisão de implementação foram escolhidos 6 possíveis eventos:
- BROADCAST Esse evento permite o escalonamento (conforme os tempos informados no início da execução) de mensagens de requisição de entrada na RC enviadas para todos os outros nodos do ambiente simulado. Para que os tempos e o cenário sejam identificados, o vetor tempos armazena os respectivos tempos de cada nodo participante da simulação. Para cada ocorrência do evento BROADCAST, ao nodo selecionado é associado um tempo que permite que cada processo incremente seu próprio timestamp sempre que uma requisição, envio ou recebimento de resposta ocorrem. Dessa forma, cada processo controla seu relógio lógico, não exigindo, portanto, que um único relógio oriente as decisões, já que o que importa não é a obediência a um relógio real, mas, a ordem de execução dos eventos. Além disso, como descrito na Figura 2, a cada momento que um processo requisita sua entrada na RC, automaticamente tem seu estado alterado para REQ_RC e dispara essa intenção para os demais. Sempre que uma requisição é disparada, ela precisa ser registrada, de forma que, possa, posteriormente ser avaliada e, consequentemente para que decisões sobre a entrada e saída da RC sejam tomadas. Esse registro é feito pela função nodoReqRC() apresentada na Figura 2.
- REQUEST Um nodo que requer sua entrada na RC apenas o faz se obtém permissões de todos os outros nodos participantes. Nesse caso, o evento REQUEST coordena as distintas mensagens que chegam e permite lidar com o controle das permissões. Nesse contexto, duas avaliações são necessárias. A primeira é, a partir da identificação do originador da mensagem, averiguar se o receptor da mensagem ja se encontra na RC. Em caso positivo, uma pendência precisa ser registrada. Caso contrário, um nodo que possua timestamp menor torna-se o candidato a receber uma mensagem de resposta. Entretanto, caso existam dois nodos com mesmo timestamp, então, deve-se considerar o envio da resposta para aquele que estiver antes na ordem lexicográfica.
- REPLY Como parte crucial da proposta de Ricart e Agrawala está a coordenação das permissões. Processos (ou nodos) recebem tais permissões por meio de repostas (replies) que denotam sua anuência do ingresso de um processo na RC. O evento REPLY, conforme descrito na Figura 3, resgata da lista de respostas já registradas no vetor rep, aquela que deve ser enviada especificamente para o nodo que foi escolhida para executar o evento.
- ENTER_RC Após o evento ter condições de identificar se um processo possui permissões suficientes para ingressar na RC, essa ação coordenada pelo evento ENTER_RC. Entretanto, como premissa básica da Exclusão Mútua e atendendo à propriedade Safety, apenas um processo usufruirá a RC por vez. Entretanto, também considerando outra propriedade básica, os processos que requisitaram e não puderam entrar na RC, em algum momento o farão. O propósito desse evento é simplesmente, simular a permanência por uma unidade de tempo de um processo na RC.
- LEAVE_RC A saída da RC envolve não somente o escalonamento da saída definitiva da simulação (EXIT), mas, também um "limpeza" das pendências que chegaram ao processo durante os instantes em que não pode responder às requisições. Conforme descrito na Figura 6, as ações decorrentes desse evento vão de limpar as permissões pendentes a efetivamente decrementar a quantidade de processos que estão usando a RC.
- EXIT Por fim, o evento EXIT é escalonado tão logo o simulador tenha completado sua lista de eventos pré-agendados e de retirada completa de todos os processos da RC.
Figura 2. Difusão das requisições de acesso a RC
Figura 3. Coordenação do envio de uma resposta a um processo
Como trata-se de uma simulação da execução do algoritmo, uma flexibilidade do cenário de execuçãoera conveniente. Para tanto, como já mencionado anteriormente, todas as requisições e todas as respostas ficam registradas em vetores, sendo, portanto, necessário identificar, à medida que um evento (como o REPLY) ocorre, identificar o originador associado à mensagem. Nesse caso, para a correta identificação da origem foi usada como chave de identificação, o tempo em que o envio da mensagem foi escalonado. No entanto, por limitações próprias da linguagem de programação, duas variáveis baseadas em ponto flutuante não poderiam ser facilmente comparadas, por isso, conforme descrito na Figura 5, uma aproximação do valor absoluto da diferença do valor escalonado para ocorrência do evento e do próprio instante de execução previamente registrado foi considerado.
Figura 4. Identificação da origem de uma mensagem de reply
Figura 5. Coordenação da entrada na RC
Ainda sobre o evento ENTER_RC é importante ressaltar o controle do tempo limite de condução da simulação. Fato expresso na Figura 5. O propósito desse controle é apenas para emitir, inequivocamente, ao usuário, o fim da execução da simulação.
Figura 6. Coordenação da saída da RC
Por fim, para esclarecimento do modo de uso do código disponível a seguir, deve-se, portanto, seguir o seguinte modo de uso:
./ricAgr [quantidade de nodos (2 ou 3)] [tempos de requisição da RC de cada nodo]. Por exemplo: ./ricAgr 3 2 3 9.