Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

DEADLOCK

No description
by

Robert Gebhardt

on 28 September 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of DEADLOCK

DEADLOCK
Detectando um deadlock

Competição por recursos
Lidando com Deadlocks



-Ignorar
-Detectar e recuperar
-Evitar
-Prevenir
Razoável se o custo para prevenção é alto e os deadlocks ocorrem raramente.
Deixar que ocorra, detectar e tomar uma ação para recuperar o sistema.
Evitação dinâmica por alocação cuidadosa de recursos.
Estruturalmente negando uma das quatro condições.
Evitando um Deadlock




Trajetórias de Recursos
Estados Seguros e não Seguros
Um estado é considerado seguro se é possivel para todos os processos concluir sua execução.
Um estado é considerado inseguro quando não existe sequencia que garante concluir a execução.
Algoritmo do banqueiro
O algoritmo do banqueiro é executado pelo sistema operacional quando um processo de cumputação requisita recursos.
O algoritmo impede o impasse ao negar ou adiar o pedido se ele determinar que aceitar o pedido pode colocar o sistema em um estado inseguro.
Para o algoritmo do banqueiro trabalhar ele precisa saber três coisas:
Quanto de cada recurso cada processo poderia solicitar
Quanto de cada recurso cada processo atualmente detém
Quanto de cada recurso o sistema tem disponível
O algoritmo do banqueiro:
Recursos simples
Multiplos recursos
Prevenção de Deadlocks
Mutual-Exclusion Condition
-Basicamente, se não designássemos a exclusividade para um processo não haveriam deadlocks.

-Usando os Daemos de impressoras, por exemplo, ajudam a diminuir os deadlocks, porém não resolve na sua totalidade.

-Abordagem de não definir exclusividade é frequentemente aplicada, só em casos que não tem para onde fugir que temos que realmente definir exclusividade.

No-Preemption Condition
Como já vimos, usar o deamon da impressora como conexão com a mesma acaba com os deadlocks de concorrência, mas poderíamos ter problemas com o processo parar no meio porque não tem os recursos necessários para a impressão.

Então poderíamos primeiro virtualizar o que será impresso antes de enviar para o Daemon.
Porém isso pode gerar um deadlock em disco, e alguns tipos de arquivos não podem ser virtualizados

Hold-and-Wait Condition
-Se pudermos prevenir de processos requererem recurso e ficarem segurando e esperando outros recursos, não teríamos mais deadlocks. Uma abordagem possível é definir que os processos só podem ser executados quando estiverem com todos os recursos disponíveis para uso.

-Porém, muitos processos não sabem o que vão precisar até eles começarem a ser executados, e outros simplesmente perderiam um pouco de sua eficiência.

-Existem outras opções como: pré alocar todos os recursos que serão usados, até que o processo acabe, e requerer o que será necessário, logo depois disso liberar os mesmos.

Circular Wait Condition
-Para evitar isso é colocado um tipo de flag nos recursos. Os processos só podem solicitar um próximo recurso, por exemplo, se ele já tiver acabado um menor.
Seguindo essa regra, um processo que esteja usando um recurso de flag maior não poderá pedir outro recurso de flag menor, porque senão ele pode ficar em loop.

-Também temos uma outra abordagem que permite que o processo requeira algo com uma flag menor, porém ele terá que ter terminado o que estava executando.
Apesar do sistema de ordem acabar com o deadlock pode ser difícil achar uma ordem que satisfaça todos os processos e que ordene recursos como informações reservadas do database.


Deadlock
Um grupo de processos esta deadlocked quando cada processo no grupo esta aguardando um evento que outro processo no grupo tem de causar, parando a execução de todo o grupo
RECURSOS
-Deadlocks ocorrem em grande parte por involver recursos com acesso exclusivo. Esses recursos podem ser arquivos, preféricos como impressoras, etc.

-Existem dois tipos de recursos: preemptíveis e não-preemptíveis. O primeiro pode ser tirado do processo que o usa sem graves consequencias, como memória, e o ultimo não pode sem ocorrer uma falha, como um gravador de cd. Deadlocks involvem os recursos não-preemptíveis.
Condições para deadlocks de recursos
-Condição de Exclusão Mútua:
Cada recurso ou já está em poder de um processo ou está disponível.
-Condição Hold-and-Wait:
Processos em poder de recursos são garantidos poder para adquirir novos recursos.
-Condição de espera circular:
Deve haver uma lista circular de dois ou mais processos no qual cada processo está esperando um recurso apropriado pelo proximo menbro da corrente.
-Condição de espera circular:
Deve haver uma lista circular de dois ou mais processos no qual cada processo está esperando um recurso apropriado pelo proximo membro da corrente.
Modelagem de Deadlocks
As condições para deadlocks acontecerem podem ser modelados usando grafos direcionados. Grafos de recursos são uma ferramenta para visualizar se determinada sequencia de Requisição/Liberação acabe em deadlock.
Processos são circulos e recursos são quadrados. A seta de um recurso para processo significa que o recurso está em possessão daquele processo. Uma seta de um processo para um recurso significa que o processo está esperando pelo recurso.
Para haver um deadlock os recursos não terão mais como atender os novos processos pois os anteriores estão inacabados, veja na figura abaixo com 7 processos e 6 recursos.
Embora seja relativamente simples para escolher os processos deadlocked pela obeservação a partir de um gráfico simples, para uso em sistemas reais precisamos de um algoritmo formal para a detecção de impassses.
Exemplo de detecção de deadlock com multiplos recursos

Recuperando um deadlock









1. Preempção:
Neste caso o processo tem a capacidade de retirar um determinado recurso de outro processo. Essa técnica resolveria o problema para determinado casos em que o recurso pode ser desalocado sem grandes danos. Mas isso depende muito da natureza do processo que está usando aquele recurso.

2. Rollback:
Se os designers dos sistemas tiverem ciência que os deadlocks são parecidos nesse caso são armazenados diversos arquivos, onde os processos causadores de deadlock são salvos, para que possam ser inicializados depois. Dessa forma quando esse deadlock é detectado o processo que possui os recursos que estão sendo pedidos sofre um Rollback até um ponto onde ele não possuia os recursos, dando possibilidade para outros processos fluirem.

3. Eliminação de processos:
A maneira mais simples de se recuperar um deadlock é matando o processo que está causando. É notável que esta não é a melhor opção pois muitos processos quando "mortos" perdem todas suas informações.
2
Outros problemas relacionados
Two-phase locking
Essa abordagem é usada em alguns sistemas, como em banco de dados. Consiste em basicamente reservar todos os recursos que serão usados pelo processo antes de propriamente executar. Em um sistema de banco de dados isso é feito, por exemplo, em querys de atualização.
Deadlock de comunicação
Esse tipo de deadlock é um pouco diferente pois não se trata de recursos. Não podemos prevenir usando a tática de colocar uma orem nos recursos porque eles não solicitam recursos e sim uma comunicação com a outra parte.

Um método para resolver esse tipo de deadlock é colocar um limite para dar "timeout" na comunicação, porém isso tem que ser bem calculado pois um pacote pode apenas ter sofrido delay para chegar.
Livelock
Em algumas situações, processos tentam ser educados desistindo de segurar um recurso quando percebe que não pode pegar um outro recurso que irá precisar. Então ele espera e tenta de novo.
Legal, bacana. Mas e se outro processo fazer exatamente a mesma coisa no exato mesmo tempo?
Diferente de um Deadlock, os processos envolvidos em um Livelock não estão "travados". Estão rodando, porém presos em um loop gerado pela concorrência de recursos, sem possibilidade de progresso.
Starvation
Ocorre quando um processo tem o acesso sempre negado a um recurso necessário para a execução, não importando quantas vezes ele tente.
Por exempo quando algum algoritmo de concorrência usa uma lógica onde esse processo perde pra outros, e sempre um processo está.
Full transcript