Inanición

La inanición se produce cuando algún proceso dentro del sistema no puede satisfacer sus necesidades de recursos debido a que otros procesos los están utilizando continuamente. Este escenario se presenta mucho en algoritmos de asignación por importancia o de asignación por tamaño. Como en un sistema operativo las tareas nunca dejan de llegar puede haber trabajos muy poco importantes o muy grandes a los cuales no les sea permitido hacer uso de los recursos.

Un ejemplo podría ser el de un proceso de baja importancia que está esperando en memoria para usar el procesador, pero debido a que hay otros trabajos de mayor importancia éste está en espera. Durante un rato los trabajos que estaban usando el procesador con anterioridad se retiraron, pero llegaron otros trabajos también de mucha importancia y el primer programa sigue esperando. Esto puede continuar indefinidamente y el proceso nunca llega a ejecutarse.

Detección y recuperación de un bloqueo

Los bloqueos mutuos se pueden detectar de manera relativamente fácil como pudimos ver en las gráficas dirigidas. Siempre que se produzca un ciclo en la solicitud y retención de dispositivos hay un bloqueo. El algoritmo para que el sistema busque los bloqueos se explica de la manera siguiente:
a) Encuentre un proceso que esté utilizando un recurso y no espere ningún otro. Este se puede eliminar de la gráfica.
b) Encentre un proceso que nada más espere recursos que no están asignados por completo.
c) Vuelva al paso uno hasta eliminar todas las líneas posibles.Si todavía quedan procesos que no se han eliminado hay un bloqueo.

En la primera imagen no hay bloqueo, pero en la segunda si.
(Haga click en la imagen para agrandar)

El sistema operativo después de detectar el bloqueo mutuo debe recuperarse del mismo y continuar con su trabajo. Para esto necesita una “víctima”, un programa que se pueda terminar y volver a iniciar desde el principio o desde un punto medio conveniente.
Algunos algoritmos para la recuperación son los siguientes:

• Terminar todos los trabajos activos y volver a arrancarlos.
• Terminar los trabajos en el bloqueo solamente y solicitar su nuevo envío.
• Terminar uno por uno los trabajos que participan en el bloqueo y ver si el bloqueo desaparece después de cada terminación.
• Terminar un trabajo que se pueda reiniciar desde un punto medio si este resuelve el bloqueo.
• Terminar un trabajo que no está en el bloqueo y asignar sus recursos a uno bloqueado.
• Este último método detiene los trabajos nuevos y permite que los que no están bloqueados terminen y liberen sus recursos para que los bloqueados los usen, es el único que no requiere víctimas, pero al igual que el anterior no siempre funciona.

Prevención de bloqueos mutuos

Para que no ocurran los bloqueos mutuos basta con eliminar cualquiera de las cuatro condiciones necesarias para que éste ocurra. El único problema es que no todas se pueden eliminar ya que son necesarias. La exclusión mutua se necesita porque hay recursos como la memoria y el CPU que deben quedar asignados solo a un usuario a la vez. Una forma de eliminarla es el spool en dispositivos de E/S, pero el spool también puede producir un bloqueo cuando se llena.

La retención de recursos se podría eliminar haciendo que los trabajos soliciten todos los dispositivos que van a usar cuando son aceptados, pero esto limitaría la multiprogramación y muchos dispositivos quedarían ociosos.

La no apropiatividad se puede eliminar al desasignar recursos de los trabajos. Esto se realiza en el round robin y cuando se intercambia una página a un almacenamiento secundario, pero muchas veces el retomar el trabajo toma muchas molestias y requiere tiempo.
Por último la espera circular se puede impedir al hacer que el sistema operativo monitoree los procesos en busca de la formación de estos círculos. Havender propuso en 1968 una solución que proponía la numeración de los recursos en orden ascendente. Cada trabajo debía solicitar sus recursos en el mismo orden de la numeración antes de ser aceptado. En ese mismo orden el sistema operativo le asignaría sus recursos y monitorearía cualquier formación de un círculo en los números. El problema sería en que orden numerar los dispositivos para una mejor utilización y también que los archivos y bases de datos no se pueden numerar conforme a importancia.

Evitar bloqueos mutuos

Aunque no se pueda eliminar todas las condiciones de un bloqueo mutuo un sistema operativo puede evitarlo si conoce el orden de las solicitudes de cada proceso activo. Un algoritmo con este propósito fue propuesto por Dijkstra en 1965. Este algoritmo se basa en los principios de un banco con una cantidad fija de capital que:

• No concede préstamos que excedan el capital.
• Todos los clientes tienen un límite de crédito máximo.
• Ningún cliente puede pedir prestado más allá de ese límite.
• La suma de todos los préstamos no pude exceder el capital total del banco.

En los ejemplos siguientes podemos ver dos situaciones:

• En la primera el sistema está en un “estado seguro” porque tiene suficientes dispositivos libres para completar los requerimientos de cualquier trabajo.
• En la segunda el sistema entró en un “estado inseguro” ya que no tiene suficientes recursos para completar los requerimientos de ninguno de los procesos.

Cuando el sistema entra en un estado inseguro es muy probable que se produzca un bloqueo mutuo por lo que el sistema operativo nunca debe permitirlo.

De todas formas este algoritmo también tiene sus desventajas. No se usan los recursos al máximo, los trabajos deben enunciar el máximo de sus recursos desde el principio, si un dispositivo deja de funcionar el algoritmo no funciona, el número de trabajos debe mantenerse fijo y esto no ocurre en la realidad, ejecutar el algoritmo agrega carga a la memoria y al procesador, entre otras.

Estrategias para el manejo de bloqueos

Para que no se formen bloqueos mutuos los sistemas operativos usan una de estas tres estrategias:

• Impedir que ocurra una de las cuatro condiciones.
• Evitar el bloqueo si este es probable.
• Detectar el bloqueo cuando ocurre y recuperarse con gracia.

Modelado de bloqueos mutuos

Los bloqueos mutuos se pueden modelar a través de gráficas. Holt demostró en 1972 que a través de estas gráficas se podían modelar las cuatro condiciones necesarias para un bloqueo mutuo. Para realizarlas se usan cuadrados para representar los recursos y círculos para representar los procesos. Una línea de un recurso a un proceso significa que éste está retenido por dicho proceso; una línea de un proceso a un recurso significa que éste está esperando dicho recurso.
En esta gráfica podemos ver dos recursos cada uno asignado a un proceso y solicitado por el otro. Al formarse el círculo con las flechas en la misma dirección podemos detectar que se formó un bloqueo mutuo.

7- Bloqueos mutuos en una red:

Las redes usan lo que se denomina buffer. El buffer es un espacio igual que el spool, pero reside en la memoria principal y no en el disco duro. En un ejemplo tenemos 7 computadoras conectadas entre sí que pueden enviarse mensajes como las flechas indican en la figura siguiente:

Al llenarse ambas colas de salida en C1 y C2, con mensajes destinados respectivamente a C2 y a C1 obtenemos un bloqueo mutuo ya que ninguna de las dos puede enviar mensajes. Además como las colas no se vacían no pueden recibir tampoco mensajes de ninguna otra computadora, por lo que todo el sistema se paraliza.

6- Bloqueos al compartir discos:

Los discos están diseñados para ser compartidos y sin controles para regular su uso los procesos que lo necesitan pueden enviarle comandos conflictivos. Un ejemplo sería el de dos procesos P1 y P2. P1 necesita leer un archivo del cilindro 20 y P2 necesita escribir uno en el cilindro 310.
a) P1 emite un comando de leer del cilindro 20 y el brazo del disco comienza a moverse hacia allá. P1 queda en espera.
b) En ese instante el canal de E/S queda liberado y P2 emite un comando de escribir en el cilindro 310 y el brazo del disco acepta el comando.
c) P1 cree que el brazo está listo para leer del cilindro 20 y emite de nuevo su comando de lectura, pero el brazo necesita moverse de nuevo.
d) A P2 le ocurre lo mismo y emite de nuevo su comando para ir al cilindro 310.El brazo está en constante movimiento pero no satisface ninguno de los dos comandos completamente.

5- Bloqueos mutuos en operaciones periféricas simultáneas en línea:

Este tipo de bloqueo ocurre cuando usamos lo que se llama “spooling”. Spooling significa que las tareas a realizar por un dispositivo (ej.: una impresora) se almacenan en una parte del disco. Estas van llegando y la impresora las realiza cuando tiene la información completa. Sin spooling sólo una tarea podría ser realizada por la impresora y las demás estarían bloqueadas esperando. Pero el spool también se puede bloquear. Si muchas tareas comienzan a llegar y el espacio en disco disponible se llena sin que ninguna de las tareas esté completa la impresora no va a imprimir hasta que una de éstas se complete, pero ninguna se puede completar porque no hay más espacio en disco.

4- Bloqueos en la asignación múltiple de dispositivos:

En el ejemplo anterior el bloqueo se puede producir también por procesos que compiten por dispositivos diferentes, inclusive siendo más de un proceso el que participa en el bloqueo, como podemos ver en la imagen siguiente.

3- Bloqueos mutuos en la asignación de dispositivos dedicados:

En este caso se produce lo mismo que en los ejemplos anteriores pero en vez de ser registros o archivos, los que producen el bloqueo son dispositivos como impresoras, cintas, discos, lectores de cd o dvd, etc.).

2- Bloqueos mutuos en bases de datos:

Igual que en el caso anterior un bloqueo mutuo puede ocurrir con registros de bases de datos. Las bases de datos pueden ser bloqueadas completas, parcialmente o sólo el registro utilizado. Al ser bloqueada la base de datos entera no ocurren bloqueos entre registros, pero ésta sólo puede ser utilizada por un usuario. Entre menor es el bloqueo más usuarios pueden trabajar con la misma base de datos, pero mayor es el riesgo de bloquear el sistema.
En el siguiente ejemplo vemos como se produce un bloqueo mutuo cuando solamente se bloquean los registros utilizados:
a) Un proceso P1 pide un registro R1 y lo bloquea.
b) Otro proceso P2 pide y bloquea el registro R2.
c) P1 solicita R2 y éste está bloqueado.
d) P2 solicita R1 y está bloqueado por P1.
Una alternativa para solucionar el problema es no usar bloqueos ya que un registro puede ser usado por más de un proceso, pero esto lleva al siguiente problema:

Si dos programas accedan el mismo registro para actualizarlo al mismo tiempo los datos del éste serán equivocados en ambas actualizaciones como podemos ver en la figura. El resultado dependerá de cual proceso gana “la carrera” o termina primero, pero en ambos casos el resultado será incorrecto.

1-Bloqueos mutuos en solicitudes de archivos:

Se produce cuando se permite que las tareas soliciten archivos y los conserven durante su ejecución. Para que se produzca este bloqueo tiene que ocurrir lo siguiente:

a) Dos programas P1 y P2 necesitan ambos dos archivos F1 y F2. P1 accede al archivo F2 y P2 al archivo F1.
b) P1 solicita F1 sin haber liberado F2.
c) P2 solicita F2 sin liberar F1.
d) En este punto ambos procesos quedan bloqueados.

Bloqueos Mutuos

Los bloqueos mutuos son más serios que la inanición debido a que afectan todo el sistema, en cambio la inanición sólo afecta unos pocos procesos. El bloqueo mutuo afecta todo el sistema ya que los recursos que participan del bloqueo nunca van a ser liberados, por lo tanto tampoco pueden ser usados por procesos nuevos.

Estos son siete casos de Bloqueos Mutuos:
1- Bloqueos mutuos en solicitudes de archivos.
2- Bloqueos mutuos en bases de datos.
3- Bloqueos mutuos en la asignación de dispositivos dedicados.
4- Bloqueos en la asignación múltiple de dispositivos.
5- Bloqueos mutuos en operaciones periféricas simultáneas en línea.
6- Bloqueos al compartir discos.
7- Bloqueos mutuos en una red.

Condiciones para un bloqueo mutuo

Para que un bloqueo mutuo se produzca se tienen que dar las siguientes cuatro condiciones:
Exclusión mutua: un solo proceso tiene acceso a un recurso.
Retención de recursos: los procesos se empeñan en conservar sus recursos y no los liberan hasta que no lo hagan los otros.
No apropiatividad: un proceso puede conservar los recursos que tiene mientras espera la liberación de otros.
Espera circular: cada proceso afectado aguarda un recurso en poder del otro. Todos los procesos están bloqueados y ninguno puede continuar.

Introducción

Hoy en día las computadoras pueden trabajar con múltiples procesos y tareas a la vez, lo que significa que deben distribuir sus recursos de manera que cada proceso pueda completarse. Cuando un sistema operativo no sabe asignar de una manera sincronizada sus dispositivos, los procesos pueden producir dos condiciones: bloqueo mutuo o inanición.

Cuando un proceso se va a ejecutar, éste bloquea los dispositivos (el dispositivo no puede ser usado por otro proceso) que está utilizando, y en algunos casos, también bloquea los que va a utilizar en el futuro. Un bloqueo mutuo es un enredo que se produce entre dos o más procesos cuando ambos se ponen en espera por la necesidad bilateral de utilizar un recurso que no está disponible ya que otro trabajo lo ha bloqueado para su uso; a su vez, el último trabajo también espera por otro recurso bloqueado por el primer trabajo. Como se puede ver ambos procesos quedarán en espera hasta que uno de los dos sea cancelado o interrumpido.

Por otro lado, la inanición se produce cuando un proceso espera por un recurso indefinidamente. Un ejemplo puede ser la asignación del procesador a los trabajos con menos tiempo de procesamiento. Si uno es muy grande y los trabajos pequeños no dejan de llegar, el grande nunca obtendrá el procesador.