Capítulo 7: Deadlocks
Operating System Concepts – 8th Edition
Silberschatz, Galvin and Gagne ©2009
O Problema do Deadlock
 Um conjunto de processos bloqueados, cada um bloqueando um
recurso e esperando adquirir um recurso bloqueado por outro processo
do conjunto


Exemplo

Sistema com dois drivers de disco

P1 e P2 possuem um driver e querem adquirir mais um driver
Exemplo

Semáforos A e B, inicializados como 1
P0
P1
wait (A);
wait (B);
wait(B) ;
wait(A);
Operating System Concepts – 8th Edition
7.2
Silberschatz, Galvin and Gagne ©2009
Exemplo do cruzamento da ponte
 Apenas uma mão por vez
 Cada seção da ponte pode ser vista como um recurso
 Se um deadlock ocorrer, ele pode ser resolvido se um dos
carros der ré (libera recursos e desfaz a ação)
 Pode ser necessário mover muitos carros se um deadlock
ocorrer
 Inanição é possível
 Observação

A maioria dos OSs não evitam ou lidam com deadlocks
Operating System Concepts – 8th Edition
7.3
Silberschatz, Galvin and Gagne ©2009
Exemplo de deadlock
 Thread-sem-deadlock.py
 Thread-com-deadlock.py
Operating System Concepts – 8th Edition
7.4
Silberschatz, Galvin and Gagne ©2009
Modelo do Sistema
 Tipos de recurso: R1, R2, . . ., Rm
Exemplos: Ciclos de CPU, espaço de memória, dispositivos
de E/S
 Cada recurso do tipo Ri tem Wi instâncias
 Cada processo usa um recurso da seguinte forma:

requisita

usa

libera
Operating System Concepts – 8th Edition
7.5
Silberschatz, Galvin and Gagne ©2009
Caracterização do deadlock
O deadlock pode ocorrer se 4 condições ocorrem
simultaneamente:
 Exclusão mútua: apenas um processo pode usar um certo
recurso de cada vez
 Posse e espera: um processo bloqueando pelo menos um
recurso está esperando para obter recursos adicionais
bloqueados por outros processos
 Sem preempção: um recurso pode ser liberado apenas
voluntariamente por um processo, após o processo ter concluído
as suas tarefas
 Espera circular: existe um conjunto {P0, P1, …, Pn} de
processos esperando de tal forma que P0 está esperando por um
recurso que está bloqueado por P1, P1 está esperando por um
recurso que está bloqueado por P2, …, Pn–1 está esperando por
um recurso que está bloqueado por Pn, e Pn está esperando por
um recurso que está bloqueado por P0.
Operating System Concepts – 8th Edition
7.6
Silberschatz, Galvin and Gagne ©2009
Grafo de alocação de recursos
Conjunto de vértices V e conjunto de arestas E.
 V é particionado em dois tipos:

P = {P1, P2, …, Pn}


Conjunto com todos os processos do sistema
R = {R1, R2, …, Rm}

Conjunto de todos os recursos do sistema
 Aresta de requisição – aresta direcionada Pi  Rj
 Aresta de atribuição – aresta direcionada Rj  Pi
Operating System Concepts – 8th Edition
7.7
Silberschatz, Galvin and Gagne ©2009
Grafo de alocação de recursos
 Processo
 Tipo de recurso com 4 instâncias
 Pi requisita uma instância de Rj
Pi
Rj
 Pi está bloqueando uma instância de Rj
Pi
Rj
Operating System Concepts – 8th Edition
7.8
Silberschatz, Galvin and Gagne ©2009
Exemplo de grafo de alocação de recursos
Operating System Concepts – 8th Edition
7.9
Silberschatz, Galvin and Gagne ©2009
Grafo de alocação de recursos com deadlock
Operating System Concepts – 8th Edition
7.10
Silberschatz, Galvin and Gagne ©2009
Grafo de alocação de recursos com
ciclo, mas sem deadlock
Operating System Concepts – 8th Edition
7.11
Silberschatz, Galvin and Gagne ©2009
Fatos básicos
 Se um grafo não contém ciclos  ausência de deadlock
 Se um grafo contém ciclos 

Se existe apenas um instância de cada tipo de recurso, então
tem deadlock

Se existem diversas instâncias por tipo de recurso, possibilidade
de deadlock
Operating System Concepts – 8th Edition
7.12
Silberschatz, Galvin and Gagne ©2009
Métodos para lidar com Deadlocks
 Garantir que o sistema nunca entrará em um estado de deadlock
 Permitir que o sistema entre em um estado de deadlock e, então,
recuperar
 Ignorar o problema e fingir que deadlocks nunca ocorrem no sistema

Usado pela maioria dos sistemas operacionais, incluindo UNIX
Operating System Concepts – 8th Edition
7.13
Silberschatz, Galvin and Gagne ©2009
Prevenção de deadlock
Restringir a forma como os pedidos podem ser feitos, tratando ao menos uma
das condições de deadlock:
 Exclusão mútua - não é necessário para recursos
compartilháveis; contudo, deve ser aplicada aos recursos não
compartilháveis
 Posse e espera – deve garantir que, sempre que um processo
solicita um recurso, não possui quaisquer outros recursos

Exigir que o processo solicite e aloque todos os seus recursos
antes de iniciar a execução, ou permitir que o processo
solicite recursos somente quando o processo não tem
nenhum recurso alocado

Desvantagens

Baixa utilização de recursos

Inanição possível
Operating System Concepts – 8th Edition
7.14
Silberschatz, Galvin and Gagne ©2009
Prevenção de deadlock (Cont.)
 Ausência de preempção – Se um processo que está em posse de
alguns recursos solicita outro recurso que não pode ser
imediatamente alocado para ele, então todos os recursos possuídos
são liberados

Recursos liberados são adicionadas à lista de recursos que o
processo está aguardando

O processo será reiniciado somente quando ele conseguir todos
os recursos que está requisitando
 Espera circular – impor uma ordenação de todos os tipos de
recursos e exigir que cada processo solicite recursos na ordem
crescente de numeração

Problemas

Como numerar recursos?

Pedidos de recursos são feitos pelo programador, que
desconhece a ordem imposta pelo sistema
Operating System Concepts – 8th Edition
7.15
Silberschatz, Galvin and Gagne ©2009
Impedimento de Deadlock
Requer que o sistema tenha informações adicionais a priori
 Modelo mais simples e mais útil

Exige que cada processo declare o número máximo de
recursos de cada tipo que pode precisar
 O algoritmo para evitar deadlock examina dinamicamente o estado
de alocação de recursos para garantir que nunca pode haver uma
condição de espera circular

O estado de alocação de recursos é definido pelo número de
recursos disponíveis e alocados

Exige que os processos declarem a sua demanda máxima
A ideia é garantir que o processo fique
em um estado seguro.
Operating System Concepts – 8th Edition
7.16
Silberschatz, Galvin and Gagne ©2009
Estado Seguro
 Quando um processo solicita um recurso disponível, o sistema deve
decidir se a alocação imediata deixa o sistema em um estado seguro
 O sistema está em estado seguro se existe uma sequência <P1, P2,
…, Pn> de todos os processos do sistema de tal forma que, para cada
Pi, os recursos que Pi ainda pode solicitar podem ser atendidos pelos
recursos atualmente disponíveis + recursos mantidos por todos Pj,
com j <i
 Isto é:

Se as necessidades de recursos do Pi não estão imediatamente
disponíveis, então Pi pode esperar até que todos os Pj ter
terminado

Quando Pj terminar, Pi pode obter os recursos necessários,
executar, retornar os recursos alocados e terminar

Quando termina Pi, Pi +1 pode obter seus recursos necessários, e
assim por diante
Operating System Concepts – 8th Edition
7.17
Silberschatz, Galvin and Gagne ©2009
Fatos básicos
 Se um sistema está em estado seguro  não ocorre deadlocks
 Se um sistema está em estado inseguro  possibilidade de
deadlock
 Para evitar deadlocks  assegurar que um sistema nunca entrará
em um estado inseguro
Operating System Concepts – 8th Edition
7.18
Silberschatz, Galvin and Gagne ©2009
Estados seguro, inseguro e de
deadlock
Operating System Concepts – 8th Edition
7.19
Silberschatz, Galvin and Gagne ©2009
Algoritmos para evitar deadlocks
 Única instância de um tipo de recurso

Use um gráfico de alocação de recursos
 Várias instâncias de um tipo de recurso

Use o algoritmo do banqueiro
Operating System Concepts – 8th Edition
7.20
Silberschatz, Galvin and Gagne ©2009
Esquema Gráfico de Alocação de
Recursos
 Aresta de reivindicação Pi  Rj indica que o processo Pj pode
solicitar recursos Rj

Representada por uma linha tracejada
 A aresta de reivindicação é convertida para aresta de pedido quando
o processo solicita o recurso
 A aresta de pedido é convertida para uma aresta de atribuição
quando o recurso é alocado ao processo
 Quando um recurso é liberado por um processo, a aresta de
atribuição é convertida em uma aresta de reivindicação
 Os recursos devem ser reivindicados a priori no sistema
Operating System Concepts – 8th Edition
7.21
Silberschatz, Galvin and Gagne ©2009
Gráfico de Alocação de Recursos
Operating System Concepts – 8th Edition
7.22
Silberschatz, Galvin and Gagne ©2009
Estado inseguro em Gráfico de Alocação de
Recursos
Operating System Concepts – 8th Edition
7.23
Silberschatz, Galvin and Gagne ©2009
Algoritmo Gráfico de alocação de
Recursos
 Suponha que o processo Pi requisite o recurso Rj
 O pedido pode ser concedido apenas se a conversão da aresta de
pedido para uma aresta de atribuição não resultar na formação de um
ciclo no gráfico de alocação de recursos
Operating System Concepts – 8th Edition
7.24
Silberschatz, Galvin and Gagne ©2009
Algoritmo do Banqueiro
 Usado quando existem várias instâncias de cada recurso
 Cada processo precisa informar a quantidade máxima que pode
utilizar de cada recurso
 Quando um processo solicita um recurso, talvez precise esperar
para poder alocá-lo
 Quando um processo recebe todos os seus recursos, deve devolvê-
los em uma quantidade finita de tempo
Operating System Concepts – 8th Edition
7.25
Silberschatz, Galvin and Gagne ©2009
Estruturas de Dados para o algoritmo do
banqueiro
Seja n o número de processos e m o número de tipos de recursos:
 Disponível: Vetor de tamanho m. Se disponível [j] = k, existem k
instâncias do tipo de recurso Rj disponíveis
 Max: matriz n x m. Se Max [i, j] = k, então o processo Pi pode
solicitar no máximo k recursos do tipo Rj
 Alocação: matriz n x m. Se Alocação [i, j] = k então Pi tem
atualmente k instâncias do recurso Rj
 Precisa: matriz n x m. Se Precisa [i, j] = k, então Pi pode precisar
de mais k instâncias do Rj para completar sua tarefa
Precisa [i, j] = Max [i, j] - Alocação [i, j]
Operating System Concepts – 8th Edition
7.26
Silberschatz, Galvin and Gagne ©2009
Algoritmo de segurança
1. Sejam Trabalho e Fim vetores de comprimento m e n,
respectivamente. Inicialize:
Trabalho = Disponível
Fim [i] = falso para i = 0, 1, …, n- 1
2. Encontre um i de tal forma que ambas as condições sejam
verdadeiras:
(a) Fim [i] = falso
(b) Precisa[i]  Trabalho
Se esse i não existir, ir para passo 4
3. Trabalho = Trabalho + Alocação[i]
Fim[i] = verdadeiro
Vá para passo 2
4. Se Fim [i] == verdadeiro para todo i, então o sistema está em um
estado seguro
Operating System Concepts – 8th Edition
7.27
Silberschatz, Galvin and Gagne ©2009
Algoritmo de pedido de recursos para o
Processo Pi
Pedido = vetor de pedido para o processo Pi. Se Pedido[i][j] = k, então
o processo Pi quer k instâncias do tipo de recurso Rj
1. Se Pedido[i]  Precisa[i], vá para o passo 2. Do contrário, gere
uma exceção, pois o processo pediu mais do que o máximo.
2. Se Pedido[i]  Disponível, vá para passo 3. Do contrario, Pi
precisa esperar, pois os recursos não estão disponíveis
3. Finja alocar os recursos requisitados para Pi modificando os
estados da seguinte forma:
Disponível = Disponível – Pedido
Alocação[i] = Alocação[i] + Pedido[i]
Precisa[i] = Precisa[i] – Pedido[i]
 Execute o algoritmo de segurança

Se seguro  aloque os recursos para Pi

Se inseguro  Pi precisa esperar e o estado anterior de
alocação deve ser restaurado
Operating System Concepts – 8th Edition
7.28
Silberschatz, Galvin and Gagne ©2009
Exemplo de Algoritmo do Banqueiro
 5 processos: P0 até P4
 3 tipos de recursos:
A (10 instâncias), B (5 instâncias) e C (7 instâncias)
Estado em T0:
Alocação
Max
Disponível
ABC
ABC
ABC
P0
010
753
332
P1
200
322
P2
302
902
P3
211
222
P4
002
433
Operating System Concepts – 8th Edition
7.29
Silberschatz, Galvin and Gagne ©2009
Exemplo (Cont.)
 O conteúdo da matriz Precisa é definido como Max – Alocação
Precisa
ABC
P0
743
P1
122
P2
600
P3
011
P4
431
 O sistema está em um estado seguro, pois a sequência < P1, P3, P4,
P2, P0> satisfaz o critério de segurança
Operating System Concepts – 8th Edition
7.30
Silberschatz, Galvin and Gagne ©2009
Exemplo: P1 pede (A=1,B=0,C=2)
 Verifique que Pedido  Disponível (ou seja, (1,0,2)  (3,3,2))
Alocação
Precisa
Disponível
ABC
ABC
ABC
P0
010
743
230
P1
302
020
P2
302
600
P3
211
011
P4
002
431
 A execução do algoritmo de segurança mostra que a sequência < P1,
P3, P4, P0, P2> satisfaz o requisito de segurança
 O pedido (3,3,0) feito por P4 pode ser concedido?
 O pedido (0,2,0) feito por P0 pode ser concedido?
Operating System Concepts – 8th Edition
7.31
Silberschatz, Galvin and Gagne ©2009
Detecção de Deadlock
 Permitir que o sistema entre no estado de deadlock
 Algoritmo de detecção
 Regime de recuperação
Operating System Concepts – 8th Edition
7.32
Silberschatz, Galvin and Gagne ©2009
Única instância de cada tipo de
recurso
 Manter gráfico de espera

Nós são processos

Pi  Pj se Pi está esperando por Pj
 Periodicamente, invocar um algoritmo que procura por um ciclo no
gráfico. Se houver um ciclo, existe um deadlock
 Um algoritmo para detectar um ciclo em um gráfico requer uma
ordem de n2 operações, onde n é o número de vértices no gráfico
Operating System Concepts – 8th Edition
7.33
Silberschatz, Galvin and Gagne ©2009
Gráfico de alocação de recursos e gráfico
de espera
Gráfico de alocação de recursos
Operating System Concepts – 8th Edition
7.34
Gráfico de espera correspondente
Silberschatz, Galvin and Gagne ©2009
Recuperação de deadlock:
encerramento de processos
 Opções

Abortar todos os processos em deadlock

Abortar um processo de cada vez, até o ciclo de bloqueio seja
eliminado

Em que ordem devemos abortar?
–
Prioridade do processo
–
Quanto tempo o processo já executou e quanto tempo
ainda falta de execução
–
Recursos que o processo usou
–
Recursos necessários para completar a execução do
processo
–
Quantos processos precisarão ser terminados
–
É um processo interativo ou batch?
Operating System Concepts – 8th Edition
7.35
Silberschatz, Galvin and Gagne ©2009
Recuperação de deadlock:
preempção de recursos
 Seleção de uma vítima - minimizar o custo
 Rollback - retornar o processo a um estado seguro

Reiniciar o processo nesse estado seguro
 Problema

Inanição - o mesmo processo pode sempre ser escolhido
como vítima
Operating System Concepts – 8th Edition
7.36
Silberschatz, Galvin and Gagne ©2009
Fim do Capítulo 7
Operating System Concepts – 8th Edition
Silberschatz, Galvin and Gagne ©2009