Deadlocks

Deadlocks

1. Modelo de Sistema.

   • Sistema: Consiste em número finito de recursos para serem distribuídos entre um número de processos em competição.
   • Cada Recurso pode ter uma ou várias instâncias.
   • Operação Normal: Processos obedecem uma sequência para utilizar os recursos.
     • Solicitação
     • Utilização
     • Liberação

2. Caracterização de Deadlock.

   • Quatro condições precisam ser mantidas simultaneamente.
     • Exclusão Mútua: Apenas um processo por vez pode usar um recurso.
     • Manter e Esperar: Um processo mantém pelo menos um recurso enquanto espera para obter outros recursos mantidos por outros processos.
     • Não Preempção: Um recurso em uso por um processo só pode ser liberado pelo processo, de modo voluntário, ao terminar sua tarefa.
     • Espera Circular:Um conjunto de processos, com o primeiro esperando recursos mantidos pelo segundo, e o segundo esperando do terceiro, e assim sucessivamente, até o último que esta esperando recurso mantido pelo primeiro.
   • Grafos de Alocação de Recursos.
     • Grafo sem Ciclos: Não existe Deadlock.
     • Grafo com Ciclos.
       • Recursos com apenas uma instância: Existe Deadlock.
       • Recursos com mais de uma instância: Não garante que existe, indica a possibilidade de existir.

3. Métodos para Tratamento de Deadlocks.

   • Protocolo para prevenir ou evitar que o sistema entre em estado de Deadlock.
   • Permitir que o sistema entre em estado de Deadlock, detectar e recuperar.
   • Ignorar completamente e fingir que Deadlocks não existem em sistemas. (Linux e Windows)

4. Prevenção de Deadlocks.

   • Garantir que pelo menos uma das quatro condições requeridas não seja mantida/atendida.
     • Exclusão Mútua: Os recursos compartilháveis não a exigem. Contudo haverá pelo menos um recurso intrinsicamente não-compartilhável que a exige.
     • Manter e Esperar: Garantir que um processo ao solicitar um recurso e não ser atendido, não manterá consigo qualquer outro recurso.
       • Exigir que o processo solicite e obtenha todos os recursos antes de iniciar a execução.
       • Exigir que o processo só possa solicitar recurso se não mantiver nenhum recurso.
     • Não Preempção: Se um processo solicita um recurso e não o obtém de imediato, todos os recursos por ele mantidos são preemptados.
       • Os recursos preemptados são acrescentados a lista de recursos pelos quais o processo esta esperando.
       • O processo só será reiniciado quando conseguir obter novamente os antigos recursos e mais o novos solicitados
     • Espera Circular: Para não existir, exige que todos os recursos sejam numerados em ordem crescente e que os processos somente solicitem os recursos em ordem crescente.

5. Evitando Deadlocks.

   • Exige que o sistema receba a priori algumas informações.
   • Processo informa o número máximo de cada recurso que poderá precisar.
   • O algoritmo de evitar Deadlocks examina dinamicamente o estado de alocação de recursos para garantir que nunca haverá uma condição de Espera Circular.
   • O estado de alocação de recursos é definido pelo número de recursos disponíveis, número de recursos alocados e pela demanda máxima de recursos dos processos.
   • Estado Seguro: É caracterizado pela existência de recursos disponíveis mais recursos mantidos por processos antecedentes em número suficiente para atender a solicitação máxima do processo que irá ser iniciado.
     • Sistema em Estado Seguro: Não existe Deadlock.
     • Sistema em Estado Inseguro: Não garante que exista um Deadlock significa apenas a possibilidade de haver.
     • Para garantir que não haverá Deadlocks, basta assegurar que o sistema não entrará em Estado Inseguro.

6. Detecção de Deadlocks.

   • Se o S.O, não emprega algoritmos de prevenção ou para evitar Deadlocks, então ele irá ocorrer.
     • Neste ambiente o sistema precisa ter um algoritmo que examine o estado do sistema para determinar se existe um Deadlock e um algoritmo para se recuperar do Deadlock.

7. Recuperação de Deadlocks.

   • Detectado um Deadlock.
     • Informar e deixar que o usuário resolva manualmente.
     • Deixar que o sistema se recupere automaticamente.
       • Abortando alguns processos para interromper a Espera Circular.
         • Abortar todos os processos em Deadlock.
         • Abortar os processos um a um até que o Deadlock seja rompido.
       • Preemptando alguns recursos de um ou mais processos em Deadlock.
         • Selecionar a Vítima: Quais recursos e quais processos serão preemptados?
         • Reversão do processo até um estado seguro.
         • Starvation: Para evitar isso deve se limitar a um número finito e pequeno a seleção de um processo como vítima.