Please enable JavaScript.
Coggle requires JavaScript to display documents.
Deadlocks - Coggle Diagram
Deadlocks
O Problema do Deadlock
Competição por recursos em um ambiente de multiprogramação
Entrar em estado de espera e impossibilidade de avançar
Deadlock = “Impasse”
Conjunto de processos bloqueados esperando por recursos
Caracterização do deadlock
Condições necessárias
Exclusão mútua
Manter e esperar
Não preempção
Espera circular
Grafo de Alocação de Recursos
Vértices para processos e recursos
Arestas de requisição e atribuição
Se o grafo não contém ciclos → sem deadlock
Se o grafo contém um ciclo →
Se apenas uma instância por tipo de recurso, então deadlock.
Se várias instâncias por tipo de recurso, possibilidade de deadlock.
Evitando Deadlock
Informações adicionais a priori para evitar deadlock
Modelo mais simples é cada processo declarando necessidade máxima de recursos
Exame dinâmico do estado de alocação para garantir que não há espera circular
Estado seguro e verificação dinâmica
Métodos para Tratamento de Deadlocks
Garantir que o sistema nunca entrará em deadlock
Garantir que pelo menos uma condição necessária não seja satisfeita
Permitir deadlock e recuperar
Ignorar o problema
Prevenção de Deadlock
Garantir que ao menos uma das condições necessárias não seja atendida
Exclusão mútua
não exigido para recursos compartilháveis
Manter e esperar
garantir que um processo que solicita um recurso, não tenha outros recursos
Baixa utilização de recursos
Não preempção
Liberação de recursos mantidos se a solicitação não pode ser atendida
Recursos preemptados adicionados à lista de espera
Reinício do processo após reobter recursos
Espera Circular
Ordenação total de tipos de recurso
Processos devem solicitar recursos em ordem de enumeração aumentada
Estado Seguro
Decisão sobre alocação imediata deixar o sistema seguro
Sequência de processos que podem obter recursos necessários uns dos outros
Fatos Básicos
Estado seguro implica sem deadlocks
Estado inseguro implica possibilidade de deadlock
Detecção de Deadlock
o sistema precisa prover
Algoritmo de detecção
Algoritmo de recuperação
Única instância de cada tipo de recurso
Gráfico de espera
Chame um algoritmo que procure um ciclo no gráfico
Se houver um ciclo, existe um deadlock
Múltiplas instâncias de um tipo de recurso
Algoritmos usando matrizes
Recuperação de deadlock
Informar o usuário
Recuperação automática
Abortar ou preemptar processos
Preempção de Recursos
Seleção de vítimas
Reversão (Rollback)
Starvation