Dead Lock

Prévia do material em texto

DEADLOCK Eng. Eduardo Juliano Alberti
Ao discutirmos a respeito da programação concorrente observamos que diversos 
problemas como a exclusão mútua e o adiamento infinito.
Porém a multiprogramação pode ainda trazer problemas adicionais.
2
DEADLOCK
Na multiprogramação pode ocorrer o que chamamos de impasse ou deadlock.
O deadlock é o nome dado a situação na qual um thread ou processo aguarda por 
um evento que não ocorrerá.
Logicamente se um thread ou processo aguarda por um evento, e este não ocorre, 
este ficará travado e não realizará sua operação determinada.
3
DEADLOCK
Adiamento Indefinido x Deadlock
4
DEADLOCK
O grande foco para evitar deadlocks é no compartilhamento de recursos, pois a 
falha no acesso a determinados recursos podem impedir o funcionamento de todo o 
sistema, diminuir sua performance ou causar perda de trabalho.
5
DEADLOCK - TRÁFEGO
6
DEADLOCK – ALOCAÇÃO DE RECURSOS
7
Temos aqui uma espera circular. Processos aguardam recursos, porém ninguém está 
disposto a entregar o recurso alocado para ele. Este ainda pode ser chamado de 
abraço mortal.
DEADLOCK – JANTAR DOS FILÓSOFOS
8
Cinco filósofos estão sentados ao redor de uma mesa redonda. Cada um leva uma vida 
simples, alternando entre pensar e comer macarrão. À frente de cada filósofo está um 
prato de macarrão que é reabastecido por um empregado dedicado. Há exatamente 
cinco garfos sobre a mesa, um entre cada par adjacente de filósofos. Comer macarrão 
(daquela maneira mais elegante) requer que um filósofo use dois garfos adjacentes a 
ele (simultaneamente).
DEADLOCK – JANTAR DOS FILÓSOFOS
9
DEADLOCK – JANTAR DOS FILÓSOFOS
10
Caso este problema não fosse livre de deadlock e adiamento indefinido, um ou mais 
filósofos morreriam de fome.
Como você implementaria este código?
O que deve ser levado em consideração?
DEADLOCK – JANTAR DOS FILÓSOFOS
11
void filósofo()
{
while(true){
Pense();
Coma();
}
}
void coma()
{
pegueGarfoEsquerdo();
pegueGarfoDireito();
ComaPorUmInstante();
devolvaGarfoEsquerdo();
devolvaGarfoEsquerdo();
}
DEADLOCK – JANTAR DOS FILÓSOFOS
12
Em que problemas esta implementação infere?
Lembre-se que os filósofos representam threads concorrentes 
assíncronas.
DEADLOCK – JANTAR DOS FILÓSOFOS
13
Imagine que todos os filósofos executem a instrução para pegar o garfos esquerdo, todos
terão um garfo, porém não existirão garfos disponíveis para serem usados como garfos da
mão direita.
Todos os filósofos morrerão de fome, pois todos esperarão por um garfo que não será
devolvido.
O que fazer para resolver?
DEADLOCK – JANTAR DOS FILÓSOFOS
14
De forma sucinta, podemos inserir uma primitiva que verifique a existência de garfos. Ao
pegar o garfo esquerdo e esta operação for realizada com sucesso, verifica-se a
possibilidade de pegar um garfo direito. Caso não haja essa possibilidade, o filósofo devolve
o garfo esquerdo.
Desta forma os filósofos não sofrerão impasse de morte -> deadlock
Porém não é garantido que sequencialmente todos os filósofos devolvam seus garfos de
forma repetida. Isso significa que apesar de não sofrer deadlock, ainda, nenhum filósofo irá
comer. Neste caso ocorre um impasse “ao vivo” -> livelock ou adiamento indefinido.
RECURSOS
15
Recursos Preemptivos: processadores e memória principal
Recursos Não-preemptivos: Unidades de CD e Scanners
Recursos Compartilhados: recursos são compartilhados entre processos. Disco e processador,
de forma multiplexada, criam a ilusão de acesso simultâneo. Dados e programas.
RECURSOS
16
Nos recursos compartilhados, podemos pensar a memória. Imagine que n processos queiram
acesso ao bloco de notas. O SO não cria uma cópia em memória para cada solicitação pois
isso acarretaria em diversas cópias redundantes. Para isso o SO cria uma área de acesso
compartilhado e disponibiliza aos usuários, porém tal área não pode ser modificada, pois
caso um thread realize uma modificação outros threads podem se tornar imprevisíveis. Então
este código é chamado REENTRANTE, não modifica enquanto executa.
RECURSOS
17
O problema dos recursos compartilhados é que são tendências a criação de deadlocks.
Portanto, no momento da declaração, deve-se tomar cuidado para definir primitivas de
acesso que evitem essa situação.
CONDIÇÕES DE DEALOCK
18
Alguns autores comprovaram que para um deadlock ocorrer são necessárias 4 condições:
 Um recurso pode ser adquirido exclusivamente por um único processo por vez (Exclusão Mútua)
 Um processo que obteve um recurso exclusivo pode reter esse recurso enquanto espera para obter outros recursos
(Condição de Espera ou Posse e Espera)
 Uma vez que o processo obtenha o recurso, o sistema não pode retirá-lo do controle do processo até que tenha
terminado de utilizar o recursos (Não-preempção)
 Dois ou mais recursos ficam travados em uma cadeia circular na qual cada processo está esperando por um ou
mais recursos que o processo seguinte detém (Espera Circular)
PREVENÇÃO DE DEADLOCK
19
Negação de Espera: Neste método, um thread especifica todos os recursos necessários para
concluir a tarefa que necessita. O sistema por sua vez deve concedê-los na base do “tudo ou
nada”. Caso os recursos não estejam disponíveis, o thread é obrigado a esperar.
Esta técnica previne o deadlock, porém desperdiça recursos.
Ainda, pode levar ao adiamento indefinido se der prioridade a processos ou threads com
menor número de recursos.
PREVENÇÃO DE DEADLOCK
20
Negação de “Não-preempção”: Neste método, um thread ou processo pode alocar recursos
e solicitar adicionais caso seja necessário. Porém caso os recursos adicionais que permitem a
conclusão de sua tarefa não estejam disponíveis, obriga-se a devolução do recurso a fim de
evitar o deadlock.
Imagine que um processo alocou um recurso R1, e necessita de um recurso R2 que está
ocupado. Caso um processo P2 necessite do recurso R1 para terminar sua tarefa ele não terá
acesso. Através da Negação de Não-preempção esse problema seria resolvido.
PREVENÇÃO DE DEADLOCK
21
Neste caso porém, a prevenção pode ser custosa, pois um processo perderá todo o trabalho
feito até um dado momento a fim de evitar o deadlock. Caso essa perda de trabalho seja
pouco frequente, o método oferece um custo relativamente baixo, caso contrário o custo para
evitar o deadlock pode ser alto e seus efeitos devastadores.
PREVENÇÃO DE DEADLOCK
22
Negação de Espera Circular: Neste métodos os recursos são
numerados sequencialmente e os processos só podem utilizá-los em
ordem subsequente. Desta forma, não há espera circular.
Neste caso, os recursos são alocados e utilizados em ordem linear.
O problema desta modalidade é que recursos que não utilizam
ordem linear de recursos deverão aloca-los por um longo período,
afetando o desempenho. Além, ainda, de ser uma estrutura
inflexível.