Evitando_DeadLock

Prévia do material em texto

DEADLOCK Eng. Eduardo Juliano Alberti
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
Negação da espera
Negação da preempção
Negação da Espera Circular
2
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
Porém nem sempre é possível implementar tais técnicas.
Imagine um sistema de tempo real. Um sistema não pode negar o processador a um 
processo ou thread caso seja necessário que este entre em execução.
Nestes casos o sistema deve permitir a execução, porém evitando um deadlock.
3
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
O Algoritmo do banqueiro é um algoritmo muito difundido quando o objetivo é evitar 
a ocorrência de deadlocks.
O algoritmo propõe o mesmo que ocorre em uma instituição financeira. O Banqueiro 
pode conceder empréstimos a diversos clientes, porém quando o faz, só o faz se 
houver um reserva de capital que possa utilizar.
O cliente por sua vez, compromete-se a devolver o valor emprestado para que o 
banqueiro possa reintegrar ao seu capital.
4
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
O que acontece no algoritmo do banqueiro é exatamente o mesmo: o sistema 
empresta seus recursos, armazenados, a medida que estes estejam disponíveis.
O sistema, portanto, reserva tipos de recursos, onde cada tipo de recurso representa 
todos os recursos disponíveis que executam a mesma função.
5
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
O Algoritmo segue uma determinada lógica de propriedades:
 O SO compartilha T recursos com N processos (ambos valores fixos)
 Cada processo tem por responsabilidade especificar o número máximo de recursos necessários para 
concluir seu trabalho.
 O SO aceita o pedido de um processo caso o número de recursos solicitados não seja maior que o 
número total de recursos disponíveis.
 Em caso de espera, o SO garante um tempo finito.
 Sabendo que um processo, cuja execução dependa de um número T de recursos, poderá garantir um 
tempo satisfatório de execução (e definido) apenas se o SO garantir o número máximo de recursos.
6
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
Antes precisamos convencionar que:
Max(Pi) representa o número máximo de recursos que um processo i necessita
Loan(Pi) representa o número de recursos emprestados atualmente ao processo i
Claim(Pi) representa uma solicitação de recurso resultante de max(Pi) – loan(Pi)
a representa o número de processos disponíveis para alocação e é calculado a partir 
da soma de todos os recursos disponíveis para alocação subtraídos dos recursos 
totais.
7
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
8
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
9
Este é um estado considerado seguro.
Perceba que ao realizar o processamento dos pedidos de recursos, caso P2 realize a 
solicitação de 2 recursos será perfeitamente possível o término do processamento. 
Ao final de seu processamento, P2 terá liberado 6 recursos, o que permite o 
processamento dos pedidos de P1 e P3.
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
10
Poderia então, P1 ou P3 realizar suas solicitações de recursos?
Se sim, suas requisições seriam atendidas?
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
11
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
12
Este é um estado considerado inseguro.
Qualquer processo que necessitar de recurso não conseguirá alocar o número de 
recursos necessários para terminar seu processamento.
Neste caso, não podemos afirmar que os processos, ao longo de seu processamento, 
não devolvam algum recurso que possibilite o término da execução.
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
13
Portanto podemos chegar a algumas conclusões:
 Caso algum processo devolva ao SO um recurso emprestado, existe a possibilidade de que um dos 
processos consiga alocar o número necessário de recursos necessário para o término de seu 
processamento.
 Caso o recurso seja alocado por um dos processos, pode haver um deadlock caso os outros processos 
decidam solicitar o recurso restante.
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
14
Podemos, com base nestas informações dizer que o estado inseguro não implica na 
ocorrência de um deadlock e tão pouco que um um deadlock irá ocorrer.
Entretanto o fato de o SO estar em um estado inseguro somado a diversos eventos 
podem levar a ocorrência de um deadlock.
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
15
Qual é o número mínimo de recursos necessários para garantir, nesta situação, um 
estado seguro?
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
16
O que aconteceria então se, em um estado seguro, um processo solicitasse um recurso 
adicional?
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
17
É importante que, ao solicitar a alocação de recursos, a política de alocação leve em 
consideração todas os recursos necessários para todas as possíveis situações, caso 
contrário um estado seguro pode migrar para um estado inseguro.
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
18
Durante a execução do algoritmo do Banqueiro pode-se perceber que as condições 
de exclusão mútua, espera e não-preempção são permitidas.
O sistema tem por objetivo manter-se em estado seguro durante todo o tempo, ou 
seja, todas as requisições de recursos que levem ao estado de insegurança serão 
negadas até que uma operação segura seja possível.
EVITANDO DEADLOCKS – ALGORITMO DO 
BANQUEIRO
19
Desta forma, se pensarmos que o SO estará sempre em estado seguro, todas as 
requisições serão atendidas em determinado tempo e o usuário poderá efetuar todas 
as operações desejadas.
NEM TUDO SÃO FLORES
20
Requer que o número de recursos seja fixo.
Requer que o número de processos seja fixo.
Requer que o sistema atenda as solicitações em um ‘tempo finito’ porém sistemas reais 
precisam muito mais que isso.
Requer que os clientes devolvam os recursos em um tempo finito, porém qual é a 
garantia de que isso irá ocorrer?
NEM TUDO SÃO FLORES
21
Requer que o número de recursos seja fixo.
Requer que o número de processos seja fixo.
Requer que o sistema atenda as solicitações em um ‘tempo finito’ porém sistemas reais 
precisam muito mais que isso.
NEM TUDO SÃO FLORES
22
Requer que os clientes devolvam os recursos em um tempo finito, porém qual é a 
garantia de que isso irá ocorrer?
Requer que todos os recursos sejam declarados inicialmente, porém nem sempre é 
fácil fazê-lo, principalmente quando utilizamos interfaces gráficas. Um usuário se 
preocupa em conseguir imprimir e não com os recursos utilizados para tal.
DETECTANDO DEADLOCKS
23
Outra possibilidade é, nem prevenir e nem evitar, detectar e removê-lo.
Nesta modalidade algoritmos verificam a ocorrência de deadlocks, em espera 
circular ou outra formação.
DETECTANDO DEADLOCKS
24
O problema é que a detecção de deadlocks é complexa. 
Imagine um processo de sincronização de dados (considere que nunca haverá 
problemas com os recursos necessários) que está constantemente acordando e 
dormindo. O processo acorda, sincroniza um pequeno número de arquivos, quando há 
necessidade, e volta a dormir. 
Como saber se este processo está em deadlock se ele nunca termina seu trabalho 
antes que o sistema seja desligado?
DETECTANDO DEADLOCKS
25
Outro problema é que um sistema normalmente não fornece meios para que um 
processo entre em suspensão e retorne sem que haja perda de trabalho.
Por fim, imagine um deadlock envolvendo dezenas ou centenas de processos 
envolveria o estudo detalhado de todos os processos envolvidos para determinar a 
situação adequada de alocação e processamento dos recursos envolvidos para que 
não haja perda de trabalho.
DETECTANDO DEADLOCKS
26
Os sistemas realizam, então, uma recuperação forçada de deadlocks, onde um oumais processos são terminados para que haja liberação de recursos. 
O término de um processo implica na perda de trabalho de um processo e por 
consequência perda de processamento. Neste caso a recuperação não é bem o 
melhor termo para tal operação já que alguns processos são mortos para o 
benefícios de outros.
DETECTANDO DEADLOCKS
27
A maneira mais interessante, porém nem sempre disponível, é a utilização do sistema 
de suspensão e retomada. Desta forma, o processo é suspenso, seus recursos são 
liberados temporariamente e logo após o término da operação o processo é 
retomado sem perda de trabalho.