Deadlock

Deadlock

1. "Impasse"

   • conjunto de
     • proc. bloqueados
       • um mantendo
         • recurso e esperando
           • p/ adquirir um
             • recurso mantido
               • por outro

2. Modelo do sistema

   • sistema =
     • conjunto finito
       • de recursos a
         • serem distribuidos
           • proc. em competição
             • ex.: ciclo de CPU,
               • espaço de memo
                 • despositivos de E/S
                   • Instâncias
                     • identicas
                       • Utilização de recursos:
                         • Requisição
                           • Uso
                             • Liberação

3. Caracterização do deadlock

   • Quatro condições
     • simultaneamente
       • 1)Exclusão mútua
         • 1 proc. de cd vz
           • usar recurso
             • 2)Manter em espera
               • Proc. mantendo
                 • pelo menos1 rec.
                   • esperando + recursos
                     • mantidos por
                       • outros proc
                         • 3)Não preempção
                           • rec. liberado somente
                             • dps do proc.
                               • terminar tarefa
                                 • 4)Espera circular
                                   • um proc. esperando
                                     • esperando recurso
                                       • mantido pelo prox
                                         • ultimo pelo primeiro

4. Grafo de alocação de recursos

   • Vertice parcionada
     • P=Processos
       • R=Recursos
         • Aresta de requisição
           • P->R
             • Aresta de atribuição
               • R->P
                 • S/ ciclos =
                   • s/ deadlock
                     • C/ ciclos
                       • Se 1 instância
                         • deadlock
                           • Se várias
                             • possibilita deadlock

5. Método p/ tratamento de deadlock

   • -Garantir q
     • sistema nunca entre
       • em deadlock
         • -Permitir q
           • sistema entre
             • em deadlock e
               • dps recupere
                 • -Fingir q
                   • nunca ocorre deadlock

6. Prevensão de deadlock

   • Garantir q
     • pelo menos 1
       • das 4 condições
         • ñ seja atendida
           • (1) ñ exigido p/
             • rec. comp.
               • manter p/
                 • rec. ñ comp
                   • (2) garantir q
                     • proc. dps de
                       • solicitar rec.
                         • mantem outro
                           • (3)proc. mantendo rec
                             • q ñ pode ser alocado
                               • rec mantidos
                                 • liberados
                                   • rec preemptado
                                     • add lst rec
                                       • Proc só reiniciado
                                         • antigos e novos rec
                                           • (4) ordenação
                                             • tipos de recursos
                                               • proc solicite rec
                                                 • ordem enumeração
                                                   • aumentada

7. Evitando deadlock

   • info adicional a priori
     • modelo + simples
       • e + útil
         • cd proc declara nº
           • max rec de cd tipo
             • O algoritmo
               • examina dinamicamente
                 • estado de alocação
                   • p/ garantir nunca
                     • haver espera circular
                       • Estado de alocação
                         • definido
                           • nº de rec
                             • disponíveis e alocados
                               • e demandas max

8. Estado seguro

   • Qndo proc. solicita
     • rec disponivel
       • sistema decidir
         • se alocação imediata
           • Estado seguro
             • Se recursos
               • ñ estiverem
                 • dispo imediatamente
                   • espera um
                     • proc terminar
                       • p/ obter rec

9. Detecção de deadlock

   • sistema prover
     • Algoritmo
       • *Examine estado
         • do sitema
           • *p/ recuperar do
             • deadlock

10. Preempção de recursos

    • 3 questões:
      • *Seleção uma vítima
        • quais rec/proc
          • preemptados?
            • ordem=
              • minimização dos custos
                • *Reversão(Rollback)
                  • retornar estado seguro
                    • reiniciar proc
                      • *Starvation
                        • proc smp apanhado
                          • vitima
                            • inclui nº
                              • rollbacks
                                • no fator de custo

11. Recuperação de deadlock

    • caso detectado:
      • *Informar ao Us
        • manualmente
          • *Sistema se recupere
            • automaticamente
              • abordando 1 ou + proc
                • p/ interromper a (4)
                  • Preemptando alguns rec
                    • de 1 ou + proc
                      • em deadlock
                        • 2 Possibilidades
                          • *Abortar todos proc
                            • *abortar 1 de cd vz
                              • até ciclo eliminado
                                • ordem abortar

12. Unica instância de cd rec

    • Gráfico de espera
      • Nós = Proc
        • Periodicamente
          • algoritmo procurando
            • ciclo no gráfico
              • ordem de n²
                • n = vertices
                  • C/ VÁRIAS instâncias
                    • ordem de O(m x n²)