Interbloqueo, inanición y Livelock

Requisito previo: punto muerto y hambre 

Livelock ocurre cuando dos o más procesos repiten continuamente la misma interacción en respuesta a cambios en los otros procesos sin realizar ningún trabajo útil. Estos procesos no están en estado de espera y se ejecutan simultáneamente. Esto es diferente de un interbloqueo porque en un interbloqueo todos los procesos están en estado de espera. 

 

 Ejemplo: imagine un par de procesos que utilizan dos recursos, como se muestra: 

void process_A(void)
{
    enter_reg(& resource_1);
    enter_reg(& resource_2);
    use_both_resources();
    leave_reg(& resource_2);
    leave_reg(& resource_1);
}
void process_B(void)
{
    enter_reg(& resource_1);
    enter_reg(& resource_2);
    use_both_resources();
    leave_reg(& resource_2);
    leave_reg(& resource_1);
}

Cada uno de los dos procesos necesita los dos recursos y utilizan la primitiva de sondeo enter_reg para intentar adquirir los bloqueos necesarios para ellos. En caso de que el intento falle, el proceso vuelve a intentarlo. Si el proceso A se ejecuta primero y adquiere el recurso 1 y luego el proceso B se ejecuta y adquiere el recurso 2, no importa cuál se ejecute a continuación, no avanzará más, pero ninguno de los dos procesos se bloquea. Lo que realmente sucede es que usa su cantidad de CPU una y otra vez sin ningún progreso pero también sin ningún tipo de bloqueo. Por lo tanto, esta situación no es la de un interbloqueo (ya que no se bloquea ningún proceso), pero tenemos algo funcionalmente equivalente a un interbloqueo: LIVELOCK. 

¿Qué lleva a Livelocks? 

La aparición de livelocks puede ocurrir de las formas más sorprendentes. El número total de procesos permitidos en algunos sistemas está determinado por el número de entradas en la tabla de procesos. Por lo tanto, las ranuras de la tabla de procesos pueden denominarse recursos finitos. Si una bifurcación falla debido a que la mesa está llena, esperar un tiempo aleatorio e intentarlo de nuevo sería un enfoque razonable para el programa que realiza la bifurcación. Considere un sistema UNIX que tiene 100 ranuras de proceso. Se están ejecutando diez programas, cada uno de los cuales tiene que crear 12 (sub)procesos. Después de que cada proceso haya creado 9 procesos, los 10 procesos originales y los 90 procesos nuevos han agotado la tabla. Cada uno de los 10 procesos originales ahora se encuentra en un bucle sin fin que se bifurca y falla, que es acertadamente la situación de un punto muerto. La probabilidad de que esto ocurra es muy pequeña pero podría ocurrir. 

Diferencia entre Deadlock, Starvation y Livelock: 

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

Livelock: 

var l1 = .... // lock object like semaphore or mutex etc
var l2 = .... // lock object like semaphore or mutex etc
     
        // Thread1
        Thread.Start( ()=> {
             
    while (true) {
         
        if (!l1.Lock(1000)) {
            continue;
        }
         
        if (!l2.Lock(1000)) {
            continue;
        }
         
        /// do some work
    });
 
        // Thread2
        Thread.Start( ()=> {
             
        while (true) {
             
            if (!l2.Lock(1000)) {
                continue;
            }
             
            if (!l1.Lock(1000)) {
                continue;
            }
             
            // do some work
        });

Punto muerto: 

var p = new object();
lock(p)
{
    lock(p)
    {
        // deadlock. Since p is previously locked
        // we will never reach here...
    }

Un interbloqueo 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 , por otro lado, es casi similar a un deadlock, excepto que los estados de los procesos involucrados en un livelock cambian constantemente entre sí, sin progresar. Por lo tanto, Livelock es un caso especial de escasez de recursos, como se indica en la definición general, el proceso no avanza. 

Inanición: 

El hambre es un problema que está estrechamente relacionado con Livelock y Deadlock. En un sistema dinámico, las requests de recursos continúan ocurriendo. Por lo tanto, se necesita alguna política para tomar una decisión sobre quién obtiene el recurso y cuándo este proceso, siendo razonable, puede llevar a que algunos procesos nunca se atiendan aunque no estén bloqueados. 

Queue q = .....
 
          while (q.Count & gt; 0)
{
    var c = q.Dequeue();
    .........
 
        // Some method in different thread accidentally
        // puts c back in queue twice within same time frame
        q.Enqueue(c);
    q.Enqueue(c);
 
    // leading to growth of queue twice then it
    // can consume, thus starving of computing
}

La inanición ocurre cuando los hilos «codiciosos» hacen que los recursos compartidos no estén disponibles durante largos períodos. Por ejemplo, suponga que un objeto proporciona un método sincronizado que, a menudo, tarda mucho en volver. Si un subproceso invoca este método con frecuencia, a menudo se bloquearán otros subprocesos que también necesitan acceso sincronizado frecuente al mismo objeto.