1. Introdução

Deadlock é um problema significativo que pode surgir até mesmo numa comunidade que coopera ou compete por processos. Ele é uma falha e não um erro, ocorre quando mais de um processo requer um determinado recurso ao mesmo tempo.

O deadlock cria uma situação em que um ou mais processos nunca correrão para conclusão sem recuperação.

Dijkstra introduz deadlock como: "Efeito colateral de estratégias de sincronização, porque dois processos ao atualizar duas variáveis compartilhadas, usam uma lock flag, um para requisitar valores de uma variável, o outro para atualizar valor da variável".

Situações semelhantes ocorrem periodicamente num conjunto de processos que estão a compartilhar recursos. Memória, os drives de uma impressora, um drive de disquetes são todos exemplos de recursos. Um processo pode bloquear quando é pedido qualquer um desses recursos e os mesmos estão ocupados, assim qualquer um pode contribuir para entrar na situação Deadlock.

2. Definição

Segundo Tanenbaum, deadlock pode ser formalmente definido como: "Um conjunto de processos estará em situação de deadlock se todo processo pertencente ao conjunto estiver esperando por um evento que somente um outro processo desse mesmo conjunto poderá fazer acontecer". (pag. 120)

Para um melhor entendimento podemos afirmar que deadlock é um termo empregado para traduzir um problema que ocorre quando um grupo ou conjunto de processos competem entre si. O aparecimento do mesmo depende das características de dois ou mais programas diferentes e dos respectivos processos a executar pelos diferentes programas ao mesmo tempo. Esses programas podem ser executados de forma repetitiva usando diferentes processos sem que ocorra a situação de deadlock, porém, basta um único processo padrão complicado para se entrar em deadlock.

Dijkstra explica a situação de deadlock através da seguinte ilustração:

Figura 1. Três processos em deadlock. Fonte: Dijkstra

Ou seja, o Processo 1 reserva para si o Recurso 1, por sua vez o Processo 2 e o Processo 3 reservam respectivamente para si o Recurso 2 e o Recurso 3. Por exemplo se um dos outros processos necessitar de um dos recursos anteriormente reservados por outros processos, como acontece no diagrama da figura anterior entramos numa situação de Deadlock.

Nenhum dos processos pode continuar, porque para isso acontecer, os mesmos necessitariam que os recursos reservados fossem disponibilizados. A não ser que um dos processos detecte a situação e abandonando o pedido do recurso anteriormente reservado por outro processo, e liberte ao mesmo tempo o recurso por si reservado. Com isso, há a possibilidade de pelo menos um processo correr.

Podemos citar como exemplo de situação de deadlock, não relacionado a computação, mas que facilita o entendimento do que seja uma situação de deadlock, dois carros seguindo em direção oposta numa pista que permite apenas a passagem de um veículo. Nesse caso os dois ficam impedidos de continuar seu percurso.

Um deadlock, em computação, ocorre normalmente com recursos como dispositivos, arquivos, memória, entre outros.

Existem algumas condições para que possa ter uma ocorrência de deadlock. São elas:

§Condição de exclusão mutua - Em um determinado instante, cada recurso esta em uma de duas situações: ou associado a um processo ou disponível.

§Condição de posse e espera - Processos que, em um determinado instante, retêm recursos concedidos anteriormente podem requisitar novos recursos.

§Condição de não preempção - Recursos concedidos previamente a um processo não podem ser forçosamente tomados desse processo –eles devem ser explicitamente libertados pelo processo que os retêm.

§Condição de espera circular - Deve existir um encadeamento circular de dois ou mais processos; cada um deles encontra-se á espera de um recurso que está sendo utilizada pelo membro seguinte dessa cadeia.

Todas estas condições devem estar presentes para que ocorra um deadlock. Se alguma delas falhar, então não ocorrerá um deadlock.

3. Estratégias para Tratar o Deadlock

As situações de deadlock podem ser tratadas ou não em um sistema, os desenvolvedores devem 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: Detecção e Recuperação, Evitar Deadlock e Prevenção.

3.1. Detecção e Recuperação

O sistema permite que ocorra o deadlock e depois executa o procedimento de recuperação, que se resume na detecção da ocorrência e na recuperação posterior do sistema.

Para detecção do deadlock, deve-se implementar no sistema uma estrutura de dados que armazene as informações sobre os processos e os recursos alocados a eles e essas reflitam a situação de cada processo/recurso no sistema. Porém, é importante ressaltar que o simples procedimento de atualização dessas estruturas gera sobrecarga no sistema, pois toda vez que o processo aloca, libera ou requisita um recurso , elas precisam ser atualizadas.

Algumas das técnicas de detecção utilizadas são:

§Detecção de deadlocks com um recurso de cada tipo – Se tem apenas um recurso de cada tipo (somente uma impressora, ou um CD,...). Existe um algoritmo para detectar se existem ciclos no grafo dos processos e recursos;

§Detecção de deadlocks com múltiplos recursos de cada tipo – O algoritmo baseia-se em um ambiente que possui vários recursos do mesmo tipo e os processos solicitam apenas pelo tipo de recursos, não especificando qual recurso desejam utilizar.

Uma vez que o algoritmo de detecção de deadlocks é bem sucedido, o que se fará em seguida é a recuperação do sistema da situação de deadlock e colocá-lo novamente em condição de funcionamento normal.

As técnicas utilizadas para recuperação, são:

§Recuperação por meio de preempção - Retirar o recurso a um processo e dá-lo a outro sem que o processo proprietário do recurso se aperceba.

§Recuperação por meio de reversão de estado - O sistema operativo, ao longo da execução dos processos vai guardando imagens dos estados do processo, para que fique como que um posto de fiscalização do processo. Não guarda apenas os estados dos processos, como guarda também os recursos associados ao processo no momento em que é criado o posto de fiscalização. O sistema não sobrepõe um posto de fiscalização novo a um já guardado anteriormente. Ele cria sempre uma imagem nova. Depois que o algoritmo de detecção de deadlocks detecta um deadlock os processos incluídos no deadlock voltam a estados anteriores.

§Recuperação por meio de eliminação de processos - A maneira mais grosseira, mas também a mais simples é matar um ou mais processos envolvidos no deadlock. Com um pouco de sorte os outros processos poderão ser capazes de prosseguir.

3.2. Evitar Deadlock

O deadlock pode ser evitado, mas só quando certas informações estiverem disponíveis.

O Sistema Operacional que adota esta estratégia, procura evitar a ocorrência de deadlocks por meio de alocação cuidadosa de recursos. O sistema deve ser capaz de saber e decidir se liberar um recurso é seguro ou não.

Abordaremos a seguir alguns processos que objetivam evitar deadlocks.

§Trajetória dos recursos – a figura abaixo demonstra o funcionamento desse processo:

Figura 2. Trajetória dos recursos de dois processos. Fonte: Sistemas Operacionais Modernos pág. 129.

Algo importante a ser visto neste exemplo é o ponto t, onde B estará requisitando um recurso. O sistema deve decidir se lhe dá o direito de uso ou não. Se o direito de uso for concedido, o sistema entrará em uma região insegura e acabará por entrar em deadlock. Para evitar o deadlock, B deverá ser suspenso até A requisitar e liberar o plotter.

§Estados seguros e não seguros – É considerado um estado segurose ele não esta em situação de deadlock e se existe alguma ordem de escalonamento na qual todo o processo possa ser executado até sua conclusão, mesmo se de repente, todos eles requisitarem, de uma só vez, o máximo possível de recursos. Um estado não seguro não é uma situação de deadlock. É um estado em que a partir do mesmo, o sistema não pode dar a garantia de que o processo vai acabar.

§Algoritmo de banqueiro - Usado para determinar se um processo pode executar de maneira segura ou não. Todos os processos declaram o máximo de recursos que vão usar durante a execução. A execução é permitida se a soma dos recursos requisitados é menor que os recursos disponíveis no sistema. O algoritmo verifica se a libertação de uma requisição pode levar a um estado não seguro. Em caso positivo, a requisição é negada. Se a libertação de uma requisição levar a um estado seguro, então ela é atendida.

Evitar deadlocks é, em sua essência, impossível, pois como já dito,requer informações sobre pedidos futuros.

3.3. Prevenção de Deadlock

Como já visto no ponto 3.3, evitar deadlock é praticamente impossível. Por isso, a prevenção de deadlock tenta garantir que pelo menos uma das condições para ocorrência de deadlock, não aconteça.

Sabendo que são quatro as condições para que possa ocorrer uma situação de deadlock simultaneamente, a prevenção procura eliminar pelo menos uma delas utilizando as seguintes técnicas:

1.Condição de exclusão mútua – O processo solicita o recurso para uso de forma mutuamente exclusiva. Essa condição é eliminada se o processo solicita todos os recursos que necessita em uma única vez.

2.Condição de posse e espera – Os processos devem pedir os recursos antes de iniciarem a sua execução.

3.Condição de não preempção – Elimina-se essa condição se os recursos forem ordenados e os processos devem requisitar os recursos em uma seqüência que respeite esta ordem.

4.Condição de espera circular – Pode ser eliminada se for construído um grafo e se for verificado, para cada requisição, se o atendimento não levará o sistema a um estado não seguro. As requisições que levarem o sistema a um estado não seguro ou de deadlock não deverão ser atendidas.

Estas estratégias são fáceis de implementar em certos sistemas, porém a avaliação de custo/benefício deve ser levada em consideração.

4. Conclusão

Deadlock é um problema potencial em qualquer sistema operacional. Um estado de deadlock ocorre quando dois ou mais processos estão esperando indefinidamente por um evento que só pode ocorrer por um dos processos em espera. Existem alguns métodos para tratar deadlocks, os quais foram citados neste trabalho: detecção e recuperação, evitar deadlock e prevenção de deadlock.

Uma das estratégias mais simples de tratar deadlock, seria ignorá-lo, porém, é necessário uma análise das necessidades da empresa, para o implemento ou não das estratégias de tratamento do deadlock, assim como, avaliar o custo/benefício que essas implantações podem gerar.

Referencias

Tanenbaum, Andrew S.. (2003) "Sistemass Operacionais Modernos", Editora Prentice Hall – 2 ed. – São Paulo.

Silberschatz, Abraham; Galin, Peter; Gagne, Grag. (2000). "Sistemas Operacionais: conceitos e aplicações", Editora Elsvier – 8 reimpressão – Rio de Janeiro.

Wikipedia.(2007). "Deadlock", http://pt.wikipedia.org/wiki/Deadlock, Novembro.

Programação Concorrente. (2007). "Deadlock", http://www.dc.ufscar.br/~mdchiodi/ProgramacaoConcorrente/ApostilaAula10.pdf, Novembro.

N. Ribeiro (2007). "Sistemas Operativos", http://ltodi.est.ips.pt/nribeiro/Lecturing/SO_02-03/A06.pdf., Novembro.

Silberschatz, Abraham; Karth, Henry F.; Sudarshan, S. (1999). "Sistema de Banco de Dados", Editora Makron Books – 3 ed. – São Paulo.

Valador, Nelson. (2007). "Sistemas Operativos", http://alumni.ipt.pt/~nvalador/trab1/cap10.html, Novembro.

E.W. Dijkstra. (1968). "Go To Statement Considered Harmful, Communications of the ACM". Vol. 11