Imaginemos que dos autos entran desde extremos opuestos de un puente estrecho de un solo carril y se encuentran frente a frente en el centro. Si los dos conductores se quedan inmóviles esperando que el otro retroceda primero, ninguno de los dos autos podrá cruzar jamás el puente. Es difícil atribuirle la culpa a alguien, pero se ha creado una situación en la que nadie puede avanzar.
Dentro de una computadora ocurre exactamente lo mismo, y a esto se le llama «interbloqueo (Deadlock)». En pocas palabras, un interbloqueo es una situación en la que varios programas se quedan detenidos porque cada uno espera recursos que tienen los demás y ninguno puede continuar su tarea. Muchos de los casos en que una computadora parece detenerse de repente sin que haya sufrido una avería se deben precisamente a un interbloqueo.
En este artículo veremos, en ese orden, cómo se manifiesta un interbloqueo, cuáles son las cuatro condiciones para que se produzca, qué ejemplo famoso lo ilustra y cómo responden las computadoras ante él.
La computadora se detiene cuando sus programas se quedan esperando unos a otros
¿Cómo se produce un interbloqueo?
Dentro de una computadora se ejecutan varios programas a la vez que comparten recursos como impresoras, archivos y memoria.
(1) Recursos que solo puede usar un programa a la vez
Si varios programas usan ciertos recursos al mismo tiempo, su contenido puede quedar desordenado. Por eso, mientras un programa utiliza uno de esos recursos, los demás tienen que esperar. El mecanismo que reserva temporalmente un recurso para uso exclusivo de un programa se llama bloqueo (Lock).
(2) Una detención causada por órdenes de acceso distintos
Por ejemplo, puede ocurrir que el primer programa mantenga bloqueado el archivo A mientras espera el archivo B, y que el segundo mantenga bloqueado el archivo B mientras espera el archivo A. Como cada programa conserva el archivo que ya tiene y se queda esperando el del otro, ambos permanecen detenidos indefinidamente.
(3) Cómo se manifiesta
Un programa en interbloqueo simplemente deja de responder, sin mostrar siquiera un mensaje de error. En entornos que procesan muchas solicitudes a la vez, como las redes informáticas bancarias o los sistemas de reservas, una detención así puede causar problemas graves.
Las cuatro condiciones para que se produzca un interbloqueo
En 1971, el informático Edward G. Coffman Jr. estableció que deben cumplirse simultáneamente las cuatro condiciones siguientes para que se produzca un interbloqueo. En su honor, se las conoce como condiciones de Coffman.
- Exclusión mutua (Mutual Exclusion). Solo un programa puede usar el recurso a la vez.
- Retención y espera (Hold and Wait). Un programa ya tiene un recurso y lo conserva mientras espera otro.
- Sin expropiación (No Preemption). Un recurso en manos de un programa solo puede liberarse si ese mismo programa lo cede voluntariamente.
- Espera circular (Circular Wait). El programa 1 espera al 2, el 2 espera al 3 y el 3 espera a su vez al 1, de modo que la cadena de esperas forma un círculo.
(1) Basta con romper una condición para resolverlo
Si falta siquiera una de las cuatro condiciones, el interbloqueo no se produce. Por eso, la mayoría de los métodos para evitar un interbloqueo parten de romper uno de esos cuatro eslabones.
El problema de la cena de los filósofos
La historia más utilizada para explicar el interbloqueo es el «problema de la cena de los filósofos (Dining Philosophers Problem)», que tiene su origen en un problema planteado por el informático neerlandés Edsger W. Dijkstra.
(1) El planteamiento del problema
Cinco filósofos están sentados alrededor de una mesa redonda. Entre cada par de vecinos hay un tenedor, para un total de cinco. Cuando a un filósofo le entra hambre mientras está pensando, solo puede comer si toma los dos tenedores que tiene a sus lados.
(2) El momento en que todos se quedan sin comer
Si los cinco toman al mismo tiempo el tenedor de la izquierda, todos se quedan esperando el de la derecha. Como nadie suelta el tenedor de la izquierda, los cinco se quedan esperando sin poder comer. Es un caso típico de interbloqueo en el que se cumplen las cuatro condiciones.
(3) Una solución sencilla
Si se numera cada tenedor y se establece que todos deben tomar primero el de menor número, no se forma un ciclo de espera. Esto ilustra cómo basta con fijar un orden para romper la espera circular.
Cómo responde la computadora ante un interbloqueo
Los sistemas operativos y las bases de datos eligen entre varios métodos según la situación.
(1) Prevenirlo
Se fija de antemano el orden en que se usan los recursos o se exige que todos los recursos necesarios se soliciten juntos al principio, de modo que una de las cuatro condiciones nunca llegue a cumplirse.
(2) Evitarlo
Antes de conceder un recurso, se calcula si atender esa solicitud podría dar lugar a un interbloqueo más adelante. El algoritmo del banquero (Banker's Algorithm), ideado por Dijkstra, es un ejemplo representativo. Se parece a lo que hace un banco cuando, antes de conceder un préstamo, evalúa si podrá atender hasta el final las solicitudes de todos sus clientes.
(3) Detectarlo y resolverlo
Se permite que se produzca el interbloqueo y se comprueba quién espera a quién. Si se detecta un ciclo, se resuelve el problema deteniendo uno de los programas o volviéndolo a ejecutar desde el principio. Muchas bases de datos utilizan este método.
(4) Hacer como si no pasara nada
Si los interbloqueos son muy poco frecuentes y causan pocos daños, a veces se opta por reiniciar el sistema cuando se producen, sin tomar medidas para prevenirlos. Este método se conoce como algoritmo del avestruz (Ostrich Algorithm), por analogía con el avestruz que esconde la cabeza en la arena.
El interbloqueo surge cuando todos conservan lo que tienen y se quedan esperando a los demás, sin que nadie en particular tenga la culpa. Por eso, la solución empieza por fijar un orden y, en ocasiones, por soltar primero lo que se tiene.
Entender que basta con que alguien suelte una de las manos que todos mantienen entrelazadas para abrir paso es el primer paso para saber cómo poner de nuevo en marcha un sistema detenido.
