Please enable JavaScript.
Coggle requires JavaScript to display documents.
Deadlocks - Coggle Diagram
Deadlocks
O problema
processo não obtém recursos para mudar de estado
estão reservados por outro processo, ele também segura
ex: Lei do Kansas sobre trens
ex: namorados orgulhosos
ex: discos D1 e D2
P1 segura D1
P2 segura D2
P1 precisa de D2 para liberar D1
vice-versa
Modelo de sistema
conjunto finito de recursos
tipos de recurso
espaço de memória
dispositivos de E/S
ciclos de clock
cada recurso admite 2 ou mais instâncias
ex: CPU de 2 núcleos
2 instâncias
instâncias de mesmo dispositivo são idênticas
processo usa recursos
uso
liberação
requisição
Caracterização
condições necessárias
exclusão mútua
um processo por vez utiliza recurso
não preempção
recurso só pode ser liberado voluntariamente
manter e esperar
espera circular
P0 aguarda R de P1
P1 aguarda R de P2
P(N-1) aguarda R de PN
PN aguarda R de P0
grafo de alocação de recusos
não há ciclos
não há deadlock
se há um ciclo
1 instância por recurso
há deadlock
+ de 1 instância por recurso
possibilidade de deadlock
Métodos para tratamento de deadlock
permitir e recuperar-se
SO capaz de verificar deadlock
ignorar se forem raros
usado pela maioria
UNIX e Windows
garantir que nunca ocorra
pelo menos uma condição não seja satisfeita
Prevenção de deadlock
Evitando deadlock
P(i) diz oq irá precisar
ex: ficha de treino
tudo está disponível?
sim
executa
não
aguarda
P(j) encerra
executa
Obj: Manter estado seguro
Estado seguro
não há deadlock
Estado inseguro
possibilidade de deadlock
Detecção de deadlock
Algoritmo 1
Verificar se há deadlock
1 instância por recurso
manter grafo de espera
periodicamente procurar por ciclos
se há ciclo, há deadlock
n^2 operações
n = nº de vértices
múltiplas instâncias por recurso
usa-se matrizes
algoritmo ordem O(m x n^2)
Recuperação de deadlock
Algoritmo 2
Se recuperar do deadlock
Informe ao usuário e deixe que ele resolva
Deixe o sistema resolver
Abortar processos
interromper espera circular
aborte todos em deadlock
um por vez até eliminar ciclo
em que ordem?
prioridade
tempo de execução passado
recursos necessários
recursos ainda necessários
interativo ou batch?
Preemptar recursos
seleciona vítima
minimizar custos
quais processos e recursos?
Rollback
retornar ao um estado seguro
reiniciar processo a esse estado
starvation
processo sempre vítima
incluir nº de rollbacks no custo