Qué es un deadlock

Sostener y esperar

En la lección sobre la condición de carrera adquirimos una buena costumbre: para cambiar algo, primero lo tomas, y los demás esperan hasta que termines, como en la fila de un baño individual. Así desapareció el accidente de dos personas que se pisan y estropean el resultado.
Ahora supongamos que un trabajo necesita dos recursos. Llamémoslos herramienta 1 y herramienta 2; el trabajo solo se termina con las dos. A toma primero la herramienta 1 y espera la 2. B toma primero la herramienta 2 y espera la 1. Cada uno tomó solo una, siguiendo la regla, y aun así ninguno consigue nunca la otra.
No soltar lo que tienes y esperar lo que te falta: ese sostener y esperar es el origen de todo el problema.

Pulsa los dos botones para que A y B tomen una herramienta cada uno. A sostiene la 1 y espera la 2; B sostiene la 2 y espera la 1. Ninguno suelta nada y cada uno espera solo lo que le falta, así que ninguno puede avanzar (rojo).

Extraño, ¿verdad? Ninguno hizo nada malo. Cada uno tomó una herramienta por turno, justo como la lección sobre la condición de carrera decía que era seguro. Y aun así los dos se quedaron atascados.
El problema no es sostener en sí, sino la forma: sostener mientras se espera al otro. Una escena conocida ayuda a ver esa forma con más claridad.

Dos personas frente a frente en un puente estrecho

Imagina un puente tan estrecho que solo cabe una persona. Una persona sube por un extremo y otra por el extremo opuesto al mismo tiempo. Caminan hacia el centro y se encuentran de frente.
Para seguir, cada una necesita que la otra se aparte. Pero ninguna cede el lugar donde está: yo llegué primero, yo tengo más prisa. Como nadie retrocede, las dos se quedan paradas en el centro para siempre.
Los lugares del puente son la herramienta 1 y la herramienta 2 de antes, y las dos personas son A y B. Cada una sostiene su sitio mientras espera el de la otra: exactamente la forma que acabamos de ver.

Usa los dos botones para acercar a A y a B al centro, una casilla cada vez. Cuando se encuentran en el centro, ninguna cede, así que las dos se detienen y ya no pueden pasar (rojo).

En el puente, las dos personas se detuvieron en cuanto quedaron frente a frente. Pero el atasco no tiene por qué ser solo de dos. Si tres, cuatro o más personas se colocan no en fila sino en círculo, cada una esperando a la siguiente, el mismo bloqueo ocurre a mayor escala.
Esta vez sentamos a varias personas alrededor de una mesa y cerramos nosotros mismos el círculo de espera.

Cuando el círculo se cierra, todos se detienen

Cinco personas están sentadas alrededor de una mesa, con un palillo entre cada par de vecinos. Para comer hacen falta el palillo de la izquierda y el de la derecha, y todos han acordado tomar primero el de la izquierda y luego esperar el de la derecha.
Si solo lo hacen una o dos, no pasa nada: alguien consigue los dos, come y los deja otra vez. Pero si todos toman a la vez el de la izquierda, el palillo derecho de cada uno está en la mano de su vecino. Todos esperan al vecino, y la espera da la vuelta completa a la mesa hasta volver al punto de partida.
Cuando las flechas de espera forman así un círculo cerrado, nadie en ese círculo puede moverse jamás. Las dos personas del puente estrecho se han convertido en un anillo entero alrededor de la mesa.

Cada vez que pulsas el botón, la siguiente persona toma su palillo izquierdo. En el momento en que lo toma la quinta, el círculo se cierra: el palillo derecho de cada uno está en la mano de un vecino y todo se detiene (rojo).

Con ese último paso que cierra el círculo, una mesa que funcionaba bien se congeló por completo. Lo inquietante es que nadie hizo nada especialmente mal. Todos tomaron primero el palillo izquierdo, del mismo modo razonable, y la mesa entera se detuvo.
Entonces, ¿cómo se descongela? Por suerte, la respuesta es sorprendentemente sencilla, y hay dos caminos.

La salida: ceder o fijar un orden

El primer camino es ceder. Alguien del círculo deja por un momento lo que sostenía. Entonces el vecino que lo esperaba reúne los dos palillos, come y los deja al terminar. Se libera un sitio, luego el siguiente, y el atasco se deshace como una fila de fichas de dominó, porque un círculo con un solo hueco ya no está cerrado.
El segundo camino es más astuto: impedir que el círculo llegue a cerrarse. Se da a todos la misma regla: "sea quien sea, toma siempre primero la de número más bajo". Así, quien no consigue la herramienta 1 tampoco toma la 2, sino que espera. Como todos toman las cosas en el mismo orden, nunca quedan dos personas cruzadas frente a frente, y el círculo no puede formarse.

Primero cierra el círculo para que todos se detengan; luego haz que una persona ceda. Cuando deja lo que sostenía, el círculo se rompe y, empezando por su vecino, todos se liberan uno tras otro y vuelven a moverse (verde).

Ceder deshace un círculo que ya se detuvo; fijar un orden evita que la detención llegue a ocurrir. Uno es primeros auxilios después del accidente; el otro, prevención antes de él.
Los dos se reducen a lo mismo: no dejar que se cierre el círculo de espera. Basta con romperlo en un solo punto para que el bloqueo vuelva a ser flujo.

En una sola página

Basta con recordar cuatro cosas.
Primera: cuando cada uno sostiene una cosa y espera la del otro, empieza el sostener y esperar. Segunda: como las dos personas del puente estrecho, si quedan frente a frente y ninguna cede, las dos se detienen.
Tercera: cuando esa detención da la vuelta completa y el círculo se cierra, todos los que están en él se detienen. Eso es un interbloqueo (deadlock). Cuarta: si alguien deja lo que sostiene y cede, o si todos acuerdan tomar las cosas en el mismo orden, el círculo se rompe o nunca se forma, y todo puede volver a fluir.

Pulsa los cuatro pasos en orden y la historia completa de un interbloqueo cabe en un panel: sostener y esperar, el cara a cara en el puente, el círculo cerrado y las dos salidas, ceder y fijar un orden.

En la lección sobre la condición de carrera aprendimos que ir por turnos, de uno en uno, es seguro; esta vez vimos que ese mismo tomar por turnos puede detenerlo todo. La misma herramienta depende de cómo se use.
Una fila segura y un interbloqueo que nunca termina están separados por muy poco. Que todos tomen las cosas en el mismo orden, y que alguien sepa ceder, es lo que decide de qué lado se cae.
Queda una sola lección en el área de sistemas operativos: cómo se despierta sola una computadora, desde que pulsas el botón de encendido hasta que se enciende la pantalla.