Ir al contenido
wannacode

Deadlock

En resumen: Un deadlock (interbloqueo) es un estado en el que dos hilos tienen cada uno un cerrojo y esperan el otro para siempre; un orden común de bloqueo lo hace imposible.

Problema

La noche en que se pararon los almacenes

La tienda tiene dos almacenes: Sofía y Plovdiv. Cuando a uno se le acaban los auriculares, un sistema traslada mercancía desde el otro. Cada traspaso bloquea los dos almacenes para que no se pierdan artículos, como en la lección sobre bloqueo.

Una noche a las 3:12 empiezan dos traspasos a la vez: 5 artículos de Sofía a Plovdiv y 3 de Plovdiv a Sofía. El programa se detiene. El procesador está al 0 %, no hay ningún error en el registro, y los hilos simplemente están ahí esperando. Hasta la mañana no pasa ni un traspaso, y los pedidos de los dos almacenes se acumulan.

En la lección sobre hilos viste lo mismo con la impresora y el escáner. Aquí verás por qué pasa y cómo hacerlo imposible.

La idea

Cada uno tiene uno y espera el otro

Un traspaso bloquea primero el almacén desde el que mueve, y luego el almacén al que mueve:

  • el traspaso 1 (Sofía → Plovdiv) toma el cerrojo de Sofía;
  • en el mismo momento el traspaso 2 (Plovdiv → Sofía) toma el cerrojo de Plovdiv;
  • el traspaso 1 quiere el cerrojo de Plovdiv: el traspaso 2 lo tiene, así que espera;
  • el traspaso 2 quiere el cerrojo de Sofía: el traspaso 1 lo tiene, así que espera.

Cada uno espera a que el otro suelte, y nadie suelta hasta conseguir lo que quiere. La espera forma un círculo. Esto es un deadlock: los hilos no cometen ningún error ni se caen, simplemente se detienen para siempre.

Lo peor es que pasa pocas veces. Los dos traspasos tienen que tomar su primer cerrojo casi en el mismo momento. Así que pasa mil veces en las pruebas y se detiene a las 3:12 de la noche.

Míralo

El círculo

def transfer(source, target, qty):
    # un orden común: primero el id menor
    first, second = sorted((source, target),
                           key=lambda w: w.id)
    with first.lock:
        with second.lock:
            source.stock -= qty
            target.stock += qty
Paso a paso, en palabras
  1. Dos traspasos a la vez. T1 mueve 5 artículos de Sofía a Plovdiv, T2 mueve 3 de vuelta. Cada uno bloquea primero el almacén del que toma.
  2. T1 toma el cerrojo de Sofía.
  3. En el mismo momento T2 toma el cerrojo de Plovdiv.
  4. La barrera los deja seguir solo cuando los dos tienen su primer cerrojo. Está aquí para que el mal momento ocurra en cada ejecución.
  5. T1 espera el cerrojo de Plovdiv, que tiene T2. T2 espera el cerrojo de Sofía, que tiene T1. Un círculo: nadie suelta.
  6. A los 200 ms los dos se rinden: deadlock. Sin el tiempo límite esperarían para siempre y el programa se colgaría. Existencias: 500 y 300.
  7. La solución: un orden para todos. Primero el cerrojo del almacén con el id menor: Sofía (1), luego Plovdiv (2), sea cual sea el sentido.
  8. Los dos empiezan por Sofía. T1 consigue el cerrojo; T2 espera, pero no tiene nada.
  9. T1 toma también Plovdiv, mueve 5 artículos y suelta los dos cerrojos.
  10. Ahora T2 toma Sofía, luego Plovdiv, y mueve 3 de vuelta.
  11. Los dos traspasos se completaron: 498 y 302. Con un solo orden nadie tiene un cerrojo mientras espera uno que tiene alguien que lo espera a él: no hay círculo.

Para que veas el mal momento en cada ejecución, el programa lo provoca a propósito. La barrera meet detiene cada traspaso hasta que los dos han llegado: así los dos ya tienen su primer cerrojo cuando quieren el segundo. La segunda barrera los retiene hasta que los dos lo han intentado. Sin ella, uno podría obtener el cerrojo que soltó el otro, y la salida dependería del momento.

El segundo cerrojo se espera con un tiempo límite: como máximo 200 ms. Si no llega, el traspaso se rinde y suelta el suyo.

with lock: espera para siempre. lock.acquire(timeout=0.2) espera como máximo 0,2 segundos y devuelve False si no lo consiguió, y release() suelta el cerrojo. threading.Barrier(2) deja pasar a los dos hilos en cuanto los dos han llamado a wait(), y se puede reutilizar.
class Warehouse:
    def __init__(self, id, name, stock):
        self.id = id
        self.name = name
        self.stock = stock
        self.lock = threading.Lock()
def transfer(source, target, qty, meet):
    with source.lock:
        meet.wait()  # cada uno tiene un cerrojo
        got = target.lock.acquire(timeout=0.2)
        meet.wait()  # los dos lo intentaron (solo para el ejemplo)
        if not got:
            return False  # esperó demasiado
        try:
            source.stock -= qty
            target.stock += qty
            return True
        finally:
            target.lock.release()
sofia = Warehouse(1, "Sofía", 500)
plovdiv = Warehouse(2, "Plovdiv", 300)
meet = threading.Barrier(2)
done = [None, None]




def run(k, source, target, qty):
    done[k] = transfer(source, target, qty, meet)




threads = [threading.Thread(target=run, args=(0, sofia, plovdiv, 5)),
           threading.Thread(target=run, args=(1, plovdiv, sofia, 3))]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print("deadlock: cada traspaso espera al otro" if not any(done) else "los dos traspasos se completaron")
print(f"{sofia.name}: {sofia.stock}, {plovdiv.name}: {plovdiv.stock}")
Salida
deadlock: cada traspaso espera al otro
Sofía: 500, Plovdiv: 300

Sin el tiempo límite el programa se colgaría y no imprimiría nada. El tiempo límite no arregla el deadlock, lo atrapa: el traspaso sabe que no pasó y puede reintentar o dar la alarma.

La idea

Un solo orden para todos

El círculo se cierra porque los dos traspasos bloquean en un orden distinto: uno Sofía y luego Plovdiv, el otro al revés. La solución es que todos bloqueen en el mismo orden, sea cual sea el sentido del traspaso. Por ejemplo, por el número del almacén: primero el id menor.

Entonces los dos traspasos empiezan por Sofía. El que consigue su cerrojo sigue hacia Plovdiv. El otro sigue esperando el primer cerrojo y no tiene nada, así que no bloquea a nadie. No puede cerrarse un círculo: cada uno espera solo un cerrojo con un id mayor que los que ya tiene.

def transfer(source, target, qty):
    # un orden común: primero el id menor
    first, second = sorted((source, target),
                           key=lambda w: w.id)
    with first.lock:
        with second.lock:
            source.stock -= qty
            target.stock += qty

Mil traspasos de 2 artículos en un sentido y mil de 1 en el otro, a la vez:

sofia = Warehouse(1, "Sofía", 5000)
plovdiv = Warehouse(2, "Plovdiv", 3000)




def many(source, target, qty):
    for _ in range(1000):
        transfer(source, target, qty)




threads = [threading.Thread(target=many, args=(sofia, plovdiv, 2)),
           threading.Thread(target=many, args=(plovdiv, sofia, 1))]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print(f"{sofia.name}: {sofia.stock}, {plovdiv.name}: {plovdiv.stock}")
print("Total:", sofia.stock + plovdiv.stock)
Salida
Sofía: 4000, Plovdiv: 4000
Total: 8000
sorted con key=lambda w: w.id ordena los dos almacenes por id: first es siempre el de id menor. with first.lock: y el with second.lock: anidado los bloquean en ese orden.

Las existencias son exactas en cada ejecución, y el total es 8000, como al principio. Los cerrojos protegen los artículos, y el orden evita que el programa se detenga.

Pruébalo

Predice la salida

Tres almacenes: Sofía (1), Plovdiv (2), Varna (3). La función solo imprime en qué orden bloquearía. ¿Qué imprime?

def transfer(source, target):
    first, second = sorted((source, target), key=lambda w: w.id)
    print(f"{first.name}, luego {second.name}")




sofia = Warehouse(1, "Sofía", 0)
plovdiv = Warehouse(2, "Plovdiv", 0)
varna = Warehouse(3, "Varna", 0)
transfer(plovdiv, sofia)
transfer(sofia, varna)
transfer(varna, plovdiv)
Respuesta

Pruébalo

Completa

¿Por qué campo ordena sorted los dos almacenes?
first, second = sorted((source, target), key=lambda w: )

Pruébalo

Encuentra el error

Los traspasos ya bloquean por id, y durante semanas no hay ningún problema. Entonces alguien añade una auditoría nocturna que suma los dos almacenes. Desde entonces el programa a veces se detiene otra vez. ¿En qué línea está el error?

Elige la línea con el error.

Míralo

Cuando no es posible un orden: intenta y retrocede

A veces no sabes de antemano qué cerrojo vas a necesitar. Entonces, en vez de un orden, usas intentar y retroceder (tryLock con backoff): toma el primero e intenta el segundo sin esperar. Si no funciona, suelta todo, espera un poco y empieza de nuevo. Nadie tiene un cerrojo mientras espera, así que no hay círculo.

def transfer(source, target, qty):
    while True:
        with source.lock:
            if target.lock.acquire(blocking=False):
                try:
                    source.stock -= qty
                    target.stock += qty
                    return
                finally:
                    target.lock.release()
        # suelta todo y vuelve a intentarlo en un momento
        time.sleep(random.random() / 1000)

Con los mismos dos traspasos (300 en cada sentido) el resultado vuelve a ser exacto:

Salida
Sofía: 4700, Plovdiv: 3300
Total: 8000

La espera es aleatoria, y eso importa. Si los dos traspasos retroceden el mismo tiempo, pueden chocar una y otra vez con el mismo ritmo: los dos trabajan y nadie avanza. Esto se llama livelock. La espera aleatoria rompe el ritmo.

Más precisamente, para curiosos

Las cuatro condiciones de Coffman. Un deadlock ocurre solo si se cumplen cuatro cosas a la vez:

  1. exclusión mutua: un cerrojo solo lo puede tener uno;
  2. retener y esperar: un hilo tiene un cerrojo mientras espera otro;
  3. sin expropiación: nadie puede quitar un cerrojo por la fuerza;
  4. espera circular: la espera forma un círculo.

Quita una y el deadlock no puede ocurrir. Un orden quita el círculo (4). Retroceder quita «retener y esperar» (2). Las operaciones atómicas y los objetos inmutables de la lección anterior suelen quitar el cerrojo mismo (1).

Las bases de datos lo resuelven de una tercera manera. Buscan el círculo ellas mismas y cancelan una de las transacciones con el error «deadlock detected». Así que el código que trabaja con una base de datos tiene que estar listo para repetir la transacción.

Cómo es en los otros lenguajes: ReentrantLock.tryLock(time) en Java (synchronized no tiene tiempo límite); Monitor.TryEnter(object, time) en C# (lock no tiene tiempo límite); Lock.acquire(timeout=…) en Python; en JavaScript hay cerrojos solo entre Workers, escritos con Atomics.wait con tiempo límite. En el código async de un solo hilo no hay cerrojos, pero un círculo sigue siendo posible: dos funciones que se esperan con await la promesa una de la otra esperan para siempre, y el programa simplemente termina sin imprimir nada.

Ejercicio

Tres monederos en círculo

Resuelve la tarea en tu editor.

Tres monederos con 1000 € cada uno y tres hilos. El primero mueve 5 € del monedero 1 al 2, el segundo del 2 al 3, el tercero del 3 al 1, cada uno 1000 veces. Eso es un círculo: sin un orden, el programa se atasca tarde o temprano. Escribe transfer de modo que no pueda atascarse, e imprime los monederos y el total:

Salida
Monedero 1: 1000 €
Monedero 2: 1000 €
Monedero 3: 1000 €
Total: 3000 €

Más tareas

  • Atrápalo. Quita el orden y pon un tiempo límite al segundo cerrojo. Cuenta cuántos traspasos se rindieron y reintenta hasta que hayan pasado todos.
  • La auditoría. Añade un hilo que sume los tres monederos 1000 veces bajo sus cerrojos. El total debe ser siempre 3000 €. ¿En qué orden bloquea?
  • Sin id. Si los objetos no tienen número, ¿por qué más se pueden ordenar? (Pista: id(), y qué pasa si dos objetos tienen el mismo.)

Test

Ponte a prueba

1. ¿Cuándo se quedan dos hilos atascados en un deadlock?
2. Todos los traspasos bloquean los almacenes por id, del menor al mayor. ¿Pueden atascarse tres traspasos Sofía → Plovdiv, Plovdiv → Varna y Varna → Sofía?
3. ¿Por qué el programa deadlock de la lección no se cuelga?
4. Dos traspasos se rinden al fallar, esperan 1 ms y lo intentan otra vez. Los dos chocan de nuevo, una y otra vez. ¿Cómo se llama y cómo se arregla?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·