Interbloqueo: detección y prevención

Dos hilos, dos candados. El primero toma A y quiere B; el segundo toma B y quiere A. Ninguno suelta lo que tiene y ninguno consigue lo que falta. El sistema no se cayó, no hay error en los logs: simplemente dos cosas dejaron de avanzar para siempre.

Las cuatro condiciones de Coffman

Coffman identificó cuatro condiciones que deben cumplirse simultáneamente. Exclusión mutua: el recurso no se puede compartir. Retener y esperar: se conserva lo tomado mientras se pide más. Sin expropiación: nadie le quita el recurso a su dueño. Espera circular: hay un ciclo de procesos donde cada uno espera algo que tiene el siguiente.

Que sean necesarias las cuatro es la buena noticia: romper una sola alcanza para que el interbloqueo sea imposible.

Prevenir es romper una de las cuatro

Romper la exclusión mutua rara vez se puede: el recurso es indivisible por naturaleza. Romper “retener y esperar” significa pedir todo junto al principio, lo que desperdicia recursos y a veces no se sabe qué hará falta.

Permitir expropiación implica poder quitarle un recurso a alguien y deshacer su trabajo parcial: es lo que hace una base de datos al cancelar una transacción. Y romper la espera circular es lo más barato de todo: definir un orden global y tomar siempre los recursos en ese orden. Sin ciclo posible, no hay interbloqueo.

El orden global, que es lo que se usa

Esa última es la técnica que se usa en la práctica. Si todos toman A antes que B, el escenario del principio no puede ocurrir: el segundo hilo nunca tendrá B sin tener A.

Implementarlo es cuestión de convención y disciplina —numerar los candados, documentar el orden— y de detectarlo con herramientas: los analizadores dinámicos avisan cuando un programa toma candados en órdenes inconsistentes, aunque en esa corrida no haya llegado a trabarse.

Evitar los estados peligrosos

Una vía intermedia es evitar dinámicamente los estados peligrosos: antes de conceder un recurso, ver si el sistema queda en un estado desde el cual todos pueden terminar. Ese es el algoritmo del banquero.

Exige conocer de antemano el máximo que cada proceso va a pedir, y ese requisito lo vuelve poco aplicable fuera del papel. Pero sirve para tener presente la distinción entre estado seguro e inseguro: inseguro no significa trabado, significa que podría trabarse según lo que pase después.

Dejarlo pasar y detectarlo

La última estrategia es dejar que ocurra y detectarlo. Se arma un grafo de espera: quién espera a quién. Un ciclo en ese grafo es un interbloqueo, y detectar ciclos en un grafo dirigido es barato.

Es lo que hacen las bases de datos: al encontrar el ciclo, eligen una víctima y cancelan su transacción. Es la opción correcta cuando deshacer es posible y barato, y por eso el código que usa transacciones tiene que estar preparado para reintentar.

Ignorarlo, que también es una decisión

Y está la estrategia que usa la mayoría de los sistemas operativos de propósito general: ignorarlo. Se la llama algoritmo del avestruz, y no es negligencia sino un cálculo: los interbloqueos del núcleo son raros y prevenirlos costaría rendimiento en todas las operaciones.

Conviene distinguirlo de dos parientes. La inanición es no conseguir nunca el recurso aunque otros avancen. El livelock es que todos cambien de estado sin progresar, como dos personas que se esquivan en un pasillo hacia el mismo lado una y otra vez.

Prevenir, detectar o ignorar

Cierre

Exclusión mutua, retener y esperar, sin expropiación y espera circular: las cuatro juntas o no hay interbloqueo. Lo barato es romper la circular con un orden global de adquisición; detectarlo por ciclos y cancelar sirve donde deshacer es posible, y muchos sistemas eligen simplemente convivir.