MC504 Sistemas Operacionais

Prof. Dr. Eng. Isaías Bittencourt Felzmann

isaias@ic.unicamp.br

​

Campinas, 2s/2026

Deadlock

1/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Aviso Legal

The following set of slides are copyright Silberschatz, Galvin and Gagne, 2018. Modifications were made for their use in conjunction with MC504. The original material is available at os-book.com .

​

Os direitos autorais do conjunto de slides a seguir pertencem a Silberschatz, Galvin and Gagne, 2018. Foram feitas modificações para seu uso em MC504. O material original está disponível em os-book.com .

​

Este material foi elaborado com apoio de ferramentas de IA generativa como recurso auxiliar. O conteúdo foi revisado, validado e é de responsabilidade do docente.

2/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Deadlock!

3/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Objetivos do Capítulo

• Ilustrar como um deadlock pode ocorrer com o uso de bloqueios mutex
• Definir as quatro condições necessárias que caracterizam um deadlock
• Identificar uma situação de deadlock em um grafo de alocação de recursos
• Avaliar quatro abordagens distintas para o tratamento de deadlocks
• Aplicar o algoritmo do banqueiro para evitar deadlocks
• Aplicar o algoritmo de detecção de deadlocks
• Avaliar abordagens para a recuperação de deadlocks

​

​

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

4/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Modelo de Sistema

• O sistema consiste em recursos
• Tipos de recursos R₁, R₂, . . ., R_m
• Ciclos de CPU, espaço de memória, dispositivos de E/S
• Cada tipo de recurso R_i possui W_i instâncias.
• Cada processo utiliza um recurso da seguinte forma:
• solicitação
• uso
• liberação

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

5/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Deadlock com Semáforos

• Dados:
• Um semáforo S1 inicializado em 1
• Um semáforo S2 inicializado em 1
• Dois processos P1 e P2
• P1:

wait(s1)

wait(s2)

• P2:

wait(s2)

wait(s1)

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

6/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Caracterização do deadlock

• Exclusão mútua: apenas um processo por vez pode usar um recurso
• Posse e espera: um processo que possui pelo menos um recurso está esperando para adquirir recursos adicionais detidos por outros processos
• Sem preempção: um recurso só pode ser liberado voluntariamente pelo processo que o possui, após esse processo ter concluído sua tarefa
• Espera circular: existe um conjunto {P₀, P₁, ..., P_n} de processos em espera tal que P₀ está esperando por um recurso mantido por P₁, P₁ está esperando por um recurso que é mantido por P₂, ..., P_n–1 está esperando por um recurso mantido por P_n, e P_n está esperando por um recurso mantido por P₀.

​

O deadlock pode ocorrer se as quatro condições forem satisfeitas simultaneamente.

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

7/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Grafo de Alocação de Recursos

• V é particionado em dois tipos:
• P = {P₁, P₂, ..., P_n}, o conjunto que consiste em todos os processos do sistema�
• R = {R₁, R₂, ..., R_m}, o conjunto que consiste em todos os tipos de recursos do sistema

​

• aresta de solicitação – aresta direcionada P_i → R_j

​

• aresta de atribuição – aresta direcionada R_j → P_i

Um conjunto de vértices V e um conjunto de arestas E.

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

8/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Exemplo de Grafo de Alocação de Recursos

• Uma instância de R1
• Duas instâncias de R2
• Uma instância de R3
• Três instâncias de R4
• T1 mantém uma instância de R2 e aguarda uma instância de R1
• T2 mantém uma instância de R1 e uma de R2, e aguarda uma instância de R3
• T3 mantém uma instância de R3

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

9/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Grafo de Alocação de Recursos com um Deadlock

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

10/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Grafo com um ciclo, mas sem deadlock

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

11/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Fatos Básicos

• Se o grafo não contém ciclos ⇒ não há deadlock
• Se o grafo contém um ciclo ⇒
• Se houver apenas uma instância por tipo de recurso, então há deadlock
• Se houver várias instâncias por tipo de recurso, há possibilidade de deadlock

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

12/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Métodos para lidar com deadlocks

• Garanta que o sistema nunca entre em estado de deadlock:
• Prevenção de deadlocks
• Evitação de deadlocks
• Permitir que o sistema entre em estado de deadlock e então se recuperar
• Ignore o problema e finja que deadlocks nunca ocorrem no sistema.

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

13/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Prevenção de Deadlock

• Exclusão Mútua – não é exigida para recursos compartilháveis (por exemplo, arquivos somente leitura); deve valer para recursos não compartilháveis
• Posse e Espera – deve garantir que, sempre que um processo solicite um recurso, ele não mantenha outros recursos
• Exigir que o processo solicite e receba todos os seus recursos alocados antes de iniciar a execução, ou permitir que o processo solicite recursos apenas quando o processo não tiver nenhum alocado para ele.
• Baixa utilização de recursos; possível inanição

Invalidar uma das quatro condições necessárias para o deadlock:

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

14/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Prevenção de Deadlock (Continuação)

• Sem Preempção:
• Se um processo que mantém alguns recursos solicitar outro que não possa ser alocado imediatamente, todos os recursos que ele mantém serão liberados
• Os recursos preemptados são adicionados à lista de recursos que o processo aguarda
• O processo será reiniciado somente quando puder recuperar os recursos anteriores e obter os novos recursos solicitados
• Espera Circular:
• Impor uma ordenação total de todos os tipos de recursos e exija que cada processo solicite recursos em uma ordem crescente de enumeração

​

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

15/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Espera Circular

• Invalidar a condição de espera circular é a abordagem mais comum.
• Basta atribuir a cada recurso (ou seja, bloqueios mutex) um número único.
• Os recursos devem ser adquiridos em �uma ordem predefinida.
• Se:��first_mutex = 1�second_mutex = 5��o código de thread_two não poderia �ser escrito da seguinte forma:

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

16/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Evitação de Deadlock

• O modelo mais simples e útil exige que cada processo declare o número máximo de recursos de cada tipo que possa precisar
• O algoritmo de evitação de deadlocks examina dinamicamente o estado de alocação de recursos para garantir que nunca ocorra uma condição de espera circular
• O estado de alocação de recursos é definido pelo número de recursos disponíveis e alocados, e pelas demandas máximas dos processos

Exige que o sistema tenha alguma informação adicional a priori �disponível

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

17/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Estado Seguro

• Quando um processo solicita um recurso disponível, o sistema deve decidir se a alocação imediata o deixa em estado seguro
• O sistema está em estado seguro se existir uma sequência <P₁, P₂, ..., P_n> de TODOS os processos no sistema tal que, para cada P_i, os recursos que P_i ainda pode solicitar possam ser satisfeitos pelos recursos atualmente disponíveis + recursos mantidos por todos os P_j, com j < i
• Ou seja:
• Se os recursos necessários a P_i não estiverem imediatamente disponíveis, então P_i pode esperar até que todos os Pj terminem
• Quando P_j termina, P_i pode obter os recursos necessários, executar, devolver os recursos alocados e terminar
• Quando P_i termina, P_{i +1} pode obter os recursos necessários, e assim por diante

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

18/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Fatos Básicos

• Se um sistema estiver em estado seguro ⇒ não há deadlocks�
• Se um sistema estiver em estado inseguro ⇒ possibilidade de deadlock�
• Evitação ⇒ garantir que o sistema nunca entre em estado inseguro.

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

19/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Estados Seguro, Inseguro e de Deadlock

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

20/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Algoritmos de Evitação

• Instância única de um tipo de recurso
• Use um grafo de alocação de recursos

​

• Múltiplas instâncias de um tipo de recurso
• Use o Algoritmo do Banqueiro

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

21/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Grafo de Alocação de Recursos

• A aresta de declaração P_i→R_j indica que o processo P_i pode requisitar pelo recurso R_j; é representada por uma linha tracejada
• A aresta de declaração é convertida em aresta de solicitação quando um processo solicita um recurso
• A aresta de solicitação é convertida em aresta de atribuição quando o recurso é alocado ao processo
• Quando um recurso é liberado por um processo, a aresta de atribuição se reconverte em uma aresta de declaração
• Recursos devem ser declarados a priori no sistema

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

22/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Grafo de Alocação de Recursos

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

23/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Estado inseguro no Grafo de Alocação de Recursos

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

24/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Algoritmo de Grafo de Alocação de Recursos

• Suponha que o processo P_i solicite um recurso R_j
• A solicitação só pode ser concedida se a conversão da aresta de declaração em aresta de atribuição não formar um ciclo no grafo de alocação de recursos

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

25/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Algoritmo do Banqueiro

• Múltiplas instâncias de recursos�
• Cada processo deve reivindicar a priori o uso máximo�
• Quando um processo solicita um recurso, pode ter que esperar �
• Quando um processo obtém todos os seus recursos, ele deve devolvê-los em um tempo finito

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

26/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Estruturas de Dados para o Algoritmo do Banqueiro

• Available: vetor de comprimento m. Se Available[j] = k, há k instâncias do tipo de recurso R_j disponíveis

​

• Max: matriz n × m. Se Max [i,j] = k, então o processo P_i pode solicitar no máximo k instâncias do tipo de recurso R_j

​

• Allocation: matriz n x m. Se Allocation[i,j] = k , então P_i tem atualmente k instâncias de R_j alocadas

​

• Need: n x m matriz. Se Need[i,j] = k, então P_i pode precisar de k instâncias adicionais de R_j para completar sua tarefa

�Need [i,j] = Max[i,j] – Allocation [i,j]

Seja n = número de processos, e m = número de tipos de recursos.

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

27/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Algoritmo de Segurança

1. Sejam Work e Finish vetores de comprimento m e n, respectivamente. Inicialize:

Work = Available

Finish [i] = false para i = 0, 1, ..., n- 1

​

• Encontre um i tal que ambos:

(a) Finish [i] = false

(b) Need_i ≤ Work

Se não existir tal i , vá para o passo 4

​

• Work = Work + Allocation_i� Finish[i] = true� ir para o passo 2

​

• Se Finish [i] == true para todo i, então o sistema está em estado seguro

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

28/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Algoritmo de Solicitação de Recursos para o Processo P_i

Request_i = vetor de solicitação para o processo P_i. Se Request_i [j] = k, então o processo P_i quer k instâncias do tipo de recurso R_j

• Se Request_i ≤ Need ir para o passo 2. Caso contrário, gere uma condição de erro, já que o processo excedeu seu máximo de reivindicação
• Se Request_i ≤ Available, vá para a etapa 3. Caso contrário , P_i deve esperar, já que os recursos não estão disponíveis
• Simule a alocação dos recursos solicitados a P_i modificando o estado da seguinte forma:

Available = Available – Request_i;

Allocation_i = Allocation_i + Request_i;

Need_i = Need_i – Request_i;

• Se for seguro ⇒, os recursos são alocados a P_i
• Se for inseguro ⇒ P_i deve esperar, e o estado antigo de alocação de recursos é restaurado

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

29/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Exemplo do Algoritmo do Banqueiro

• 5 processos P₀ a P₄;

3 tipos de recursos:

A (10 instâncias), B (5 instâncias) e C (7 instâncias)

• Estado do sistema no instante T₀:

Allocation Max Available

A B C A B C A B C

P₀ 0 1 0 7 5 3 3 3 2

P₁ 2 0 0 3 2 2

P₂ 3 0 2 9 0 2

P₃ 2 1 1 2 2 2

P₄ 0 0 2 4 3 3

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

30/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Exemplo (cont.)

• O conteúdo da matriz Need é definido como Max – Allocation

​

Need

A B C

P₀ 7 4 3

P₁ 1 2 2

P₂ 6 0 0

P₃ 0 1 1

P₄ 4 3 1 �

• O sistema está em estado seguro, pois a sequência < P₁, P₃, P₄, P₂, P₀> atende aos critérios de segurança

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

31/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Exemplo: Solicitação de P1 (1,0,2)

• Verifique que Request  Available (isto é, (1,0,2) ≤ (3,3,2))

Allocation Need Available

A B C A B C A B C

P0 0 1 0 7 4 3 2 3 0

P1 3 0 2 0 2 0

P2 3 0 2 6 0 0

P3 2 1 1 0 1 1

P4 0 0 2 4 3 1

​

​

• Executar o algoritmo de segurança mostra que a sequência < P₁, P₃, P₄, P₀, P₂> atende ao requisito de segurança

​

• A solicitação (3,3,0) por P₄ pode ser concedido?

​

• A solicitação (0,2,0) por P₀ pode ser concedido?

​

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

32/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Detecção de Deadlocks

• Permitir que o sistema entre em estado de deadlock�
• Algoritmo de detecção�
• Esquema de recuperação

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

33/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Instância única de cada tipo de recurso

• Manter o grafo de espera
• Os nós são processos
• P_i -> P_j se P_i estiver esperando por P_j�
• Invocar periodicamente um algoritmo que procure um ciclo no grafo. Se houver um ciclo, há um deadlock

​

• Um algoritmo para detectar um ciclo em um grafo requer O( n² ) operações, em que n é o número de vértices no grafo

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

34/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Grafo de Alocação de Recursos e Grafo de Espera

Grafo de Alocação de Recursos

Grafo correspondente de espera

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

35/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Várias instâncias de um tipo de recurso

• Available: Um vetor de comprimento m indica o número de recursos disponíveis de cada tipo
• Allocation: Uma matriz n x m define o número de recursos de cada tipo atualmente alocados a cada processo
• Request: Uma matriz n x m indica a solicitação atual de cada processo. Se Request [i][j] = k, então o processo P_i está solicitando k mais instâncias do tipo de recurso R_j.

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

36/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Algoritmo de Detecção

1. Sejam Work e Finish vetores de comprimento m e n, respectivamente Inicializar:
1. Work = Available
2. Para i = 1,2, ..., n, se Allocation_i ≠ 0, então � Finish[i] = false; caso contrário, Finish[i] = true

​

• Encontre um índice i tal que ambos:
• Finish[i] == false
• Request_i ≤ Work�

Se não existir tal i, vá para o passo 4

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

37/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Algoritmo de Detecção (cont.)

3. Work = Work + Allocation_i� Finish[i] = true� ir para o passo 2�
4. Se Finish[i] == false, para algum i, 1 ≤ i ≤ n, então o sistema está em estado de deadlock. Além disso, se Finish[i] == false, então P_i está em deadlock

O algoritmo requer uma ordem de operações O(m x n²) para detectar se o sistema está em estado de deadlock

​

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

38/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Exemplo de algoritmo de detecção

• Cinco processos P₀ a P₄; três tipos de recursos �A (7 instâncias), B (2 instâncias) e C (6 instâncias)

​

• Estado do sistema no instante T₀:

Allocation Request Available

A B C A B C A B C

P₀ 0 1 0 0 0 0 0 0 0

P₁ 2 0 0 2 0 2

P₂ 3 0 3 0 0 0

P₃ 2 1 1 1 0 0

P₄ 0 0 2 0 0 2

​

• A sequência <P₀, P₂, P₃, P₁, P₄> resultará em Finish[i] = true para todos os i

​

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

39/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Exemplo (cont.)

• P₂ solicita uma instância adicional do tipo C

Request

A B C

P₀ 0 0 0

P₁ 2 0 2

P₂ 0 0 1

P₃ 1 0 0

P₄ 0 0 2

​

• Como é o sistema?
• Os recursos mantidos por P₀ podem ser recuperados, mas são insuficientes para atender às solicitações dos demais processos
• Existe um deadlock, composto pelos processos P₁, P₂, P₃ e P₄

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

40/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Uso do Algoritmo de Detecção

• Quando e com que frequência invocar depende de:
• Com que frequência é provável que um deadlock ocorra?
• Quantos processos precisarão sofrer rollback?
• um para cada ciclo independente�
• Se o algoritmo de detecção for invocado em intervalos arbitrários, poderá haver muitos ciclos no grafo de recursos; assim, não será possível determinar qual processo em deadlock “causou” o problema.

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

41/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Recuperação do Deadlock: Término de Processo

• Abortar todos os processos em deadlock�
• Abortar um processo por vez até eliminar o ciclo de deadlock�
• Em que ordem devemos escolher abortar?
1. Prioridade do processo
2. Quanto tempo o processo já executou e quanto falta para sua conclusão
3. Recursos utilizados pelo processo
4. Recursos de que o processo precisa para concluir
5. Quantos processos precisarão ser terminados
6. O processo é interativo ou em lote?

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

42/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Recuperação do Deadlock: Preempção de Recursos

• Seleção de vítima – minimizar custos�
• Rollback – retornar a algum estado seguro e reiniciar o processo a partir desse estado�
• Inanição – o mesmo processo pode ser sempre escolhido como vítima; incluir o número de rollbacks no fator de custo

Silberschatz, Galvin e Gagne ©2018

Operating System Concepts – 10^th Edition

43/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais

Bibliografia

Capítulo 2.

Capítulo 8.

(Capítulo 7 na 9^a edição em Português).

44/44

rev. 2s/2026

IC/UNICAMP – MC504 Sistemas Operacionais