Resumo artigo “An Optimal Algorithm for Mutual Exclusion in Computer Networks”

Resumo artigo “An Optimal Algorithm for Mutual Exclusion in Computer Networks”

1. Introdução

Um algoritmo é proposto para exclusão mútua em redes em que os nós se comunicam apenas por mensagens e não compartilham memória. O algoritmo utiliza apenas 2*(n - 1) mensagens entre os nós, onde N é o número de nós e é um algoritmo ótimo, no sentido de que, um algoritmo simétrico distribuído não pode usar menos mensagens se os requests são processados por cada nó concorrentemente. Algumas premissas são assumidas no uso desse algoritmo: Há uma rede de comunicações subalterna livre de erros, em que a latência pode variar e as mensagens não podem ser entregues na ordem enviada; Assume-se que os nós operam corretamente.

2. O algoritmo

2.1 Descrição

Um nó entra em sua seção crítica após todos os outros nós terem sido notificados do request e terem enviado uma resposta concedendo sua permissão. Após o recebimento da mensagem de request, o nó envia uma resposta, ou adia uma resposta até que ele saia da sua própria seção crítica. Este processo simplesmente conta o número de mensagens de resposta, mantendo o controle de quantas mensagens estão pendentes antes do nó poder entrar em sua seção crítica.

2.2 Especificação

Em uma rede de N nós, cada nó implementa a exclusão mútua em três processos. Os Processos são executados de forma assíncrona e possuem variáveis compartilhadas.

Processo 1. É despertado quando a exclusão mútua é invocada em nome deste nó;

Processo 2. Recebe e processa mensagens de REQUEST;

Processo 3. Recebe e processa mensagens de REPLY.

Um semáforo é usado para serializar o acesso a variáveis compartilhadas quando necessário.

3. Afirmações

Exclusão mútua é alcançada; Deadlock é impossível; Starvation é impossível.

4. Tráfego de Mensagens

4.1 Processamento simultâneo

Para cada invocação de Seção Crítica, o nó solicitante deverá enviar (n-1) pedidos. Antes do nó solicitante poder entrar na seção crítica, deverá receber (n-1) respostas. Portanto, este algoritmo requer 2*(n-1) mensagens para cada seção crítica. Este número de mensagens é o mínimo necessário para qualquer algoritmo paralelo, simétrico, e distribuído quando os nós agem de forma independente e ao mesmo tempo.

4.2 Processamento em série

Assim como antes, para cada invocação de Seção Crítica, cada nó deve receber e enviar uma mensagem. O algoritmo modificado para processar em série requer apenas N mensagens para cada invocação. A operação de paralelismo é sacrificada.

5. Atraso nas seções críticas

Algoritmo tem atraso mínimo se alguns pressupostos forem feitos: é preciso tempo de ida e volta para determinar o estado de um outro nó; Nó não tem acesso a Seção Crítica sem primeiro solicitar isso; Nós não antecipam pedidos.