¿Cuál es la diferencia entre deadlock y livelock?

¿Alguien puede explicar con ejemplos (de código) cuál es la diferencia entre un punto muerto y un punto muerto ?

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

En la computación concurrente, un punto muerto es un estado en el que cada miembro de un grupo de acciones espera que algún otro miembro libere un bloqueo

Un livelock es similar a un punto muerto, excepto que los estados de los procesos involucrados en el livelock cambian constantemente entre sí, ninguno progresa. Livelock es un caso especial de inanición de recursos; la definición general solo establece que un proceso específico no está progresando.

Un ejemplo del mundo real de livelock ocurre cuando dos personas se encuentran en un pasillo estrecho, y cada una trata de ser cortés moviéndose a un lado para dejar pasar a la otra, pero terminan balanceándose de lado a lado sin progresar porque ambas se mueven repetidamente de la misma manera al mismo tiempo.

Livelock es un riesgo con algunos algoritmos que detectan y se recuperan del punto muerto. Si más de un proceso toma medidas, el algoritmo de detección de punto muerto se puede activar repetidamente. Esto puede evitarse asegurando que solo un proceso (elegido al azar o por prioridad) tome medidas.

Livelock

Un hilo a menudo actúa en respuesta a la acción de otro hilo. Si la acción del otro subproceso también es una respuesta a la acción de otro subproceso, puede resultar en livelock.

Al igual que con el punto muerto, los subprocesos en vivo no pueden avanzar más . Sin embargo, los hilos no están bloqueados , simplemente están demasiado ocupados respondiéndose unos a otros para reanudar el trabajo . Esto es comparable a dos personas que intentan cruzarse en un corredor: Alphonse se mueve a su izquierda para dejar pasar a Gaston, mientras que Gaston se mueve a su derecha para dejar pasar a Alphonse. Al ver que todavía se están bloqueando, Alphonse se mueve hacia su derecha, mientras que Gastón se mueve hacia su izquierda. Todavía se están bloqueando, y así sucesivamente ...

La principal diferencia entre livelock y deadlock es que los hilos no se bloquearán, sino que intentarán responderse entre sí de manera continua.

En esta imagen, ambos círculos (hilos o procesos) intentarán dar espacio al otro moviéndose hacia la izquierda y hacia la derecha. Pero no pueden avanzar más.

Todo el contenido y ejemplos aquí son de

Sistemas operativos: principios internos y principios de diseño
William Stallings
8º Edición

Punto muerto : una situación en la que dos o más procesos no pueden continuar porque cada uno está esperando que el otro haga algo.

Por ejemplo, considere dos procesos, P1 y P2, y dos recursos, R1 y R2. Suponga que cada proceso necesita acceso a ambos recursos para realizar parte de su función. Entonces es posible tener la siguiente situación: el sistema operativo asigna R1 a P2 y R2 a P1. Cada proceso está esperando uno de los dos recursos. Ninguno de los dos liberará el recurso que ya posee hasta que haya adquirido el otro recurso y haya realizado la función que requiere ambos recursos. Los dos procesos están estancados

Livelock : una situación en la que dos o más procesos cambian continuamente sus estados en respuesta a cambios en los otros procesos sin realizar ningún trabajo útil:

Inanición : una situación en la que el planificador pasa por alto indefinidamente un proceso ejecutable; aunque puede continuar, nunca se elige.

Suponga que tres procesos (P1, P2, P3) requieren acceso periódico al recurso R. Considere la situación en la que P1 está en posesión del recurso, y tanto P2 como P3 están retrasados, esperando ese recurso. Cuando P1 sale de su sección crítica, P2 o P3 deberían tener acceso a R. Suponga que el sistema operativo otorga acceso a P3 y que P1 nuevamente requiere acceso antes de que P3 complete su sección crítica. Si el sistema operativo concede acceso a P1 después de que P3 haya finalizado y, posteriormente, concede acceso alternativamente a P1 y P3, entonces a P2 se le puede denegar indefinidamente el acceso al recurso, aunque no haya una situación de punto muerto.

APÉNDICE A - TEMAS EN CONCURRENCIA

Ejemplo de punto muerto

Si ambos procesos establecen sus banderas en verdadero antes de que cualquiera haya ejecutado la instrucción while, entonces cada uno pensará que el otro ha entrado en su sección crítica, causando un punto muerto.

/* 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;

Ejemplo 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 la siguiente secuencia de eventos:

• P0 establece el indicador [0] en verdadero.
• P1 establece el indicador [1] en verdadero.
• P0 comprueba la bandera [1].
• P1 comprueba la bandera [0].
• P0 establece el indicador [0] en falso.
• P1 establece el indicador [1] en falso.
• P0 establece el indicador [0] en verdadero.
• P1 establece el indicador [1] en verdadero.

Esta secuencia podría extenderse indefinidamente, y ninguno de los procesos podría entrar en su sección crítica. Estrictamente hablando, esto no es un punto muerto , porque cualquier alteración en la velocidad relativa de los dos procesos romperá este ciclo y permitirá que uno entre en la sección crítica. Esta condición se conoce como livelock . Recuerde que el punto muerto se produce cuando un conjunto de procesos desea ingresar a sus secciones críticas pero ningún proceso puede tener éxito. Con livelock , hay posibles secuencias de ejecuciones que tienen éxito, pero también es posible describir una o más secuencias de ejecución en las que ningún proceso ingresa a su sección crítica.

Ya no es contenido del libro.

¿Y qué hay de los spinlocks?

Spinlock es una técnica para evitar el costo del mecanismo de bloqueo del sistema operativo. Por lo general, harías:

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

Un problema comienza a aparecer cuando beginLock()cuesta mucho más que doSomething(). En términos muy exagerados, imagine lo que sucede cuando beginLockcuesta 1 segundo, pero doSomethingcuesta solo 1 milisegundo.

En este caso, si esperaba 1 milisegundo, evitaría verse obstaculizado durante 1 segundo.

¿Por qué beginLockcostaría tanto? Si el bloqueo es gratuito, no cuesta mucho (consulte https://stackoverflow.com/a/49712993/5397116 ), pero si el bloqueo no es gratuito, el sistema operativo "congelará" su hilo, configure un mecanismo para despertarlo cuando se libera la cerradura y luego te despierta nuevamente en el futuro.

Todo esto es mucho más costoso que algunos bucles que controlan la cerradura. Es por eso que a veces es mejor hacer un "spinlock".

Por ejemplo:

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

Si su implementación no es cuidadosa, puede caer en livelock, gastando toda la CPU en el mecanismo de bloqueo.

Ver también:

https://preshing.com/20120226/roll-your-own-lightweight-mutex/
¿Es correcta y óptima mi implementación de bloqueo de giro?

Resumen :

Punto muerto : situación en la que nadie progresa, no hace nada (dormir, esperar, etc.). El uso de la CPU será bajo;

Livelock : situación en la que nadie progresa, pero la CPU se gasta en el mecanismo de bloqueo y no en su cálculo;

Inanición: situación en la que un procress nunca tiene la oportunidad de correr; por pura mala suerte o por alguna de sus propiedades (baja prioridad, por ejemplo);

Spinlock : técnica para evitar el costo esperando que se libere el bloqueo.

DEADLOCK Deadlock es una condición en la que una tarea espera indefinidamente condiciones que nunca pueden satisfacerse: la tarea reclama el control exclusivo sobre los recursos compartidos - la tarea retiene recursos mientras espera que se liberen otros recursos - las tareas no pueden ser forzadas a reponer los recursos - una espera circular condición existe

Las condiciones de Livelock de LIVELOCK pueden surgir cuando dos o más tareas dependen y usan algún recurso que causa una condición de dependencia circular donde esas tareas continúan ejecutándose para siempre, bloqueando así todas las tareas de menor nivel de prioridad (estas tareas de menor prioridad experimentan una condición llamada inanición)

Quizás estos dos ejemplos ilustran la diferencia entre un punto muerto y un punto muerto:

Ejemplo Java para un punto muerto:

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

Salida de muestra:

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

Ejemplo Java para un 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
        }
    }
}

Salida de muestra:

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 ejemplos obligan a los hilos a adquirir las cerraduras en diferentes órdenes. Mientras que el punto muerto espera la otra cerradura, el livelock no espera realmente, intenta desesperadamente adquirir la cerradura sin la posibilidad de obtenerla. Cada intento consume ciclos de CPU.

Imagine que tiene el hilo A y el hilo B. Ambos están synchroniseden el mismo objeto y dentro de este bloque hay una variable global que ambos están actualizando;

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

Así, cuando el hilo A entra en el whilebucle y mantiene el bloqueo, que hace lo que tiene que hacer y establecer el commonVara true. Luego, el hilo B entra, entra en el whilebucle y, como commonVares trueahora, puede mantener el bloqueo. Lo hace, ejecuta el synchronisedbloque y commonVarvuelve a establecer false. Ahora, el subproceso A vuelve a tener su nueva ventana de CPU, estaba a punto de abandonar el whilebucle, pero el subproceso B acaba de restablecerlo false, por lo que el ciclo se repite nuevamente. Los subprocesos hacen algo (por lo que no están bloqueados en el sentido tradicional) sino por casi nada.

Quizás también sea bueno mencionar que livelock no necesariamente tiene que aparecer aquí. Supongo que el planificador favorece al otro hilo una vez que el synchronisedbloque termina de ejecutarse. La mayoría de las veces, creo que es una expectativa difícil de alcanzar y depende de muchas cosas que suceden bajo el capó.