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

pthreads

Question

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

Answer 1

Con referencia: http://operatingsystemgeeks.blogspot.in/ Ejemplo de interbloqueo: se aplica la condición de exclusión mutua, ya que solo un vehículo puede estar en una sección de la calle a la vez. Se aplica la condición de espera y espera, ya que cada vehículo está ocupando una sección de la calle y esperando para pasar a la siguiente sección de la calle. No se aplica ninguna condición preventiva, ya que una sección de la calle que es una sección de la calle que está ocupada por un vehículo no se puede quitar de ella. Se aplica la condición de espera circular, ya que cada vehículo está esperando al próximo vehículo para moverse. Es decir, cada vehículo en el tráfico está esperando una sección de la calle que está sujeta el siguiente vehículo en el tráfico.

Answer 2

Tal vez estos dos ejemplos ilustran la diferencia entre un interbloqueo y un bloqueo vital:

Java-Ejemplo para un interbloqueo:

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

Java-Ejemplo 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 los bloqueos en diferentes órdenes. Mientras que el interbloqueo espera el otro bloqueo, el bloqueo vital no espera realmente, intenta desesperadamente adquirir el bloqueo sin la posibilidad de obtenerlo. Cada intento consume ciclos de CPU.

Answer 3

Todo el contenido y ejemplos aquí son de

Sistemas operativos: internos y principios de diseño
William Stallings
8ª edición

Interbloqueo : 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. Supongamos 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á a la espera de uno de los dos recursos. Tampoco 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 bloqueados

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

Hambre : una situación en la que el programador pasa por alto indefinidamente un proceso ejecutable; Aunque es capaz de proceder, nunca se elige.

Supongamos que tres procesos (P1, P2, P3) requieren un 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 se retrasan, esperando ese recurso. Cuando P1 sale de su sección crítica, se debe permitir el acceso a P2 o P3 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 otorga acceso a P1 después de que P3 finalice, y posteriormente otorga acceso alternativamente a P1 y P3, entonces a P2 se le puede negar el acceso al recurso de manera indefinida, aunque no haya una situación de interbloqueo.

APÉNDICE A - TEMAS DE CONCURRENCIA

Ejemplo de punto muerto

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

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

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

Ejemplo de Livelock

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

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

[...] considera la siguiente secuencia de eventos:

• P0 establece la bandera [0] en verdadero.
• P1 establece la bandera [1] en verdadero.
• P0 marca la bandera [1].
• P1 marca la bandera [0].
• P0 establece la bandera [0] en falso.
• P1 establece la bandera [1] en falso.
• P0 establece la bandera [0] en verdadero.
• P1 establece la bandera [1] en verdadero.

Esta secuencia podría extenderse indefinidamente y ninguno de los procesos podría ingresar a 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 interrumpirá este ciclo y permitirá que uno entre en la sección crítica. Esta condición se conoce como Livelock . Recuerde que el interbloqueo 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.

Answer 4

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 está esperando 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 uno con respecto al otro, y ninguno avanza. Livelock es un caso especial de hambre 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 estrecho corredor, y cada una trata de ser cortés apartándose para dejar pasar a la otra, pero terminan meciéndose de lado a lado sin hacer ningún progreso porque ambos se mueven repetidamente de la misma manera al mismo tiempo.

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

Answer 5

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, entonces puede resultar livelock.

Al igual que con el interbloqueo, los subprocesos bloqueados no pueden avanzar más . Sin embargo, los subprocesos no están bloqueados , simplemente están demasiado ocupados respondiéndose entre sí 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 a su derecha, mientras que Gaston se mueve a su izquierda. Todavía se están bloqueando, y así sucesivamente ...

La principal diferencia entre livelock y deadlock es que los hilos no se van a bloquear, sino que intentarán responder entre sí continuamente.

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 moverse más lejos.

Answer 6

DEADLOCK El interbloqueo es una condición en la cual una tarea espera indefinidamente por condiciones que nunca pueden cumplirse: la tarea reclama el control exclusivo sobre los recursos compartidos: la tarea retiene los recursos mientras se espera que se liberen otros recursos. existe condición

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