DeadLock
Sistemas Operacionais I
Módulo 7
DEADLOCK
Ocorre quando um grupo de
processos competem por acesso a
recursos fixos
 Definição

–
Deadlock ocorre entre um conjunto de
processos se todos os processos estão
aguardando por um evento que só pode
ser gerado por um processo do conjunto
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-2
DEADLOCK

Exemplo
–
Dois processos compartilham dois
recursos que precisam ser requisitados,
antes do uso, e liberados, após o uso. A
ação de requisição causa bloqueio do
processo até o recursos estar disponível
 Proc1:
request tape
request printer
… <uso>
release printer
release tape
Sistemas Operacionais I - Versão Beta 3
Proc2:
request printer
request tape
… <uso>
release tape
release printer
24/04/2001
9-3
CONDIÇÃO PARA DEADLOCK

Quatro condições necessárias
–
Exclusão mutua
 Ao
menos um processo retém recurso em
modo não compartilhado
–
Hold-and-wait
 Um
processo pode reter um recurso
enquanto aguarda outro
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-4
CONDIÇÃO PARA DEADLOCK

Quatro condições necessárias
–
Não preempção
 Recurso
–
não pode ser preemptado
Espera circular
 Existe
um conjunto de processos [p1, p2, …,
pn] tal que p1 espera p2, p2 por p3, ….
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-5
GRAFO DE ALOCAÇÃO DE
RECURSOS

Deadlock pode ser descrito por meio
de um Grafo de Alocação de Recursos
–
Conjunto de vértices
 Processos={P1,P2,…,Pn}
 Recursos={R1,R2,…,Rm}
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-6
GRAFO DE ALOCAÇÃO DE
RECURSOS

Deadlock pode ser descrito por meio
de um Grafo de Alocação de Recursos
–
–
–
Uma conexão direta de um Processo
para um Recurso, Pi Rj, indica que Pi
requisitou Rj.
Uma conexão direta de um Recurso para
um Processo , RjPi, implica que es that
Rj foi alocada por Pi.
Se não houver ciclos deadlock não existe
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-7
GRAFO DE ALOCAÇÃO DE
RECURSOS
R1
R1
R3
.
.
P1
R1
P2
.
.
R2
R3
P3
R3
P1
P2
.
.
.
.
.
.
R4
R2
P3
.
.
.
R4
P4
Há deadlock.
Mesmo ciclos mas sem deadlock.
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-8
ENFOQUES

Prevenir
–
Assegure que ao menos uma das quatro
condições não será satisfeita
 Exclusão
–
mutua
Torne os recursos compartilháveis (não é sério)
 Hold-and-wait
–
–
Garanta que um processo não pode reter um
recurso quando requisitar outro, ou...
Requisição coletiva: faça com que os recursos
sejam alocados de um só vez e liberados antes de
requisitar um novo conjunto
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-9
ENFOQUES

Prevenir
–
Assegure que ao menos uma das quatro
condições não será satisfeita
 Espera
–
–
circular
Imponha uma ordenação nos recurso
Só é possível alocar Rj se j>i
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-10
ENFOQUES

Evitar
–
Idéia
 Prover
informação sobre os recursos que
serão necessários para o processo
 Garantir que o deadlock não ocorrerá
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-11
ENFOQUES

Evitar
–
Passo 1
 Quando
requisitado um recurso Rj, mesmo
que esteja disponível, não é alocado ao
processo solicitante, embora seja garantido o
uso
–
Processo vai para bloqueio
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-12
ENFOQUES

Evitar
–
Passo 2
 Avaliar
quando é possível efetuar a alocação
seguramente
–
Passo 3
 Se
seguro, alocar
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-13
ENFOQUES

Evitar
–
Exemplo
 Processos
p0, p1 e p2 competem por 12
dispositivos de fita
max
 p0 10
 p1 4
 p2 9
 Existe uma
–
–
–
corrente
solicitado
5
5
2
2
2
7
seqüência segura <p1,p0,p2>
p1 pode completar com os recursos livres
p0 pode completar com os recursos livres+p1
p2 pode completar com os recursos livres+p1+p0
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-14
ENFOQUES

Evitar
–
Exemplo
 Se
p2 requisitar uma unidade, deve esperar
porque o estado se tornará inseguro
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-15
ENFOQUES

Algoritmo do banqueiro
–
Decide quando ceder um recurso
solicitado
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-16
ENFOQUES

Deteção
–
–
Se não prevenir e não evitar, deadlock vai
atacar
Nesse caso, devemos ter:
 Um
algoritmo para determinar quando o
deadlock ocorre
 Um algoritmo para corrigir o deadlock
 É “lindo”! Mas custa caro
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-17
ENFOQUES

Deteção
–
Algoritmo de deteção de deadlock
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-18
ENFOQUES

Deteção
–
–
Deteção é cara
Quando detectar?
 Depende
–
–
de:
Qual a possibilidade de deadlock
Quantos processos são afetados quando o
deadlock ocorre
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-19
ENFOQUES

Recuperação
–
Opções
 Abortar
todos os processos envolvidos no
deadlock
–
Resulta no custo computacional repetido
(submissão dos processos novamente)
 Abortar
um dos processos por vez até que o
ciclo (deadlock) seja eliminado
–
Resulta na aplicação do algoritmo de deteção após
cada aborto
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-20
ENFOQUES

Recuperação
–
Opções
 Preemptar
–
–
Liberar recursos até que o deadlock termine
Pontos negativos:
 Seleção da vítima
 Rollback
 starvation
 Ficar
–
quietinho e deixar o sistema parar
Muito utilizado
Sistemas Operacionais I - Versão Beta 3
24/04/2001
9-21