Alguém pode explicar com exemplos (de código) qual é a diferença entre deadlock e livelock ?
multithreading
pthreads
deadlock
livelock
macindows
fonte
fonte
Respostas:
Retirado de http://en.wikipedia.org/wiki/Deadlock :
fonte
Livelock
A principal diferença entre livelock e deadlock é que os threads não serão bloqueados; eles tentarão responder um ao outro continuamente.
Nesta imagem, os dois círculos (threads ou processos) tentarão dar espaço ao outro movendo-se para a esquerda e para a direita. Mas eles não podem avançar mais.
fonte
Todo o conteúdo e exemplos aqui são de
Sistemas operacionais: Internos e princípios de design
William Stallings
8º Edição
Impasse : uma situação em que dois ou mais processos não podem prosseguir porque cada um deles espera um dos outros para fazer alguma coisa.
Por exemplo, considere dois processos, P1 e P2, e dois recursos, R1 e R2. Suponha que cada processo precise acessar os dois recursos para desempenhar parte de sua função. É possível ter a seguinte situação: o sistema operacional atribui R1 a P2 e R2 a P1. Cada processo está aguardando um dos dois recursos. Nem liberará o recurso que ele já possui até adquirir o outro recurso e executar a função que requer os dois recursos. Os dois processos estão em um impasse
Livelock : uma situação em que dois ou mais processos alteram continuamente seus estados em resposta a alterações nos outros processos sem realizar nenhum trabalho útil:
Inanição : uma situação em que um processo executável é ignorado indefinidamente pelo planejador; embora possa prosseguir, nunca é escolhido.
Suponha que três processos (P1, P2, P3) requeiram acesso periódico ao recurso R. Considere a situação em que P1 está de posse do recurso e ambos, P2 e P3, estão atrasados, aguardando esse recurso. Quando P1 sai de sua seção crítica, P2 ou P3 devem ter acesso a R. Suponha que o SO conceda acesso a P3 e que P1 novamente exija acesso antes de P3 concluir sua seção crítica. Se o SO conceder acesso a P1 após a conclusão de P3 e, posteriormente, conceder acesso alternadamente a P1 e P3, P2 poderá indefinidamente ser negado o acesso ao recurso, mesmo que não haja situação de conflito.
APÊNDICE A - TÓPICOS EM CONCORRÊNCIA
Exemplo de impasse
Se os dois processos definirem seus sinalizadores como true antes de qualquer um executar a instrução while, cada um deles pensará que o outro entrou em sua seção crítica, causando um conflito.
Exemplo de Livelock
[...] considere a seguinte sequência de eventos:
Essa sequência pode ser estendida indefinidamente, e nenhum processo pode entrar em sua seção crítica. Estritamente falando, isso não é um impasse , porque qualquer alteração na velocidade relativa dos dois processos interromperá esse ciclo e permitirá a entrada na seção crítica. Essa condição é conhecida como livelock . Lembre-se de que o conflito ocorre quando um conjunto de processos deseja inserir suas seções críticas, mas nenhum processo pode ser bem-sucedido. Com o livelock , existem possíveis sequências de execuções com êxito, mas também é possível descrever uma ou mais sequências de execução nas quais nenhum processo entra em sua seção crítica.
Não há mais conteúdo do livro.
E os spinlocks?
Spinlock é uma técnica para evitar o custo do mecanismo de bloqueio do SO. Normalmente você faria:
Um problema começa a aparecer quando
beginLock()
custa muito mais do quedoSomething()
. Em termos muito exagerados, imagine o que acontece quando obeginLock
custo é de 1 segundo, masdoSomething
custa apenas 1 milissegundo.Nesse caso, se você esperasse 1 milissegundo, evitaria ser prejudicado por 1 segundo.
Por
beginLock
que custaria tanto? Se o bloqueio é gratuito, não custa muito (consulte https://stackoverflow.com/a/49712993/5397116 ), mas se o bloqueio não estiver livre, o sistema operacional "congelará" seu encadeamento, configure um mecanismo para acordá-lo quando o bloqueio for liberado e, em seguida, acordá-lo novamente no futuro.Tudo isso é muito mais caro do que alguns loops verificando a trava. É por isso que às vezes é melhor fazer um "spinlock".
Por exemplo:
Se sua implementação não for cuidadosa, você poderá usar o livelock, gastando toda a CPU no mecanismo de bloqueio.
Veja também:
https://preshing.com/20120226/roll-your-own-lightweight-mutex/
Minha implementação de bloqueio de rotação está correta e ideal?
Resumo :
Impasse : situação em que ninguém progride, não faz nada (dorme, espera etc.). O uso da CPU será baixo;
Livelock : situação em que ninguém progride, mas a CPU é gasta no mecanismo de bloqueio e não no seu cálculo;
Fome: situação em que um processo nunca tem a chance de correr; por pura má sorte ou por algumas de suas propriedades (baixa prioridade, por exemplo);
Spinlock : técnica de evitar o custo de espera para liberar o bloqueio.
fonte
DEADLOCK Deadlock é uma condição na qual uma tarefa aguarda indefinidamente por condições que nunca podem ser satisfeitas - tarefa reivindica controle exclusivo sobre recursos compartilhados - tarefa mantém recursos enquanto aguarda a liberação de outros recursos - tarefas não podem ser forçadas a redesignar recursos - uma espera circular condição existe
LIVELOCK As condições do Livelock podem surgir quando duas ou mais tarefas dependem e usam algum recurso, causando uma condição circular de dependência em que essas tarefas continuam em execução para sempre, impedindo a execução de todas as tarefas de nível de prioridade mais baixa (essas tarefas de prioridade mais baixa sofrem uma condição chamada inanição)
fonte
Talvez estes dois exemplos ilustrem a diferença entre um impasse e um livelock:
Exemplo de Java para um conflito:
Saída de amostra:
Exemplo de Java para um livelock:
Saída de amostra:
Ambos os exemplos forçam os encadeamentos a adquirir os bloqueios em ordens diferentes. Enquanto o impasse aguarda o outro bloqueio, o bloqueio realmente não espera - ele tenta desesperadamente adquiri-lo sem a chance de obtê-lo. Cada tentativa consome ciclos da CPU.
fonte
Imagine que você tenha o segmento A e o segmento B. Ambos estão
synchronised
no mesmo objeto e, dentro desse bloco, há uma variável global que eles estão atualizando;Portanto, quando o segmento A entra no
while
loop e mantém a trava, ele faz o que tem que fazer e definecommonVar
comotrue
. Então a linha B entra, entra nowhile
loop e, comocommonVar
étrue
agora, é capaz de segurar a trava. Faz isso, executa osynchronised
bloco ecommonVar
volta parafalse
. Agora, o thread A novamente obtém sua nova janela da CPU, estava prestes a sair dowhile
loop, mas o thread B acabou de configurá-lo novamente parafalse
que o ciclo se repita novamente. Os threads fazem alguma coisa (para que não sejam bloqueados no sentido tradicional), mas praticamente para nada.Talvez também seja bom mencionar que o livelock não precisa necessariamente aparecer aqui. Estou assumindo que o agendador favorece o outro thread quando o
synchronised
bloco terminar de executar. Na maioria das vezes, acho que é uma expectativa difícil de atingir e depende de muitas coisas acontecendo sob o capô.fonte