Deadlock

Deadlock

1. Evitando Deadlock

   • Exige que o sistema tenha alguma informação adicional a priori
   • 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
   • 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.
   • Estado Seguro
     • Quando um processo solicita um recurso disponível, o sistema deve decidir se a alocação imediata deixa o sistema em um estado seguro
     • Um sistema está em estado seguro se:
       • For possível encontrar uma sequência de execução dos processos onde, para cada processo, seus recursos necessários podem ser atendidos pelos recursos disponíveis no momento, somados aos recursos liberados por processos que já foram executados.
     • Fatos Básicos
       • Se um sistema estiver no estado seguro -> sem deadlocks.
       • Se um sistema estiver em estado inseguro -> possibilidade de deadlock
       • Como evitar deadlock?
         • Garanta que um sistema nunca entrará em um estado inseguro

2. Detecção de Deadlock

   • 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
   • Única Instância de Cada Tipo de Recurso
     • Manter gráfico de espera
       • Nós são processos
       • Pi -> Pj se Pi estiver esperando por Pj
     • Periodicamente, chame um algoritmo que procure um ciclo no gráfico. Se houver um ciclo, existe um deadlock
     • Um algoritmo para detectar um ciclo em um gráfico requer uma ordem de n 2 operações, onde n é o número de vértices no gráfico
   • Múltiplas Instâncias de um Tipo de Recurso
     • Algoritmo requer uma ordem de O(m x n2 ) operações para detectar se o sistema está em estado de deadlock

3. Recuperação de Deadlock

   • Se 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
     • Em que ordem devemos decidir abortar
       • Em que ordem devemos decidir abortar
       • Por quanto tempo o processo foi executado, e quanto falta para terminar
       • Recursos que o processo utilizou
       • Recursos que o processo precisa para completar
       • Quantos processos terão que ser terminados
       • O processo é interativo ou batch?
   • Preempção de Recursos
     • Três questões
       • Seleção uma vítima
         • Quais recursos/processos devem ser preemptados?
         • 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