Deadlock

Deadlock

1. Modelo do Sistema

   • Sistema
     • Conjunto finito de recursos a serem distribuídos entre uma série de processos em competição.
   • Tipos de recurso R1, R2, . . ., Rm
     • Cada recurso pode admitir uma ou mais instancias
       • As instancias de um mesmo dispositivos possuem exatamente a mesma funcionalidade (são idênticas).
     • Cada processo utiliza um recurso da seguinte forma:
       • Requisição,Uso, Liberação

2. Caracterização do deadlock

   • Deadlock pode surgir se quatro condições forem mantidas simultaneamente
     • Exclusão mútua:
       • apenas um processo de cada vez pode usar um recurso
     • Manter e esperar
       • um processo mantendo pelo menos um recurso está esperando para adquirir outros recursos mantidos por outros processos.
     • Não preempção
       • um recurso só pode ser liberado voluntariamente pelo processo que o mantém, depois que esse processo tiver terminado sua tarefa.
     • Espera circular
       • existe um conjunto {P0, P1, …, Pn} de processos esperando tal que P0 está esperando por um recurso que é mantido por P1, P1 está esperando por um recurso que é mantido por P2, …, Pn–1 está esperando por um recurso que é mantido por Pn, e Pn está esperando por um recurso que é mantido por P0

3. Métodos para tratamento de deadlocks

   • Garantir que o sistema nunca entrará em um estado de deadlock
     • Garantindo que pelo uma das condições necessárias não seja satisfeita.
       • Permitir que o sistema entre em um estado de deadlock e depois se recupere
         • No entanto, o SO deverá ser capaz de determinar se aconteceu um deadlock.
           • Ignorar o problema e fingir que os deadlocks nunca ocorrem no sistema

4. Prevenção de deadlock

   • Garantir que pelo menos uma das quatro condições necessárias (para haver deadlock) não possa ser atendida:
     • Exclusão mútua
       • não exigido para recursos compartilháveis; deve manter para recursos não compartilháveis
       • Manter e esperar
         • deve garantir que sempre que um processo solicita um recurso, ele não mantém quaisquer outros recursos.
           • Exige que o processo solicite e tenha todos os seus recursos alocados antes de iniciar a execução, ou permite que o processo solicite recursos somente quando o processo não tiver recursos
             • Baixa utilização de recursos
               • starvation possível
         • Não-preempção
           • Se um processo que está mantendo alguns recursos solicitar outro recurso que não pode ser alocado imediatamente a ele, então todos os recursos atualmente sendo mantidos são liberados
             • Recursos preemptados são acrescentados à lista de recursos pelos quais o processo está esperando
               • O processo só será reiniciado quando puder reobter seus antigos recursos, além dos novos que está solicitando
           • Espera circular
             • impõe uma ordenação total de todos os tipos de recurso, e exige que cada processo solicite recursos em uma ordem de enumeração aumentada.

5. Evitando deadlock

   • Modelo mais simples e mais útil exige que cada processo declare o número máximo de recursos de cada tipo que ele pode precisar
     • Estado seguro
       • Se as necessidades de recurso de Pi não estiverem disponíveis imediatamente, então Pi pode esperar até que todo Pj tenha terminado.
         • Quando Pj tiver terminado, Pi pode obter os recursos necessários, executar, retornar recursos alocados e terminar.
           • Quando Pi termina, Pi +1 pode obter seus recursos necessários, e assim por diante.
   • O algoritmo para evitar impasse examina dinamicamente o estado de alocação de recurso para garantir que nunca poderá haver uma condição de espera circular
     • O estado de alocação de recurso é definido pelo número de recursos disponíveis e alocados, e as demandas máximas dos processos.

6. Detecção de deadlock

   • Nesse ambiente, o sistema precisa prover
     • Um algoritmo que examine o estado do sistema para determinar se ocorreu um deadlock
       • Um algoritmo para se recuperar do deadlock

7. Recuperação de deadlock

   • Caso detectado o deadlock
     • Informar ao usuário e deixar que o mesmo resolva manualmente. Deixar que o sistema se recupere automaticamente
       • Abortando um ou mais processos para interromper a espera circular.
         • Preemptar alguns recursos de um ou mais processos em deadlock.
           • Terminando o(s) processo(s)
             • Duas possibilidades
               • Aborte todos os processos em deadlock.
               • Aborte um processo de cada vez até que o ciclo de deadlock seja eliminado.
     • Preempção de recursos
       • Ordem = minimização dos custos
         • Reversão (Rollback)
           • Retornar a algum estado seguro, reiniciar processo para esse estado
             • Starvation
               • Algum processo pode sempre ser apanhado como vítima
                 • Incluir número de rollbacks no fator de custo