Cuchillos y tablas: interbloqueo

Quinta noche, once en punto. La cocina está extrañamente silenciosa. Minho tiene el cuchillo en la mano y no le quita ojo a la tabla; Sua abraza la tabla y mira fijamente el cuchillo. Los dos repiten lo mismo: «Lo uso yo primero y luego te lo paso».

El señor Tak deja de picar cebolleta y murmura: «Con los dos ahí plantados, aquí no termina nadie».

La chef Yoon Seoyeon detiene el temporizador que lleva colgado al cuello. «Los dos, a soltar. Esto no ha pasado porque alguien sea lento. Ha pasado porque no hay reglas».

5-1. Dos cocineros que se esperan el uno al otro (7 min)

Igual que los fogones de anoche, el cuchillo y la tabla son cerrojos: solo una persona puede usarlos a la vez. Minho los toma en el orden cuchillo → tabla; Sua, en el orden tabla → cuchillo.

import threading
import time

knife = threading.Lock()
board = threading.Lock()

def minho():
    with knife:              # toma el cuchillo
        time.sleep(0.1)
        with board:          # espera la tabla
            print("minho done")

def sua():
    with board:              # toma la tabla
        time.sleep(0.1)
        with knife:          # espera el cuchillo
            print("sua done")

a = threading.Thread(target=minho, daemon=True)
b = threading.Thread(target=sua, daemon=True)
a.start(); b.start()
a.join(timeout=1); b.join(timeout=1)
print("alive:", a.is_alive(), b.is_alive())
# alive: True True

• Después de esperar un segundo, los dos hilos siguen vivos. No están trabajando: están parados, cada uno esperando a que el otro suelte lo suyo. Eso es un interbloqueo (deadlock).
• join(timeout=1) espera como mucho un segundo y vuelve. Como los hilos son daemon=True, el programa termina sin más. Cuando experimentes con interbloqueos, déjate siempre una salida como esta.
• time.sleep(0.1) es un truco para que los dos tomen su primera herramienta casi a la vez. En un programa real ese hueco aparece muy de vez en cuando, y el interbloqueo se convierte en un bug aún más retorcido: uno que solo pasa «a veces».

Para que el propio programa se dé cuenta de que se ha atascado, usa acquire(timeout=...). Devuelve True si consigue el cerrojo y False si no lo consigue a tiempo. A with lock: no se le puede poner límite de tiempo, así que en este caso llamas tú a acquire y release.

knife = threading.Lock()   # cuchillo y tabla nuevos
board = threading.Lock()

def cook(name, first, second, patience):
    with first:
        time.sleep(0.1)
        if second.acquire(timeout=patience):   # espera como mucho patience segundos
            second.release()
            print(name, "done")
        else:
            print(name, f"gave up after {patience}s")

a = threading.Thread(target=cook, args=("minho", knife, board, 1.0))
b = threading.Thread(target=cook, args=("sua", board, knife, 0.5))
a.start(); b.start()
a.join(); b.join()
# sua gave up after 0.5s
# minho done

Sua se rinde a los 0,5 segundos y suelta la tabla; Minho, que seguía esperando, la toma y termina su plato. Basta con que uno ceda para que el interbloqueo se deshaga. El porqué lo explican las cuatro condiciones de la siguiente sección.

5-2. Las cuatro condiciones del interbloqueo (8 min)

Un interbloqueo solo se produce cuando se cumplen las cuatro condiciones a la vez. Dicho al revés: si rompes una sola, el interbloqueo no puede ocurrir.

• La exclusión mutua es la razón de ser de un cerrojo, así que normalmente no se rompe. Si hubiera cuchillos de sobra, no haría falta cerrar nada.
• Lo más habitual en la práctica es romper la espera circular. Si todos toman en el mismo orden, no se puede formar un círculo.
• Lo siguiente es romper a la vez la retención y espera y la falta de expropiación: si no consigues el segundo en cierto tiempo, sueltas tú mismo lo que tenías.

5-3. Solución 1: todos toman en el mismo orden (8 min)

La chef escribe una regla en la pizarra: «Cada herramienta lleva un número. Cuchillo, 1; tabla, 2. Siempre se toma primero el número menor».

Si tanto Minho como Sua empiezan por el cuchillo, solo quien tiene el cuchillo espera la tabla. Quien no ha conseguido el cuchillo espera sin tener nada en la mano, así que no se forma ningún círculo. No dejemos la regla en la memoria de las personas: metámosla en una función.

from contextlib import contextmanager

KNIFE = (1, threading.Lock())   # (número, cerrojo)
BOARD = (2, threading.Lock())

@contextmanager
def hold(*tools):
    ordered = sorted(tools, key=lambda t: t[0])   # del número menor al mayor
    for _, lock in ordered:
        lock.acquire()
    try:
        yield
    finally:
        for _, lock in reversed(ordered):        # al soltar, al revés
            lock.release()

done = []

def minho():
    for _ in range(100):
        with hold(KNIFE, BOARD):
            time.sleep(0)
    done.append("minho")

def sua():
    for _ in range(100):
        with hold(BOARD, KNIFE):     # se escriben en otro orden, pero se toman en el mismo
            time.sleep(0)
    done.append("sua")

ts = [threading.Thread(target=f, daemon=True) for f in (minho, sua)]
for t in ts: t.start()
for t in ts: t.join(timeout=2)
print(sorted(done), [t.is_alive() for t in ts])
# ['minho', 'sua'] [False, False]

• Aunque Sua escriba hold(BOARD, KNIFE), hold ordena por número, así que en realidad toma cuchillo → tabla.
• Los dos toman y sueltan 100 veces cada uno, alternándose, y no se atascan ni una vez. Da igual que time.sleep(0) les dé ocasión de cederse el turno.
• El número lo puedes asignar tú o, si solo se usa dentro del programa, puede ser cualquier valor que no se repita, como id(lock). Lo importante es que todo el código use el mismo criterio.
• El orden en que se sueltan no influye en el interbloqueo, pero acostumbrarte a soltar en orden inverso al de tomar hace el código más fácil de leer.

En cuanto haya un sitio que necesite dos o más cerrojos, deja esta regla por escrito en un comentario al principio del código o en la documentación. El día que llegue alguien nuevo, no conozca el orden y tome al revés, el interbloqueo volverá.

5-4. Solución 2: si no lo consigues, suelta (7 min)

A veces es difícil fijar un orden, por ejemplo cuando no sabes de antemano qué cerrojos vas a necesitar. Para esos casos se usa otra regla: «Si después de esperar un rato no lo consigues, suelta también lo que tienes y empieza de cero».

import random

tries = {}

def polite_cook(name, first, second):
    tries[name] = 0
    while True:
        tries[name] += 1
        with first:
            time.sleep(0.05)
            if second.acquire(timeout=0.1):     # si no lo consigue en 0.1 s
                try:
                    return                       # tiene los dos: plato terminado
                finally:
                    second.release()
        # al salir del with ha soltado first
        time.sleep(random.uniform(0, 0.1))       # descansa un rato al azar y lo vuelve a intentar

a = threading.Thread(target=polite_cook, args=("minho", knife, board))
b = threading.Thread(target=polite_cook, args=("sua", board, knife))
a.start(); b.start()
a.join(); b.join()
print(tries)
# p. ej.: {'minho': 2, 'sua': 3}  (cambia en cada ejecución)

Tras chocar unas cuantas veces, los dos acaban terminando. Pero si quitas random.uniform(0, 0.1), puede aparecer un problema nuevo: el bloqueo activo (livelock).

Es como dos personas que se cruzan en un pasillo y se apartan una y otra vez hacia el mismo lado. A diferencia del interbloqueo, los dos están muy ocupados, pero ninguno termina el plato. Si los descansos son aleatorios, alguien acaba moviéndose antes y el ciclo se rompe.

Con hilos de verdad, el momento exacto en que se ejecuta cada uno siempre baila un poco, así que es difícil reproducir un bloqueo activo cada vez con un ejemplo corto. Eso lo hace más peligroso: solo aparece los días de mucha carga. Cuando uses la solución 2, añade siempre el descanso aleatorio.

5-5. Cinco cocineros y cinco cuchillos (6 min)

En informática hay un problema famoso llamado el problema de la cena de los filósofos. Cinco personas se sientan a una mesa redonda, con un tenedor entre cada dos. Para comer, cada una necesita los dos tenedores que tiene a los lados. Llevado a la cocina: cinco cocineros alrededor de una encimera redonda y cinco cuchillos.

N = 5

def service(ordered):
    knives = [threading.Lock() for _ in range(N)]   # cinco cuchillos
    meals = [0] * N

    def cook(i):
        left, right = i, (i + 1) % N
        if ordered:
            first, second = min(left, right), max(left, right)
        else:
            first, second = left, right
        for _ in range(3):
            with knives[first]:
                time.sleep(0.05)          # un momento con el primer cuchillo en la mano
                with knives[second]:
                    meals[i] += 1

    ts = [threading.Thread(target=cook, args=(i,), daemon=True) for i in range(N)]
    for t in ts: t.start()
    for t in ts: t.join(timeout=1)
    return sum(t.is_alive() for t in ts), meals

print("left first:", service(ordered=False))
print("small first:", service(ordered=True))
# left first: (5, [0, 0, 0, 0, 0])
# small first: (0, [3, 3, 3, 3, 3])

• Todos empiezan por el cuchillo de la izquierda: si los cinco toman a la vez el de su izquierda, el de la derecha siempre está en la mano del vecino. Las esperas forman un círculo que da la vuelta a los cinco, y al cabo de un segundo los cinco hilos siguen parados.
• Primero el cuchillo de número menor: los cocineros 0 a 3 (en el código se cuenta desde 0) siguen empezando por la izquierda, pero el cocinero 4 pasa a empezar por la derecha (el cuchillo 0). Se rompe el único círculo, y todos terminan sus tres platos.

El banco de pruebas de abajo muestra esta situación paso a paso. Si metiéramos en un interbloqueo hilos de verdad del servidor, no habría forma de sacarlos, así que este banco, y solo este, funciona como una simulación. El número sobre cada cuchillo es el del cocinero que lo tiene.

• Todos toman primero el de la izquierda: en el primer paso los cinco toman un cuchillo cada uno y aparece el aviso rojo de interbloqueo. A partir de ahí, por mucho que pulses, nada cambia.
• Primero el cuchillo de número menor: el cocinero 5 intenta empezar por el cuchillo 1 y se queda esperando. Gracias a eso el cuchillo 5 queda libre, y el cocinero 4 empieza a cocinar en el segundo paso. Si activas la reproducción automática, los platos terminados van subiendo de forma pareja.
• Soltarlo si se atasca: los dos primeros pasos parecen un interbloqueo, y hasta sale el aviso. En el tercer paso, los cocineros que esperaban sueltan su cuchillo, y el cocinero 5 toma uno libre y se pone a cocinar. Piensa que, si todos soltaran y volvieran a tomar exactamente al mismo ritmo, podría acabar en un bloqueo activo.

5-6. Investigar una cocina parada: faulthandler (4 min)

Cuando el programa se ha quedado parado y no sabes dónde, te ayuda faulthandler, de la biblioteca estándar. Muestra en qué línea está ahora mismo cada hilo. Guarda el código de abajo como stuck.py y ejecútalo.

import faulthandler
import threading
import time

knife = threading.Lock()
board = threading.Lock()

def minho():
    with knife:
        time.sleep(0.1)
        with board:
            pass

def sua():
    with board:
        time.sleep(0.1)
        with knife:
            pass

faulthandler.dump_traceback_later(1)        # si 1 s después sigue aquí, muestra todos los hilos
crew = [threading.Thread(target=f, name=f.__name__, daemon=True) for f in (minho, sua)]
for t in crew: t.start()
for t in crew: t.join(timeout=2)
faulthandler.cancel_dump_traceback_later()  # si terminó a tiempo, anula el aviso programado

Timeout (0:00:01)!
Thread 0x00009560 [sua] (most recent call first):
  File "stuck.py", line 17 in sua
  ...
Thread 0x0000a670 [minho] (most recent call first):
  File "stuck.py", line 11 in minho
  ...

La salida está recortada (las direcciones y las rutas cambian en cada ejecución). Sua está parada en la línea 17, with knife:, y Minho en la línea 11, with board:. De un vistazo se ve quién espera qué.

• faulthandler.dump_traceback_later(timeout): programa que, al cabo de timeout segundos, se escriba en la salida de error estándar dónde está cada hilo. Con repeat=True se repite una y otra vez; con exit=True el programa termina después de escribirlo.
• faulthandler.dump_traceback(all_threads=True): lo escribe ahora mismo, sin programar nada. Sirve para echar un vistazo al estado en mitad de una tarea larga.
• Si un test se cuelga de vez en cuando, pon dump_traceback_later al principio del test. El día que se cuelgue, quedará constancia del culpable.

Cierre (10 min)

El objetivo de esta noche era que tres cocineros que comparten cuchillo y tabla cocinaran 100 veces cada uno sin atascarse ni una vez. El señor Tak usa además una sartén: tres herramientas. Si cada herramienta lleva un número y todos toman con hold, da igual en qué orden las escriba cada uno.

PAN = (3, threading.Lock())
meals = {}

def cook(name, *tools):
    for _ in range(100):
        with hold(*tools):            # siempre primero la herramienta de número menor
            time.sleep(0)
            meals[name] = meals.get(name, 0) + 1

crew = [threading.Thread(target=cook, args=a, daemon=True) for a in [
    ("minho", KNIFE, BOARD), ("sua", BOARD, KNIFE), ("tak", PAN, BOARD, KNIFE)]]
for t in crew: t.start()
for t in crew: t.join(timeout=3)
print([meals[n] for n in ("minho", "sua", "tak")], sum(t.is_alive() for t in crew))
# [100, 100, 100] 0

Los tres, 100 veces cada uno, y cero personas atascadas. La chef añade una línea junto a la regla de la pizarra: «Cuchillo 1, tabla 2, sartén 3. Primero el número menor».

«Hoy nos hemos atascado por las herramientas. Mañana nos atascaremos por las personas. Cuando lluevan los pedidos, ¿quién decide qué cocinero prepara cada uno?»

Ejercicios

1. En el primer ejemplo de 5-1, borra time.sleep(0.1) y ejecútalo varias veces. ¿Se produce el interbloqueo siempre? Explica en una frase por qué un «bug que solo se atasca a veces» es más peligroso.
2. En service de 5-5, comprueba con print que, con ordered=True, solo el cocinero 4 toma en otro orden. Explica con las cuatro condiciones por qué basta con que un solo cocinero cambie el orden para deshacer el interbloqueo.
3. En el banco de pruebas, elige «Soltarlo si se atasca», deja correr 24 pasos con la reproducción automática y compara los platos terminados con «Primero el cuchillo de número menor».