• Author / Uploaded
• charlyred70

Citation preview

Abrazo Mortal

Sistemas Operativos Abrazo mortal CONTENIDOS INTRODUCCIÓN......................................................2 CONDICIONES PARA LA OCURRENCIA DE UN ABRAZO MORTAL........... 2 RECURSOS REUTILIZABLES Y RECURSOS CONSUMIBLES........ 2 RECURSOS COMPARTIDOS Y RECURSOS EXCLUSIVOS........ 5 RECURSOS ÚNICOS Y RECURSOS MÚLTIPLES....................................................... 5 RECURSOS EXPROPIABLES Y RECURSOS NO EXPROPIABLES..........6 GRAFOS DE ASIGNACIÓN DE RECURSOS (GAR)….................................... 7 REPRESENTACIÓN MATRICIAL.....................................................................11 BIBLIOGRAFÍA.................................................................................................15 INTRODUCCIÓN El abrazo mortal, también llamado interbloqueo, deadlock o bloqueo mutuo, se define como el bloqueo permanente de un conjunto de procesos, o hilos, que ya sea compitan entre sí por recursos del sistema o se comunican entre sí. Luego un conjunto de procesos está en un abrazo mortal cuando cada proceso del conjunto está bloqueado esperando por un evento, generalmente la liberación de algún recurso solicitado, que sólo puede generar otro proceso bloqueado del conjunto. Este bloqueo es permanente porque no puede producirse ninguno de los eventos esperados. Para este tipo de problema no existe una solución eficiente.

CONDICIONES PARA LA OCURRENCIA DE UN ABRAZO MORTAL Las condiciones para su ocurrencia fueron descritas por primera vez en 1971 por Edward G. Cofmman, deben cumplirse de forma simultánea y no son totalmente independientes entre ellas. Un abrazo mortal puede ocurrir sólo si se cumplen las condiciones siguientes: 1 EXCLUSIÓN MUTUA Significa que si un proceso posee un conjunto de recursos compartibles estos no pueden ser usados por otro proceso hasta haber tenido todos los recursos necesarios y haber podido usarlos. 2 ESPERA Y RETENCIÓN Mientras un proceso espera la asignación de algún recurso no libera otros recursos que ya tiene asignado. 3 SIN DESALOJO Ningún proceso puede ser forzado a abandonar un recurso que retenga. Es decir que, si un proceso tiene tomados recursos y hay otros recursos que no se le pueden asignar, no se le pueden quitar los que ya tiene asignados.

/1

Abrazo Mortal

4 ESPERA CIRCULAR Se dice que dos o más procesos de una cadena cerrada de procesos están en espera circular de recursos cuando cada proceso tiene asignado un recurso y espera por otro recurso que ya está tomado por el siguiente proceso de la cadena y éste a su vez espera la liberación de otro recurso que también está asignado. Las tres primeras condiciones son necesarias, pero no suficientes, para que exista un abrazo mortal. La cuarta condición es, en realidad, una consecuencia potencial de las tres primeras. Es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en una espera circular irresoluble. Una espera circular irresoluble es, de hecho, la definición de abrazo mortal. La espera circular de la condición 4 es irresoluble porque se mantienen las tres primeras condiciones. Es decir, las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el abrazo mortal. Por ejemplo, la exclusión mutua hace falta para asegurar la consistencia de resultados y la integridad de la base de datos. De forma similar, la expulsión o apropiación no se puede aplicar arbitrariamente y, cuando se encuentran involucrados especialmente recursos de datos, debe estar acompañada de un mecanismo de recuperación y reanudación, que devuelva a un proceso y a sus recursos a un estado previo adecuado, desde el que el proceso pueda finalmente repetir sus acciones. Puede existir un abrazo mortal con estas tres condiciones, pero no puede existir con sólo estas tres condiciones. Para que se produzca un abrazo mortal, se necesita la cuarta condición. RECURSOS REUTILIZABLES Y RECURSOS CONSUMIBLES En principio, se pueden distinguir dos categorías generales de recursos: reutilizables y consumibles. *Un recurso reutilizable es aquél que puede ser usado con seguridad por un proceso y no se agota con el uso. Los procesos obtienen unidades de recursos que liberan posteriormente para que otros procesos las reutilicen. Como ejemplos de recursos reutilizables se tienen los procesadores, canales de E/S, memoria principal y secundaria, dispositivos y estructuras de datos tales como archivos, bases de datos y semáforos. Como ejemplo de interbloqueo con recursos reutilizables, considérense dos procesos que compiten por el acceso exclusivo a un archivo en el disco (D) y a otro en una unidad de cinta (C). El esquema de las acciones sería el siguiente:

El abrazo mortal se produce si cada proceso mantiene en su poder un recurso y pide el otro. Durante la ejecución de estos procesos en un sistema multiprogramado se puede producir un abrazo mortal, ya que se puede llegar a una situación en la que el primer proceso tiene asignada cinta y está bloqueado /2

Abrazo Mortal

esperado por la unidad de disco, mientras que el segundo tiene la unidad de disco, pero está esperando por la cinta. Dado que se trata del primer ejemplo de abrazo mortal que se presenta, se verá a continuación un posible orden de ejecución de los procesos que produciría el abrazo mortal: A: Solicita C B: Solicita D B: Solicita C —> se bloquea puesto que el recurso no está disponible A: Solicita D —> se bloquea ya que el recurso no está disponible Se produce un abrazo mortal. En un sistema monoprocesador, este orden de ejecución entrelazado característico del abrazo mortal se debería a que se producen cambios de contexto en los instantes correspondientes. En un multiprocesador podrán ocurrir simplemente debido a que cada proceso se ejecuta en un procesador diferente. Es interesante resaltar que no todos los posibles órdenes de ejecución de estos dos procesos causarían un interbloqueo. Así, por ejemplo, si el orden de ejecución fuera el siguiente: A: Solicita C A: Solicita D B: Solicita D —> se bloquea puesto que el recurso no está disponible A: Libera D —> se desbloquea B porque el recurso ya está disponible B: Solicita C —> se bloquea puesto que el recurso no está disponible A: Libera C —> se desbloquea B porque el recurso ya está disponible B: Libera C B: Libera D Los dos procesos habrían terminado realizando su labor sin producirse el abrazo mortal. Debe observarse que se debe diferenciar claramente entre el bloqueo de un proceso debido a la falta de un recurso (como ocurre con en las líneas 3 y 5 anteriores) que terminará cuando dicho recurso esté disponible y el abrazo mortal que implica el bloqueo indefinido de los procesos involucrados. Aunque parece que es un problema generado por un error de programación más que de un error del diseño del sistema operativo, lo que ocurre es que se ha visto que el diseño de programas concurrentes es complejo y hace difícil la detección del problema. Una posible estrategia para resolver estos bloqueos mutuos es imponer restricciones en el diseño del sistema sobre el orden en el que se solicitan los recursos. Otro ejemplo de interbloqueo con un recurso reutilizable tiene que ver con las peticiones a memoria principal. Supóngase que el espacio disponible es de 200 KB y la secuencia de peticiones es la siguiente:

El abrazo mortal ocurrirá si ambos procesos continúan hasta su segunda petición. Si la cantidad de memoria que van a solicitar no se conoce con antelación, resulta difícil enfrentarse a este tipo de interbloqueo por medio de /3

Abrazo Mortal

restricciones en el diseño del sistema. La mejor forma de resolver este problema es mediante el uso de memoria virtual. *Los recursos consumibles son aquellos que pueden ser creados, o producidos, y se caracterizan porque dejan de existir cuando son consumidos (“destruidos”) una vez que un proceso los usa. Dentro de esta categoría se encuentran, básicamente, los recursos lógicos relacionados con la comunicación y sincronización de procesos. Algunos ejemplos serían los mensajes, los semáforos, las interrupciones, la información en buffers de E/S. Así, por ejemplo, en el caso de un mensaje, existe un proceso que genera el recurso (el emisor del mensaje) y otro que lo consume cuando lo recibe (el receptor del mensaje). A continuación, se muestra un ejemplo de abrazo mortal con tres procesos que se comunican mediante mensajes. Se ha elegido deliberadamente una situación con tres procesos ya que hasta ahora sólo se habían planteado ejemplos en los que intervenían dos y, como se ha comentado previamente, el abrazo mortal puede afectar un número ilimitado de procesos. Se tiene un sistema de comunicación que proporciona instrucciones para enviar y recibir mensajes en las que se especifica como primer dato el proceso al que se le quiere enviar o del que se quiere recibir, respectivamente, y como segundo dato el mensaje en sí. Además, en este sistema el envío del mensaje no es bloqueante pero la recepción sí lo es. En el ejemplo se considera que se ejecutan en este sistema los siguientes tres procesos:

La ejecución de estos tres procesos produciría un abrazo mortal de los mismos con independencia de cuál sea su orden de ejecución. El proceso C quedaría bloqueado indefinidamente esperando el mensaje de B, ya que éste no lo puede mandar hasta que reciba un mensaje de A que, a su vez, no puede hacerlo porque debe antes recibir un mensaje de C. Cada proceso se queda bloqueado esperando un mensaje que sólo puede enviar otro de los procesos implicados, lo que no puede ocurrir ya que dicho proceso está también bloqueado esperando un mensaje. Es importante resaltar que, en este ejemplo, a diferencia del anterior, se produce el abrazo mortal con independencia del orden en que se ejecuten los procesos. Se trata, por lo tanto, de un abrazo mortal que se podría denominar estructural puesto que se debe a un error en el diseño del patrón de comunicaciones entre los procesos. En una aplicación relativamente compleja, formada por múltiples procesos comunicándose entre sí, pueden ocurrir errores de este tipo que son bastante difíciles de detectar. En un sistema general, los procesos usarán tanto recursos reutilizables como consumibles y. por lo tanto, como se puede apreciar en el siguiente ejemplo, pueden aparecer bloqueos mutuos en los que estén implicados recursos de ambos tipos.

/4

Abrazo Mortal

Si durante la ejecución concurrente de estos dos procesos el proceso B obtiene el recurso, se producirá un abrazo mortal entre los dos procesos, ya que B, nunca recibirá el mensaje puesto que A, está bloqueado esperando que se libere el recurso. Observemos que si, en cambio, fuera el proceso A, el que obtuviera el recurso, no se produciría un abrazo mortal. No hay una solución general eficiente para tratar el problema de los interbloqueos con ambos tipos de recursos debido, principalmente, a las características específicas que presentan los recursos consumibles. Por ello, la exposición se centrará en los recursos reutilizables. Normalmente, no hay límite en el número de recursos consumibles de un tipo en particular. Un proceso productor que no está bloqueado puede liberar cualquier número de recursos consumibles. Seguidamente se muestra otro ejemplo en el que, cuando un proceso adquiere un recurso, éste deja de existir. Sea el siguiente par de procesos:

El abrazo mortal se produce si el receptor se bloquea. Nuevamente, la causa del abrazo mortal es un error de diseño. Estos errores pueden ser bastante sutiles y difíciles de detectar. Es más, puede darse una combinación de sucesos poco habitual que origine el abrazo mortal; así pues, un programa puede funcionar durante un periodo de tiempo considerable, incluso años, antes de que el problema se manifieste. RECURSOS COMPARTIDOS Y RECURSOS EXCLUSIVOS Aunque hasta el momento no se haya expresado explícitamente, se ha estado suponiendo que cuando un proceso está usando un recurso, ningún otro lo puede usar. O sea, se ha considerado que los recursos se usan de forma exclusiva o dedicada. Sin embargo, esto no es así para todos los recursos. Algunos recursos pueden ser usados simultáneamente por varios procesos: son recursos compartidos, Considérese, como ejemplo de recurso de este tipo, un archivo al que pueden acceder simultáneamente múltiples procesos. Como es evidente, los recursos de tipo compartido no se ven afectados por los interbloqueos ya que los procesos que quieran usarlos podrán hacerlo inmediatamente sin posibilidad de quedarse bloqueados. Por tanto, las estrategias de tratamiento de interbloqueos que se detallarán luego no tratarán este tipo de recursos, centrándonos únicamente en los recursos reutilizables de uso exclusivo (a los que también se les denomina recursos reutilizables en serie). Es interesante resaltar que en un sistema pueden existir recursos que tengan ambos modos de uso (compartido y exclusivo). Cuando un proceso quiere usar un recurso de este tipo, debe especificar en su solicitud si desea utilizarlo en modo exclusivo o compartido. El sistema permitirá que varios procesos usen el recurso, si lo hacen todos ellos en modo compartido, pero, sin embargo, sólo permitirá que un único proceso lo use en modo exclusivo. Así, una solicitud de un recurso para su uso en modo compartido se satisfará inmediatamente siempre que el recurso no esté siendo usado en modo exclusivo. En cambio, una solicitud de uso en modo exclusivo sólo se concederá si el recurso no está siendo utilizado en ese momento. /5

Abrazo Mortal

RECURSOS ÚNICOS Y RECURSOS MÚLTIPLES Hasta ahora se consideró que cada recurso es una entidad única. Sin embargo, en un sistema pueden existir múltiples instancias o ejemplares de un determinado recurso. Una solicitud de ese recurso por parte de un proceso podría satisfacerse con cualquier ejemplar de este. Así, por ejemplo, en un sistema en el que haya cinco impresoras, cuando un proceso solicita una impresora, se le podría asignar cualquier unidad que esté disponible. La existencia de múltiples unidades de un mismo recurso también permite generalizar los servicios de solicitud de forma que un proceso pueda pedir simultáneamente varios ejemplares de un recurso. Evidentemente, el número de unidades solicitadas nunca debería ser mayor que el número de unidades existentes. Las soluciones al problema del abrazo mortal que se plantearán serán aplicables a este modelo general en el que existe un conjunto de recursos, cada uno de los cuales está formado por una o más unidades. Obsérvese que, a veces, puede ser discutible si dos elementos constituyen dos instancias de un recurso o se trata de dos recursos diferentes. Incluso distintos usuarios pueden querer tener una visión u otra de los mismos. Considérese, por ejemplo, un equipo que tiene conectadas dos impresoras láser con la misma calidad de impresión, pero tal que una de ellas es algo más rápida. Un usuario puede querer usar indistintamente cualquiera de estas impresoras con lo que preferiría considerarlas como dos ejemplares del mismo recurso. Sin embargo, otro usuario que necesite con urgencia imprimir un documento requeriría verlas como dos recursos separados para poder especificar la impresora más rápida. Lo razonable en este tipo de situaciones sería proporcionar a los usuarios ambas vistas de los recursos, Sin embargo, las soluciones clásicas del abrazo mortal no contemplan esta posibilidad de un doble perfil: o son recursos independientes o son ejemplares del mismo recurso. En este documento, por tanto, se adoptará también esta restricción. A los usuarios de un sistema operativo convencional les puede parecer que este tipo de organización de los recursos no se corresponde con su experiencia de trabajo habitual en la que, generalmente, hay que solicitar una unidad específica de un recurso. Sin embargo, aunque no sea de forma evidente, este tipo de situaciones se dan hasta cierto punto en todos los sistemas operativos. Considérese el caso de la memoria. Se trata de un único recurso con múltiples unidades: cada palabra que forma parte de esta. Cuando un proceso solicita una reserva de memoria de un determinado tamaño, está solicitando el número de unidades de ese recurso que corresponde con dicho tamaño. Obsérvese que en este caso existe una restricción adicional, ya que las unidades asignadas, sean cuales sean, deben corresponder con posiciones de memoria contiguas. Veamos nuevamente un ejemplo de abrazo mortal en el uso de la memoria. Considérese la ejecución de los procesos P y Q, suponiendo que se dispone de 450 KB de memoria.

Si se produce un orden de ejecución tal que se satisfacen las dos primeras solicitudes del primer proceso y la primera del segundo, se produciría un abrazo mortal puesto que la cantidad de memoria libre (50 KB) no es suficiente para cumplir con ninguna de las peticiones pendientes. /6

Abrazo Mortal

Aunque ya se comentó previamente que los recursos consumibles quedaban fuera del alcance de esta exposición, es interesante resaltar que también pueden existir múltiples unidades asociadas a un recurso de este tipo. Así, por ejemplo, un semáforo se puede considerar un recurso consumible que tiene tantas instancias como indica el contador que esté asociado al mismo. RECURSOS EXPROPIABLES Y RECURSOS NO EXPROPIABLES Algunas de las estrategias para el tratamiento del abrazo mortal que se verán en este texto implicarán la expropiación de recursos, o sea, la quita de un recurso a un proceso, mientras éste lo está usando, para otorgárselo a otro proceso. Para evitar la pérdida de información, esta expropiación implica salvar de alguna forma el trabajo que llevaba hecho el proceso con el recurso expropiado. La posibilidad de llevar a cabo esta expropiación de forma relativamente eficiente va a depender de las características específicas del recurso, pudiéndose, por tanto, clasificar los recursos de acuerdo con este criterio. Algunos recursos tienen un carácter no expropiable ya que o bien no es factible esta operación o, en caso de serlo, sería ineficiente, Por ejemplo, no tendría sentido quitarle a un proceso un trazador gráfico cuando lo está usando ya que con ello se perdería todo el trabajo realizado. Otros recursos, sin embargo, pueden expropiarse de manera relativamente eficiente. Consideremos, por ejemplo, el caso de un procesador. Cada vez que se produce un cambio de proceso, el sistema operativo está expropiando el procesador a un proceso para asignárselo a otro. La expropiación de un procesador implicaría únicamente salvar el estado de este en el bloque de control del proceso correspondiente para que así éste pueda seguir ejecutando normalmente cuando se le vuelva a asignar. Debe considerarse que, conceptualmente, el procesador, como cualquier otro recurso reutilizable de uso exclusivo, puede verse implicado en interbloqueos. Supóngase, por ejemplo, una situación en la que existe un proceso que tiene asignada una cinta y está en estado listo para ejecutar (o sea, no tiene asignado el procesador). Si el proceso que está en ejecución (o sea, que tiene asignado el procesador) solicita la cinta, se producirá un abrazo mortal ya que cada proceso necesita un recurso que posee el otro. Este abrazo mortal potencial no ocurre en la práctica ya que, en un sistema multiprogramado, cuando el proceso en ejecución se bloquea, se asigna automáticamente el procesador a otro proceso (gracias al carácter expropiable de este recurso). En los sistemas que utilizan un dispositivo de almacenamiento secundario (generalmente un disco) como respaldo de la memoria principal, como son los sistemas con intercambio o con memoria virtual, el recurso memoria también es expropiable. Cuando se requiera expropiar a un proceso parte o toda la memoria que está usando, se copia el contenido de esta en el dispositivo de respaldo dejándola libre para que pueda usarla otro proceso. El ejemplo de abrazo mortal en el uso de la memoria planteado previamente podría resolverse de esta forma. Observemos que dicha operación de copia tiene un costo asociado que afectará al rendimiento del sistema.

/7

Abrazo Mortal

GRAFOS DE ASIGNACIÓN DE RECURSOS (GAR) Un grafo de asignación de recursos G consiste en un conjunto de nodos ND y un conjunto de aristas AR: G= {{ND}, {AR}}. El GAR es un grafo dirigido que representa el estado del sistema en lo referido a los recursos y los procesos, de forma tal que cada proceso y cada recurso se representa por un nodo o vértice. El conjunto de nodos ND se descompone a su vez en dos subconjuntos disjuntos que se corresponden con los procesos P y los recursos R. Cada recurso R tiene asociado un valor que representa cuántas unidades (instancias) del recurso existen (su inventario). El conjunto de aristas también se descompone en dos subconjuntos que se corresponden con las dos relaciones antes planteadas:  Aristas de asignación que relacionan recursos con procesos. Una arista entre un recurso RJ y un proceso PI indica que el proceso tiene asignada una unidad de dicho recurso.  Aristas de solicitud que relacionan procesos con recursos. Una arista entre un proceso PI y un recurso RJ indica que el proceso está esperando la concesión de una unidad de dicho recurso. Las restricciones de coherencia se implementarían en el grafo de asignación de recursos de la siguiente manera:  Restricción de asignación El número de aristas que salen de un recurso debe ser menor o igual que su inventario,  Restricción de solicitud Se debe cumplir que por cada pareja proceso I y recurso J, el número de aristas de asignación que van de RJ a PI más el número de aristas de solicitud que conectan PI a RJ sea menor o igual que el inventario. Las formas utilizadas para la representación de todos los elementos del grafo que se usarán son las siguientes:

/8

Abrazo Mortal

A partir de la especificación de las primitivas genéricas de solicitud y liberación, se puede analizar cómo afectaría su procesamiento al grafo que representa el estado del sistema. Supóngase que se tiene una solicitud del proceso I de U1 unidades del recurso 1, U2 unidades del recurso 2, etc. Se presentan dos situaciones dependiendo de si todos los recursos pedidos están disponibles o no. Sí no están disponibles, se bloquea el proceso añadiendo al grafo, por cada recurso pedido J, tantas aristas desde el nodo PI hasta RJ como unidades se hayan solicitado (UJ). Cuando el proceso se desbloquee posteriormente, al quedar disponibles todos los recursos requeridos, se eliminarán del grafo todas estas aristas de solicitud y se añadirán las aristas de asignación que en el caso de que los recursos hubiesen estado disponibles desde el principio. Si están disponibles, ya sea desde el principio o posteriormente, se añaden al grafo por cada recurso pedido J tantas aristas desde el nodo RJ como unidades se hayan solicitado (UJ). Supóngase ahora que existe una liberación por parte del proceso I de U1 unidades del recurso 1, U2 unidades del recurso 2, etc. Por cada recurso liberado J se eliminan del grafo tantas aristas desde el nodo R J hasta PI como unidades se hayan dejado libres (UJ). Se debe observar que sólo se añaden aristas en el grafo durante las solicitudes, tanto si se trata de solicitud como de asignación. En cuanto a la eliminación de aristas, en la liberación se quitan aristas de asignación, mientras que las de solicitud se retiran en el desbloqueo de un proceso que realizó una petición. A continuación, se verán dos ejemplos del uso de un grafo de asignación de recursos. En primer lugar, supóngase que, en un sistema con 3 recursos, R1 (2 unidades), R2 (3 unidades) y R3 (2 unidades), se ejecutan tres procesos que realizan la siguiente secuencia de peticiones:  Al proceso P1 se le asignan las 2 unidades del recurso R1 que solicitó.  Al proceso P2 se le asigna la unidad del recurso R2 que pidió.  El proceso P2 solicita 1 unidad del recurso R1. Como el recurso no está disponible se bloquea.  Al proceso P3 se le asigna la unidad del recurso R2 que solicitó. El grafo que representa la situación del sistema después de ejecutarse esta secuencia es el siguiente: ND = {P1, P2, P3, R1(2), R2(3), R3(2)} AR = {(R1(2), P1), (R2(1), P2), (P2, R1(1)), (R2(1), P3)} Para poder entender de forma intuitiva el estado de un sistema es conveniente establecer una representación gráfica del grafo de asignación de recursos. La convención que se suele utilizar es la siguiente:  Cada proceso se representa con un círculo.  Cada recurso con un cuadrado. Dentro del cuadrado que representa a un determinado recurso se dibuja un círculo por cada unidad existente del recurso.  Las aristas de solicitud se representan como arcos que van desde el proceso hasta el cuadrado que representa al recurso, mientras que las aristas de asignación se dibujan como arcos que unen el circulo que representa una unidad determinada del recurso con el proceso correspondiente. Siguiendo esta convención, en la siguiente figura se muestra la representación gráfica correspondiente al grafo del ejemplo anterior.

/9

Abrazo Mortal

Otro ejemplo, supóngase que, en un sistema con 3 recursos: R (1 unidad), S (1 unidad) y T (2 unidades), se ejecutan tres procesos: A, B y C, que realizan la siguiente secuencia de peticiones: Al proceso A se le asigna la unidad del recurso S que solicitó. Al proceso B se le asigna la unidad del recurso R y otra del S que pidió. Al proceso C se le asigna la unidad del recurso T que solicitó El proceso A solicita 1 unidad del recurso R. El proceso B solicita 1 unidad del recurso T. Los conjuntos que representan la situación del sistema después de ejecutarse esta secuencia es el siguiente: ND = {A, B, C, R(1), S(1), T(2)} AR = {(S(1), A), (R(1), B), (S(1), B), (T(1), C), (A, R(1)), (B, T(1))} El grafo de asignación de recursos sería el siguiente:

Analizando el grafo se puede decir que, si el grafo no tiene ciclo alguno no existe abrazo mortal, pero, si el grafo tiene un ciclo puede existir un abrazo mortal. ¿Cómo es posible esto? Si por cada recurso existe solo una instancia entonces, el que el grafo tenga un ciclo implica si o si que existe abrazo mortal. Asimismo, si hay recursos con más de una instancia, pero, los recursos que conforman el ciclo tienen sólo una instancia, entonces los procesos que forman parte del ciclo están en un abrazo mortal. Luego la existencia de un ciclo en un grafo con esas características es condición necesaria y suficiente para que haya un abrazo mortal. Ahora bien, si existen varias instancias por tipo de recurso, la existencia de un ciclo no implica obligatoriamente la existencia de un abrazo mortal. Es decir que, el que haya un ciclo en el grafo es condición necesaria pero no suficiente para la aparición de un abrazo mortal. Continuando con el ejemplo anterior, si el proceso C solicita una instancia del recurso S, se tendría el siguiente grafo……

/10

Abrazo Mortal

en el cual se tienen los siguientes ciclos…

donde los procesos A, B y C están en un abrazo mortal. Sin embargo, en el siguiente grafo, que también presenta un ciclo…

no existe ningún abrazo mortal porque en algún momento el proceso D liberará la instancia del recurso S que tiene asignada haciendo desaparecer así el ciclo. En definitiva, si un grafo de asignación de recurso no tiene un ciclo, entonces el sistema no está en un abrazo mortal, mientras que, si tiene un ciclo, entonces el sistema puede o no estar en un abrazo mortal. Por el contrario, el siguiente grafo está mostrando un ejemplo de espera circular, condición imprescindible para que exista un abrazo mortal, marcando con las flechas en rojo el ciclo correspondiente.

En el mismo se tiene una única unidad de los recursos R, S y T. El proceso A retiene la unidad del recurso T y solicita una unidad del recurso R mientras que, el proceso B retiene la única unidad de R y pide una unidad de /11

Abrazo Mortal

S, por último, el proceso C retiene la unidad del recurso S y solicita una unidad del recurso T. Por el contrario, si se mantienen las mismas asignaciones y solicitudes, en el siguiente grafo no existirá abrazo mortal porque hay disponibles varias unidades, o instancias, de cada recurso.

REPRESENTACIÓN MATRICIAL Una forma alternativa de representar esta información es mediante el uso de matrices. Para representar el estado del sistema se usan dos matrices: una matriz de solicitud S y una de asignación A. Además, por cada recurso se debe guardar el número de unidades existentes del mismo: un vector VR que contiene el inventario de cada recurso. Siendo n el número de procesos existentes (o sea n =│N│) y m el número de recursos diferentes que hay en el sistema (o sea, m =│M│). El significado de las estructuras de datos es el siguiente:  Matriz de asignación MA, de dimensión n x m. La componente MAIJ de la matriz especifica cuántas unidades del recurso J están asignadas al proceso I.  Matriz de solicitud MS, de dimensión n x m. La componente MSIJ de la matriz especifica cuántas unidades del recurso J está esperando el proceso I que se le concedan.  Vector de recursos existentes VR, de dimensión m. La componente VRI especifica cuantas unidades del recurso I existen. En este tipo de representación, las restricciones de coherencia del sistema implicarían lo siguiente:  Restricción de asignación Se debe cumplir para cada recurso I que la suma de la columna J de la matriz MA (ΣMAIJ, para I = 1, ..., n) sea menor o igual que el número de unidades existentes de dicho recurso (VRJ).  Restricción de solicitud Se tiene que verificar para cada proceso I y recurso J la siguiente expresión MAIJ + MSIJ