D EADLOCKS I MPASSES Vinícius Pádua. O que é um Deadlock ? 2

DEADLOCKSIMPASSES

Vinícius Pádua

Vinícius PáduaVinícius Pádua 2

O que é um Deadlock ?

Vinícius PáduaVinícius Pádua 3

O que é um Deadlock ?

• Cenário– Dois processos : Gravar CD com dados do scanner

• Processo A solicita o CD é autorizado• Processo B solicita o scanner é autorizado• Processo A solicita o scanner é negado• Processo B solicita o CD é negado• Processos A e B estão em deadlock• Como proceder ?• E se os hardware fosse acessados de forma compartilhada?

• Não é exclusividade dos processos– Banco de dados, arquivos no disco, threads, ...

• Recursos

Vinícius PáduaVinícius Pádua 4

Deadlock

• Eventos necessários para utilizar de um recurso– Requisitar o recurso

• Se recurso não disponível quando solicitado– Processo requisitante terá que esperar

» Processo ficara constantemente solicitando até ser atendido– Usar o recurso

• Utilizar o recurso• Nessa etapa que os deadlock ocorrem

– Liberar o recurso• Liberar recurso

Vinícius PáduaVinícius Pádua 5

Como ocorre um Deadlock ?

• Cenários

• Quem define a ordem de execução?

...public void process_A(){ resource_1.down(); resource_2.down(); use_both_resources(); resource_2.up(); resource_1.up(); }...

... public void process_B(){ resource_1.down(); resource_2.down(); use_both_resources(); resource_2.up(); resource_1.up(); }...

...public void process_A(){

resource_1.down(); resource_2.down();

use_both_resources(); resource_2.up(); resource_1.up();

}...

... public void process_B(){ resource_2.down(); resource_1.down(); use_both_resources(); resource_1.up(); resource_2.up(); }...

Vinícius PáduaVinícius Pádua 6

Deadlock

• Natureza do recurso– Preemptíveis

• Podem ser retirados do processo proprietário sem prejuízo• Ex.: Memória

– Não Preemptíveis• Não podem ser retirado, pois causam prejuízos• Ex.: Gravação de DVD

...public void process_A(){

resource_1.down(); resource_2.down();

use_both_resources(); resource_2.up(); resource_1.up();

}...

... public void process_B(){ resource_2.down(); resource_1.down(); use_both_resources(); resource_1.up(); resource_2.up(); }...

Recurso 2 é preemptível

Vinícius PáduaVinícius Pádua 7

O que é um Deadlock ?

• Um conjunto de processos estará em situação de deadlock se todo processo pertencente ao conjunto estiver esperando por um evento que somente outro processo desse mesmo conjunto poderá fazer acontecer

• Condições necessárias para ocorrência de deadlock– Condição de exclusão mútua

• Processo solicita recurso de forma exclusiva– Condição de posse e espera

• Processos que, em um determinado instante, retêm recursos concedidos anteriormente podem requisitar novos recursos

– Condição de não preempção• Recursos não preemptível: Recursos concedidos previamente não podem ser

forçadamente tomados– Condição de espera circular

• Deve se um encadeamento de 2 ou mais processos• Cada um encontra-se à espera de um recurso que está sendo usando pelo membro

seguinte dessa cadeia

Vinícius PáduaVinícius Pádua 8

Como identificar um Deadlock ?• Visual : Modelados através de Grafos dirigidos• Simbolização

– Quadrado - Recursos– Círculo - Processos– Seta - Situação

(a) recurso R alocado ao processo A(b) processo B está solicitando/esperando pelo recurso S(c) processos C e D estão em deadlock sobre recursos T e U

Vinícius PáduaVinícius Pádua 9

Deadlock• Modelados através de Grafos dirigidos

Ordem de Execuçãoda CPU

Vinícius PáduaVinícius Pádua 10

Deadlock• Modelados através de Grafos dirigidos

Ordem de Execuçãoda CPU

Sem deadlock, pois não formou um ciclo

Vinícius PáduaVinícius Pádua 11

Deadlock

• Estratégia para tratar deadlock– Detectar e Recuperar– Evitando deadlock– Prevenir– Ignorar

Vinícius PáduaVinícius Pádua 12

DeadlockDetectar e Recuperar

• Objetivo– Não tenta prevenir a ocorrência de deadlock

• Deixara que ocorra• Ficara a procura e ao encontrá-lo ira tratá-lo

• Cenários– Um (1) recurso de cada tipo

• Modelagem com grafos dirigidos

– Múltiplos recursos de cada tipo• Baseado em matrizes

Vinícius PáduaVinícius Pádua 13

DeadlockDetectar e Recuperar• Um recurso de cada tipo

– Visual• Utiliza a modelagem de grafos dirigidos

– Verificar a existência de um ou mais ciclos

– Real• Algoritmo de detecção de deadlock

• Modele o grafo dirigido abaixo– P. A usa R e precisa de S– P. B precisa de T– P. C precisa de S– P. D usa U e precisa de S e T– P. E usa T e precisa de V– P. F usa W e precisa de S– P. G usa V e precisa de U

• Como ficou o grafo?– Deadlock? Pq? Quais processos e recursos envolvidos?

Vinícius PáduaVinícius Pádua 14

• Um ciclo pode se encontrado no grafo -> Deadlock– Fácil visualização, e o computador?

• Algoritmo para detecção de deadlock

DeadlockDetectar e Recuperar

Vinícius PáduaVinícius Pádua 15

• Algoritmo para detecção de deadlock– Sentido: Esquerda para direita e Superior para inferior– L=[] ; L=[R] ; L=[R,A] ; L=[R,A,S] ; L=[R,A] ; L=[R] ; L=[] -> R completado– L=[] ; L=[A] ; L=[A,S] ; L=[A] ; L=[] -> A completo– L=[] ; L=[B] ; L=[B,T] ; L=[B,T,E] ; ... L=[B,T,E,V,G,U,D] ;

L=[B,T,E,V,G,U,D,S] ; L=[B,T,E,V,G,U,D] ; L=[B,T,E,V,G,U,D,T]

DeadlockDetectar e Recuperar

Repetição = Deadlock

Vinícius PáduaVinícius Pádua 16

DeadlockDetectar e Recuperar• Múltiplos recursos de cada tipo

– Utiliza matrizes e vetores

– Tentar procurar um processo que posso ser atendido por completo

Quantidade total de Recursos no sistema

Quantidade total de Recursos alocadospor processo e por recurso

Quantidade total de recursos disponíveis

Quantidade total de recursos necessários

por processo e por recurso

Vinícius PáduaVinícius Pádua 17

DeadlockDetectar e Recuperar

• Múltiplos recursos de cada tipo

• Processo 1• Não satisfeito, pois não existe cd-rom disponível

• Processo 2• Não satisfeito, pois não existe scanner disponível

• Processo 3• Satisfeito -> Após executado -> A = (2 2 2 0)

• Com fica o resto da execução?• Processo 2: Satisfeito -> Após executado -> A = (4 2 2 1)• Processo 1: Satisfeito

• Todos os processos podem ser executados -> sem deadlock

Vinícius PáduaVinícius Pádua 18

DeadlockDetectar e Recuperar

• Múltiplos recursos de cada tipo– Exercício de fixação

• De acordo com o exemplo abaixo verifique– Se esta em deadlock– Como chegou a esta conclusão?

1 0 2 1 12 0 1 1 01 1 0 1 01 1 1 1 0

ABCD

ALOCADOS1 1 2 1 32 2 2 1 02 1 3 1 01 1 2 2 1

MÁXIMO DISPONÍVEL0 0 2 1 1

Vinícius PáduaVinícius Pádua 19

DeadlockDetectar e Recuperar• Encontramos o deadlock? E Agora? Como recuperar?– Técnicas de recuperação

• Por Preempção– Verificar se algum recurso é do tipo preemptível

• Por Retrocesso– Checkpoints

» Salva estado atual da máquina– Retornar até o último checkpoint

» Trabalho é perdido

• Por Eliminação de Processo– Simples e radical– Eliminar um ou mais processos presentes no ciclo

Lembre-se são tentativas, não quer dizer que são

todas viáveis

Vinícius PáduaVinícius Pádua 20

Deadlock

• Estratégia para tratar deadlock– Detectar e Recuperar– Evitando deadlock– Prevenir– Ignorar

Vinícius PáduaVinícius Pádua 21

• Objetivo– Verifica se a alocação de um recurso pode gerar um deadlock

• Apenas liberar o recurso se a solicitação

• Como identificar se um recurso pode ser liberado?

DeadlockEvitando deadlock

Vinícius PáduaVinícius Pádua 22

• Estados Seguros e Inseguros– Utilizam a analise dos estados para alocar ou não um recurso– Estado Seguro

• Não esta em deadlock• Nenhuma ordem de execução dos processo causa deadlock

– Estado Inseguro• Pode surgir um deadlock

– Não significa deadlock• Existe(m) ordem de execução que gera deadlock

DeadlockEvitando deadlock

Vinícius PáduaVinícius Pádua 23

• Analise dos estados– Qual o estado em A?

DeadlockEvitando deadlock

Estado Seguro

Verificar se se existe um processo que pode ser

atendido por completo?

Estado Inseguro Deadlock

Vinícius PáduaVinícius Pádua 24

• Estados Seguros e Inseguros

DeadlockEvitando deadlock

DEADLOCK

Inseguro

Seguro

Vinícius PáduaVinícius Pádua 25

• Algoritmo do banqueiro• Analisa como seria o novo estado com a solicitação do recurso

– Seguro: Requisição é aceita– Inseguro: Requisição é negada

• Necessidade– Saber número máximo de cada recurso que um processo poderá

solicitar– Número de processos

– Tipo dos algoritmos• Para um único recurso• Para múltiplos recursos• Algoritmos são semelhantes aos anteriores

DeadlockEvitando deadlock

Vinícius PáduaVinícius Pádua 26

• Algoritmo do banqueiro– Exercício de fixação

• De acordo com os exemplos abaixo verifique se é seguro ou inseguro– Como chegou a esta conclusão?

DeadlockEvitando deadlock

A B

Vinícius PáduaVinícius Pádua 27

• Algoritmo do banqueiro– Exercício de fixação

• De acordo com os exemplos abaixo verifique se é seguro ou inseguro– Como chegou a esta conclusão?

DeadlockEvitando deadlock

Recursos ExistentesRecursos AlocadosRecursos Disponíveis

Vinícius PáduaVinícius Pádua 28

DeadlockEvitando deadlock

• Algoritmo do banqueiro– Teoria x Prática

• Teoria– Funcional

• Prática– Inútil– Processos não sabem quantos recursos necessitam– Número de processos dinâmicos– Recursos podem sumir

Vinícius PáduaVinícius Pádua 29

Deadlock

• Estratégia para tratar deadlock– Detectar e Recuperar– Evitando deadlock– Prevenir– Ignorar

Vinícius PáduaVinícius Pádua 30

DeadlockPrevenção

• Objetivo– Garantir que os deadlock nunca iram acontecer

• Será possível? Como?– Evitar uma das condições para ocorrência de deadlock

• Condição de exclusão mútua• Condição de posse e espera• Condição de não preempção• Condição de espera circular

Vinícius PáduaVinícius Pádua 31

DeadlockPrevenção

• Condição de exclusão mútua– Evitar que um processo acesse o recurso diretamente– Ex.: Utilização das impressoras– Utilização da técnica de spoll

• Condição de posse espera– Evitar que processo em posse de um recurso espere por

outros recursos• Solicitar que os processos solicitem todos os recursos no início

– Algoritmo do banqueiro– Retêm recursos que outros processos podem estar usando

Vinícius PáduaVinícius Pádua 32

DeadlockPrevenção

• Condição de não preempção– Tratar todos os recursos como preemptível– Considere um processo A esteja gravando um CD-ROOM

• No meio da gravação o processo B solicitou o CD-ROOM• Processo B ira “tomar” o CD-ROOM do processo A• Ocasionará um erro na gravação! inviável!• Opção inviável

Vinícius PáduaVinícius Pádua 33

DeadlockPrevenção

• Condição de espera circular– Idéias

• Possuir apenas um recurso de cada vez– Liberar o recurso atual antes de solicitar o novo

• Fornecer uma numeração global para os recursos– Apenas pode alocar recurso se a numeração for maior que do recurso

atual– A requisitar recurso i e B requisitar recurso j– Se i <> j e i > j

» A não pode requisitar j, pois tem menor prioridade que i– Se i <> j e i < j

» B não pode requisitar i, pois tem menor prioridade que j– Dificuldade: Como encontrar uma ordem satisfatória ?

» Impossível

Vinícius PáduaVinícius Pádua 34

DeadlockPrevenção

• Resumo

Vinícius PáduaVinícius Pádua 35

• Estratégias para tratar deadlock– Detectar e Recuperar– Evitando deadlock– Prevenir– Ignorar

Deadlock

Vinícius PáduaVinícius Pádua 36

DeadlockIgnorar

• Algoritmo do Avestruz• Idéia

– Fingir que não há problema– Não fazer nada! Ctrl + alt + del

• É aceitável se– Deadlocks ocorrerem com pouca freqüência– Custo da prevenção for alto

Vinícius PáduaVinícius Pádua 37

Outras formas de prevenção

• Bloqueio em duas fazes– BD →Bloqueio de registro e depois atualização– Fases

• Fase um : Bloqueio• Fase dois: Atualização

• Impasses de Comunicação– Envio de dados pela rede → Timeout dos pacotes

• Livelocks• Condição de inanição (starvation)

Vinícius Pádua