Sistemas Operacionais – Deadlock

Olá, querido (a) aluno(a)!

Neste artigo entenderemos conceitos importantes sobre Sistemas Operacionais – Deadlock que são cobrados com frequência em questões de concursos.

Introdução ao Conceito de Deadlock

Deadlock (ou Impasse) é um conceito fundamental no estudo de sistemas operacionais e em ambientes de computação concorrente. Refere-se a uma situação em que dois ou mais processos estão impedidos de prosseguir porque cada um está esperando por um recurso que está sendo retido por outro processo. 

Este artigo explora o conceito de deadlock, suas características, e discute diversos algoritmos desenvolvidos para lidar com ou evitar essa condição, incluindo o Algoritmo do Banqueiro, a Estratégia do Avestruz, entre outros.

Deadlock ocorre em um sistema de computador quando dois ou mais processos se encontram em um estado de espera permanente porque cada processo está esperando por um recurso que está sendo ocupado por outro processo. Em outras palavras, cada processo na situação de deadlock está esperando por um evento que só pode ser causado por outro processo na mesma situação. Isso resulta em um impasse, onde nenhum dos processos pode avançar.

Características do Deadlock

As principais características do deadlock podem ser resumidas nas quatro seguintes condições, também conhecidas como Condições de Coffman: 

• exclusão mútua, 
• retenção e espera, 
• não preempção e 
• espera circular. 

Exclusão mútua refere-se à necessidade de recursos que não podem ser compartilhados. 

Retenção e espera ocorrem quando um processo mantém pelo menos um recurso e espera adquirir recursos adicionais. 

Não preempção significa que recursos não podem ser forçadamente removidos de um processo que os está segurando. 

Espera circular acontece quando existe um conjunto de processos, cada um dos quais está esperando por um recurso que é mantido por outro processo no conjunto.

O Algoritmo do Banqueiro

Proposto por Edsger W. Dijkstra, é uma estratégia de prevenção de deadlock que se baseia na analogia de um banqueiro que aloca recursos limitados entre vários clientes sem entrar em insolvência. 

Este algoritmo evita deadlocks ao recusar pedidos de recursos que possam levar a uma situação de impasse, assegurando que pelo menos um dos processos possa sempre avançar.

Estratégia do Avestruz

É uma abordagem pragmática para o tratamento de deadlocks, baseando-se na premissa de que o custo de prevenir ou detectar deadlocks pode ser maior do que o custo de simplesmente ignorá-los. 

Nesta estratégia, assume-se que deadlocks são extremamente raros e que seria mais eficiente permitir que eles ocorram e reiniciar o sistema caso sejam detectados.

Outros Algoritmos e Estratégias

Além do Algoritmo do Banqueiro e da Estratégia do Avestruz, existem várias outras técnicas para lidar com deadlocks. 

Detecção de deadlock e recuperação envolvem a implementação de algoritmos que periodicamente verificam a existência de ciclos de espera e tomam medidas para interromper o deadlock, liberando recursos ou terminando processos. 

Outra abordagem é a prevenção de deadlocks, que procura evitar uma ou mais das quatro condições de Coffman através de um design cuidadoso do sistema e alocação de recursos.

Detecção Dinâmica de Deadlocks

A detecção dinâmica de deadlocks é realizada por meio de algoritmos que constroem e analisam o grafo de alocação de recursos para identificar ciclos de espera. 

Quando um ciclo é encontrado, indica a presença de um deadlock. A partir daí, o sistema deve tomar medidas para resolver o impasse, o que pode envolver a interrupção de um ou mais processos ou a preempção de recursos.

Prevenção de Deadlocks

A prevenção de deadlocks foca em desenhar o sistema e os algoritmos de tal maneira que pelo menos uma das condições necessárias para a ocorrência de deadlock nunca seja satisfeita. Isso pode envolver a imposição de uma ordem estrita na alocação de recursos, garantindo que cada processo possa ser interrompido e retomado sem causar problemas, ou limitando o acesso a recursos compartilhados.

Limitações dos Algoritmos Existentes

Embora os algoritmos e estratégias para lidar com deadlocks sejam úteis, eles têm suas limitações. 

O Algoritmo do Banqueiro, por exemplo, requer um conhecimento prévio de todos os recursos que cada processo irá necessitar, o que nem sempre é possível em sistemas dinâmicos. 

A Estratégia do Avestruz, por outro lado, pode não ser viável em sistemas críticos onde deadlocks podem ter consequências graves.

Considerações Finais

Deadlocks são um desafio significativo na gestão de sistemas operacionais e ambientes concorrentes. A escolha da estratégia ou algoritmo adequado para lidar com deadlocks depende de vários fatores, incluindo o tipo de aplicação, o ambiente de execução, e os recursos disponíveis. Entender as características do deadlock e as diferentes abordagens para seu gerenciamento é crucial para o desenvolvimento de sistemas robustos e confiáveis.

Referências

Silberschatz, A., Galvin, PB e Gagne, G. (2018). Conceitos de sistema operacional (10ª ed.). John Wiley & Filhos, Inc.

Tanenbaum, AS e Bos, H. (2014). Sistemas operacionais modernos (4ª ed.). Pearson.

Dijkstra, EW (1965). Solução de um problema de controle de programação concorrente. Comunicações da ACM, 8 (9), 569.

Coffman, EG, Elphick, M., & Shoshani, A. (1971). Impasses do sistema. Pesquisas de Computação ACM (CSUR) , 3(2), 67-78.

Vamos ver como esse conteúdo já foi cobrada em concurso?

1) Ano: 2023 Banca: UFMA Órgão: UFMA Prova: UFMA – 2023 – UFMA – Analista de Tecnologia da Informação

Em sistemas operacionais, o “algoritmo do Banqueiro”, desenvolvido por Edsger Dijkstra é utilizado para:

A) encerrar deadlocks

B) resolver deadlocks

C) recuperar-se de deadlocks

D) iniciar deadlocks

E) evitar deadlocks

Gabarito: E.

Comentário: O Algoritmo do Banqueiro é uma técnica de alocação de recursos que previne deadlocks ao garantir que, antes de conceder um pedido de recurso, o estado do sistema permanecerá seguro, o que significa que ainda haverá uma sequência segura de execução para todos os processos. Ao recusar pedidos que poderiam potencialmente levar a um estado inseguro, o Algoritmo do Banqueiro evita a ocorrência de deadlocks.

2) Ano: 2023 Banca: FUNDATEC Órgão: GHC-RS Prova: FUNDATEC – 2023 – GHC-RS – Programador

Qual alternativa descreve melhor o significado de deadlock em um sistema operacional? 

A) Estado em que um processo entra em loop infinito, ocupando continuamente a CPU.

B) Estado em que dois processos compartilham um recurso e tentam acessá-lo simultaneamente, levando a inconsistências.

C) Estado de espera em que um processo aguarda indefinidamente pela liberação de um recurso que outro processo está utilizando. 

D) Estado em que um processo é executado em paralelo com outro processo, sem sincronização adequada.

E) Estado em que um processo deve ceder a sua vez no processador a outro processo.

Gabarito: C.

Comentário: Deadlock é uma condição indesejável em um sistema de multiprocessamento onde pelo menos dois processos estão impedidos de prosseguir porque cada um espera que o outro libere um recurso. Em um deadlock, nenhum dos processos envolvidos pode avançar, realizar outras operações ou mesmo liberar os recursos que já possui. Este estado pode levar a uma paralisação da parte do sistema ou do sistema inteiro, necessitando intervenção para ser resolvido.

Então é isso! 

Bons estudos e até o nosso próximo artigo.

Prof. Jósis Alves

Coordenador TI – Gran Concursos

Analista de TI no Supremo Tribunal Federal