Como implementar a exclusão mútua em sistemas distribuídos?

2 Algoritmo de Ricart-Agrawala

O algoritmo de Ricart-Agrawala é uma otimização do algoritmo de Lamport para exclusão mútua em sistemas distribuídos. Ele reduz o número de mensagens trocadas usando o conceito de respostas adiadas. Quando um processo deseja inserir uma seção crítica, ele envia uma mensagem de solicitação para todos os outros processos com seu valor de relógio lógico atual e o identificador de recurso. Cada processo compara sua mensagem de solicitação com a mensagem de solicitação do remetente - se o remetente tiver uma prioridade mais alta, ele responde com uma mensagem de confirmação e atualiza seu relógio lógico e, se o remetente tiver uma prioridade menor, adia a resposta até que saia da seção crítica ou desista da solicitação. Quando um processo recebe confirmações de todos os outros processos, ele entra na seção crítica. Ao sair da seção crítica, ele envia uma mensagem de liberação para todos os outros processos com seu valor de relógio lógico atual e o identificador de recurso, bem como quaisquer respostas adiadas que não foram reconhecidas antes.

3 Algoritmos baseados em tokens

Uma abordagem diferente para exclusão mútua em sistemas distribuídos é usar algoritmos baseados em tokens, que dependem de uma mensagem especial chamada token que circula entre os processos. O processo que contém o token tem o direito exclusivo de entrar na seção crítica. Os algoritmos baseados em tokens vêm em duas variedades: baseados em anel e baseados em árvores. Os algoritmos baseados em anel organizam os processos em um anel lógico e o token é passado de um processo para o próximo em uma ordem fixa. O algoritmo Suzuki-Kasami é um exemplo disso, usando um token com um vetor de solicitações de cada processo e uma fila de solicitações pendentes. Algoritmos baseados em árvore organizam os processos em uma árvore lógica e o token é passado da raiz para as folhas e vice-versa. Um exemplo disso é o algoritmo de Raymond, que usa um token com a identidade do processo que o solicitou por último. Quando um processo deseja entrar na seção crítica, ele envia uma mensagem de solicitação para seu pai na árvore. Se ele receber o token, ele entrará na seção crítica e o devolverá ao pai com a identidade do próximo solicitante.