Questão de Sistemas Operacionais — Geral — FUNDATEC 2025

Exclusão mútua em sistemas distribuídos: algoritmo do anel

Gabarito: letra C. O trecho descreve exatamente o algoritmo baseado em anel (token ring) para exclusão mútua em sistemas distribuídos: os processos são organizados em um círculo lógico, cada um com um canal para o próximo, e a exclusão é concedida pela posse de uma ficha (token) que circula em uma única direção. As demais alternativas descrevem outros algoritmos de exclusão mútua distribuída, que não se encaixam na descrição.

A exclusão mútua em sistemas distribuídos é um problema clássico: como garantir que apenas um processo, entre vários que rodam em máquinas diferentes, acesse um recurso compartilhado por vez, sem que haja memória compartilhada? Diferentemente dos sistemas monoprocessados, onde semáforos e monitores resolvem o problema, em um sistema distribuído a comunicação é feita exclusivamente por troca de mensagens. O algoritmo do anel, também chamado de token ring, resolve isso de forma elegante: os processos são organizados logicamente em um círculo, e uma mensagem especial, a ficha (token), circula continuamente por esse anel. Quando um processo quer entrar na seção crítica, ele espera receber a ficha; ao recebê-la, ele a segura, executa sua seção crítica e, ao terminar, a envia para o próximo processo do anel. A exclusão mútua é garantida porque só existe uma ficha no sistema — quem não a tem, não pode entrar na seção crítica.

A beleza desse algoritmo está na sua simplicidade: ele não exige um coordenador central, nem comunicação por multicast, nem votação entre processos. Cada processo só precisa conhecer seu vizinho no anel. A desvantagem é que, se um processo falhar, a ficha pode se perder, e o sistema precisa de mecanismos de detecção e regeneração da ficha. Outra característica é que ele garante justiça (fairness), pois a ficha circula em ordem, dando a cada processo uma chance de entrar na seção crítica de forma cíclica.

É importante distinguir o algoritmo do anel de outros algoritmos de exclusão mútua distribuída. O algoritmo do servidor central, por exemplo, usa um processo coordenador que recebe pedidos e concede acesso. O algoritmo de Maekawa usa votação: um processo precisa obter o consentimento de um subconjunto de outros processos (um quórum) para entrar na seção crítica. Já os algoritmos baseados em multicast e relógios lógicos, como o de Lamport, usam timestamps para ordenar os pedidos e garantir que o processo com o menor timestamp entre primeiro. O algoritmo de eleição, por sua vez, não trata de exclusão mútua, mas sim de escolher um líder entre os processos.

A pegadinha desta questão está em reconhecer a descrição exata do algoritmo do anel. A banca descreve os elementos-chave: "círculo lógico", "canal de comunicação com o processo seguinte" e "ficha passada de processo para processo em uma única direção". Esses são os termos que identificam o token ring. O candidato que conhece os nomes dos algoritmos, mas não suas características, pode confundir com o algoritmo de Maekawa (que também é distribuído) ou com o de servidor central (que também usa uma forma de "ficha", mas centralizada).

Guarde a distinção fundamental: no algoritmo do anel, a exclusão é concedida pela posse de uma ficha que circula; nos outros algoritmos, a concessão é feita por um coordenador, por votação ou por ordenação de eventos. É exatamente essa característica que separa a alternativa correta das demais.

Alternativa A — ❌ Incorreta

O algoritmo que emprega um servidor central usa um processo coordenador que recebe pedidos de todos os outros e concede ou nega o acesso à seção crítica. No trecho, não há menção a um servidor central; a exclusão é concedida pela posse da ficha, que circula entre os processos. A descrição do anel não se encaixa nesse modelo.

Alternativa B — ❌ Incorreta

Os algoritmos que utilizam multicast e relógios lógicos, como o algoritmo de Lamport, baseiam-se no envio de mensagens para todos os processos (multicast) e no uso de timestamps para ordenar os pedidos de entrada na seção crítica. O trecho descreve uma comunicação ponto a ponto (cada processo fala apenas com o próximo) e não menciona relógios lógicos ou ordenação por timestamps.

Alternativa C — ✅ Correta ⟵ GABARITO

O trecho descreve exatamente o algoritmo baseado em anel (token ring). Os processos são organizados em um círculo lógico, cada um com um canal para o processo seguinte, e a exclusão é concedida pela posse de uma ficha que circula em uma única direção. Essa é a definição clássica do algoritmo do anel para exclusão mútua em sistemas distribuídos.

Alternativa D — ❌ Incorreta

O algoritmo de votação de Maekawa exige que um processo obtenha o consentimento de um subconjunto de outros processos (um quórum) antes de entrar na seção crítica. Não há ficha circulando nem organização em anel; a comunicação é feita por mensagens de pedido e concessão entre os processos do quórum.

Alternativa E — ❌ Incorreta

O algoritmo de eleição (como o Bully ou o Ring) é usado para escolher um líder entre os processos de um sistema distribuído, não para garantir exclusão mútua. Embora o algoritmo de eleição em anel também organize os processos em um círculo, seu objetivo é eleger um coordenador, não conceder acesso a uma seção crítica por meio de uma ficha.

Gabarito: letra C