¿Qué causa un deadlock y cómo lo previene el orden consistente de locks?

#Las cuatro condiciones, con precisión

Un deadlock es un estado en el que un conjunto de hilos está, cada uno, esperando un recurso que tiene otro hilo del mismo conjunto, de modo que ninguno puede avanzar jamás. La formalización clásica (las condiciones de Coffman) dice que un deadlock requiere las cuatro siguientes de forma simultánea:

1. Exclusión mutua - un recurso (un lock) solo puede estar en manos de un hilo a la vez.
2. Retener y esperar - un hilo retiene al menos un recurso mientras espera adquirir otro.
3. Sin apropiación - un recurso solo puede liberarlo voluntariamente el hilo que lo tiene, nunca se le puede quitar por la fuerza.
4. Espera circular - existe un ciclo de hilos, cada uno esperando un recurso que tiene el siguiente en el ciclo.

La razón por la que este marco importa en una entrevista es que cada técnica de prevención de deadlocks funciona rompiendo exactamente una de estas cuatro condiciones, no por magia. El orden de locks apunta específicamente a la espera circular, y vale la pena poder decir eso con precisión, no solo "usa los locks en el mismo orden".

#El ejemplo clásico: transferir entre dos cuentas

class Account(val id: Int, var balance: Double) {
    val lock = ReentrantLock()
}

// CON BUG: los locks se adquieren en el orden que sea que pase quien llama.
fun transfer(source: Account, destination: Account, amount: Double) {
    source.lock.lock()
    try {
        destination.lock.lock()
        try {
            source.balance -= amount
            destination.balance += amount
        } finally {
            destination.lock.unlock()
        }
    } finally {
        source.lock.unlock()
    }
}

Supongamos que el Hilo 1 llama a transfer(cuentaA, cuentaB, 100.0) en el mismo momento en que el Hilo 2 llama a transfer(cuentaB, cuentaA, 50.0). El Hilo 1 bloquea A, y luego intenta bloquear B. El Hilo 2 bloquea B, y luego intenta bloquear A. Ambos están ahora esperando un lock que el otro tiene, y ninguno liberará jamás el que ya posee, porque la liberación ocurre en el bloque finally después de que la transferencia se completa, lo cual nunca sucede. Eso es las cuatro condiciones de Coffman a la vez: exclusión mutua (cada ReentrantLock permite un solo poseedor), retener-y-esperar (cada hilo retiene un lock mientras está bloqueado esperando el otro), sin apropiación (nada puede forzar a ninguno de los dos hilos a soltar su lock), y espera circular (A → espera a B → espera a A).

#La solución: un orden global fijo de locks

El orden de locks elimina la espera circular haciendo que todo hilo, sin importar en qué dirección esté transfiriendo dinero, adquiera los dos locks en el mismo orden global: aquí, ordenados por el ID estable y comparable de las cuentas, en vez de por cuál cuenta resulte ser el "origen" en esta llamada en particular.

// ARREGLADO: siempre adquiere los locks en un orden global fijo - por id de
// cuenta - sin importar cuál cuenta es el origen y cuál el destino.
fun transferOrdered(source: Account, destination: Account, amount: Double) {
    val first = if (source.id < destination.id) source else destination
    val second = if (source.id < destination.id) destination else source

    first.lock.lock()
    try {
        second.lock.lock()
        try {
            source.balance -= amount
            destination.balance += amount
        } finally {
            second.lock.unlock()
        }
    } finally {
        first.lock.unlock()
    }
}

Ahora, tanto el Hilo 1 (transfiriendo A → B) como el Hilo 2 (transfiriendo B → A) intentan bloquear primero la cuenta con el ID menor. El que llegue primero la bloquea, y el otro simplemente se bloquea esperando ese único lock: nunca retiene un lock distinto mientras lo hace, así que retener-y-esperar no puede formar un ciclo. Un hilo avanza por completo, libera ambos locks, y luego avanza el otro. Nunca es posible un ciclo, porque ambos hilos siempre están de acuerdo en el orden.

#Otras mitigaciones que vale la pena nombrar

El orden de locks es la respuesta más común, pero no es la única herramienta, y una buena respuesta de entrevista también nombra los trade-offs de las alternativas:

• Timeouts en los locks - usar tryLock(timeout) en vez de un lock() bloqueante, y hacer backoff con reintento al fallar. Esto rompe "sin apropiación" en la práctica: un hilo suelta voluntariamente el lock que tiene en vez de esperar para siempre. El trade-off es que cambias un deadlock por un posible livelock o una tormenta de reintentos si no le agregas jitter al backoff.
• Reducir el alcance de lo que haces mientras tienes un lock - nunca llamar a código que no controlas (un callback, un servicio downstream) mientras tienes un lock, ya que no hay garantía de que ese código no intente readquirir un lock que ya tienes, en un orden distinto.
• Estructuras de datos sin locks o atómicas - eliminar la exclusión mutua por completo para un dato específico (p. ej. un balance único modelado como un valor atómico con reintentos de compare-and-swap) evita el problema entero para ese dato, a costa de ser considerablemente más difícil de razonar más allá de un solo valor.
• Diagnóstico en producción - un volcado de hilos de la JVM (jstack <pid>) a menudo imprime explícitamente "Found one Java-level deadlock", nombrando los hilos y locks exactos del ciclo. Eso suele ser más rápido que intentar reproducir un deadlock en local.

#Comparando las estrategias

#Ideas clave

• Un deadlock requiere exclusión mutua, retener-y-esperar, sin apropiación y espera circular de forma simultánea; rompe cualquiera de las cuatro y se vuelve imposible.
• El orden de locks elimina específicamente la espera circular al forzar a todo hilo a pedir múltiples locks en el mismo orden global, sin importar la dirección de la operación.
• Los timeouts de locks, el alcance reducido de los locks y las estructuras sin locks son las otras herramientas reales, cada una sacrificando algo distinto (complejidad de reintento, disciplina de código, o dificultad de razonamiento).
• En producción, un volcado de hilos de la JVM a menudo nombra un deadlock explícitamente - revisa eso antes de intentar reproducirlo en local.