Introdução

Existem inúmeros recursos nos sistemas de computadores que se adéquam ao uso de somente um processo a cada vez, como, por exemplo, impressoras, unidades de fita e entradas nas tabelas internas do sistema. Caso dois ou mais processos quiserem escrever simultaneamente na mesma impressora, haverá um impasse. Desse modo, todos os sistemas operacionais devem ter a capacidade de garantir o acesso exclusivo de um processo a certos recursos, mesmo que seja temporariamente.

Em muitos casos, um processo não necessita apenas de acesso exclusivo a somente um recurso, mas sim a vários. Por exemplo, dois processos querem gravar em CD um documento obtido pelo scanner. O processo A está usando o scanner, enquanto o processo B, que é programado diferentemente, está usando o gravador de CD. Então, o processo A pede para usar o gravador de CD, mas a solicitação é negada até que o processo B o libere. Porém, ao invés de liberar o gravador de CD, o processo B pede para usar o scanner. Nesse momento, ambos os processos ficam bloqueados e assim ficarão para sempre. Essa situação é denominada deadlock.

Definição

Segundo Tanenbaum, deadlock pode ser 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”.

De uma forma mais simples, para melhor entendimento, podemos dizer que deadlock é um termo empregado para traduzir um problema ocorrido quando um grupo de processos competem entre si. A ocorrência do deadlock depende das características de dois ou mais programas diferentes e dos respectivos processos a executar pelos diferentes programas ao mesmo tempo. Pode ser, que esses processos possam ser executados de forma repetitiva usando diferentes processos sem que ocorra deadlock, todavia, basta um único processo padrão complicado para entrar em situação de deadlock.

Mesmo não relacionado a computação, podemos citar um exemplo de situação de deadlock que facilita o entendimento do que seja uma situação de deadlock. Dois carros estão seguindo em direções opostas, um de encontro ao outro, em uma pista que permite apenas a passagem de um veículo. Nesse caso os dois ficam impedidos de continuar seu percurso.

Existem quatro condições para a ocorrência de deadlock:

  • Condição de exclusão mútua. Em um determinado instante, cada recurso está em uma de duas situações: ou associado a um único processo ou disponível.
  • Condição de posso 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 tomados a força desse processo, eles devem ser explicitamente liberados pelo processo que os retém.
  • Condição de espera circular. Deve existir u encadeamento circular de dois ou mais processos; cada um deles encontra-se à espera de um recurso que está sendo usado pelo membro seguinte dessa cadeia.

Todas essas condições devem ocorrer simultaneamente para que ocorra um deadlock. Se uma dessas condições não ocorrer, não haverá deadlock.

Exemplo de deadlock:

Exemplo de deadlock

Figura 1: Exemplo de deadlock

Neste exemplo, os recursos são não preemptíveis e estão em condição de exclusão mútua. Inicialmente, os processos A, B e C ficam em posse dos recursos R, S, e T, respectivamente. O processo A solicita o recurso S, porém ele está sendo usado pelo processo B, então o processo A fica em condição de posse e espera. O processo B solicita o recurso T, formando a segunda condição de posse e espera. E o processo C solicita o recurso R, formando a terceira condição de posse e espera, formando, assim, uma espera circular, e por consequência, ocorre deadlock.

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, como, por exemplos, detecção e recuperação, evitar deadlock e prevenção de deadlock. Uma das estratégias mais simples é ignorar a ocorrência de deadlock, essa estratégia é útil se, praticamente, não existe a ocorrência de deadlock. Mas é necessário uma análise das necessidades da empresa, para saber se é ou não útil a implantação das estratégias de tratamento de deadlocks, avaliando o custo/benefício que essas implantações podem gerar.

Referências


  • Andrew S. Tanenbaum, “Sistemas Operacionais Modernos”, Editora Pearson/Prentice Hall, 2ª Edição
  • Abraham Silberschatz, "Sistemas Operacionais: conceitos e aplicações", Editora Elsevier 8.
  • Web Artigos. “Deadlock”