Bloqueo mutuo para niños

El bloqueo mutuo es un problema que ocurre en los sistemas informáticos cuando dos o más programas o tareas (llamados procesos) se quedan esperando el uno por el otro, sin que ninguno pueda avanzar. Imagina que tienes dos amigos que quieren jugar con un arco y una flecha. Uno toma el arco y el otro la flecha. Ninguno puede empezar a jugar hasta que el otro suelte lo que tiene. Así se quedan esperando, sin poder hacer nada.

En las computadoras, esto pasa cuando los procesos necesitan usar recursos, como partes de la memoria o dispositivos, y cada uno tiene un recurso que el otro necesita. Como cada proceso no suelta lo que tiene hasta que consigue lo que le falta, se produce un "abrazo mortal" o "traba mortal", y el sistema se detiene. No hay una solución sencilla que funcione para todos los casos de bloqueo mutuo.

Cuatro procesos (líneas azules) compiten por un recurso (círculo gris), siguiendo una política de derecha-antes que-izquierda. Un bloqueo mutuo aparece cuando todos los procesos bloquean el recurso simultáneamente (líneas negras). El bloqueo puede resolverse rompiendo la simetría.

En este ejemplo, dos procesos compiten por dos recursos. El primer proceso obtiene un recurso. El segundo proceso toma el otro recurso. Luego, el segundo proceso intenta usar el recurso que ya tiene el primero, y se queda esperando. Cuando el primer proceso intenta usar el recurso que tiene el segundo, se produce un bloqueo mutuo.

¿Cómo se representan los bloqueos mutuos?

Los bloqueos mutuos se pueden dibujar usando unos diagramas especiales llamados grafos dirigidos. En estos diagramas:

• Un cuadrado representa un proceso (una tarea que la computadora está haciendo).
• Un círculo representa un recurso (algo que los procesos necesitan, como una parte de la memoria o un archivo).

Cuando un proceso necesita un recurso, se dibuja una flecha desde el cuadrado (proceso) hacia el círculo (recurso). Si un recurso ya está siendo usado por un proceso, se dibuja una flecha desde el círculo (recurso) hacia el cuadrado (proceso).

Ejemplo de un bloqueo mutuo representado con grafos. Los procesos A y B esperan recursos que el otro tiene.

En el ejemplo de la imagen, puedes ver dos procesos, A y B, y dos recursos, R1 y R2. El proceso A tiene el recurso R1 y necesita el R2. El proceso B tiene el recurso R2 y necesita el R1. Esto crea una "espera circular", donde cada uno espera algo que el otro tiene, y ninguno puede avanzar.

¿Qué condiciones causan un bloqueo mutuo?

Para que ocurra un bloqueo mutuo, deben cumplirse cuatro condiciones al mismo tiempo. Estas condiciones fueron descritas por E. G. Coffman en 1971.

Exclusión mutua

Significa que al menos un recurso solo puede ser usado por un proceso a la vez. Si varios procesos intentan usarlo al mismo tiempo, solo uno lo consigue y los demás tienen que esperar.

Retención y espera

Un proceso ya tiene un recurso y lo mantiene, mientras espera otro recurso que ya está siendo usado por otro proceso. Es como si tu amigo tiene el arco y no lo suelta, pero necesita la flecha que tú tienes.

No expropiación

Los recursos no se pueden quitar a la fuerza a un proceso. El proceso que tiene el recurso debe soltarlo por sí mismo cuando termina de usarlo. El sistema operativo no puede simplemente quitárselo.

Espera circular

Varios procesos están esperando en círculo. Por ejemplo, el proceso 1 espera un recurso que tiene el proceso 2, el proceso 2 espera un recurso que tiene el proceso 3, y así sucesivamente, hasta que el último proceso de la cadena espera un recurso que tiene el proceso 1. Esto crea un ciclo sin fin.

Existe un método llamado Algoritmo de grafos de asignación de recursos que ayuda a detectar si hay un bloqueo mutuo.

¿Cómo se evitan los bloqueos mutuos?

Los bloqueos mutuos se pueden evitar si el sistema sabe de antemano qué recursos necesitarán los procesos. Así, antes de dar un recurso, el sistema puede revisar si esa acción podría llevar a un bloqueo. Si hay riesgo, el sistema no da el recurso hasta que sea seguro. Para esto, el sistema necesita saber cuántos y qué tipos de recursos hay disponibles y cuáles se necesitan.

Algunos algoritmos que ayudan a evitar bloqueos mutuos son:

• El Algoritmo del banquero, creado por Edsger Dijkstra.
• El Algoritmo de solicitud de recursos.

Ejemplos de bloqueos mutuos en sistemas modernos

Los bloqueos mutuos no solo ocurren en los sistemas operativos antiguos, sino también en programas y dispositivos que usamos hoy en día:

• Bases de datos: En programas como MySQL o PostgreSQL, si dos transacciones (operaciones) intentan cambiar la misma información, pueden bloquearse mutuamente. Por ejemplo, si una transacción bloquea una fila y espera otra que la segunda transacción ya bloqueó. Los sistemas de bases de datos suelen detectar esto y detienen una de las transacciones para resolverlo.
• Sistemas distribuidos: En sistemas donde muchos programas pequeños trabajan juntos (microservicios), dos de ellos pueden quedarse esperando una respuesta del otro mientras tienen un recurso importante, como una conexión a una base de datos. Esto se soluciona con límites de tiempo o formas especiales de diseño.
• Dispositivos IoT: En aparatos inteligentes como sensores o dispositivos conectados a internet, dos tareas pueden bloquearse si intentan usar al mismo tiempo un recurso compartido, como un canal de comunicación. Se evita usando colas o dando prioridades a las tareas.
• Servidores web: En las aplicaciones de internet, dos procesos pueden bloquearse si compiten por recursos como conexiones a bases de datos o archivos. Esto se resuelve con programación que permite hacer varias cosas a la vez o con límites de tiempo.

¿Cómo se previenen los bloqueos mutuos?

La prevención de bloqueos mutuos se basa en asegurarse de que alguna de las cuatro condiciones necesarias (exclusión mutua, retención y espera, no expropiación, espera circular) no se cumpla.

• Eliminar la exclusión mutua: Esto significaría que varios procesos podrían usar el mismo recurso al mismo tiempo. Pero esto no es posible para muchos recursos, como una impresora, que solo puede imprimir un documento a la vez.
• Eliminar la retención y espera: Una forma es que los procesos pidan todos los recursos que van a necesitar antes de empezar a trabajar. Pero a veces es imposible saber de antemano todos los recursos. Otra forma es que un proceso suelte todos sus recursos antes de pedir otros nuevos, lo cual también es poco práctico.
• Eliminar la no expropiación: Esto implicaría que el sistema podría quitarle un recurso a un proceso en cualquier momento. Pero esto puede causar problemas si el proceso necesita el recurso por un tiempo para terminar su tarea correctamente.
• Eliminar la espera circular: Esta es la condición más fácil de evitar. Se puede hacer que los procesos solo puedan tener un recurso a la vez, o establecer un orden (una jerarquía) para pedir los recursos, de modo que no se formen ciclos de espera.

Livelock

Un livelock es parecido a un bloqueo mutuo, pero en este caso, los procesos no se quedan quietos. En cambio, cambian su estado constantemente, pero sin hacer ningún progreso real. Es como si dos personas se encuentran en un pasillo estrecho y cada una intenta moverse para dejar pasar a la otra, pero terminan moviéndose al mismo lado al mismo tiempo, sin que ninguna avance.

El livelock puede ocurrir cuando los algoritmos que detectan y resuelven bloqueos mutuos actúan de forma repetitiva, haciendo que los procesos cambien de estado sin resolver el problema. Para evitarlo, se puede asegurar que solo un proceso (elegido al azar o por prioridad) intente resolver la situación.