Questão de Sistemas Operacionais — Deadlock (SO) — INSTITUTO AOCP 2024

Deadlock: prevenção e o Algoritmo do Banqueiro

Gabarito: letra C. O Algoritmo do Banqueiro é a técnica clássica de prevenção de deadlocks que, em vez de simplesmente detectar o impasse depois que ele ocorre, evita que o sistema entre em um estado inseguro, analisando cada solicitação de recurso antes de concedê-la. Ele é o único entre as alternativas que se encaixa na descrição de "algoritmo de prevenção e resolução de impasses" — os demais são algoritmos de escalonamento de CPU ou de substituição de páginas de memória, que não lidam com deadlock.

O deadlock, ou impasse, é uma situação em que dois ou mais processos ficam permanentemente bloqueados, cada um esperando por um recurso que está retido por outro processo do mesmo conjunto. Para que um deadlock ocorra, quatro condições precisam ser satisfeitas simultaneamente: exclusão mútua (recursos não podem ser compartilhados), posse e espera (um processo detém um recurso enquanto espera por outro), não-preempção (recursos não podem ser retirados à força) e espera circular (existe um ciclo de processos esperando por recursos uns dos outros). O Algoritmo do Banqueiro ataca diretamente a condição de posse e espera, ao exigir que um processo declare antecipadamente o número máximo de recursos que precisará. Com essa informação, o sistema pode simular a alocação de cada solicitação e verificar se, após a concessão, ainda existe uma sequência segura de execução que permita que todos os processos terminem. Se a concessão levar o sistema a um estado inseguro — ou seja, um estado onde não há garantia de que todos os processos possam ser concluídos — a solicitação é negada, e o processo é forçado a esperar. Dessa forma, o sistema nunca entra em um estado que possa levar a um deadlock.

Na prática, o algoritmo funciona como um banqueiro que só empresta dinheiro se tiver certeza de que conseguirá receber de volta. Cada processo é um cliente, cada recurso é uma unidade de capital, e o banqueiro (o sistema operacional) só concede um empréstimo (recurso) se, mesmo após a concessão, houver uma sequência de pagamentos (execuções) que garanta que todos os clientes consigam quitar suas dívidas. Por exemplo, se um sistema tem 10 unidades de um recurso e três processos precisam de, no máximo, 5, 4 e 3 unidades respectivamente, o banqueiro pode conceder 3, 2 e 2 unidades inicialmente. Se um dos processos solicitar mais uma unidade, o banqueiro verifica se, após concedê-la, ainda existe uma ordem de execução que permita que todos terminem. Se não houver, a solicitação é negada, mesmo que a unidade esteja disponível. Essa abordagem é conservadora e pode subutilizar recursos, mas garante a ausência de deadlocks.

A distinção crucial que a banca explora nesta questão é entre prevenção de deadlocks (evitar que o impasse ocorra) e detecção e recuperação (permitir que o impasse ocorra e depois resolvê-lo). O Algoritmo do Banqueiro é um método de prevenção, pois impede que o sistema entre em um estado inseguro. Já a detecção envolve a construção de um grafo de alocação de recursos e a verificação de ciclos; a recuperação pode envolver a preempção de recursos ou a eliminação de processos. As alternativas incorretas apresentam algoritmos de outras áreas, como escalonamento de CPU (Segunda Chance, LRU Aprimorado) ou algoritmos de substituição de páginas (Clock), que não têm relação com deadlock. O "Algoritmo de Coffman" é uma referência às condições de Coffman (as quatro condições necessárias para o deadlock), não um algoritmo de prevenção em si.

Guarde a fronteira entre prevenção (Algoritmo do Banqueiro) e detecção/recuperação (grafo de alocação, preempção): é exatamente nela que as alternativas se dividem. A questão pede um algoritmo de prevenção, e o Banqueiro é o único que se encaixa.

Alternativa A — ❌ Incorreta

O Algoritmo Clock (ou do Relógio) é um algoritmo de substituição de páginas em memória virtual, utilizado para decidir qual página da memória deve ser removida quando uma nova página precisa ser carregada. Ele é uma variação do algoritmo FIFO (First-In, First-Out) que usa um bit de referência para dar uma "segunda chance" às páginas recentemente usadas. Não tem nenhuma relação com deadlock ou com a prevenção de impasses. A banca o inclui como distrator por ser um algoritmo de gerenciamento de memória, área que também envolve concorrência, mas que não trata do problema de processos bloqueados esperando por recursos.

Alternativa B — ❌ Incorreta

O Algoritmo da Segunda Chance é uma variação do algoritmo de substituição de páginas FIFO, que também utiliza um bit de referência para evitar a remoção de páginas que foram recentemente acessadas. Assim como o Clock, ele é um algoritmo de gerenciamento de memória virtual, não de prevenção de deadlocks. A confusão pode surgir porque ambos os algoritmos (Segunda Chance e Clock) são frequentemente estudados juntos em sistemas operacionais, mas eles resolvem problemas diferentes: um decide quais páginas manter na memória, o outro decide se um processo pode obter um recurso sem causar um impasse.

Alternativa C — ✅ Correta ⟵ GABARITO

O Algoritmo do Banqueiro é o algoritmo clássico de prevenção de deadlocks, proposto por Edsger Dijkstra. Ele funciona exigindo que cada processo declare antecipadamente o número máximo de recursos que poderá precisar. Antes de conceder uma solicitação de recurso, o sistema verifica se, após a concessão, o sistema permanece em um estado seguro — ou seja, se existe uma sequência de execução que permita que todos os processos terminem. Se a concessão levar a um estado inseguro, a solicitação é negada. Dessa forma, o sistema evita entrar em estados que possam resultar em deadlock. É exatamente o que o enunciado pede: um algoritmo de prevenção e resolução de impasses.

Alternativa D — ❌ Incorreta

O Algoritmo de Coffman não é um algoritmo de prevenção de deadlocks, mas sim uma referência às quatro condições de Coffman (exclusão mútua, posse e espera, não-preempção e espera circular), que são as condições necessárias para que um deadlock ocorra. Essas condições foram formalizadas por Edward G. Coffman Jr. e são usadas para analisar e prevenir deadlocks, mas não constituem um algoritmo em si. A banca pode tentar confundir o candidato ao sugerir que "Coffman" é um algoritmo, quando na verdade é um conjunto de condições que o Algoritmo do Banqueiro tenta evitar.

Alternativa E — ❌ Incorreta

O Algoritmo LRU Aprimorado (Least Recently Used) é um algoritmo de substituição de páginas em memória virtual, que combina o critério de menor uso recente com bits de referência e modificação para escolher a página a ser removida. Ele é uma evolução do algoritmo LRU básico e é usado para otimizar o desempenho da memória, não para prevenir deadlocks. Assim como as alternativas A e B, é um distrator que explora a confusão entre gerenciamento de memória e gerenciamento de processos.

Gabarito: letra C