Qual é a diferença entre deadlock e livelock?

Respostas:

398

Retirado de http://en.wikipedia.org/wiki/Deadlock :

Na computação simultânea, um impasse é um estado no qual cada membro de um grupo de ações está aguardando que outro membro libere um bloqueio

Um livelock é semelhante a um impasse, exceto que os estados dos processos envolvidos no livelock mudam constantemente um em relação ao outro, nenhum progredindo. Livelock é um caso especial de inanição de recursos; a definição geral afirma apenas que um processo específico não está progredindo.

Um exemplo do mundo real de livelock ocorre quando duas pessoas se encontram em um corredor estreito, e cada uma tenta ser educada movendo-se para o lado para deixar o outro passar, mas elas acabam balançando de um lado para o outro sem progredir, porque ambas se movem repetidamente da mesma maneira ao mesmo tempo.

Livelock é um risco em alguns algoritmos que detectam e se recuperam de um conflito. Se mais de um processo executar uma ação, o algoritmo de detecção de deadlock poderá ser acionado repetidamente. Isso pode ser evitado, garantindo que apenas um processo (escolhido aleatoriamente ou por prioridade) tome medidas.

mah
fonte
8
Eu encontrei-o já, mas eles não têm exemplos lá como você pode ver, obrigado de qualquer maneira
macindows
61
Não fornecerei um exemplo de código, mas considere dois processos, cada um aguardando um recurso que o outro possui, mas aguardando de maneira não-bloqueante. Quando cada um aprende que não pode continuar, libera seu recurso retido e dorme por 30 segundos, recupera seu recurso original seguido de tentar o recurso que o outro processo retinha, depois sai e depois recupera. Como os dois processos estão tentando lidar (apenas mal), isso é um livelock.
mah 27/05
4
Você pode me dar o mesmo exemplo, mas com impasse, desde já obrigado
#
32
Um exemplo de conflito é muito mais fácil ... assuma dois processos A e B, e cada um deseja o recurso r1 e o recurso r2. Suponha que A receba (ou já tenha) r1 e B receba (ou já tenha) r2. Agora, cada um tenta obter o recurso que o outro possui, sem tempo limite. A é bloqueado porque B contém r2 e B é bloqueado porque A contém r1. Cada processo é bloqueado e, portanto, não pode liberar o recurso que o outro deseja, causando um conflito.
mah 27/05
2
Dentro do contexto da memória transacional há uma grande vídeo demonstrando impasse e livelock: youtube.com/watch?v=_IxsOEEzf-c
BlackVegetable
78

Livelock

Um encadeamento geralmente atua em resposta à ação de outro encadeamento. Se a ação do outro encadeamento também for uma resposta à ação de outro encadeamento, poderá ocorrer livelock.

Como no impasse, os threads com bloqueio de transmissão não conseguem fazer mais progressos . No entanto, os threads não estão bloqueados - eles estão ocupados demais respondendo um ao outro para retomar o trabalho . É comparável a duas pessoas que tentam passar uma pela outra em um corredor: Alphonse se move para a esquerda para deixar Gaston passar, enquanto Gaston se move para a direita para deixar Alphonse passar. Vendo que eles ainda estão se bloqueando, Alphonse se move para a direita, enquanto Gaston se move para a esquerda. Eles ainda estão se bloqueando, e assim por diante ...

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.

insira a descrição da imagem aqui

Buru
fonte
Exemplos de código para livelocks stackoverflow.com/questions/1036364/good-example-of-livelock
Yauhen Yakimovich
1
Essa coisa tem um nome. Uma palavra de gíria, talvez, mas ainda assim: schlumperdink : P
Red John John
64

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.

/* PROCESS 0 */
flag[0] = true;            // <- get lock 0
while (flag[1])            // <- is lock 1 free?
    /* do nothing */;      // <- no? so I wait 1 second, for example
                           // and test again.
                           // on more sophisticated setups we can ask
                           // to be woken when lock 1 is freed
/* critical section*/;     // <- do what we need (this will never happen)
flag[0] = false;           // <- releasing our lock

 /* PROCESS 1 */
flag[1] = true;
while (flag[0])
    /* do nothing */;
/* critical section*/;
flag[1] = false;

Exemplo de Livelock

/* PROCESS 0 */
flag[0] = true;          // <- get lock 0
while (flag[1]){         
    flag[0] = false;     // <- instead of sleeping, we do useless work
                         //    needed by the lock mechanism
    /*delay */;          // <- wait for a second
    flag[0] = true;      // <- and restart useless work again.
}
/*critical section*/;    // <- do what we need (this will never happen)
flag[0] = false; 

/* PROCESS 1 */
flag[1] = true;
while (flag[0]) {
    flag[1] = false;
    /*delay */;
    flag[1] = true;
}
/* critical section*/;
flag[1] = false;

[...] considere a seguinte sequência de eventos:

  • P0 define o sinalizador [0] como verdadeiro.
  • P1 define o sinalizador [1] como verdadeiro.
  • P0 verifica o sinalizador [1].
  • P1 verifica o sinalizador [0].
  • P0 define o sinalizador [0] como falso.
  • P1 define o sinalizador [1] como falso.
  • P0 define o sinalizador [0] como verdadeiro.
  • P1 define o sinalizador [1] como verdadeiro.

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:

try
{
   lock = beginLock();
   doSomething();
}
finally
{
   endLock();
}

Um problema começa a aparecer quando beginLock()custa muito mais do que doSomething(). Em termos muito exagerados, imagine o que acontece quando o beginLockcusto é de 1 segundo, mas doSomethingcusta apenas 1 milissegundo.

Nesse caso, se você esperasse 1 milissegundo, evitaria ser prejudicado por 1 segundo.

Por beginLockque 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:

void beginSpinLock(lock)
{
   if(lock) loopFor(1 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   if(lock) loopFor(2 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   // important is that the part above never 
   // cause the thread to sleep.
   // It is "burning" the time slice of this thread.
   // Hopefully for good.

   // some implementations fallback to OS lock mechanism
   // after a few tries
   if(lock) return beginLock(lock);
   else 
   {
     lock = true;
     return;
   }
}

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.

Daniel Frederico Lins Leite
fonte
Senhor, o exemplo que você deu para Deadlock é na verdade um exemplo de Spinlock. O impasse ocorre quando um conjunto de processos é bloqueado, que não está no estado pronto ou em execução e aguarda alguns recursos. Mas em nosso exemplo, cada um está executando alguma tarefa, ou seja, verificando a condição repetidamente. Corrija-me se eu estiver errada.
Vinay Yadav 16/04
O exemplo é tão mínimo que abre chances para essa interpretação, então eu melhorei para ser um pouco mais explícito sobre a diferença. Espero que ajude.
Daniel Frederico Lins Leite
Obrigado por adicionar sobre spinlocks, de acordo com você spinlocks é uma técnica e você também justificou e eu entendi. Mas e o problema de inversão de prioridade quando um processo P1 está na Seção Crítica e outro processo de alta prioridade P2 é agendado antecipando P1; nesse caso, a CPU está com P2 e nosso mecanismo de Sincronização está com P1. Isso é chamado Spinlock, pois P1 está no estado pronto e P2 está no estado de execução . Aqui spinlock é um problema. Estou acertando as coisas? Não consigo entender os meandros corretamente. Por favor ajude
Vinay Yadav
Minha sugestão para você é criar outra pergunta indicando seu problema com mais clareza. Agora, se você estiver no "espaço do usuário", e o P1 estiver dentro de uma sessão crítica protegida com um SpinLock implementado com um loop infinito e seu preempção; então o P2 tentará entrar, falhará e queimará todo o seu intervalo de tempo. Você criou um livelock (uma CPU estará em 100%). (um mau uso seria proteger uma E / S de sincronização com o spinlock. Você pode facilmente tentar este exemplo) No "espaço do kernel", talvez esta nota possa ajudá-lo: lxr.linux.no/linux+v3.6.6/Documentation/…
Daniel Frederico Lins Leite
Muito obrigado pelo esclarecimento. Enfim, sua resposta foi bastante descritiva e útil, diferentemente dos outros
Vinay Yadav
13

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)

Deepak Lamichhane
fonte
Se as tarefas 'livelocked' estiverem seguindo protocolos de arbitragem de recursos, que incluem atrasos de 'backoff', e passam a maior parte do tempo no estado de suspensão como resultado, outras tarefas não passarão fome.
Greggo
8

Talvez estes dois exemplos ilustrem a diferença entre um impasse e um livelock:


Exemplo de Java para um conflito:

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class DeadlockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(DeadlockSample::doA,"Thread A");
        Thread threadB = new Thread(DeadlockSample::doB,"Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
        lock1.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 1");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
            lock2.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } finally {
            lock1.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
        }
    }

    public static void doB() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
        lock2.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 2");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
            lock1.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } finally {
            lock2.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
        }
    }
}

Saída de amostra:

Thread A : waits for lock 1
Thread B : waits for lock 2
Thread A : holds lock 1
Thread B : holds lock 2
Thread B : waits for lock 1
Thread A : waits for lock 2

Exemplo de Java para um livelock:


import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class LivelockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(LivelockSample::doA, "Thread A");
        Thread threadB = new Thread(LivelockSample::doB, "Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        try {
            while (!lock1.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                while (!lock2.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 2");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
                } finally {
                    lock2.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
                }
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }

    public static void doB() {
        try {
            while (!lock2.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                while (!lock1.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 1");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
                } finally {
                    lock1.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
                }
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }
}

Saída de amostra:

Thread B : holds lock 2
Thread A : holds lock 1
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
...

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.

mmirwaldt
fonte
O código é legal. Mas o exemplo de bloqueio ao vivo não é bom. Se um encadeamento está bloqueado em um valor ou está pesquisando uma alteração no valor, não é conceitualmente diferente. Uma mudança fácil para melhor ilustrar um bloqueio ativo é fazer com que os encadeamentos A e B liberem os bloqueios que possuem quando percebem que não podem obter o segundo bloqueio necessário. Então eles dormem por um segundo cada, recuperam o bloqueio que tinham originalmente, depois dormem por mais um segundo e tentam adquirir o outro bloqueio novamente. Portanto, o ciclo para cada um seria: 1) adquirir-mina, 2) dormir, 3) tentar adquirir outra e falhar, 4) liberar-mina, 5) dormir, 6) Repita.
CognizantApe
1
Duvido que os bloqueios ao vivo que você pensa realmente existam o suficiente para causar problemas. Quando você sempre desiste de todos os bloqueios em espera quando não pode alocar o próximo bloqueio, a condição de bloqueio (e bloqueio em tempo real) "espera e espera" está ausente porque na verdade não há mais espera. ( pt.wikipedia.org/wiki/Deadlock )
mmirwaldt
na verdade, a condição de bloqueio morto está faltando, porque são bloqueios ativos que estamos discutindo. O exemplo que dei é semelhante ao exemplo de corredor padrão: geeksforgeeks.org/deadlock-starvation-and-livelock , en.wikibooks.org/wiki/Operating_System_Design/Concurrency/… , docs.oracle.com/javase/tutorial/essential / simultaneidade /…
CognizantApe
0

Imagine que você tenha o segmento A e o segmento B. Ambos estão synchronisedno mesmo objeto e, dentro desse bloco, há uma variável global que eles estão atualizando;

static boolean commonVar = false;
Object lock = new Object;

...

void threadAMethod(){
    ...
    while(commonVar == false){
         synchornized(lock){
              ...
              commonVar = true
         }
    }
}

void threadBMethod(){
    ...
    while(commonVar == true){
         synchornized(lock){
              ...
              commonVar = false
         }
    }
}

Portanto, quando o segmento A entra no whileloop e mantém a trava, ele faz o que tem que fazer e define commonVarcomo true. Então a linha B entra, entra no whileloop e, como commonVaré trueagora, é capaz de segurar a trava. Faz isso, executa o synchronisedbloco e commonVarvolta para false. Agora, o thread A novamente obtém sua nova janela da CPU, estava prestes a sair do whileloop, mas o thread B acabou de configurá-lo novamente para falseque 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 synchronisedbloco terminar de executar. Na maioria das vezes, acho que é uma expectativa difícil de atingir e depende de muitas coisas acontecendo sob o capô.

stdout
fonte
Belo exemplo. Também ilustra por que você deve sempre ler e escrever atomicamente em um contexto simultâneo. Se os loops while estivessem dentro dos blocos de sincronização, os itens acima não seriam um problema.
CognizantApe 30/04