INTERBLOQUEOS

Los sistemas computacionales están llenos de recursos que pueden ser utilizados por sólo un proceso a la vez. Algunos ejemplos comunes son las impresoras, las unidades de cinta y las ranuras en los tableros internos del sistema.

El proceso A pide permiso para utilizar el escáner y se le otorga.

 El proceso B se programa de manera distinta y solicita primero el grabador de CDs, y también se le otorga. Ahora A pide el grabador de CDs, pero la petición se rechaza hasta que B lo libere. Por desgracia, en vez de liberar el grabador de CD, B pide el escáner.

 En este punto ambos procesos están bloqueados y permanecerán así para siempre. A esta situación se le conoce como interbloqueo.

Los interbloqueos también pueden ocurrir entre máquinas A menudo, los dispositivos como escáneres, grabadores de CD, impresoras y unidades de cinta se conectan a la red como recursos compartidos, disponibles para cualquier usuario en cualquier equipo. Si estos dispositivos se pueden reservar de manera remota (es decir, desde el equipo doméstico del usuario), pueden ocurrir los mismos tipos de interbloqueos antes descritos. Las situaciones más complicadas pueden ocasionar interbloqueos que involucren a tres, cuatro o más dispositivos y usuarios.

Los interbloqueos pueden ocurrir en una variedad de situaciones, además de solicitar dispositivos de E/S dedicados.

Si el proceso A bloquea el registro R1 y el proceso B bloquea el registro R2, y después cada proceso trata de bloquear el registro del otro, también tenemos un interbloqueo. Por ende, los interbloqueos pueden ocurrir en los recursos de hardware o de software.

Se ha escrito mucho sobre los interbloqueos.

Dos bibliografías sobre el tema han aparecido en Operating Systems Review y deben consultarse en busca de referencias (Newton, 1979; y Zobel, 1983). Aunque estas bibliografías son antiguas, la mayor parte del trabajo sobre los interbloqueos se hizo mucho antes de 1980, por lo que aún son de utilidad.

Recursos

Una clase principal de interbloqueos involucra a los recursos, Los interbloqueos pueden ocurrir cuando a los procesos se les otorga acceso exclusivo a los dispositivos, registros de datos, archivos, etcétera. Para que el análisis sobre los interbloqueos sea lo más general posible, nos referiremos a los objetos otorgados como recursos Un recurso puede ser un dispositivo de hardware (por ejemplo, una unidad de cinta) o una pieza de información (como un registro bloqueado en una base de datos). En resumen, un recurso es cualquier cosa que se debe adquirir, utilizar y liberar con el transcurso del tiempo.

Recursos apropiativos y no apropiativos

Los recursos son de dos tipos: apropiativos y no apropiativos. Un recurso apropiativo es uno que se puede quitar al proceso que lo posee sin efectos dañinos. La memoria es un ejemplo de un recurso apropiativo.

Un recurso no apropiativo es uno que no se puede quitar a su propietario actual sin hacer que el cómputo falle. Si un proceso ha empezado a quemar un CD-ROM y tratamos de quitarle de manera repentina el grabador de CD y otorgarlo a otro proceso, se obtendrá un CD con basura.

En general, los interbloqueos involucran a los recursos no apropiativos. Los interbloqueos potenciales que pueden involucrar a los recursos apropiativos por lo general se pueden resolver mediante la reasignación de los recursos de un proceso a otro. Por ende, nuestro análisis se enfocará en los recursos no apropiativos.

La secuencia de eventos requerida para utilizar un recurso se proporciona a continuación, en un formato abstracto.

1. Solicitar el recurso.

2. Utilizar el recurso.

3. Liberar el recurso.

Adquisición de recursos

Para ciertos tipos de recursos, como los registros de una base de datos, es responsabilidad de los procesos de usuario administrar su uso. Una manera de permitir que los usuarios administren los recursos es asociar un semáforo con cada recurso. Estos semáforos se inicializan con 1. Se pueden utilizar mutexes de igual forma. Los tres pasos antes listados se implementan como una operación down en el semáforo para adquirir el recurso, usarlo y finalmente realizar una operación up en el recurso para liberarlo.

Algunas veces los procesos necesitan dos o más recursos. Se pueden adquirir de manera secuencial. Si se necesitan más de dos recursos, sólo se adquieren uno después del otro. Mientras sólo haya un proceso involucrado, todo funciona sin problemas.

INTRODUCCIÓN A LOS INTERBLOQUEOS

El interbloqueo se puede definir formalmente de la siguiente manera:

Un conjunto de procesos se encuentra en un interbloqueo si cada proceso en el conjunto está esperando un evento que sólo puede ser ocasionado por otro proceso en el conjunto

Debido a que todos los procesos están en espera, ninguno de ellos producirá alguno de los eventos que podrían despertar a cualquiera de los otros miembros del conjunto, y todos los procesos seguirán esperando para siempre.

El evento por el que cada proceso espera es la liberación de algún recurso que actualmente es poseído por otro miembro del conjunto.

El número de procesos y el número de cualquier tipo de recursos poseídos y solicitados es irrelevante. Este resultado se aplica a cualquier tipo de recurso, tanto de hardware como de software. A este tipo de interbloqueo se le conoce como interbloqueo de recursos.

Condiciones para los interbloqueos de recursos

Coffman y colaboradores (1971) mostraron que deben aplicarse cuatro condiciones para un interbloqueo

(De recursos):

|1. Condición de exclusión mutua. Cada recurso se asigna en un momento dado a sólo un proceso, o está disponible.

2. Condición de contención y espera. Los procesos que actualmente contienen recursos que se les otorgaron antes pueden solicitar nuevos recursos.

3. Condición no apropiativa. Los recursos otorgados previamente no se pueden quitar a un proceso por la fuerza. Deben ser liberados de manera explícita por el proceso que los contiene.

4. Condición de espera circular. Debe haber una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso contenido por el siguiente miembro de la cadena.

Las cuatro condiciones deben estar presentes para que ocurra un interbloqueo.

  

Modelado de interbloqueos

Holt (1972) mostró cómo se pueden modelar estas cuatro condiciones mediante el uso de gráficos dirigidos.

Los gráficos tienen dos tipos de nodos: procesos, que se muestran como círculos, y recursos, que se muestran como cuadros. Un arco dirigido de un nodo de recurso (cuadro) a un nodo de proceso (círculo) significa que el recurso fue solicitado previamente por, y asignado a, y actualmente es contenido por ese proceso.

        EL ALGORITMO DE LA AVESTRUZ

El método más simple es el algoritmo de la avestruz: meta su cabeza en la arena y pretenda que no hay ningún problema.† Las personas reaccionan a esta estrategia de diversas formas. Los matemáticos la encuentran totalmente inaceptable y dicen que los interbloqueos se deben prevenir a toda costa; los ingenieros preguntan con qué frecuencia se espera el problema, con qué frecuencia falla el sistema por otras razones y qué tan grave es un interbloqueo. Si ocurren interbloqueos en promedio de una vez cada cinco años, pero los fallos del sistema debido al hardware, errores del compilador y errores en el sistema operativo ocurren una vez por semana, la mayoría de los ingenieros no estarán dispuestos a reducir considerablemente el rendimiento por la conveniencia de eliminar los interbloqueos.

Para que este contraste sea más específico, considere un sistema operativo que bloquea al proceso llamador cuando no se puede llevar a cabo una llamada a los sistemas open en un dispositivo físico, como una unidad de CD-ROM o una impresora, debido a que el dispositivo está muy ocupado.

Por lo general es responsabilidad del driver (controlador) de dispositivos decidir qué acción tomar bajo tales circunstancias. Bloquear o devolver una clave de error son dos posibilidades obvias. Si un proceso abre exitosamente la unidad de CD-ROM y otro la impresora, y después cada proceso trata de abrir el otro recurso y se bloquea en el intento, tenemos un interbloqueo. Pocos sistemas actuales detectarán esto.

DETECCIÓN Y RECUPERACIÓN DE UN INTERBLOQUEO

Una segunda técnica es la detección y recuperación. Cuando se utiliza esta técnica, el sistema no trata de evitar los interbloqueos. En vez de ello, intenta detectarlos cuando ocurran y luego realiza cierta acción para recuperarse después del hecho

Detección de interbloqueos con un recurso de cada tipo sólo existe un recurso de cada tipo. Dicho sistema podría tener un escáner, un grabador de CD, un trazador (plotter) y una unidad de cinta, pero no más que un recurso de cada clase.

Para un sistema así, podemos construir un gráfico de recursos.

Si este gráfico contiene uno o más ciclos, existe un interbloqueo. Cualquier proceso  que forme parte de un ciclo está en interbloqueo. Si no existen ciclos, el sistema no está en interbloqueo.

Como ejemplo de un sistema más complejo que los que hemos analizado hasta ahora, considere un sistema con siete procesos, A a G, y seis recursos, R a W. El estado de cuáles recursos están contenidos por algún proceso y cuáles están siendo solicitados es el siguiente:

1. El proceso A contiene a R y quiere a S.

2. El proceso B no contiene ningún recurso pero quiere a T.

3. El proceso C no contiene ningún recurso pero quiere a S.

4. El proceso D contiene a U y quiere a S y a T.

5. El proceso E contiene a T y quiere a V.

6. El proceso F contiene a W y quiere a S.

7. El proceso G contiene a V y quiere a U.

 

Es relativamente fácil distinguir los procesos en interbloqueo a simple vista a partir de un sencillo gráfico, para usar este método en sistemas reales necesitamos un algoritmo formal para la detección de interbloqueos. Hay muchos algoritmos conocidos para detectar ciclos en gráficos dirigidos. A continuación veremos un algoritmo simple que inspecciona un gráfico y termina al haber encontrado un ciclo, o cuando ha demostrado que no existe ninguno. Utiliza cierta estructura dinámica de datos: L, una lista de nodos, así como la lista de arcos. Durante el algoritmo, los arcos se marcarán para indicar que ya han sido inspeccionados, para evitar repetir inspecciones.

El algoritmo opera al llevar a cabo los siguientes pasos, según lo especificado:

1. Para cada nodo N en el gráfico, realizar los siguientes cinco pasos con N como el nodo inicial.

2. Inicializar L con la lista vacía y designar todos los arcos como desmarcados.

3. Agregar el nodo actual al final de L y comprobar si el nodo ahora aparece dos veces en L.

Si lo hace, el gráfico contiene un ciclo (listado en L) y el algoritmo termina.

4. Del nodo dado, ver si hay arcos salientes desmarcados. De ser así, ir al paso 5; en caso contrario, ir al paso

5. Elegir un arco saliente desmarcado al azar y marcarlo. Después seguirlo hasta el nuevo nodo actual e ir al paso 3.

6. Si este nodo es el inicial, el gráfico no contiene ciclos y el algoritmo termina. En caso contrario, ahora hemos llegado a un punto muerto. Eliminarlo y regresar al nodo anterior; es decir, el que estaba justo antes de éste, hacerlo el nodo actual e ir al paso 3.

Lo que hace este algoritmo es tomar cada nodo en turno, como la raíz de lo que espera sea un árbol, y realiza una búsqueda de un nivel de profundidad en él. Si alguna vez regresa a un nodo que ya se haya encontrado, entonces ha encontrado un ciclo. Si agota todos los arcos desde cualquier nodo dado, regresa al nodo anterior. Si regresa hasta la raíz y no puede avanzar más, el subgráfico que se puede alcanzar desde el nodo actual no contiene ciclos. Si esta propiedad se aplica para todos los nodos, el gráfico completo está libre de ciclos, por lo que el sistema no está en interbloqueo.

Detección del interbloqueo con varios recursos de cada tipo

Cuando existen varias copias de algunos de los recursos, se necesita un método distinto para detectar interbloqueos. Ahora presentaremos un algoritmo basado en matrices para detectar interbloqueos entre n procesos, de P1 a Pn. Hagamos que el número de clases de recursos sea m, con E1 recursos de la clase 1, E2 recursos de la clase 2 y en general, Ei recursos de la clase i (1 ≤i ≤m). E es el vector de recursos existentes. Este vector proporciona el número total de instancias de cada recurso en existencia. Por ejemplo, si la clase 1 son las unidades de cinta, entonces E1 _ 2 significa que el sistema tiene dos unidades de cinta.

En cualquier instante, algunos de los recursos están asignados y no están disponibles. Hagamos que A sea el vector de recursos disponibles, donde Ai proporciona el número de instancias del recurso i que están disponibles en un momento dado (es decir, sin asignar). Si ambas de nuestras unidades de cinta están asignadas, A1 será 0.

Ahora necesitamos dos arreglos: C, la matriz de asignaciones actuales y R, la matriz de peticiones.

La i-ésima fila de C nos indica cuántas instancias de cada clase de recurso contiene Pi en un momento dado. Así Cij es el número de instancias del recurso j que están contenidas por el proceso i. De manera similar, Rij es el número de instancias del recurso j que desea Pi. Estas cuatro estructuras de datos

El algoritmo de detección de interbloqueos se muestra a continuación.

1. Buscar un proceso desmarcado, Pi, para el que la i-ésima fila de R sea menor o igual que A.

2. Si se encuentra dicho proceso, agregar la i-ésima fila de C a A, marcar el proceso y regresar al paso 1.

3. Si no existe dicho proceso, el algoritmo termina.

RECUPERACION DE INTERBLOQUEOS

Un sistema que pretenda recuperarse del interbloqueo, debe invocar a un algoritmo de detección cuando lo considere oportuno.

 Formas de intentar la recuperación:

 Terminación de procesos

 Expropiación de recursos

Terminación de procesos

 Matando a todos los procesos implicados (drástico)

 Matando a uno de los procesos ¿cuál?

 El que más recursos libere

 El que menos tiempo lleve en ejecución...

 Retrocediendo la ejecución de algún proceso (rollback)

 Muy complicado de implementar y necesita que el programa esté diseñado para que pueda retroceder

Expropiación de recursos

 Selección de la víctima

 ¿Qué recursos y de que procesos se expropian?

 Retroceso

 Si expropiamos un recurso de un proceso, ¿qué hacemos con ese proceso?

 En ambos casos (terminación de procesos o expropiación de recursos) hay que tener cuidado de no provocar la inanición de procesos

Recuperación por medio de apropiación

En algunos casos puede ser posible quitar temporalmente un recurso a su propietario actual y otorgarlo a otro proceso. En muchos casos se puede requerir intervención manual, en especial en los sistemas operativos de procesamiento por lotes que se ejecutan en mainframes.

Recuperación a través del retroceso

Realizar puntos de comprobación en un proceso significa que su estado se escribe en un archivo para poder reiniciarlo más tarde. El punto de comprobación no sólo contiene la imagen de la memoria, sino también el estado del recurso; en otras palabras, qué recursos están asignados al proceso en un momento dado.

Para realizar la recuperación, un proceso que posee un recurso necesario se revierte a un punto en el tiempo antes de que haya adquirido ese recurso, para lo cual se inicia uno de sus puntos de comprobación anteriores.

Recuperación a través de la eliminación de procesos

La forma más cruda y simple de romper un interbloqueo es eliminar uno o más procesos. Una posibilidad es eliminar a uno de los procesos en el ciclo.

En este método, el proceso a eliminar se elige con cuidado, debido a que está conteniendo recursos que necesita cierto proceso en el ciclo.

Donde sea posible, es mejor eliminar un proceso que se pueda volver a ejecutar desde el principio sin efectos dañinos.

Un proceso que actualiza una base de datos no siempre se puede ejecutar una segunda vez en forma segura. Si el proceso agrega 1 a algún campo de una tabla en la base de datos, al ejecutarlo una vez, después eliminarlo y volverlo a ejecutar de nuevo, se agregará 2 al campo, lo cual es incorrecto.

CÓMO EVITAR INTERBLOQUEOS

Con la evitación no se tienen reglas estáticas a los procesos, sino que el sistema operativo analiza cada petición de recursos y determina si el sistema quedará en un estado estable o inestable, en este último caso, se deniega la petición, posponiéndola temporalmente.

Conceptos

La evitación se basa en los siguientes conceptos:

Estado de asignación de recursos: Número de recursos asignados, disponibles y máximo de recursos posibles por proceso.

Secuencia segura: Secuencia de finalización de procesos, tal que todos los procesos puedan finalizar exitosamente, iniciando en un determinado estado de asignación de recursos

Estado seguro de asignación de recursos: Estado de asignación de recursos, donde existe al menos una secuencia segura.

Estado inseguro de asignación de recursos: No existe ninguna secuencia segura. Obsérvese, que aunque un estado inseguro no implica que exista interbloqueo, talvez una secuencia determinada de eventos lleve a uno.

Estados seguros e inseguros

Se dice que un estado es seguro si hay cierto orden de programación en el que se puede ejecutar cada proceso hasta completarse, incluso aunque todos ellos solicitaran de manera repentina su número máximo de recursos de inmediato.

Un estado inseguro no es un estado en interbloqueo, la diferencia entre un estado seguro y uno inseguro es que, desde un estado seguro, el sistema puede garantizar que todos los procesos terminarán; desde un estado inseguro, no se puede dar esa garantía.

El algoritmo del banquero para un solo recurso

Dijkstra (1965) ideó un algoritmo de programación que puede evitar interbloqueos; este algoritmo se conoce como el algoritmo del banquero y es una extensión del algoritmo de detección de interbloqueos.

Se modela de la forma en que un banquero de una pequeña ciudad podría tratar con un grupo de clientes a los que ha otorgado líneas de crédito. Lo que hace el algoritmo es comprobar si al otorgar la petición se produce un estado inseguro. Si es así, la petición se rechaza. Si al otorgar la petición se produce un estado seguro, se lleva a cabo.

En la imagen (a) podemos ver cuatro clientes, A, B, C y D, cada uno de los cuales ha recibido un cierto número de unidades de crédito (por ejemplo, 1 unidad es 1K dólares). El banquero sabe que no todos los clientes necesitan su crédito máximo de inmediato, por lo que ha reservado sólo 10 unidades en vez de 22 para darles servicio (en esta analogía, los clientes son procesos, las unidades son, por ejemplo, unidades de cinta, y el banquero es el sistema operativo).

Los clientes hacen sus respectivas labores, pidiendo préstamos de vez en cuando (es decir, solicitando recursos).

Este estado es seguro debido a que, con dos unidades restantes, el banquero puede retrasar cualquier petición excepto la de C, con lo cual deja que C termine y libere todos sus cuatro recursos. Con cuatro unidades a la mano, el banquero puede dejar que D o B tengan las unidades necesarias, y así en lo sucesivo. Considere lo que ocurriría si se otorgara una petición de B por una o más unidades en la (b). Tendríamos la situación de la (c), que es insegura. Si todos los clientes pidieran de manera repentina sus préstamos máximos, el banquero no podría satisfacer a ninguno de ellos, y tendríamos un interbloqueo.

El algoritmo del banquero considera cada petición a medida que va ocurriendo, y analiza si al otorgarla se produce un estado seguro. Si es así, se otorga la petición; en caso contrario, se pospone hasta más tarde. Para ver si un estado es seguro, el banquero comprueba si tiene los suficientes recursos para satisfacer a algún cliente.

El algoritmo del banquero para varios recursos

El algoritmo del banquero se puede generalizar para manejar varios recursos. La figura muestra cómo funciona.

En la figura se muestran dos matrices. La de la izquierda muestra cuántas instancias de cada recurso están asignadas en un momento dado a cada uno de los cinco procesos. La matriz de la derecha muestra cuántos recursos sigue necesitando cada proceso para poder completarse.

Al igual que en el caso con un solo recurso, los procesos deben declarar sus necesidades totales de recursos antes de ejecutarse, por lo que el sistema puede calcular la matriz derecha en cada instante.

Los tres vectores a la derecha de la figura muestran los recursos existentes (E), los recursos poseídos

(P) y los recursos disponibles (A), respectivamente. De E podemos ver que el sistema tiene seis unidades de cinta, tres trazadores, cuatro impresoras y dos unidades de CD-ROM. De éstos, ya hay asignados cinco unidades de cinta, tres trazadores, dos impresoras y dos unidades de CD-ROM.

Ahora se puede declarar el algoritmo para comprobar si un estado es seguro.

1. Buscar una fila R, cuyas necesidades de recursos no satisfechas sean menores o iguales que A. Si no existe dicha fila, el sistema entrará en interbloqueo en un momento dado, debido a que ningún proceso se podrá ejecutar hasta completarse (suponiendo que los procesos mantienen todos los recursos hasta que terminan).

2. Suponer que el proceso seleccionado de la fila solicita todos los recursos que necesita (lo que se garantiza que es posible) y termina. Marcar ese proceso como terminado y agregar todos sus recursos al vector A.

3. Repetir los pasos 1 y 2 hasta que todos los procesos se marquen como terminados (en cuyo caso el estado inicial era seguro) o hasta que no haya ningún proceso cuyas necesidades de recursos se puedan satisfacer (en cuyo caso hay un interbloqueo).

CÓMO PREVENIR INTERBLOQUEOS

Habiendo visto que evitar los interbloqueos es algo en esencia imposible, debido a que se requiere información sobre las peticiones futuras, que no se conocen, ¿cómo evitan los sistemas reales el interbloqueo?

La respuesta es volver a las cuatro condiciones establecidas por Coffman y colaboradores

(1971) para ver si pueden proporcionarnos una pista.

Cómo atacar la condición de exclusión mutua

Concepto de exclusión mutua:

Consiste en que un solo proceso excluye temporalmente a todos los demás para usar un recurso compartido de forma que garantice la integridad del sistema.

Concepto de sección critica:

Es la parte del programa con un comienzo y un final claramente marcados que generalmente contiene la actualización de una o más variables compartidas.

Para que una solución al problema de la exclusión mutua sea válida, se tienen que cumplir una serie de condiciones:

Hay que garantizar la exclusión mutua entre los diferentes procesos a la hora de acceder al recurso compartido. No puede haber en ningún momento dos procesos dentro de sus respectivas secciones críticas.

No se deben hacer suposiciones en cuanto a la velocidad relativa de los procesos en conflicto.

Ningún proceso que esté fuera de su sección crítica debe interrumpir a otro para el acceso a la sección crítica.

Cuando más de un proceso desee entrar en su sección crítica, se le debe conceder la entrada en un tiempo finito, es decir, que nunca se le tendrá esperando en un bucle que no tenga final.

REQUISITOS PARA LA EXCLUSIÓN MUTUA

  

 Sólo un proceso, de todos los que poseen secciones críticas por el mismo recurso compartido, debe tener permiso para entrar en ella en un momento dado.Un proceso que se interrumpe en una sección no crítica debe hacerlo sin interferir con los otros procesos.

  Un proceso no debe poder solicitar acceso a una sección crítica para después ser demorado indefinidamente, no puede permitirse el interbloqueo o la inanición.

 Si ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora.

No se debe suponer sobre la velocidad relativa de los procesos o el número de procesadores.

6  Un proceso permanece en su sección crítica por un tiempo finito.
Una manera de satisfacer los requisitos de exclusión mutua es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente. Tanto si son programas del sistema como de aplicación, los procesos deben coordinarse unos con otros para cumplir la exclusión mutua, sin ayuda del lenguaje de programación o del sistema operativo. Estos métodos se conocen como soluciones por software.

Si podemos evitar que los procesos que contienen recursos esperen por más recursos, podemos eliminar los interbloqueos. Una forma de lograr esta meta es requerir que todos los procesos soliciten todos sus recursos antes de empezar su ejecución. Si completa al proceso se le asignará lo que necesite y podrá ejecutarse hasta completarse. Si uno o más recursos están ocupados, no se asignará nada y el proceso sólo esperará.

Un problema inmediato con este método es que muchos procesos no saben cuántos recursos necesitarán hasta que hayan empezado a ejecutarse. Otro problema es que los recursos no se utilizarán de una manera óptima con este método.

Sin embargo, algunos sistemas de procesamiento por lotes de mainframes requieren que el usuario liste todos los recursos en la primera línea de cada trabajo.

Una manera ligeramente distinta de romper la condición de contención y espera es requerir que un proceso que solicita un recurso libere temporalmente todos los recursos que contiene en un momento dado. Después puede tratar de obtener todo lo que necesite a la vez.

Cómo atacar la condición no apropiativa

Si a un proceso se le ha asignado la impresora y está a la mitad de imprimir su salida, quitarle la impresora a la fuerza debido a que el trazador que necesita no está disponible es algo engañoso como máximo, e imposible en el peor caso. Sin embargo, ciertos recursos se pueden virtualizar para evitar esta situación. Al colocar en una cola de impresión en el disco la salida de la impresora y permitir que sólo el demonio de impresión tenga acceso a la impresora real, se eliminan los interbloqueos que involucran a la impresora, aunque se crea uno para el espacio en disco.

Cómo atacar la condición de espera circular

La espera circular se puede eliminar de varias formas. Una de ellas es simplemente tener una regla que diga que un proceso tiene derecho sólo a un recurso en cualquier momento. Si necesita un segundo recurso, debe liberar el primero.

Otra manera de evitar la espera circular es proporcionar una numeración global de todos los recursos, como se muestra en la figura

Con esta regla, el gráfico de asignación de recursos nunca puede tener ciclos. Veamos por qué es esto cierto para el caso de dos procesos, en la figura (b). Podemos obtener un interbloqueo sólo si A solicita el recurso j y B solicita el recurso i. Suponiendo que i y j sean recursos distintos, tendrán diferentes números. Si i > j, entonces A no puede solicitar a j debido a que es menor de lo que ya tiene. Si i < j, entonces B no puede solicitar a i debido a que es menor de lo que ya tiene. De cualquier forma, el interbloqueo es imposible.

Con más de dos procesos se aplica la misma lógica.

Una variación menor de este algoritmo es retirar el requerimiento de que los recursos se adquieran en una secuencia cada vez más estricta, y simplemente insistir que ningún proceso puede solicitar un recurso menor del que ya contiene.

Los diversos métodos para evitar el interbloqueo se definen en la siguiente imagen:

 

Bloqueo de dos fases

Aunque los métodos para evitar y prevenir los interbloqueos no son muy prometedores en el caso general, para aplicaciones específicas se conocen muchos algoritmos excelentes de propósito especial. Como ejemplo, en muchos sistemas de bases de datos, una operación que ocurre con frecuencia es solicitar bloqueos sobre varios registros y después actualizar todos los registros bloqueados. Cuando hay varios procesos en ejecución al mismo tiempo, hay un peligro real de interbloqueo.

Este método se le conoce como bloqueo de dos fases. El proceso trata de bloquear todos los registros que necesita, uno a la vez.

Si tiene éxito pasa a la segunda fase, realizando sus actualizaciones y liberando los bloqueos. No se realiza ningún trabajo real en la primera fase.

Si durante la primera fase se necesita cierto registro que ya esté bloqueado, el proceso sólo libera todos sus bloqueos e inicia la primera fase desde el principio.

Interbloqueos de comunicaciones

Otro tipo de interbloqueo puede ocurrir en los sistemas de comunicaciones (como las redes), en donde dos o más procesos se comunican mediante el envío de mensajes.

Un arreglo común es que el proceso A envía un mensaje de petición al proceso B, y después se bloquea hasta que B envía de vuelta un mensaje de respuesta. Suponga que el mensaje de petición se pierde. A se bloquea en espera de la respuesta. B se bloquea en espera de una petición para que haga algo. Tenemos un interbloqueo.

Los interbloqueos de comunicación no se pueden evitar mediante el ordenamiento de recursos (ya que no hay ninguno), ni se puede evitar mediante una programación cuidadosa (ya que no hay momentos en los que se puede posponer una petición). Por fortuna hay otra técnica que por lo general se puede utilizar para romper los interbloqueos de comunicación: los tiempos de espera. En la mayoría de los sistemas de comunicación de red, cada vez que se envía un mensaje del que se espera una respuesta, también se inicia un temporizador. Si el temporizador termina su conteo antes de que llegue la respuesta, el emisor del mensaje asume que éste se ha perdido y lo envía de nuevo (una y otra vez, si es necesario). De esta forma se evita el interbloqueo.

Bloqueo activo

Esta estrategia se utiliza a menudo cuando se va a usar la exclusión mutua por un tiempo muy corto, y la sobrecarga de la suspensión es grande en comparación con realizar el trabajo. Considere una primitiva atómica en la que el proceso que llama prueba un mutex y lo sostiene o devuelve una falla.

El bloqueo activo puede ocurrir en formas sorprendentes. En algunos sistemas, el número total de procesos permitidos se determina con base en el número de entradas en la tabla de procesos.

Así, las entradas de la tabla de procesos son recursos finitos. Si una operación fork falla debido a que la tabla está llena, un método razonable para el programa que realiza la operación fork es esperar un tiempo aleatorio y probar de nuevo.

Inanición

Un problema muy relacionado con el interbloqueo y el bloqueo activo es la inanición. En un sistema dinámico, las peticiones de recursos ocurren todo el tiempo. Se necesita cierta política para decidir acerca de quién obtiene qué recurso y cuándo. Esta política, aunque parece razonable, puede ocasionar que ciertos procesos nunca reciban atención, aun cuando no estén en interbloqueo.

Un posible algoritmo de asignación es otorgar la impresora al proceso con el archivo más pequeño a imprimir

Este método maximiza el número de clientes satisfechos y parece razonable. Ahora considere lo que ocurre en un sistema ocupado, cuando un proceso tiene que imprimir un archivo enorme. Cada vez que la impresora esté libre, el sistema buscará y elegirá el proceso con el archivo más pequeño.

La inanición se puede evitar mediante el uso de una política de asignación de recursos del tipo “primero en llegar, primero en ser atendido”. Con este método, el proceso que espere más tiempo será el que se atienda primero. A su debido tiempo, cualquier proceso dado se convertirá en el más antiguo y, por ende, obtendrá el recurso que necesita.