Impasse - Deadlock
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.
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:
- 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.
- 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.
- Sem preempção : um recurso só pode ser liberado voluntariamente pelo processo que o detém.
- 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:
- 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.
- 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 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
- Aporia
- Algoritmo do banqueiro
- Catch-22 (lógica)
- Referencia circular
- Problema de filósofos gastronômicos
- Bloqueio de arquivo
- Bloqueio (no tráfego de veículos)
- Hang (computação)
- Impasse
- Loop infinito
- Linearizabilidade
- O verificador de modelo pode ser usado para verificar formalmente se um sistema nunca entrará em um impasse
- Algoritmo de avestruz
- Inversão de prioridade
- Condição de corrida
- Bloqueio leitor-escritor
- Problema de barbeiro dormindo
- Impasse
- Sincronização (ciência da computação)
- Roteamento de restrição de curvas
Referências
Leitura adicional
-
Kaveh, Nima; Emmerich, Wolfgang. "Detecção de deadlock em sistemas de objetos distribuídos" (PDF) . Londres: University College London. Citar diário requer
|journal=
( ajuda ) - Bensalem, Saddek; Fernandez, Jean-Claude; Havelund, Klaus; Mounier, Laurent (2006). Confirmação dos potenciais de deadlock detectados pela análise de tempo de execução . Proceedings of the Workshop on Parallel and Distributed Systems: Testing and Debugging . ACM. pp. 41–50. CiteSeerX 10.1.1.431.3757 . doi : 10.1145 / 1147403.1147412 . ISBN 978-1595934147. S2CID 2544690 .
- Coffman, Edward G., Jr .; Elphick, Michael J .; Shoshani, Arie (1971). "Deadlocks do sistema" (PDF) . Pesquisas de computação ACM . 3 (2): 67–78. doi : 10.1145 / 356586.356588 . S2CID 15975305 .
- Mogul, Jeffrey C .; Ramakrishnan, KK (1997). "Eliminando o livelock de recebimento em um kernel controlado por interrupção". Transações ACM em sistemas de computador . 15 (3): 217–252. CiteSeerX 10.1.1.156.667 . doi : 10.1145 / 263326.263335 . ISSN 0734-2071 . S2CID 215749380 .
- Havender, James W. (1968). “Evitando deadlock em sistemas multitarefa” . IBM Systems Journal . 7 (2): 74. doi : 10.1147 / sj.72.0074 .
- Holliday, JoAnne L .; El Abbadi, Amr. "Deteção de impasse distribuído" . Enciclopédia de Computação Distribuída . Arquivado do original em 2 de novembro de 2015 . Página visitada em 29 de dezembro de 2004 .
- Knapp, Edgar (1987). "Detecção de deadlock em bancos de dados distribuídos". Pesquisas de computação ACM . 19 (4): 303–328. CiteSeerX 10.1.1.137.6874 . doi : 10.1145 / 45075.46163 . ISSN 0360-0300 . S2CID 2353246 .
- Ling, Yibei; Chen, Shigang; Chiang, Jason (2006). "On Optimal Deadlock Detection Scheduling". Transações IEEE em computadores . 55 (9): 1178–1187. CiteSeerX 10.1.1.259.4311 . doi : 10.1109 / tc.2006.151 . S2CID 7813284 .
links externos
- " Advanced Synchronization in Java Threads " por Scott Oaks e Henry Wong
- Agentes de detecção de deadlock
- DeadLock no Portland Pattern Repository
- Etimologia do "impasse"