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 ?



• 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


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


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();

}...



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();

}...


Recurso 2 é preemptível



• 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


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


Deadlock• Modelados através de Grafos dirigidos

Ordem de Execuçãoda CPU


Deadlock• Modelados através de Grafos dirigidos

Ordem de Execuçãoda CPU

Sem deadlock, pois não formou um ciclo


Deadlock

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


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


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?


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

• Algoritmo para detecção de deadlock



• 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]


Repetição = Deadlock


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



• 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



• 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


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


Deadlock



• 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


• 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



• Analise dos estados– Qual o estado em A?


Estado Seguro

Verificar se se existe um processo que pode ser

atendido por completo?

Estado Inseguro Deadlock


• Estados Seguros e Inseguros


DEADLOCK

Inseguro

Seguro


• 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



• 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?


A B


• 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?


Recursos ExistentesRecursos AlocadosRecursos Disponíveis



• 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


Deadlock



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


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


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


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


DeadlockPrevenção

• Resumo


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

Deadlock


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


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

Documents

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