Impasse - Deadlock

Ambos os processos precisam de recursos para continuar a execução. P1 requer recurso adicional R1 e está em posse do recurso R2 , P2 requer recurso adicional R2 e está em posse de R1 ; nenhum processo pode continuar.
Quatro processos (linhas azuis) competem por um recurso (círculo cinza), seguindo uma política direita antes da esquerda. Um deadlock ocorre quando todos os processos bloqueiam o recurso simultaneamente (linhas pretas). O impasse pode ser resolvido quebrando a simetria.

Na computação simultânea , um deadlock é um estado em que cada membro de um grupo espera que outro membro, incluindo ele mesmo, execute uma ação, como enviar uma mensagem ou, mais comumente, liberar um bloqueio . Deadlocks são um problema comum em sistemas de multiprocessamento , computação paralela e sistemas distribuídos , onde bloqueios de software e hardware são usados ​​para arbitrar recursos compartilhados e implementar sincronização de processos .

Em um sistema operacional , um deadlock ocorre quando um processo ou thread entra em um estado de espera porque um recurso de sistema solicitado é mantido por outro processo em espera, que por sua vez está esperando por outro recurso mantido por outro processo em espera. Se um processo não puder mudar seu estado indefinidamente porque os recursos solicitados por ele estão sendo usados ​​por outro processo em espera, o sistema é considerado um deadlock.

Em um sistema de comunicação , os deadlocks ocorrem principalmente devido a sinais perdidos ou corrompidos, em vez de contenção de recursos.

Dois processos competindo por dois recursos em ordem oposta.
  1. Um único processo é executado.
  2. O último processo tem que esperar.
  3. Um conflito ocorre quando o primeiro processo bloqueia o primeiro recurso ao mesmo tempo que o segundo processo bloqueia o segundo recurso.
  4. O impasse pode ser resolvido cancelando e reiniciando o primeiro processo.

Condições necessárias

Uma situação de deadlock em um recurso pode surgir se e somente se todas as seguintes condições ocorrerem simultaneamente em um sistema:

  1. Exclusão mútua : pelo menos dois recursos devem ser mantidos em um modo não compartilhável. Caso contrário, os processos não seriam impedidos de usar o recurso quando necessário. Apenas um processo pode usar o recurso em um determinado momento.
  2. Reter e aguardar ou retenção de recurso: um processo está atualmente retendo pelo menos um recurso e solicitando recursos adicionais que estão sendo retidos por outros processos.
  3. Sem preempção : um recurso só pode ser liberado voluntariamente pelo processo que o detém.
  4. Espera circular: cada processo deve estar esperando por um recurso que está sendo retido por outro processo, que por sua vez está aguardando que o primeiro processo libere o recurso. Em geral, existe um conjunto de processos de espera, P = { P 1 , P 2 , ..., P N }, tal que P 1 está esperando por um recurso mantido por P 2 , P 2 está esperando por um recurso mantido por P 3 e assim por diante até que P N esteja esperando por um recurso retido por P 1 .

Essas quatro condições são conhecidas como condições de Coffman por sua primeira descrição em um artigo de 1971 de Edward G. Coffman, Jr.

Embora essas condições sejam suficientes para produzir um conflito em sistemas de recursos de instância única, elas indicam apenas a possibilidade de conflito em sistemas com várias instâncias de recursos.

Tratamento de deadlock

A maioria dos sistemas operacionais atuais não pode evitar bloqueios. Quando ocorre um deadlock, diferentes sistemas operacionais respondem a eles de maneiras diferentes e fora do padrão. A maioria das abordagens funciona evitando que uma das quatro condições de Coffman ocorra, especialmente a quarta. As principais abordagens são as seguintes.

Ignorando impasse

Nessa abordagem, presume-se que nunca ocorrerá um deadlock. Esta também é uma aplicação do algoritmo de avestruz . Essa abordagem foi inicialmente usada pelo MINIX e UNIX . Isso é usado quando os intervalos de tempo entre as ocorrências de deadlocks são grandes e a perda de dados incorrida a cada vez é tolerável.

Ignorar deadlocks pode ser feito com segurança se os deadlocks forem formalmente comprovados como nunca ocorrendo. Um exemplo é o framework RTIC.

Detecção

Sob a detecção de deadlock, os deadlocks podem ocorrer. Em seguida, o estado do sistema é examinado para detectar se ocorreu um conflito e, posteriormente, ele é corrigido. É empregado um algoritmo que rastreia a alocação de recursos e os estados do processo, reverte e reinicia um ou mais processos para remover o impasse detectado. Detectar um deadlock que já ocorreu é facilmente possível, uma vez que os recursos que cada processo bloqueou e / ou solicitou atualmente são conhecidos pelo planejador de recursos do sistema operacional.

Depois que um deadlock é detectado, ele pode ser corrigido usando um dos seguintes métodos:

  1. Encerramento do processo: um ou mais processos envolvidos no deadlock podem ser abortados. Pode-se optar por abortar todos os processos concorrentes envolvidos no impasse. Isso garante que o impasse seja resolvido com certeza e velocidade. Mas a despesa é alta, pois cálculos parciais serão perdidos. Ou, pode-se escolher abortar um processo por vez até que o impasse seja resolvido. Essa abordagem tem uma grande sobrecarga porque, após cada aborto, um algoritmo deve determinar se o sistema ainda está em conflito. Vários fatores devem ser considerados ao escolher um candidato para rescisão, como prioridade e idade do processo.
  2. Preempção de recursos : os recursos alocados a vários processos podem ser sucessivamente eliminados e alocados a outros processos até que o impasse seja resolvido.

Prevenção

(A) Dois processos competindo por um recurso, seguindo uma política de ordem de chegada. (B) O deadlock ocorre quando ambos os processos bloqueiam o recurso simultaneamente. (C) O impasse pode ser resolvido quebrando a simetria dos bloqueios. (D) O impasse pode ser evitado quebrando a simetria do mecanismo de travamento.

A prevenção de deadlock funciona evitando que uma das quatro condições de Coffman ocorra.

  • Remover a condição de exclusão mútua significa que nenhum processo terá acesso exclusivo a um recurso. Isso é impossível para recursos que não podem ser armazenados em spool . Mas mesmo com recursos em spool, o impasse ainda pode ocorrer. Os algoritmos que evitam a exclusão mútua são chamados de algoritmos de sincronização sem bloqueio .
  • As condições de retenção e espera ou retenção de recurso podem ser removidas exigindo que os processos solicitem todos os recursos de que precisarão antes de iniciar (ou antes de embarcar em um determinado conjunto de operações). Este conhecimento prévio é freqüentemente difícil de satisfazer e, em qualquer caso, é um uso ineficiente de recursos. Outra maneira é exigir que os processos solicitem recursos apenas quando não houver nenhum; Primeiro, eles devem liberar todos os recursos atualmente mantidos antes de solicitar todos os recursos de que precisarão do zero. Isso também costuma ser impraticável. É assim porque os recursos podem ser alocados e permanecer sem uso por longos períodos. Além disso, um processo que requer um recurso popular pode ter que esperar indefinidamente, já que esse recurso pode sempre ser alocado para algum processo, resultando em escassez de recursos . (Esses algoritmos, como tokens de serialização , são conhecidos como algoritmos tudo ou nada .)
  • A condição de ausência de preempção também pode ser difícil ou impossível de evitar, pois um processo deve ser capaz de ter um recurso por um determinado período de tempo, ou o resultado do processamento pode ser inconsistente ou pode ocorrer um thrashing . No entanto, a incapacidade de impor a preempção pode interferir com um algoritmo de prioridade . A preempção de um recurso "bloqueado" geralmente implica em uma reversão e deve ser evitada, uma vez que é muito cara em despesas gerais. Os algoritmos que permitem a preempção incluem algoritmos sem bloqueio e sem espera e controle de simultaneidade otimista . Se um processo retém alguns recursos e solicita algum outro recurso (s) que não podem ser alocados imediatamente a ele, a condição pode ser removida liberando todos os recursos retidos atualmente desse processo.
  • A condição final é a condição de espera circular . Abordagens que evitam esperas circulares incluem desabilitar interrupções durante seções críticas e usar uma hierarquia para determinar uma ordenação parcial de recursos. Se nenhuma hierarquia óbvia existe, até mesmo o endereço de memória de recursos foi usado para determinar a ordem e os recursos são solicitados na ordem crescente da enumeração. A solução de Dijkstra também pode ser usada.

Livelock

Um livelock é semelhante a um deadlock, exceto que os estados dos processos envolvidos no livelock mudam constantemente entre si, nenhum progredindo.

O termo foi cunhado por Edward A. Ashcroft em um artigo de 1975 em conexão com um exame dos sistemas de reserva de companhias aéreas. Livelock é um caso especial de escassez de recursos ; a definição geral afirma apenas que um processo específico não está progredindo.

Livelock é um risco com alguns algoritmos que detectam e se recuperam de deadlock . Se mais de um processo entrar em ação, o algoritmo de detecção de deadlock pode ser disparado repetidamente. Isso pode ser evitado garantindo que apenas um processo (escolhido arbitrariamente ou por prioridade) execute a ação.

Impasse distribuído

Deadlocks distribuídos podem ocorrer em sistemas distribuídos quando transações distribuídas ou controle de simultaneidade estão sendo usados.

Os deadlocks distribuídos podem ser detectados pela construção de um gráfico de espera global a partir de gráficos de espera locais em um detector de deadlock ou por um algoritmo distribuído como perseguição de borda .

Deadlocks fantasmas são deadlocks que são falsamente detectados em um sistema distribuído devido a atrasos internos do sistema, mas não existem de fato.

Por exemplo, se um processo libera um recurso R1 e emite uma solicitação de R2 , e a primeira mensagem é perdida ou atrasada, um coordenador (detector de deadlocks) pode concluir falsamente um deadlock (se a solicitação de R2 enquanto tem R1 causaria um impasse).

Veja também

Referências

Leitura adicional

links externos