Deadlock
Prof. Alexandre Monteiro
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878

Exemplos de recursos de computador
• impressoras
• unidades de fita
• tabelas

Processos precisam de acesso aos recursos numa ordem racional

Suponha que um processo detenha o recurso A e solicite o recurso B
• ao mesmo tempo um outro processo detém B e solicita A
• ambos são bloqueados e assim permanecem

Seqüência de eventos necessários ao uso de um recurso
1. solicitar o recurso
2. usar o recurso
3. liberar o recurso

Deve esperar se solicitação é negada
– processo solicitante pode ser bloqueado
– pode falhar resultando em um código de erro

Deadlocks ocorrem quando …
• garante-se aos processos acesso exclusivo aos
dispositivos
• esses dispositivos são normalmente chamados de
recursos

Recursos preemptíveis
• podem ser retirados de um processo sem quaisquer
efeitos prejudiciais

Recursos não preemptíveis
• vão induzir o processo a falhar se forem retirados
Conceito


Deadlock (interbloqueio, encravamento, impasse)pode
se definir como situação em que ocorre um impasse e
dois ou mais processos ficam impedidos de continuar
suas execuções, ou seja, ficam bloqueados.
O deadlock ocorre com um conjunto de processos e
recursos não-preemptíveis, onde um ou mais processos
desse conjunto está aguardando a liberação de um
recurso por um outro processo que, por sua vez,
aguarda a liberação de outro recurso alocado ou
dependente do primeiro processo.
Conceito



Representação de Deadlock em grafos de alocação
de recursos, com dois processos A e B, e dois
recursos R1 e R2.
O deadlock é representado na forma de grafos
dirigidos, onde o processo é representado por um
círculo e o recurso, por um quadrado.
Quando um processo solicita um recurso, uma
seta é dirigida do círculo ao quadrado. Quando um
recurso é alocado a um processo, uma seta é
dirigida do quadrado ao círculo.
Conceito
Na figura, podemos ver
dois processos diferentes
(A e B), cada um com um
recurso diferente alocado
(R1 e R2). Neste exemplo,
é facilmente visível a
condição
de
espera
circular
em
que
os
processos se encontram,
onde cada um solicita o
recurso que está alocado
ao outro processo.
Conceito


O deadlock pode ocorrer mesmo que haja
somente um processo no SO, considerando que
este processo utilize múltiplos threads e que
tais threads requisitem os recursos alocados a
outros threads no mesmo processo;
O deadlock é independente da quantidade de
recursos disponíveis no sistema;
Condições Necessárias para a Ocorrência
de Deadlock
O deadlock ocorre naturalmente em alguns sistemas. No entanto, existem
Condições de Coffman para que uma situação de deadlock se manifeste:
1.
2.
3.
4.
Condição de exclusão mútua: cada recurso pode estar,
alocado a um processo ou estar disponível;
Condição de posse-e-espera: cada processo pode solicitar um
recurso, ter esse recurso alocado para si e ficar bloqueado
esperando por um outro recurso;
Condição de não-preempção: recursos já alocados a processos
não podem ser tomados a força. Eles precisam ser liberados
explicitamente pelo processo que detém a sua posse;
Condição de espera circular: deve existir uma cadeia circular
de dois ou mais processos, cada um dos quais esperando por um
recurso que está com o próximo membro da cadeia.
Escalonamento de Processos
Prevenir a ocorrência de deadlocks
1)
Exclusão mútua: o processo solicita o recurso para
uso de forma mutuamente exclusiva.
Esta condição é eliminada se o processo solicita
todos os recursos que necessita em uma única vez.
Escalonamento de Processos
Prevenir a ocorrência de deadlocks
2) Espera por recursos (posse-e-espera):. Processos
possuem recursos enquanto esperam por recursos
adicionais.
Um processo pode requisitar e liberar recursos, mas
quando requisitar um recurso não disponível deve
liberar os que estavam utilizando e, então solicitar
todos coletivamente
Escalonamento de Processos
Prevenir a ocorrência de deadlocks
3) Não preempção: Quando os recursos não puderem
ser confiscados temporariamente para serem
alocados a outros processos.
Elimina-se esta condição se os recursos forem
ordenados e os processos devem requisitar os
recursos em uma seqüência que respeite esta
ordenação.
Escalonamento de Processos
Prevenir a ocorrência de deadlocks
4) Espera circular: Quando for possível a formação
de um ciclo no qual cada processo está
bloqueado à espera de recursos que estão
alocados para outros processos de mesmo ciclo.
Esta condição é eliminada se for construído um
grafo e se for verificado, para cada requisição,
se o atendimento não levará o sistema a um
estado não seguro. As requisições que levarem
o sistema a um estado não seguro ou de
deadlock não deverão ser atendidas.
Condições Necessárias para a Ocorrência
de Deadlock
As três primeiras caracterizam um modelo de sistema, e
a última é o deadlock propriamente dito:



Processos que estejam de posse de recursos obtidos
anteriormente podem solicitar novos recursos.
Caso estes recursos já estejam alocados a outros
processos, o processo solicitante deve aguardar pela
liberação do mesmo;
Uma solução bastante utilizada na maioria dos S.Os. é
eliminar os processos envolvidos no deadlock e
desalocar os recursos já garantidos por eles,
quebrando assim a espera circular.
Estratégias para tratar Deadlocks
1. ignorar por completo o problema
2. detecção e recuperação
3. evitação dinâmica
• alocação cuidadosa de recursos
4. prevenção
• negação de uma das quatro condições necessárias
Tratamento de Deadlock
Existem quatro estratégias para tratamento
de deadlocks:
Algoritmo do Avestruz (Ignorar a situação)

A estratégia mais simples para tratamento
(ou não) do deadlock, conhecida como
Algoritmo do Avestruz, é simplesmente
ignorá-lo. É defendida pelo fato de que a
frequência de ocorrência deste tipo de
evento é baixa demais para que seja
necessário sobrecarregar a CPU com
códigos extras de tratamento, e que,
ocasionalmente, é tolerável reiniciar o
sistema como uma ação corretiva.
Tratamento de Deadlock
Existem quatro estratégias para tratamento
de deadlocks:
Detectar o deadlock e recuperar o sistema



Nessa estratégia, o sistema permite que ocorra o deadlock
e só então executa o procedimento de recuperação, que
resume-se na detecção da ocorrência e na recuperação
posterior do sistema. Na execução desse procedimento
ocorre a sobrecarga, pois existem dois grandes problemas:
primeiramente, como/quando detectar o deadlock e
depois, como corrigi-lo.
Caso um recurso seja solicitado e a nova situação gere um
impasse, o Sistema Operacional tentará eliminar um
processo do ciclo.
Se o ciclo ainda existir, outro processo será eliminado até
que o ciclo seja quebrado.
Tratamento de Deadlock
Existem quatro estratégias para tratamento de
deadlocks:
Evitar o deadlock (Deadlock avoidance)


O sistema pode evitar que um impasse ocorra mediante a
alocação cuidadosa dos recursos disponíveis. Para que isso
ocorra, o sistema precisará de informações adicionais a
priori de quais recursos um processo irá requisitar e usar
durante sua execução.
Analisaremos o algoritmo do banqueiro para um recurso e
para múltiplos recursos, que são utilizados para avaliar se
uma alocação de recursos é considerada segura ou não.
Algoritmo do Banqueiro


O algoritmo do banqueiro foi proposto por Dijkstra (1965).
Este algoritmo é baseado na mesma idéia de um banqueiro
de uma pequena cidade para garantir ou não crédito a seus
clientes. A idéia é que um banco jamais possa alocar todo
seu dinheiro disponível em caixa de tal modo que não possa
mais atender às necessidades de todos os seus clientes.
Tratamento de Deadlock
Existem quatro estratégias para tratamento de
deadlocks:
Prevenção

Negação de uma das quatro condições necessárias.
Exercício
Represente em forma de
grafos a situação da
figura ao lado.
Solução
Referências


Sistemas Operacionais Modernos – 3ª Edição. A.
Tanenbaum, 2008.
Modern Operating Systems 3 e. Prentice-Hall, 2008.