Please enable JavaScript.
Coggle requires JavaScript to display documents.
Deadlocks - Coggle Diagram
Deadlocks
Evitando Deadlock
Cada processo deve declarar o núm máx de recursos que pode precisar
Algoritmo examina estado de alocação de recurso para evitar espera circular
Estado Seguro: todos os processos possam ser satisfeitos com recursos disponíveis no sistema
Sistema no estado seguro = sem deadlocks
Sistema no estado inseguro = possível deadlock
Garanta que um sistema nunca entre em estado inseguro
Prevenção
Manter e esperar
Não-preempção
Exclusão Mútua
Espera circular
O problema Deadlock
Deadlock = Impasse
Conjunto de processos bloqueados mantendo um recurso e esperando por outro de outro processo
Processo em espera não muda estado pois recursos solicitados estão em outros processos
Modelo do Sistema
Recursos
Espaço de memória
Ciclos de CPU
Dispositivos E/S
Como processos utilizam recursos
Requisição/Solicitação
Uso
Liberação
Sistema: conjunto finito de recursos distribuídos entre processos em competição
Métodos para Tratamento
Garantir que o sistema nunca entrará em deadlock
Permitir que o sistema entre em deadlock e depois se recupere
Ignorar o problema e fingir que deadlocks nunca ocorrem no sistema (windows e unix)
Recuperação de Deadlock
Terminando os processos
Abortar todos os processos em deadlock
Abortar um de cada vez até que o ciclo deadclock seja eliminado
Preempção de Recursos
Reversão
Retornar a algum estado seguro
Starvation
Algum processo pode ser apanhado como vítima
Incluir rollbacks(reversão) no fator de custo
Seleção da vítima
Ordem = minimização de custos
Quais recursos/processos devem ser preemptados?
Deadlock detectado
Deixar o sistema se recuperar automaticamente
Informar o usuário e deixar resolver manualmente
Caracterização
Condições Necessárias
Manter e esperar
Processo mantem um recurso e espera para adquirir outro de outro processo
Não preempção
Recurso só é liberado pelo processo depois do mesmo terminar sua tarefa
Exclusão mútua
Apenas um processo de cada vez usando um recurso
Espera circular
Impõe ordenação de todos os recursos e exige solicitações de cada processo
Grafo de Alocação de Recursos
R = conjunto de todos os recursos no sistema
Aresta de requisição = Pi -> Rj
P = conjunto de todos os processos no sistema
Aresta de atribuição = Rj -> Pi
Se grafo não contém ciclo = sem deadlock
Se grafo contém ciclo e só uma instância por recurso = deadlock
Se grafo contém ciclo e várias instâncias por recurso = possível deadlock
Detecção
Única Instância de cada tipo de recurso
Algoritmo procura ciclo gráfico
Se houver ciclo = deadlock
Mantem gráfico de espera
Múltiplas Instâncias de um tipo de recurso
Detectar se o sistema está em deadlock
Algoritmos utilizando matrizes