Deadlock
Origem: Wikipédia, a enciclopédia livre.
Deadlock (blocagem, impasse), no contexto do sistemas operacionais (SO), caracteriza uma situação em que ocorre um impasse e o SO fica impedido de continuar suas atividades normais indefinidamente. Trata-se de um problema bastante estudado no contexto dos Sistemas Operacionais, assim como em outras disciplinas, como 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 que, por sua vez, aguarda a liberação de outro recurso alocado ou dependente do primeiro processo.
A definição textual de deadlock normalmente, 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 como dispositivos, arquivos, memória etc. Apesar da 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.
Um exemplo onde erros de deadlock ocorrem é no banco de dados. As aplicações clientes, usando a base de dados, exigem acesso exclusivo a uma certa tabela e, para ganhar acesso exclusivo, eles pedem um travamento desta tabela. Se duas aplicações clientes tentam travar a mesma tabela ao mesmo tempo, então nem um nem outra aplicação receberá o acesso e a trava. Uma vez que não há meio geral para decidir para quem dar a trava, ambos os clientes esperarão eternamente pela trava.
Devido a este erro de deadlock, alguns sistemas precisam tratá-lo. Usando o mesmo exemplo acima, quando os clientes buscarem uma trava ao mesmo tempo, o sistema tem que definir uma solução para isso e tratá-la, por exemplo, através da prioridade entre os clientes.
Índice |
[editar] 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, onde 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 a força. Eles precisam ser liberados explicitamente pelo processo que detém a sua posse;
- 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 membro da cadeia.
- Condição de exclusão mútua: cada recurso ou está alocado a exatamente um processo ou está disponível;
- Condição de posse-e-espera:
[editar] Representação de deadlock em grafos
O deadlock também pode ser representado na forma de grafos dirigidos, onde o processo é representado por um círculo e o recurso, por um quadrado. Quando um processo solicita um recurso, uma seta é dirigida do círculo ao quadrado. Quando um recurso é alocado a um processo, uma seta é dirigida do quadrado ao círculo.
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.
[editar] 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; e
- Evitar o deadlock;
[editar] Algoritmo do Avestruz (Ignorar a situação)
A estratégia mais simples para tratamento (ou não, é claro) do deadlock, é ignorá-lo, pois 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..
[editar] 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 estuturas 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.
[editar] 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 =
: Matriz unidimensional, de tamanho m. Representa a Matriz de Recursos Existentes; - Matriz A =
: Matriz unidimensional, de tamanho m. Representa a Matriz de Recursos Atualmente Disponíveis; - Matriz W =
: Matriz unidimensional, de tamanho m. Representa uma Matriz Auxiliar, presente somente para facilitar o cálculo durante a execução do algoritmo; - Matriz C =
: Matriz bidimensional, de tamanho n x m. Representa a Matriz de Alocação Corrente; - Matriz R =
: Matriz bidimensional, de tamanho n x m. Representa a Matriz de Recursos Requisitados.
- Faça (para preenchimento das estruturas):
- Preencher a Matriz E com as quantidade de instâncias de cada tipo de recurso;
- Preencher a Matriz C com as quantidade de instâncias de cada tipo alocadas aos processos, sendo que a somatória 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);
- 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:
- Preencher inicialmente a Matriz A com os valores da Matriz W.
Note que:
; - 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):
- Inicialmente, desmarcar todos os processos;
- Para um processo Pi desmarcado, verificar se todos os elementos da linha i na Matriz R são menores ou iguais aos da Matriz A;
- Se for, então marque o execute o processo Pi e libere os recursos requisitados pelo processo na Matriz C (adicionar a linha i da Matriz C na Matriz A);
- 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.
[editar] Referências na internet
- Em caráter educativo, existe um simulador de sistemas operacionais denomidado SISO 2.0, disponível na rede, que permite simular a implementação desse algoritmo (SISO 2.0 - Simulador de Sistema Operacional).
