Deadlocks

Deadlocks

1. Um processo em espera não consegue mais mudar de estado pois precisa de um evento de outro processo que também está em espera

   • Deadlock surge quando acontece simultaneamente:
     • Exclusão mútua
       • Apenas um processo por vez pode usar um recurso
     • Manter e esperar
       • Um processo com um recurso está esperando para adquirir outros recursos mantidos por outros processos
     • Não preempção
       • O recurso só pode ser liberado voluntariamente pelo processo
     • Espera circular
       • Há um conjunto de processos (P0 até Pn) onde P0 espera recurso de P1... até Pn espera processos de P0

2. Grafo de alocação de recursos

   • Conjunto P =Processos do sistema, Conjunto R = Recursos do sistema
     • Aresta de requisição
       • Pi -> Rj
     • Aresta direcionada
       • Rj -> Pi
   • Se o grafo não contém ciclos, não tem deadlock
   • Se o grafo tem ciclos
     • Uma instância por tipo de recurso
       • Deadlock
     • Várias instâncias por tipo de recurso
       • Possível deadlock

3. Tratamentos de deadlock

   • Nunca entrará em deadlock
     • Garantir que pelo menos umas das condições não sejam satisfeitas
       • Exclusão mútua
       • Manter e esperar
       • Não-preempção
       • Espera circular
   • Permitir que entre em deadlock porém se recupere
     • SO deve ser capaz de determinar se houve deadlock
   • Ignorar o problema e fingir que os deadlocks nunca ocorrem no sistema

4. Evitando deadlock

   • Exigir que o sistema tenha alguma informação adicional de ínicio
   • Cada processo declara o número máximo de recursos que ele pode precisar
   • Garantia de nunca 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
     • Sistema decide se a alocação imediata deixa o sistema em estado seguro
       • Sistema está seguro quando uma sequência de todos os processos na qual, para cada Pi possa esperar até Pj acabar
         • Quando Pj tiver terminado, Pi pode obter os recursos necessários, executar, retornar recursos alocados e terminar
           • Se estiver seguro, sem deadlocks
           • Se estiver inseguro, possibilidade de deadlocks

5. Detecção de deadlock

   • SO precisa ter algoritmo que examine o estado do sistema para ver se ocorreu deadlock ou pra recuperar do deadlock
   • Única instância de cada tipo de recurso
     • Periodicamente, chame um algoritmo que procure um ciclo no gráfico
       • Se houver, existe deadlock
   • 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

6. Recuperação de deadlock

   • Informar ao usuário e deixar que o mesmo resolva manualmente
   • Deixar que o sistema se recupere automaticamente
   • Terminando processos
     • Aborte todos os processos em deadlock
     • Aborte um processo de cada vez até que o ciclo de deadlock seja eliminado

7. Preempção de recursos

   • Seleção de uma vítima
     • Escolhe um recurso/processo por minimização de recursos
   • Reversão
     • Retornar a algum estado seguro
   • Starvation
     • Algum processo pode sempre ser apanhado como vítima