SISTEMAS OPERACIONAIS
Deadlock



Os sistemas computacionais estão repletos de recursos
que podem ser usados por um processo por vez.
Exemplo: CD-ROM, Driver de Fita Dat, etc. Ter dois
processos simultaneamente gravando na impressora,
por exemplo, resulta em uma confusão.
Todos os SO têm a capacidade de temporariamente
conceder acesso exclusivo a certos recursos para um
processo.



Para muitos aplicativos, um processo requer acesso
exclusivo não a um, mas a vários recursos. Imagine uma
gráfica que precisa plotar um banner, cujas
informações vêm em um CD.
Um processo A solicita a leitura do CD; um momento
mais tarde outro processo B solicita a impressão de
uma imagem.
Agora o processo B solicita a plotadora e a bloqueia,
esperando por ela. O processo B também solicita o CD
e também bloqueia.

Neste ponto os dois processos estão bloqueados e
assim permaneceram eternamente. Essa situação é
chamada de Deadlock ou impasse.



Os deadlocks podem ocorrer em outras situações além
dessas de solicitar dispositivos dedicados de E/S.
Em banco de dados, um programa pode precisar
travar vários registros que ele está utilizando para
evitar condição de corrida.
Se o processo A trava o registro R1 e o processo B
trava o registro R2, e cada processo tenta travar o
registro do outro também ocorre um deadlock. Em
suma, os deadlocks ocorrem tanto em hardware como
em software.
Recursos



Um recurso pode ser um dispositivo de hardware ou um
conjunto de informações. Um computador terá muitos
recursos diferentes que podem ser adquiridos.
Quando várias cópias de um recurso estiverem
disponíveis, qualquer uma delas pode ser utilizada
para satisfazer qualquer solicitação ao recurso.
Em suma, um recurso é qualquer coisa que pode ser
usada somente por um único processo.
Recursos

Os recursos dividem-se em dois tipos:
 Recurso
Preemptível;
 Recurso não-Preemptível.
Recurso Preemptível


O primeiro é aquele que pode ser tirado do processo
que é proprietário sem nenhum problema.
A memória é um exemplo de um recurso preemptível.
No caso da impressora quando B solicitasse o recurso
do CD, teoricamente haveria um impasse. No caso do
recurso preemptível é possível preemptar a memória
de A comutando-a para o disco e comutando B para a
memória. Dessa forma B pode usar u CD. Nenhum
impasse ocorre.
Recurso não preemptivo


No segundo caso, recurso não-preemptível, é
aquele que não pode ser tirado de seu
proprietário atual sem causar falha na computação.
Se um processo começou a imprimir, a ação de tirar
dele e dá-la a outro processo resultará em
problemas na saída. As impressoras não são
preemptíveis.

Em geral, deadlocks envolvem recursos nãopreemptíveis.
A seqüência de eventos requerida para utilizar um
recurso é:
 Solicitar o recurso;
 Utilizar o recurso;
 Liberar o recurso.

Se o recurso requerido não está disponível, duas
situações podem ocorrer:
 Processo
que requisitou o recurso fica bloqueado até
que o recurso seja liberado, ou;
 Processo que requisitou o recurso falha, e depois de
certo tempo tenta novamente requisitar o recurso;
Princípios Básicos de Impasses

Em deadlock pode ser definido formalmente da
seguinte forma:
 Um
conjunto de processos está em situação de
deadlock se todo processo pertencente ao conjunto
estiver esperando por um evento que somente um outro
processo desse mesmo conjunto poderá fazer
acontecer.



Na maioria dos casos, o evento que cada processo está
esperando é a liberação de algum recurso atualmente
possuído por outro membro do conjunto.
Em outras palavras, cada membro do conjunto de
processos em impasse está esperando um recurso que é
possuído por um processo em estado de impasse.
Nenhum processo pode executar, nenhum pode liberar
recurso e nenhum pode ser acordado.
Quatro Condições para Deadlock

Condição de exclusão mútua


Condição de posse e espera (hold and wait)


Processos que já possuem algum recurso podem solicitar novos
recursos;
Condição de não preempção



Um recurso só pode estar alocado para um processo em um
determinado momento;
Recursos já alocados não podem ser retirados do processo que os
alocou;
Somente o processo que alocou o recurso pode liberá-lo;
Condição de espera circular


Deve ser uma cadeia circular de dois ou mais processos;
Cada um está à espera de recurso retido pelo membro seguinte
dessa cadeia;
Modelagem de Deadlocks

Geralmente, deadlocks são representados por
grafos a fim de facilitar sua detecção, prevenção e
recuperação – Ocorrência de ciclos pode levar a
um deadlock; Os grafos podem ser modelados
utilizando grafos dirigidos:
Modelagem de Deadlocks
a)
b)
c)
recurso R
está
alocado ao
processo A;
processo B
está
solicitando/
esperando
pelo recurso
S;
processos C
e D estão
em deadlock
sobre
recursos T e
U;
Estratégias para lidar com impasses


Ignorar por completo o problema.
Detectar e recuperar o problema:
 deixar

os deadlocks ocorrerem, detectá-los e agir;
Evitar dinamicamente o problema:
 alocação

cuidadosa de recursos;
Prevenir o problema:
 negação
de uma das quatro condições necessárias
para gerar deadlocks;
O Algoritmo do Avestruz




Esta é a abordagem mais simples: Fingir que não há nenhum
problema.
Dentro dessa idéia, o UNIX (e o MINIX) apresentam
impasses que nem mesmo são detectados ou por vezes são
automaticamente interrompidos.
Esta abordagem é simplesmente ignorar o problema na
suposição de que a maioria dos usuários preferiria um
impasse ocasional a uma regra que restringisse todos os
usuários.
Assim, ignorar o problema é razoável se deadlocks ocorrem
muito raramente e o custo da prevenção é alto. Esta é uma
ponderação entre conveniência e correção.
Detecção e Recuperação

Quando esta técnica é utilizada, o SO não faz
nada senão monitorar as solicitações e as
liberações.
 Exemplo:
Processos estão com todos os recursos
alocados;
 Procedimento: permitir que os deadlocks ocorram
tentar detectar as causas e solucionar a situação;
Detecção e Recuperação
•
Algoritmos:





Detecção com um recurso de cada tipo;
Detecção com vários recursos de cada tipo;
Recuperação por meio de preempção;
Recuperação por meio de rollback (volta ao passado)
Recuperação por meio de eliminação de processos
Prevenção de Deadlock


A terceira estratégia é impor restrições
convenientes para os processos de tal modo que os
impasses sejam impossíveis. Se for possível que pelo
menos uma das condições de deadlocks não ocorra,
então os deadlocks não acontecerão.
No caso da Exclusão Mútua, se nenhum recurso
for atribuído exclusivamente a um único
processo, nunca haverá deadlock.
Prevenção de Deadlock

O princípio é evitar alocar um recurso quando ele
não for absolutamente necessário e tentar
assegurar que o menor número possível de
processos possa de fato requisitar o recurso.
Exemplo: O uso de spool permitindo que
somente um recurso da impressora seja usado
por processo.
Prevenção de Deadlock


Na segunda condição (condição de posse e
espera), basta requerer que todos os processos
solicitem os seus recursos antes de iniciar a
execução. No entanto, um processo nunca tem que
esperar por aquilo que precisa.
Um dos problemas é não poder não saber quantos
e quais recursos vão precisar no início da execução
e também reter recursos que outros processos
poderiam estar usando
Prevenção de Deadlock


A terceira condição (nenhuma preempção) seria
tomar o recurso a força, contudo é uma solução
pouco promissora, de certa forma inviável.
Por último, a espera circular pode ser eliminado
de várias maneiras, uma delas é ter uma regra que
diz que um processo é intitulado somente para um
único recurso em qualquer momento, ou atribuir uma
ordem para chamada para aquele recurso.
Impedimento do Impasse

Anteriormente o deadlock não foi evitado pela
imposição de regras arbitrárias aos processos, mas
pela análise cuidadosa de cada solicitação de
recurso para ver se ele poderia ser concedido
seguramente.
Impedimento do Impasse

Para evitar dinamicamente o deadlock podem-se
adotar algumas soluções:
 Alocação
individual de recursos à medida que processo
necessita;
 Escalonamento cuidadoso - impõe um alto custo e
conhecimento prévio dos recursos que serão utilizados;
Impedimento do Impasse

Algoritmos:
 Banqueiro
para um único tipo de recurso;
 Banqueiro para vários tipos de recurso;
 Definição de estados seguros e inseguros.
Impedimento e Impasse


Neste último, estados seguros não provocam
deadlocks e há uma maneira de atender a todas
as requisições pendentes finalizando normalmente
todos os processos.
Os estados inseguros podem provocar deadlocks,
mas não necessariamente provocam.
Impedimento e Impasse

O algoritmo do banqueiro idealizado por Dijkstra
(1965), considera cada requisição no momento em
que ela ocorre, verificando se essa requisição leva
a um estado seguro; Se sim, a requisição é
atendida, se não o atendimento é adiado para
outro momento; Premissas adotadas por um
banqueiro para garantir ou não crédito (recursos)
para seus clientes (processos). Nem todos os clientes
(processos) precisam de toda a linha de credito
(recursos) disponível para eles.
Vantagens e desvantagens do
algoritmo do banqueiro:



Pouco utilizado, pois é difícil saber quais recursos
serão necessários;
O número de processos é dinâmico e pode variar
constantemente, tornando o algoritmo custoso;
Na teoria o algoritmo é ótimo.
Questionário




O que é deadlock, e quais as suas possíveis causas?
O que é recurso e como podemos categorizar?
Quais as 4 condições para o deadlock?
Descreva as estratégias para lidar com impasses