UESB Sistemas de Informação
Sistemas Operacionais
Impasses ou Deadlocks
Prof. VANILDO MEIRA
Prof. Vanildo Meira
Introdução
• Os sistemas computacionais (S.C.) possuem
inúmeros recursos adequados ao uso de apenas um
processo de cada vez.
• P.E. se dois processos acessam uma impressora
simultaneamente e sem controle do SO, o mais
provável que aconteça é que se “misturem” as duas
impressões, ficando o resultado final, imprestável
aos dois processos.
• O S.O. deverá garantir o acesso exclusivo.
Prof. Vanildo Meira
Recursos
São os componentes de um S.C. acessados:
• Dispositivos físicos (hardware): memória, discos,
impressoras, fitas magnéticas, etc.
• Dados: Variáveis compartilhadas, registros de
banco de dados, tabelas, etc.
Observações:
• Podem existir diversas cópias um recurso.
• Processos podem requisitar vários recursos.
• Os Processos precisam acessar os recursos em uma
ordem definida (organizada pelo SO).
Prof. Vanildo Meira
Impasse (ou deadlock)
Prof. Vanildo Meira
Impasse (ou deadlock)
Prof. Vanildo Meira
Impasse (ou deadlock)
Prof. Vanildo Meira
Preempção
• Recurso preemptível – pode se retirado do
processo proprietário sem prejuízo. Ex. memória.
• Recurso não preemptível – retirada do recurso
gera falhas na computação. Ex. Gravador de
CD/DVD..
• Em geral, impasses envolvem recursos não
preemptíveis. Para garantir que recursos não
compartilháveis e não preemptíveis possam ser
adquiridos normalmente são usados semáforos.
Prof. Vanildo Meira
Eventos
Prof. Vanildo Meira
Condições para impasses
• Condição de exclusão mútua – em um
dado instante cada recurso está em uma de
duas situações: associado a um único
processo ou disponível.
• Condição de posse e espera – processos
podem reter recursos anteriormente
concedidos e requisitar novos recursos.
Prof. Vanildo Meira
Condições para impasses
• Condição de não preempção – recursos
concedidos previamente a um processo não
podem ser tomados a força deste processo.
• Condição de espera circular – deve existir
um encadeamento circular de 2 ou mais
processos, cada um esperando por um recurso
que está associado ao membro seguinte desta
cadeia.
Prof. Vanildo Meira
Como ocorre um impasse
Prof. Vanildo Meira
Como tratar impasses
Prof. Vanildo Meira
1. Algoritmo do avestruz
• A ocorrência de deadlock é ignorada. Solução
adotada pela maioria dos sistemas
operacionais, como Unix e Windows.
• Solução razoável se: Deadlocks são raros, e
muitos deadlocks não geram danos ao sistema.
O custo da prevenção de deadlocks é alto.
Prof. Vanildo Meira
2. a) Detecção de deadlocks
• Construir um grafo do sistema.
• Existe um recurso de cada tipo – Um
deadlock é identificado por ciclos no grafo
direcionado do sistema.
• Utilizar algoritmos de busca que procuram
ciclos em grafos direcionados. Busca em
profundidade; e Busca em amplitude.
Prof. Vanildo Meira
2. b) Recuperação
• Preempção – depende da natureza do recurso;
• Reversão de estado: a) Verificação periódica
(checkpoint), armazenando o estado de cada processo
em um arquivo (checkpoint file). b) Retorna os
processos em deadlock para um estado anterior à
ocorrência do deadlock. O trabalho executado é
perdido.
• Eliminação de processos presentes no ciclo – pode ser
escolhido o processo com maior número de recursos
bloqueados. Outros processos serão eliminados até o
deadlock ser desfeito.
Prof. Vanildo Meira
3. Evitar impasses
• Só alocar recursos quando for seguro.
• Estado seguro – não existe deadlock, e existe
uma ordem de escalonamento na qual todos os
processos podem executar até a sua conclusão.
• Gráfico representando o escalonamento de cada
processo, sua execução, e situações com risco
de deadlock.
• Algoritmo do banqueiro (Dijkstra 1965).
Prof. Vanildo Meira
Resumo - Evitando impasses