4

O termo deadlock é bem conhecido na programação concorrente, porém acabei me deparando com o termo livelock nos meus estudos, e me perguntei o que seria isso?

O que é livelock? E poderia dar algum exemplo (com código em qualquer linguagem, ou pseudocódigo) de como isso acontece?

1 Resposta 1

2

Segundo, tradução livre, esta resposta:

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 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.

Um exemplo para explicar um livelock pode ser encontrado neste link:

Imagine um exemplo em que duas ou mais threads precisam adquirir todas as Locks de um objeto, se a thread não conseguir obter todas as locks então ela tenta de novo, isso cria um livelock com todas as threads tentando obter todos os locks mas nenhuma consegue porque uma atrapalha a outra.

LiveLock pode ocorrer numa situação onde há um mecanismo de travas em um dado programa que tenham dos recursos compartilhados, A e B. Se uma thread T1 requer lock sobre A e um T2 requer lock sobre B simultaneamente. Após isso T1 tenta acessar B e T2 tenta acessar A concomitantemente, T1 e T2 vão para um estado sleep, quando acordam, voltam a buscar pelo recurso alvo, que continuará com lock em ambas situações. Dada situação está constituído um livelock .

Um exemplo em Java pode ser extraído da resposta desta pergunta Good example of livelock?: (Recomendo a leitura dos comentários da resposta)

public class Livelock {
    static class Colher {
        private Cliente dono;
        public Colher(Cliente c) { dono = c; }
        public Cliente getDono() { return dono; }
        public synchronized void setDono(Cliente c) { dono = c; }
        public synchronized void usar() { 
            System.out.printf("%s comeu!", dono.nome); 
        }
    }

    static class Cliente {
        private String nome;
        private boolean comFome;

        public Cliente(String n) { nome = n; comFome = true; }      
        public String getNome() { return nome; }
        public boolean isComFome() { return comFome; }

        public void comerCom(Colher colher, Cliente conjuge) {
            while (comFome) {
                // Não tem a colher, então espera pacientemente pelo conjuge.
                if (colher.dono != this) {
                    try { Thread.sleep(1); } 
                    catch(InterruptedException e) { continue; }
                    continue;
                }                       

                // Se o conjuge está com fome, insista em passar a colher.
                if (conjuge.isComFome()) {                  
                    System.out.printf(
                        "%s: Você come primeiro %s!%n", 
                        nome, conjuge.getNome());
                    colher.setDono(conjuge);
                    continue;
                }

                // Conjuge não está com fome, então coma usando a colher.
                colher.usar();
                comFome = false;                
                System.out.printf(
                    "%s: Estou cheio, %s!%n", 
                    nome, conjuge.getNome());               
                colher.setDono(conjuge);
            }
        }
    }

    public static void main(String[] args) {
        final Cliente marido = new Cliente("Bob");
        final Cliente esposa = new Cliente("Alice");

        final Colher colher = new Colher(marido);

        new Thread(() -> marido.comerCom(colher, esposa)).start();

        new Thread(() -> esposa.comerCom(colher, marido)).start();
    }
}
0

Você deve fazer log-in para responder a esta pergunta.