Livelock, inanición e inversión de prioridades

1. Livelock

Un livelock ocurre cuando dos o más hilos están activos (no bloqueados) pero no progresan. A diferencia del deadlock, donde los hilos están bloqueados, en el livelock los hilos están ejecutándose pero no avanzan hacia la solución.

El livelock es como dos personas que se encuentran en un pasillo estrecho y, para dejar pasar al otro, se mueven al mismo lado. Ambos están activos (se mueven), pero no progresan (no pasan).

El livelock es más difícil de detectar que el deadlock porque los hilos están activos (consumen CPU) y no están bloqueados. Las herramientas de detección de deadlock no lo detectan.

2. Un ejemplo de livelock

Dos hilos que intentan adquirir dos locks, pero ceden el lock si el otro lo tiene:

pthread_mutex_t lock_a, lock_b;

void *hilo_1(void *arg) {
    while (1) {
        pthread_mutex_lock(&lock_a);
        if (pthread_mutex_trylock(&lock_b) == 0) {
            /* Tiene ambos locks. */
            pthread_mutex_unlock(&lock_b);
            pthread_mutex_unlock(&lock_a);
            break;
        }
        /* No pudo adquirir lock_b: ceder lock_a. */
        pthread_mutex_unlock(&lock_a);
        /* Reintentar. */
    }
    return NULL;
}

void *hilo_2(void *arg) {
    while (1) {
        pthread_mutex_lock(&lock_b);
        if (pthread_mutex_trylock(&lock_a) == 0) {
            /* Tiene ambos locks. */
            pthread_mutex_unlock(&lock_a);
            pthread_mutex_unlock(&lock_b);
            break;
        }
        /* No pudo adquirir lock_a: ceder lock_b. */
        pthread_mutex_unlock(&lock_b);
        /* Reintentar. */
    }
    return NULL;
}

Los dos hilos adquieren su primer lock, intentan adquirir el segundo, fallan, ceden el primero y reintentan. Si ambos ceden al mismo tiempo, se vuelven a bloquear mutuamente. Esto puede repetirse indefinidamente: livelock.

3. Inanición

La inanición (starvation) ocurre cuando un hilo espera indefinidamente porque otros hilos siempre tienen prioridad sobre él. A diferencia del deadlock, los demás hilos progresan; solo el hilo de baja prioridad no.

La inanición se estudia en detalle en el tema 18 (bloque 5). Aquí la mencionamos porque es un fallo de vivacidad que no es un deadlock.

La inanición puede ocurrir en:

• Planificación por prioridades: un hilo de baja prioridad espera indefinidamente.
• Lectores-escritores: los escritores esperan indefinidamente si siempre hay lectores.
• Semáforos: si los hilos se despiertan en orden LIFO en lugar de FIFO.

4. Inversión de prioridades

La inversión de prioridades (priority inversion) ocurre cuando un hilo de alta prioridad se bloquea esperando un recurso que tiene un hilo de baja prioridad. El hilo de alta prioridad no puede ejecutarse hasta que el de baja prioridad libere el recurso, pero el de baja prioridad no puede ejecutarse porque hay hilos de prioridad media en la CPU.

La inversión de prioridades es un problema de vivacidad: el hilo de alta prioridad no progresa, aunque no esté en un deadlock.

Este problema es famoso porque causó el fallo de la misión Mars Pathfinder en 1997: un hilo de alta prioridad se bloqueó esperando un mutex que tenía un hilo de baja prioridad, y un hilo de prioridad media se ejecutó indefinidamente, causando que el sistema se reiniciara.

5. Un ejemplo de inversión

Tres hilos con prioridades distintas y un mutex compartido:

Secuencia:

1. t = 0: L adquiere M. adquirir
2. t = 1: H llega, necesita M. H se bloquea. L sigue ejecutándose. bloquear
3. t = 2: M llega. M preempta a L (prioridad 50 > 10). L deja de ejecutarse (no libera M). preemptar
4. t = 2 a 10: M se ejecuta. L no se ejecuta. H sigue bloqueado. bloqueo
5. t = 10: M termina. L se ejecuta y libera M. H se desbloquea y se ejecuta. liberar

H (prioridad 90) esperó 9 unidades porque M (prioridad 50) se ejecutó antes que L (prioridad 10). La prioridad de H fue «invertida».

6. Herencia de prioridad

La herencia de prioridad (priority inheritance) es una solución a la inversión de prioridades: cuando un hilo de alta prioridad se bloquea esperando un mutex que tiene un hilo de baja prioridad, el hilo de baja prioridad hereda la prioridad del hilo de alta prioridad.

Con herencia de prioridad, en el ejemplo anterior:

1. t = 0: L adquiere M con prioridad 10. adquirir
2. t = 1: H llega, necesita M. H se bloquea. L hereda la prioridad de H (90). heredar
3. t = 2: M llega. M tiene prioridad 50 < L (90, heredada). M no preempta a L. L sigue ejecutándose. no preemptar
4. t = 3: L libera M. L vuelve a prioridad 10. H se desbloquea y se ejecuta. liberar

Con herencia, H espera solo 2 unidades en lugar de 9. La inversión se evita.

Linux implementa la herencia de prioridad en mutexes con PTHREAD_PRIO_INHERIT (en pthreads) y en futexes con prioridad heredada en el núcleo.

7. Techo de prioridad

El techo de prioridad (priority ceiling) es otra solución: cuando un hilo adquiere un mutex, su prioridad se eleva al techo (la prioridad más alta de todos los hilos que pueden usar ese mutex). Esto previene la inversión antes de que ocurra.

Ventajas del techo de prioridad:

• Previene la inversión antes de que ocurra: no espera a que un hilo de alta prioridad se bloquee.
• Previene deadlocks: si los techos están bien definidos, no puede haber deadlocks por inversión.

Desventajas:

• Requiere conocer las prioridades: de todos los hilos que usan el mutex.
• Puede elevar la prioridad innecesariamente: un hilo de baja prioridad que adquiere un mutex se ejecuta con alta prioridad, incluso si no hay hilos de alta prioridad esperando.

8. Comparación

9. Simulador interactivo

Este simulador muestra la inversión de prioridades y cómo la herencia la resuelve:

10. Resumen

• El livelock es cuando los hilos están activos pero no progresan.
• La inanición es cuando un hilo espera indefinidamente por prioridad injusta.
• La inversión de prioridades ocurre cuando un hilo de alta prioridad se bloquea por un recurso de baja prioridad.
• La herencia de prioridad eleva la prioridad del hilo que tiene el recurso.
• El techo de prioridad eleva la prioridad al adquirir el recurso.
• Linux implementa herencia de prioridad en mutexes y futexes.
• La inversión de prioridades causó el fallo de Mars Pathfinder en 1997.

11. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Escribe un programa que demuestre la inversión de prioridades.
2. Implementa la herencia de prioridad con pthreads.
3. Compara la herencia con el techo de prioridad.
4. Investiga el caso de Mars Pathfinder.
5. Diseña un livelock y verifica que los hilos están activos pero no progresan.
6. Explica por qué el livelock es más difícil de detectar que el deadlock.