¿Qué es un interbloqueo?
Un interbloqueo o deadlock es una situación en la que múltiples hilos se bloquean la ejecución hasta el punto de que el programa deja de operar correctamente o que incluso se queda congelado y bloqueado definitivamente (de ahí su nombre, porque da la impresión de que el programa ha muerto).
Cuando accedemos a recursos compartidos, es cierto que tenemos que poner mecanismos de control para organizar su acceso y evitar condiciones de carrera, como las que contaba hace unas lecciones. Sin embargo, esos mismos mecanismos de control de concurrencia también pueden corromper la ejecución del programa si los usamos mal.
Un interbloqueo sucede cuando dos hilos que tienen dependencia entre sí se quedan bloqueados porque uno está a la espera del otro, y otro está a la espera del uno. En muchas ocasiones esto ocurre precisamente por emplear un mecanismo de control de concurrencia en el que uno queda esperando a que el otro libere un recurso, pero para liberar ese recurso antes tiene que producirse otra situación en el otro hilo.
Suponte que tenemos dos hilos, Hilo1 e Hilo2. Ambos hilos necesitan un RecursoA y un RecursoB para poder operar, y además son recursos compartidos; dicho de otro modo, ambos hilos tienen acceso a las mismas instancias de recurso y sólo se pueden usar de uno en uno.
En el mejor de los casos, los hilos podrían conseguir coordinar su ejecución para que ocurra de este modo:
- Hilo1 bloquea el acceso a RecursoA.
- Hilo1 bloquea el acceso a RecursoB.
- Hilo2 trata de bloquear RecursoA, pero está ocupado. Se mantiene a la espera.
- Hilo1 hace su trabajo.
- Hilo1 libera el RecursoB.
- Hilo1 libera el RecursoA. Hilo2 ya puede continuar su ejecución.
- Hilo2 bloquea el acceso a RecursoA.
- Hilo2 bloquea el acceso a RecursoB.
- Hilo2 hace su trabajo.
- Hilo2 libera el RecursoB.
- Hilo2 libera el RecursoA.
Sin embargo, como la concurrencia precisamente es admitir que partes del programa podrían ejecutarse en otro orden diferente, bien podría ocurrir lo siguiente:
- Hilo1 bloquea el acceso a RecursoA.
- Hilo2 bloquea el acceso a RecursoB.
- Hilo1 trata de bloquear RecursoB, pero está ocupado porque lo tiene Hilo2. Se mantiene a la espera.
- Hilo2 trata de bloquear RecursoA, pero está ocupado porque lo tiene Hilo1. Se mantiene a la espera.
- El programa se queda congelado.
Es el problema cíclico. Como Hilo1 no puede adquirir RecursoB, nunca podrá terminar su ejecución y liberar RecursoA. El problema es que para poder adquirir RecursoB, Hilo2 necesita antes bloquear RecursoA para poder hacer su trabajo, pero eso va a ser imposible porque exigiría pedir que Hilo1 termine su trabajo, algo que ya queda claro que es imposible.
Los interbloqueos deben ser evitados y el acceso a recursos debe organizarse para que esto no suceda.
Un problema mítico: la cena de los filósofos pensantes
Se trata de una de las formas de ejemplificar este problema. Tenemos una mesa en la que hay sentados un número de filósofos. Esos filósofos sólo pueden estar en dos etapas: pensando o comiendo. Cuando terminan de pensar, comen; y cuando terminan de comer, vuelven a pensar.
Los filósofos están sentados en una mesa en la que hay tantos platos como filósofos, pero en la que no hay tenedores para todo el mundo. Entre cada plato hay un tenedor, y para poder comer, un filósofo necesita agarrar un tenedor con su mano izquierda y otro tenedor con su mano derecha. (Una alternativa de este problema es que lo que usan para comer son palillos chinos; es raro necesitar dos tenedores para comer en cada mano, pero necesitar dos palillos chinos es una explicación perfectamente coherente y que incluso sólo requiere una mano.)
Para poder comer, por lo tanto, un filósofo debe tomar el cubierto que tiene a la izquierda, y luego tomar el cubierto que tiene a su derecha. Solo entonces puede comer, para soltar los cubiertos y dejarlos donde estaban. (Resulta un poco asqueroso, pero tal vez los filósofos no solo no tenían suficientes cubiertos para todos sino que tampoco tenían lavaplatos.)
En cualquier caso, esto ejemplifica perfectamente el problema del interbloqueo. Cada filósofo es un hilo, que necesita acceso a dos recursos compartidos para poder operar. Debido a la forma en la que están sentados y organizados los cubiertos, el palillo derecho de un filósofo será el palillo izquierdo de su vecino, por lo que hay cierta competencia a la hora de acceder a este recurso compartido, ya que mientras un filósofo tenga el cubierto derecho, su vecino no podrá usar el cubierto izquierdo.
Si todos los filósofos tratan de comer exactamente a la vez, una cosa que puede ocurrir es que todos alcancen a tomar el cubierto que tienen a su izquierda. Sin embargo, cuando traten de agarrar el cubierto que tienen a su derecha, ya no quedarán cubiertos libres, porque todos han sido pillados con la otra mano. Esto provoca que los filósofos se queden infinitamente bloqueados sin poder comer, e imaginamos sin poder pensar.
Cómo solucionar problemas de interbloqueo o deadlock
Existen varias soluciones, que precisamente podemos aplicar en programas concurrentes donde haya accesos a varios recursos compartidos de una forma parecida a esta.
Una solución inicial podría ser introducir pausas aleatorias para impedir que todos los hilos hagan su trabajo exactamente a la vez. De este modo, el factor aleatorio puede provocar que haya más ocasiones en las que todos los recursos puedan adquirirse por un hilo, permitiendo así el avance del programa. Sin embargo, esto es un parche. Eventualmente la misma aleatoriedad puede provocar que todos los hilos se interbloqueen.
Otra solución puede ser asegurarse de que nunca hay tantos filósofos como cubiertos. En este caso, si hubiese un agente en la puerta encargado de dar turnos para comer, que le pida a un filósofo que se espere antes de comer si detecta que no quedan cubiertos libres, para impedir que trate de sentarse y agarrarlos destruyendo la ejecución del programa, podríamos evitar el interbloqueo. Aplicada a código, requeriremos más estructuras concurrentes para poder implementar esta solución.
Finalmente, podríamos hacer que los filósofos voluntariamente desistiesen de comer si detectan que llevan demasiado tiempo esperando para tomar un cubierto cuando ya tienen el otro. Dicho de otro modo, si pillo el cubierto izquierdo, pero paso demasiado tiempo esperando hasta tener el cubierto derecho, entonces suelto el izquierdo y vuelvo a intentar comer. De este modo, al liberar uno de los cubiertos, otro que tal vez esté esperando a que suelte ese cubierto lo podría agarrar para desbloquear el resto del sistema. O bien incluso el filósofo podría levantarse de la mesa y marcharse sin comer si se queda demasiado tiempo a la espera sin que pueda empezar a comer.
En el caso de Java, únicamente con synchronized ninguna de estas soluciones nos va a ser posible. También necesitaremos estructuras adicionales debido a que al usar synchronized, los monitores o se pillan en el momento, o se espera hasta que puedan pillar. La llamada a un método de este estilo o el acceso a un bloque con exclusión mutua no podrá ser abortado o cancelado si se produce un timeout. Otro tipo de locks en Java sí que nos pueden proporcionar una forma de intentar adquirirlo, y desistir si pasa un límite de tiempo sin haberlo podido adquirir de forma segura.
Todas estas soluciones las planteo aquí pero no las respondo, sino que lo haré en una lección futura para poder darle el tiempo que requieren.