What is the livelock?

Question

The term deadlock is well known in concurrent programming, but I came across the term livelock in my studies, and I wondered what that might be?

What is livelock? And could you give some example (with code in any language, or pseudocode) of how it happens?

Answer 1

Second, free translation, this reply:

Taken from http://en.wikipedia.org/wiki/Deadlock :

In simultaneous computing, a deadlock is a state in which each member of a group of actions is waiting for another member to release a blockade

A livelock is similar to an impasse, except that the states of the processes involved in livelock constantly change one relative to the other, none progressing. Livelock is a special case of starvation of resources; the general definition states only that a specific process is not progressing.

A real example of livelock occurs when two people meet in a narrow corridor, and each tries to be educated by moving to the side to let the other pass, but they end up swinging on one side to the other without progressing, because both move repeatedly from the same way at the same time.

Livelock is a risk in some algorithms that detect and recover of a conflict. If more than one process executes an action, the algorithm deadlock detection can be triggered repeatedly. This can be avoided by ensuring that only one process (chosen at random or by priority) take measures.

An example to explain a livelock can be found in this link:

Imagine an example where two or more threads need to acquire all the Locks of an object, if the thread can’t get all the Locks then she tries again, this creates a livelock with all threads trying to get all the Ocks but none can because a disturbs the other.

Livelock can occur in a situation where there is a locking mechanism in a given program that have the resources shared, A and B. If a T1 thread requires lock over A and a T2 requires lock on B simultaneously. After that T1 attempts to access B and T2 tries to access A concomitantly, T1 and T2 go to a Sleep state, when they wake up, they return to search for the target resource, which will continue with lock in both situations. Given situation is constituted a livelock .

An example in Java can be extracted from reply of this question Good example of livelock?: (I recommend reading the comments of the reply)

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();
    }
}