BENÇAO

UD II : Impasse: ”Deadlock”
Ref:

• SOM - A.S. Tanenbaum – cap 1 e 3
• SOC-SGG - Silberschatz – cap 7e 8
• ASO – F. B. Machado – cap 7
(Adaptado de Arquitetura de Sistemas Operacionais de F. B. Machado e L. P. Maia e
Sistemas Operacioais Modernos – A.S. Tanenbaum)

1

Deadlocks: sumário

1. Conceitos de Deadlock
2. Definição Formal
3. Condições para Deadlock
4. Algoritmo do avestruz (“ostrich”)
5. Deteccão e Recuperação de Deadlock
6. Evitando Deadlock
7. Prevenção de Deadlock

2

Deadlock no trânsito (analogia)

(a) Deadlock potencial (b) Deadlock real
3

Deadlocks: conceitos (1) (SOM-TB)
• Exemplos de recursos computacionais
– Impressoras
– Drives de fita magnética, Gravadores de CD/DVD
– Tabelas, registros de BD

• Processos precisam ter acesso aos recursos em uma ordem razoável
• Suposição:
– Processo A retém o recurso 1 e requisita o recurso 2
– Processo B retém o recurso 2 e requisita o recurso 1 mesmo tempo (simultanente)
– Ambos ficam bloqueados e permanecem assim

4

Deadlock Computacional (ASO-M)
• Espera circular
Processo A
Processo A solicita o
Recurso 2

Recurso 1 alocado ao
Processo A

Recurso 2

Recurso 1

Processo B

Recurso 2 alocado ao
Processo B

Processo B solicita o
Recurso 1

5

Deadlocks: conceitos (2) (SOM-TB)
• Deadlocks ocorrem quando os processos precisam de acesso exclusivo ao recurso.
• Recursos preemptivos podem ser retirados dos processos sem causar falhas.
• Recursos não preemptivos não podem ser retirados dos processos, pois se forem retirados podem causar falhas.

6

Deadlocks: conceitos (3) (SOM-TB)
•

Seqüência de eventos necessários adquirir e usar um recurso
1. Requisitar o recurso
2. Usar o recurso
3. Liberar o recurso

•

Processos precisam esperar (“wait”) se um recurso não estiver disponível
– O processo requisitante pode bloquear ou
– Pode falhar com um código de erro
7

Deadlock: definição formal (SOM-TB)
• Um