INTRODUÇÃO
Deadlock (interbloqueio, blocagem, impasse), no contexto dos sistemas operacionais (SO), caracteriza uma situação em que ocorre um impasse e dois ou mais processos ficam impedidos de continuar suas execuções, ou seja, ficam bloqueados. 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.
DEADLOCK
O deadlock ocorre com um conjunto de processos e recursos não-preemptíveis (sem preferência definida), 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 abstracta, é mais difícil de se compreender do que a representação por grafos (conjunto de vértices em diagrama), 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 (sequência de instruções) e que tais threads requisitem os recursos alocados a outras threads no mesmo processo.
O deadlock indecente 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 prevenível, pois existem os escalonadores (procedimento operacional) 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. Suponha que uma empresa tenha vários vendedores e vários pontos de venda/caixas. O vendedor A vendeu 1 martelo e 1 fumadeira. O sistema então solicita o travamento do registo da tabela stock que contém o total de martelos em stock e em seguida solicita o travamento do registo que contém o total de fumadeiras em stock. Na posse da exclusividade de acesso aos dois registos, ele lê a quantidade de martelos, subtrai 1 e escreve de novo no registo, o mesmo com o registo de fumadeiras. Observe, no entanto que existem diversos caixas operando simultaneamente de forma que se algum outro caixa naquele exacto instante estiver vendendo uma fumadeira, ele ficará aguardando a liberação do registo das fumadeiras para depois alterá-lo. Note que ele só altera os registos depois que for dada exclusividade para todos os recursos que ele precisa, ou seja, de todos os registos. Suponha agora que em outra caixa foram vendidos 1 fumadeira e 1 martelo e que o outro caixa solicitou o travamento do registo com a quantidade de fumadeiras e agora quer o acesso ao de martelos, no entanto o de martelos está travado para o primeiro caixa. Nenhum deles devolve o recurso (registo) sobre o qual tem exclusividade e também não consegue acesso ao outro registo 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 referir que tais sistemas precisam de 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 exclusão mútua: cada recurso ou está alocado exactamente 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 membro 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 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.
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 frequê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 acção correctiva.
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: primeiro, 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 actualizadas dinamicamente, de modo que reflictam realmente a situação de cada processo/recurso no sistema.
Só o mero procedimento de actualizaçã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 actualizadas. Além disso, o SO precisa de verificar a ocorrência da condição de espera circular nessas estruturas para a efectiva 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.Finalmente, só após detectar a presença do deadlock no sistema, o SO precisa corrigi-lo, executando um procedimento de recuperação.
Evitar o deadlock, detecção de deadlock com vários recursos de cada tipo:
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.
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 recursos 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 solícita o recurso pelo tipo, sem discriminação.
Conclusão
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.
Autores:
Mário Anjos
Mykhaylo Bilinkevych
