Deadlock

 Nota: Para a banda alemã ver Deadlock (banda). Não confundir com Dreadlocks.

Deadlock (interbloqueio, blocagem, impasse), no contexto de sistemas operacionais (SO), refere-se a uma situação em que ocorre um impasse, e dois ou mais processos ficam impedidos de continuar suas execuções - ou seja, ficam bloqueados, esperando uns pelos outros. Trata-se de um problema bastante estudado em sistemas operacionais e banco de dados, pois é inerente à própria natureza desses sistemas.

O deadlock ocorre com um conjunto de processos e recursos não-preemptíveis, onde um ou mais processos desse conjunto está aguardando a liberação de um recurso por um outro processo, o qual, por sua vez, aguarda a liberação de outro recurso alocado ou dependente do primeiro processo.

A definição textual de deadlock por ser muito abstrata, é mais difícil de se compreender do que a representação por grafos, que será resumida mais adiante. No entanto, algumas observações são pertinentes:

• O deadlock pode ocorrer mesmo que haja somente um processo no SO, considerando que este processo utilize múltiplos threads e que tais threads requisitem os recursos alocados a outros threads no mesmo processo;

• O deadlock independe da quantidade de recursos disponíveis no sistema;

• Normalmente o deadlock ocorre com recursos, tais como dispositivos, arquivos, memória etc. Apesar de a CPU também ser um recurso para o SO, em geral é um recurso facilmente preemptível, pois existem os escalonadores para compartilhar o processador entre os diversos processos, quando trata-se de um ambiente multitarefa.

Erros de deadlock podem ocorrer em bancos de dados. Suponha que uma empresa tenha vários vendedores e vários pontos de venda ou caixas. O vendedor A vendeu 1 martelo e 1 furadeira. O sistema, então, solicita o travamento do registro da tabela "ESTOQUE", que contém o total de martelos em estoque e, em seguida, solicita o travamento do registro que contém o total de furadeiras em estoque. De posse da exclusividade de acesso aos dois registros, ele lê a quantidade de martelos, subtrai 1 e escreve de novo no registro; o mesmo ocorre com relação ao registro de furadeiras. Observe, no entanto, que existem diversos caixas operando simultaneamente, de forma que, se algum outro caixa, naquele exato instante, estiver vendendo uma furadeira, ele ficará aguardando a liberação do registro das furadeiras para depois alterá-lo. Note que ele só altera os registros depois que for dada exclusividade para ele de TODOS os recursos que ele precisa, ou seja, de todos os registros. Suponha agora que, em outro caixa, foram vendidos 1 furadeira e 1 martelo e que o outro caixa solicitou o travamento do registro com a quantidade de furadeiras e agora quer o acesso ao de martelos; no entanto o registro de martelos está travado para o primeiro caixa. Nenhum deles devolve o recurso (registro) sobre o qual tem exclusividade e também não consegue acesso ao outro registro que falta para terminar a operação. Isto é um deadlock.

Condições necessárias para a ocorrência de deadlock

No texto acima, foi dito que o deadlock ocorre naturalmente em alguns sistemas. No entanto, é necessário ressaltar que tais sistemas precisam obedecer a algumas condições para que uma situação de deadlock se manifeste.

Essas condições estão listadas abaixo. As três primeiras caracterizam um modelo de sistema, e a última é o deadlock propriamente dito. Processos que estejam de posse de recursos obtidos anteriormente podem solicitar novos recursos. Caso estes recursos já estejam alocados a outros processos, o processo solicitante deve aguardar pela liberação do mesmo;

• Condição de não-preempção: recursos já alocados a processos não podem ser tomados à força. Eles precisam ser liberados explicitamente pelo processo que detém a sua posse;

• Condição de exclusividade mútua: cada recurso ou está alocado a um processo ou está disponível;

• Condição de posse-e-espera: cada processo pode solicitar um recurso, ter esse recurso alocado para si e ficar bloqueado, esperando por um outro recurso;

• Condição de espera circular: deve existir uma cadeia circular de dois ou mais processos, cada um dos quais esperando por um recurso que está com o próximo integrante da cadeia.

Representação de deadlock em grafos

Exemplo de representação de deadlock em grafos de alocação de recursos, com dois processos A e B, e dois recursos R1 e R2.

O deadlock também pode ser representado na forma de grafos dirigidos, onde o processo é representado por um quadrado e o recurso por um círculo. Quando um processo solicita um recurso, uma seta é dirigida do quadrado ao círculo. Quando um recurso é alocado a um processo, uma seta é dirigida do círculo ao quadrado.

Na figura do exemplo, podem-se ver dois processos diferentes (A e B), cada um com um recurso diferente alocado (R1 e R2). Nesse exemplo clássico de deadlock, é facilmente visível a condição de espera circular em que os processos se encontram, onde cada um solicita o recurso que está alocado ao outro processo.

Tratamento de deadlock

As situações de deadlock podem ser tratadas ou não em um sistema, e cabe aos desenvolvedores avaliar o custo/benefício que essas implementações podem trazer. Normalmente, as estratégias usadas para detectar e tratar as situações de deadlocks geram grande sobrecarga, podendo até causar um dano maior que a própria ocorrência do deadlock, sendo, às vezes, melhor ignorar a situação.

Existem três estratégias para tratamento de deadlocks:

• Ignorar a situação
• Detectar o deadlock e recuperar o sistema
• Evitar o deadlock

Algoritmo do avestruz (ignorar a situação)

A estratégia mais simples para tratamento (ou não) do "deadlock", conhecida como Algoritmo do Avestruz, é simplesmente ignorá-lo. Muitos defendem que a freqüência de ocorrência deste tipo de evento é baixa demais para que seja necessário sobrecarregar a CPU com códigos extras de tratamento, e que, ocasionalmente, é tolerável reiniciar o sistema como uma ação corretiva.

Detectar o deadlock e recuperar o sistema

Nessa estratégia, o sistema permite que ocorra o deadlock e só então executa o procedimento de recuperação, que resume-se na detecção da ocorrência e na recuperação posterior do sistema. É na execução desse procedimento que ocorre a sobrecarga, pois existem dois grandes problemas: primeiramente, como/quando detectar o deadlock e depois, como corrigi-lo.

Para detectar o deadlock, o sistema deve implementar uma estrutura de dados que armazene as informações sobre os processos e os recursos alocados a eles. Essas estruturas deverão ser atualizadas dinamicamente, de modo que reflitam realmente a situação de cada processo/recurso no sistema.

Só o mero procedimento de atualização dessas estruturas já gera uma sobrecarga no sistema, pois toda vez que um processo aloca, libera ou requisita um recurso, as estruturas precisam ser atualizadas.

Além disso, o SO precisa verificar a ocorrência da condição de espera circular nessas estruturas para a efetiva detecção do deadlock. Esse procedimento, por sua vez, gera outra sobrecarga, que pode ser mais intensa se não for definido um evento em particular para ser executado, como a liberação de um recurso, por exemplo. Assim, ou o SO verifica periodicamente as estruturas (o que não é aconselhável, pois pode aumentar consideravelmente o tempo de espera dos processos não-bloqueados), ou pode-se implementar uma política, onde o SO verifica as estruturas quando o mesmo realizar algum procedimento de manutenção do sistema, por exemplo.

Finalmente, só após detectar a presença do deadlock no sistema, o SO precisa corrigi-lo, executando um procedimento de recuperação.

Quanto à detecção do deadlock, vamos apresentar uma das técnicas usadas para detectar a ocorrência de deadlock em sistemas que possuem vários recursos de cada tipo.

Detecção de deadlock com vários recursos de cada tipo

O algoritmo de detecção de deadlock com vários recursos de cada tipo baseia-se em um ambiente que possua vários recursos do mesmo tipo e os processos solicitam apenas pelo tipo de recursos, não especificando qual recurso desejam utilizar.

Assim, um processo pode requisitar uma unidade de CD para leitura. Se o sistema possuir duas, o processo pode utilizar a que estiver disponível, em vez de especificar uma delas. Dessa forma, o processo solicita o recurso pelo tipo, sem discriminação.

O algoritmo para essa detecção trabalha com duas variáveis, três matrizes unidimensionais (vetores) e duas matrizes bidimensionais, descritas a seguir:

• Estruturas:
  • n: Variável inteira. Representa a Quantidade de Processos Ativos;
  • m: Variável inteira. Representa a Quantidade de Tipos de Recursos;
  • Matriz E = $\left(e_{j}\right)_{m}$: Matriz unidimensional, de tamanho m. Representa a Matriz de Recursos Existentes;
  • Matriz A = $\left(a_{j}\right)_{m}$: Matriz unidimensional, de tamanho m. Representa a Matriz de Recursos Atualmente Disponíveis;
  • Matriz W = $\left(w_{j}\right)_{m}$: Matriz unidimensional, de tamanho m. Representa uma Matriz Auxiliar, presente somente para facilitar o cálculo durante a execução do algoritmo;
  • Matriz C = $\left(c_{ij}\right)_{nxm}$: Matriz bidimensional, de tamanho n x m. Representa a Matriz de Alocação Corrente;
  • Matriz R = $\left(r_{ij}\right)_{nxm}$: Matriz bidimensional, de tamanho n x m. Representa a Matriz de Recursos Requisitados.

• Faça (para preenchimento das estruturas):
  1. Preencher a Matriz E com as quantidade de instâncias de cada tipo de recurso;
  2. Preencher a Matriz C com as quantidade de instâncias de cada tipo alocadas aos processos, sendo que o somatório de cada coluna da Matriz C deve ser menor ou igual à quantidade do recurso correspondente na Matriz E (os processos nunca podem requisitar mais recursos que existentes no sistema);
  3. Preencher a Matriz W com o resultado da subtração da quantidade de cada recurso da Matriz E com o valor do somatório de cada coluna do recurso correspondente da Matriz C, ou seja:
     $w_{j}=e_{j}-\sum _{i=1}^{n}c_{ij}$
  4. Preencher inicialmente a Matriz A com os valores da Matriz W.
     Note que: $a_{j}=e_{j}+w_{j}\,\!$;
  5. Preencher a Matriz R com as próximas requisições dos processos, seguindo as mesmas regras da Matriz C.

• Faça (para detecção do deadlock):
  1. Inicialmente, desmarcar todos os processos;
  2. Para um processo P_i desmarcado, verificar se todos os elementos da linha i na Matriz R são menores ou iguais aos da Matriz A;
  3. Se for, então marque o execute o processo P_i e libere os recursos requisitados pelo processo na Matriz C (adicionar a linha i da Matriz C na Matriz A);
  4. Retornar ao passo 2.

A lógica do algoritmo é a seguinte: cada processo é considerado como apto a ser executado até que a detecção prove o contrário. A detecção apenas verifica se os processos requisitam mais recursos do que estão disponíveis, o que caracteriza um deadlock. Caso o processo requisite uma quantidade disponível, então ele pode ser executado, e os recursos que foram solicitados antes podem também ser liberados de volta ao sistema, o que pode permitir que outros processos também concluam suas execuções e liberem os recursos.

Um exemplo do preenchimento das matrizes encontra-se na figura abaixo, considerando-se n=2 e m=3.

Exemplo do preenchimento das matrizes do algoritmo de detecção de deadlock com vários recursos de cada tipo.

Ligações externas

• Com relação à detecção de deadlock com vários recursos, existe um software educacional online, o SISO 2.0, que permite simular a implementação desse algoritmo: SISO 2.0 - Simulador de Sistema Operacional.