Bloqueos

1. Introducción y Ejemplos de Bloqueo (o Interbloqueo)
2. Conceptos de Recursos
3. Bloqueos y Condiciones Necesarias Para el Bloqueo
4. Modelación de Bloqueos
5. Areas Principales en la Investigación de Bloqueos
6. El Algoritmo del Avestrúz o de Ostrich
7. Detección de Bloqueos
1. Gráficas de Asignación de Recursos
2. Reducción de Gráficas de Asignación de Recursos
3. Detección de Bloqueos de Forma “Un Recurso de Cada Tipo”
4. Detección de Bloqueos de Forma “Varios Recursos de Cada Tipo”
5. Cuándo Buscar los Bloqueos
8. Recuperación de Bloqueos
1. Recuperación Mediante la Apropiación
2. Recuperación Mediante Rollback
3. Recuperación Mediante la Eliminación de Procesos
9. Evasión de Bloqueos
1. Trayectorias de Recursos
2. Estados Seguros e Inseguros
3. El Algoritmo del Banquero (de Dijkstra) Para Solo Un Recurso
4. El Algoritmo del Banquero (de Dijkstra) Para Varios Recursos
5. Asignación de Recursos por el Algoritmo del Banquero
6. Debilidades del Algoritmo del Banquero
10. Prevención de Bloqueos
1. Prevención de la Condición de Exclusión Mutua
2. Prevención de la Condición “detenerse y esperar” o “espera por”
3. Prevención de la Condición de “no apropiación”
4. Prevención de la Condición de “espera circular”
11. Otros Aspectos
1. Cerradura de Dos Fases
2. Bloqueos Sin Recursos
3. Inanición
12. Tendencias del Tratamiento del Bloqueo
13. Fin

 

Un proceso dentro de un sistema de multiprogramación está en un estado de interbloqueo (o interbloqueado) si está esperando por un evento determinado que no ocurrirá [7, Deitel].

Cuando los recursos son compartidos entre usuarios:

• Pueden producirse interbloqueos en los cuales los procesos de algunos usuarios nunca podrán llegar a su término.
• Se debe considerar la prevención, evitación, detección y recuperación del interbloqueo y la postergación indefinida, que se da cuando un proceso, aunque no esté interbloqueado, puede estar esperando por un evento que probablemente nunca ocurrirá.
• En algunos casos:
• El precio de liberar interbloqueos en un sistema es demasiado alto.
• Permitir el interbloqueo podría resultar catastrófico.

• Ej.: impresoras, unidades de cinta, espacio de la tabla de nodos-i.
• Los S. O. tienen la capacidad de otorgar temporalmente a un proceso el acceso exclusivo a ciertos recursos.
• Frecuentemente un proceso necesita el acceso exclusivo no solo a un recurso, sino a varios.

• Dos procesos desean imprimir grandes archivos en cinta.
• El proceso “a” solicita la impresora, que se le concede.
• El proceso “b” solicita la unidad de cinta, que se le concede.
• El proceso “a” solicita la unidad de cinta, pero se deniega la solicitud hasta que “b” la libera.
• El proceso “b” solicita la impresora y se produce el bloqueo (deadlock).

Tiene similitud con el congestionamiento del tránsito en las ciudades.

El tráfico puede detenerse completamente.

Es necesaria una intervención externa para poner orden y restablecer la normalidad.

Ejemplo de interbloqueo de un recurso simple:

Tiene su origen en la contención normal de los recursos dedicados o reutilizables en serie:

• Pueden ser utilizados por un solo usuario a la vez.
• Cada proceso está esperando por el otro para liberar uno de los recursos.
• El recurso retenido no será liberado hasta que el otro proceso usuario libere su recurso.
• Este último proceso usuario no liberará su recurso retenido hasta que el primer proceso usuario libere su recurso retenido.
• Se produce una espera circular (ver Figura 6.1 [7, Deitel]).

Ejemplo de interbloqueo en sistemas de spool:

Un sistema de spool es utilizado para incrementar la capacidad de ejecución del sistema, al disasociar un programa de la lenta velocidad de los dispositivos (ej.: impresoras):

• Si un programa envía líneas a una impresora, en realidad son enviadas a un dispositivo más rápido (disco).
• Se almacenan temporalmente hasta ser impresas.

• Se reduce la probabilidad de interbloqueos del spool:
• Proporcionando un espacio en disco considerablemente mayor que el necesario, preferentemente con asignación dinámica.
• Limitando los spoolers de entrada para que no lean más trabajos cuando los archivos de spool llegan a cierto nivel de saturación.

Es posible que un proceso sea postergado indefinidamente en tanto que otros reciben la atención del sistema:

• Se trata de la postergación indefinida.
• Cuando los recursos son planificados en función de prioridades, un proceso dado puede esperar indefinidamente, mientras sigan llegando procesos de prioridades mayores.

Inicio:   Fin:

Conceptos de Recursos

El S. O. es, sobre todo, un administrador de recursos [7, Deitel].

Los recursos pueden ser “apropiativos”, como la cpu y la memoria principal.

La apropiatividad es extremadamente importante para el éxito de los sistemas computacionales multiprogramados.

Ciertos recursos son “no apropiativos”, como las unidades de cinta o cartridge magnéticos, o sea que no pueden sacarse de los procesos a los que están asignados.

Algunos recursos:

• Pueden ser compartidos entre varios procesos.
• Pueden estar dedicados a procesos individuales.

• Se carga una copia del código a memoria.
• Se habilitan varias copias de las estructuras de datos, una para cada usuario.
• Como el código puede ser utilizado por varios usuarios a la vez, no puede cambiar durante la ejecución:
• El código que no cambia durante la ejecución se denomina reentrante.
• El código que puede ser cambiado, pero se inicializa cada vez que se usa, se denomina reutilizable en serie.

El código reutilizable en serie puede ser usado solo por un proceso a la vez.

Cuando se consideran compartidos a determinados recursos, se debe establecer si son utilizables por varios procesos simultáneamente o de a uno por vez, estos últimos son los recursos que más a menudo están implicados en los interbloqueos.

Inicio:   Fin:

Bloqueos y Condiciones Necesarias Para el Bloqueo

La secuencia de eventos necesarios para utilizar un recurso es la siguiente [23, Tanenbaum]:

1. Solicitar el recurso.
2. Utilizar el recurso.
3. Liberar el recurso.

• El proceso solicitante debe esperar.
• En algunos S. O. el proceso se bloquea automáticamente y se despierta cuando dicho recurso está disponible.
• En otros S. O. la solicitud falla y el proceso debe esperar para luego intentar nuevamente.

• Un conjunto de procesos se bloquea si cada proceso del conjunto espera un evento que solo puede ser provocado por otro proceso del conjunto[23, Tanenbaum]:
• Ya que todos los procesos están esperando:
• Ninguno realizará un evento que pueda despertar a los demás miembros del conjunto.
• Todos los procesos esperarán por siempre.
• Generalmente el evento que espera cada proceso es la liberación de cierto recurso que posee por el momento otro miembro del conjunto:
• Cada miembro del conjunto de procesos bloqueados espera un recurso poseído por un proceso bloqueado.
• Ninguno de los procesos bloqueados puede continuar su ejecución, ni liberar recursos, ni puede ser despertado.

• Los procesos reclaman control exclusivo de los recursos que piden (condición de exclusión mutua).
• Los procesos mantienen los recursos que ya les han sido asignados mientras esperan por recursos adicionales (condición de espera por).
• Los recursos no pueden ser extraídos de los procesos que los tienen hasta su completa utilización (condición de no apropiatividad).
• Existe una cadena circular de procesos en la que cada uno mantiene a uno o más recursos que son requeridos por el siguiente proceso de la cadena (condición de espera circular).

Inicio:   Fin:

Modelación de Bloqueos

La modelación de bloqueos se puede mostrar mediante gráficas dirigidas (Holt) (ver Figura 6.2 [23, Tanenbaum]).

Las gráficas tienen dos tipos de nodos:

• Procesos (aparecen como círculos).
• Recursos (aparecen como cuadrados).
• Un arco de un nodo de recurso a uno de proceso indica que el recurso fue solicitado con anterioridad, fue otorgado y es poseído en ese momento por dicho proceso.
• Un arco de un proceso a un recurso indica que el proceso está bloqueado, en espera de ese recurso.
• Un ciclo en la gráfica indica la existencia de un bloqueo relacionado con los procesos y recursos en el ciclo (ver Figura 6.3 y Figura 6.4 [23, Tanenbaum]).

Las estrategias utilizadas para enfrentar los bloqueos son:

• Ignorar todo el problema.
• Detección y recuperación.
• Evitarlos dinámicamente mediante una cuidadosa asignación de recursos.
• Prevención mediante la negación estructural de una de las cuatro condiciones necesarias.

Inicio:   Fin:

Areas Principales en la Investigación de Bloqueos

Los principales aspectos son los siguientes [7, Deitel]:

• Prevención del bloqueo.
• Evitación del bloqueo.
• Detección del bloqueo.
• Recuperación del bloqueo.

• El interés se centra en condicionar un sistema para que elimine toda posibilidad de que éstos se produzcan.
• Los métodos pueden dar como resultado una pobre utilización de los recursos, aún así son ampliamente utilizados.

• La meta es imponer condiciones menos estrictas que en la prevención, para intentar lograr una mejor utilización de los recursos.
• No precondiciona al sistema para que evite todas las posibilidades de que se produzca un bloqueo.
• Permiten la aparición del bloqueo, pero siempre que se produce una posibilidad de bloqueo, éste se esquiva.

• Se utiliza en sistemas que permiten que éstos ocurran, ya sea voluntaria o involuntariamente.
• La meta es determinar si ha ocurrido un bloqueo:
• Se debe detectar con precisión los procesos y recursos implicados en el bloqueo.
• Se puede eliminar el bloqueo detectado.

• Se utiliza para despejar bloqueos de un sistema para que:
• Continúe operando sin ellos.
• Terminen los procesos estancados.
• Se liberen los recursos correspondientes a ellos.
• Generalmente se logra “extrayendo” (cancelando) a uno o varios de los procesos bloqueados, que se reinician luego de forma normal.

Inicio:   Fin:

El Algoritmo del Avestrúz o de Ostrich

El punto de vista más simple es pretender que no existe el problema [23, Tanenbaum].

Esta estrategia puede generar distintas reacciones:

• Matemáticamente es inaceptable, considerándose que los bloqueos deben evitarse a toda costa.
• Desde la ingeniería de software podría considerarse cuál es la frecuencia esperada del problema, cuáles son sus consecuencias esperadas, cuáles son las frecuencias esperadas de fallas de otro tipo, etc.

Los S. O. que ignoran el problema de los bloqueos asumen la siguiente hipótesis:

• La mayoría de los usuarios preferiría un bloqueo ocasional, en vez de una regla que restringiera a todos los usuarios en el uso de los distintos tipos de recursos.

• En restricciones para los procesos.
• En el uso de recursos.

Es muy difícil encontrar teóricamente soluciones prácticas de orden general aplicables a todos los tipos de S. O.

Un criterio de orden general utilizado por los S. O. que no hacen tratamiento específico del bloqueo consiste en:

• Intentar acceder al recurso compartido.
• De no ser factible el acceso:
• Esperar un tiempo aleatorio.
• Reintentar nuevamente.

Inicio:   Fin:

Detección de Bloqueos

El S. O. no intenta evitar los bloqueos [23, Tanenbaum]:

• Intenta detectar cuando han ocurrido.
• Acciona para recuperarse después del hecho.

• Determinar si de hecho existe o no un bloqueo.
• Identificar cuáles son los procesos y recursos implicados en el bloqueo.

Inicio:   Fin:

Gráficas de Asignación de Recursos

Una gráfica dirigida indica las asignaciones y peticiones de recursos.

Los cuadros representan procesos.

Los círculos grandes indican clases de recursos idénticos.

Los círculos pequeños, dibujados dentro de los grandes, representan el número de recursos idénticos dentro de cada clase (ver Figura 6.5 [7, Deitel]).

Inicio:   Fin:

Reducción de Gráficas de Asignación de Recursos

Si las peticiones de recursos de un proceso pueden ser concedidas, se dice que una gráfica puede ser reducida por ese proceso.

La reducción de una gráfica por un proceso determinado se muestra retirando:

• Las flechas que van de los recursos al proceso (los recursos asignados al proceso).
• Las flechas que van del proceso al recurso (las peticiones actuales del proceso).

Si una gráfica no puede ser reducida por todos sus procesos, entonces los procesos “irreducibles” constituyen la serie de procesos interbloqueados de la gráfica (ver Figura 6.6 [7, Deitel]).

Inicio:   Fin:

Detección de Bloqueos de Forma “Un Recurso de Cada Tipo”

No se dispone de más de un objeto de cada clase de recurso.

Si la gráfica de recursos contuviera uno o más ciclos, existiría un bloqueo.

Cualquier proceso que forme parte de un ciclo está bloqueado; si no existen ciclos, el sistema no está bloqueado.

Ejemplo: sistema con 7 (siete) procesos (“A” a “G”) y 6 (seis) recursos (“R” a “W”):

• La posesión de los recursos es la siguiente:
• El proceso A posee a R y desea a S.
• El proceso B no posee recurso alguno y desea a T.
• El proceso C no posee recurso alguno y desea a S.
• El proceso D posee a U y desea a S y a T.
• El proceso E posee a T y desea a V.
• El proceso F posee a W y desea a S.
• El proceso G posee a V y desea a U.
• La pregunta es: ¿está bloqueado este sistema y, en tal caso, cuáles son los procesos bloqueados?.
• La respuesta se obtiene mediante la gráfica de recursos: si la gráfica presenta un ciclo significa procesos bloqueados (ver Figura 6.7 [23, Tanenbaum]).

Se hace necesario un algoritmo formal para la detección de bloqueos que se pueda utilizar en los sistemas reales.

Ejemplo de algoritmo aplicable a cada nodo “N” de la gráfica:

1. Se considera a “N” como nodo inicial.
2. Se inicializan:
• La estructura de datos “L”como una lista vacía.
• Todos los arcos como no marcados.
3. Se añade el nodo activo al final de “L” y se verifica si el nodo aparece en “L” dos veces:
• Si aparece dos veces existe un ciclo y el algoritmo termina.
4. Desde el nodo dado se verifica si existen arcos que salgan de dicho nodo y no estén marcados:
• En caso afirmativo se va al paso 5.
• En caso negativo se va al paso 6.
5. Se elige al azar un arco de salida no marcado y se le marca:
• Luego se sigue este arco hasta el nuevo nodo activo y se regresa al paso 3.
6. Se ha llegado a un punto donde no se puede continuar:
• Se regresa al nodo anterior, es decir al que estaba activo antes del actual.
• Se señala de nuevo como nodo activo.
• Se pasa al paso 3.
• Si este nodo era el nodo inicial, la gráfica no contiene ciclos y el algoritmo termina.

• Se parte de “R” y se inicializa “L” como la lista vacía.
• Se añade “R” a la lista y se mueve a la única posibilidad, “A”.
• Se añade “A” a la lista: L=[R,A].
• Se pasa de “A” a “S”, quedando L=[R,A,S].
• “S” no tiene arcos que salgan de él, por lo que no se puede continuar y se regresa a “A”.
• Ya que “A” no tiene arcos de salida no marcados se regresa a “R”, finalizando la inspección de “R”.
• Se inicia nuevamente el algoritmo partiendo de “A”, siendo “L” otra vez la lista vacía.
• La búsqueda termina rápidamente y se parte de “B”.
• De “B” se siguen los arcos de salida hasta llegar a “D”, siendo L=[B,T,E,V,G,U,D].
• Se efectúa una elección al azar.
• Si se elige “S” llegamos a un punto sin salida y debemos regresar a “D”.
• La segunda vez se elige “T” quedando L=[B,T,E,V,G,U,D,T] :
• Se ha descubierto un ciclo y el algoritmo se detiene.

Inicio:   Fin:

Detección de Bloqueos de Forma “Varios Recursos de Cada Tipo”

Se considera un algoritmo basado en matrices para la detección de un bloqueo entre “n” procesos, “P₁” hasta “P_n”.

Se considera “m” el número de clases de recursos con:

• E₁ recursos de la clase 1.
• E₂ recursos de la clase 2.
• E_i recursos de la clase “i” (1 menor o igual que “i ” menor o igual que “m”).
• “E” es el vector de recursos existentes.

Se considera un vector “A” de recursos disponibles:

• “A_i” indica el número de instancias disponibles del recurso “i ” ; se refiere a recursos no asignados.

• La matriz “C” de la asignación actual.
• La matriz “R” de solicitudes.

“Cij ”  es el número de instancias del recurso“ j” deseadas por “P_i”.

Cada recurso está asignado o disponible, es decir que la suma de las instancias del recurso “j ” asignadas y el número de instancias disponibles es el número de instancias existentes de esa clase de recurso [23, Tanenbaum].

El algoritmo de detección de bloqueos se basa en la comparación de vectores:

• Definimos que “A” es menor o igual que “B” si y solo si “A_i”es menor o igual que “B_i” para “i” entre “0” y “m”, ambos inclusive.

Al avanzar el algoritmo los procesos se marcarán:

• Esto indica que pueden terminar su labor, ya que no están bloqueados.
• Al concluir el algoritmo se sabe que los procesos no marcados estarán bloqueados.

1. Se busca un proceso no marcado “P_i” , para el cual el i -ésimo renglón de “R” sea menor que “A”.
2. Si se encuentra tal proceso, se suma el i -ésimo renglón de “C” a “A”, se marca el proceso y se regresa al paso 1.
3. Si no existe tal proceso, el algoritmo termina.

El proceso 1 tiene 1 impresora.

El proceso 2 tiene 2 unidades de cinta y 1 unidad de cd rom.

El proceso 3 tiene 1 plotter y 2 impresoras.

La matriz “R” indica las necesidades de recursos adicionales.

El algoritmo de detección de bloqueos busca un proceso cuya solicitud de un recurso pueda ser satisfecha:

• El proceso 1 no se puede satisfacer por no disponer de una unidad de cd rom.
• El proceso 2 no se puede satisfacer por no disponer de una impresora.
• El proceso 3 sí se puede satisfacer, por lo que se ejecuta, regresando en cierto momento sus recursos, lo que resulta en: A = (2 2 2 0).

Se ejecuta el proceso restante: no existe bloqueo en el sistema.

Si se considera la siguiente variante:

• El proceso 2 necesita 1 unidad de cd rom, las 2 unidades de cinta y el plotter.
• No se pueden satisfacer las 3 solicitudes y todo el sistema se bloquea.

Inicio:   Fin:

Cuándo Buscar los Bloqueos

Una posibilidad es cada vez que se solicita un recurso, pero esto podría sobrecargar al sistema.

Otra posibilidad es verificar cada k minutos.

Otro criterio es verificar cuando el uso de la cpu baje de cierto valor fijo:

• Si se bloquean suficientes procesos:
• Existirán pocos procesos en ejecución.
• La cpu estará inactiva con más frecuencia.

Inicio:   Fin:

Recuperación de Bloqueos

Para romper el bloqueo de un sistema hay que anular una o más de las condiciones necesarias para el bloqueo [7, Deitel].

Normalmente, varios procesos perderán algo o todo lo realizado hasta el momento.

Los principales factores que dificultan la recuperación del bloqueo son los siguientes:

• Puede no estar claro si el sistema se ha bloqueado o no.
• Muchos sistemas tienen limitaciones para suspender un proceso por tiempo indefinido y reanudarlo más tarde:
• Ej.: Los procesos de tiempo real, que deben funcionar continuamente, no son fáciles de suspender y reanudar.
• Los procedimientos de suspensión / reanudación implican una sobrecarga considerable.
• La sobrecarga de recuperación está en función de la magnitud del bloqueo (algunos, decenas o centenas de procesos involucrados).

• Retirando forzosamente (cancelando) a un proceso.
• Reclamando sus recursos.
• Permitiendo que los procesos restantes puedan finalizar.

• Pueden no existir las prioridades de los procesos bloqueados.
• Las prioridades instantáneas (en un momento dado), pueden ser incorrectas o confusas debido a consideraciones especiales, por ej.: procesos de baja prioridad que tienen prioridad alta momentáneamente debido a un tiempo tope inminente.
• La decisión óptima puede requerir un gran esfuerzo.

• Recuperación mediante la apropiación.
• Recuperación mediante rollback.
• Recuperación mediante la eliminación de procesos.

Inicio:   Fin:

Recuperación Mediante la Apropiación

En ciertos casos podría ser posible tomar un recurso temporalmente de su poseedor y dárselo a otro proceso, por ej.:

• Retirar una impresora de un proceso para dedicarla a otro proceso.
• Retomar luego el primer proceso reasignándola al mismo.

La elección del proceso a suspender depende mucho:

• De cuáles procesos poseen recursos que pueden ser tomados con facilidad.
• De las posibilidades de recuperación luego de la apropiación.

Inicio:   Fin:

Recuperación Mediante Rollback

En los S. O. donde es posible que ocurran bloqueos se puede hacer que los procesos sean verificados periódicamente:

• Su estado se graba en un archivo de modo que pueda volver a iniciar más tarde.
• El punto de verificación o de control contiene:
• La imagen de la memoria.
• El estado de los recursos, es decir, el detalle de los recursos asignados al proceso en ese instante.
• Los puntos de verificación grabados durante un proceso se mantienen sin ser regrabados.

Para la recuperación, un proceso que posee un recurso necesario regresa hasta cierto instante en el tiempo anterior a la adquisición:

• Inicializa alguno de sus anteriores puntos de verificación.
• El proceso regresa a un momento anterior en el que no poseía el recurso.
• El recurso se asigna ahora a uno de los procesos bloqueados.
• Si el proceso que volvió a iniciar intenta adquirir de nuevo el recurso, tendrá que esperar hasta que esté disponible.

Inicio:   Fin:

Recuperación Mediante la Eliminación de Procesos
 

• Es la forma más sencilla de romper un bloqueo.
• Una posibilidad es eliminar un proceso del ciclo: si el bloqueo no se rompe, se puede intentar con otro proceso del ciclo, hasta romper dicho ciclo.
• Otra posibilidad es eliminar un proceso que no esté en el ciclo, para poder liberar sus recursos: debe elegirse un proceso que posea recursos necesarios por algún proceso del ciclo.
• Siempre que sea posible, es mejor eliminar un proceso que pueda volver a iniciar su ejecución sin efectos dañinos:
• Es preferible eliminar un proceso de compilación que un proceso de actualización de una base de datos:
• La compilación se puede repetir sin problemas.
• La actualización de una base de datos no siempre se puede repetir directamente.

Inicio:   Fin:

Evasión de Bloqueos

En este análisis se supone implícitamente que si un proceso solicita recursos, los solicita todos al mismo tiempo [23, Tanenbaum]:

• En la mayoría de los sistemas los recursos se solicitan uno a la vez.
• El S. O. debe poder:
• Decidir si el otorgamiento de un recurso es seguro o no.
• Asignarlo solo en caso de que sea seguro.

Inicio:   Fin:

Trayectorias de Recursos

Los principales algoritmos para evitar los bloqueos se basan en el concepto de estados seguros (ver Figura 6.9 [23, Tanenbaum]).

El ejemplo de modelo gráfico utilizado indica lo siguiente:

• Es válido para dos procesos y dos recursos.
• El eje horizontal representa el número de instrucciones ejecutadas por el proceso “A”.
• El eje vertical representa el número de instrucciones ejecutadas por el proceso “B”.
• En “I1”; “A” solicita una impresora y en “I 2” necesita un plotter.
• En “I 3” e “I 4” se liberan la impresora y el plotter.
• El proceso “B” necesita el plotter desde “I5” hasta “I7” y la impresora desde “I6” hasta “I8”.
• Cada punto del diagrama representa un estado conjunto de los dos procesos.
• El estado inicial es “p”, sin que los procesos hayan ejecutado instrucción alguna.
• Si el planificador del S. O. elige “A” se pasa a “q”, en donde “A” ha ejecutado instrucciones pero no “B”.
• En “q” la trayectoria se vuelve vertical, ya que el planificador ha elegido ejecutar “B”.
• Con un monoprocesador todas las trayectorias serán horizontales o verticales (no diagonales).
• Cuando “A” cruza la línea “I1” en la trayectoria de “r” a “s”, solicita y se le otorga la impresora.
• Cuando “B” alcanza el punto “t”, solicita el plotter.
• La región delimitada por “I 1”, “I 3”, “I6” e “I 8” representa que ambos procesos poseen la impresora, pero esto es imposible y la regla de exclusión mutua impide la entrada a esta región.
• La región delimitada por “I 2”, “I 4”, “I 5” e “I 7” representa que ambos procesos poseen el plotter, lo que es imposible.
• Si el sistema ingresara a la región delimitada por “I 1”, “I 2”, “I 5” e “I 6” se bloqueará en la intersección de “I 2” e “I 6”:
• Acá, “A” solicita el plotter y “B” la impresora, que ya están asignados.
• Toda la región no es segura y no hay que entrar a ella:
• En “t”, lo único seguro es ejecutar “A” hasta llegar a “I 4”.
• Luego se puede utilizar cualquier trayectoria hasta “u”.
• En “t”, “B” solicita un recurso:
• El S. O. debe decidir si lo otorga o no.
• Si lo otorga, el sistema entrará a una región insegura y se bloqueará en algún momento.
• Para evitar el bloqueo, hay que suspender a “B” hasta que “A” haya solicitado y liberado el plotter.

Inicio:   Fin:

Estados Seguros e Inseguros

Un estado actual está conformado por “E”, “A”, “C” y “R”:

• “E”: vector de recursos en existencia.
• “A”: vector de recursos disponibles.
• “C”: matriz de asignación actual.
• “R”: matriz de solicitudes.

• No está bloqueado.
• Existe una forma de satisfacer todas las solicitudes pendientes, mediante la ejecución de los procesos en cierto orden.

El estado es seguro ya que existe una sucesión de asignaciones que permiten terminar a todos los procesos; dicha sucesión de asignaciones es la siguiente (ver Tabla 6.1 [23, Tanenbaum]:

Ejemplo con un recurso para mostrar un estado inseguro (ver Tabla 6.2 [7, Deitel]):

• No se puede garantizar que terminen los tres procesos.
• Si el proceso “A” pide y se le otorga una unidad, puede producirse un bloqueo de tres vías si cada uno de los procesos necesita al menos otra unidad del recurso antes de liberar ninguna.

• No implica la existencia, ni siquiera eventual, de bloqueo.
• Sí implica que alguna secuencia infortunada de eventos dé como resultado un bloqueo.

• A partir de un estado seguro, el sistema puede garantizar la conclusión de todos los procesos.
• A partir de un estado inseguro, no existe tal garantía.

• Dado un estado actual seguro, ello no implica que vayan a ser seguros todos los estados futuros.

Inicio:   Fin:

El Algoritmo del Banquero (de Dijkstra) Para Solo Un Recurso

Es un algoritmo de planificación que puede evitar los bloqueos [23, Tanenbaum].

En la analogía:

• Los clientes son los procesos, las unidades de crédito son los recursos del sistema y el banquero es el S. O.
• El banquero sabe que no todos los clientes necesitaran su crédito máximo otorgado en forma inmediata, por ello reserva menos unidades (recursos) de las totales necesarias para dar servicio a los clientes.

El algoritmo del banquero consiste en:

• Estudiar cada solicitud al ocurrir ésta.
• Ver si su otorgamiento conduce a un estado seguro:
• En caso positivo, se otorga la solicitud.
• En caso negativo, se la pospone.
• Para ver si un estado es seguro:
• Verifica si tiene los recursos suficientes para satisfacer a otro cliente:
• En caso afirmativo, se supone que los préstamos se pagarán.
• Se verifica al siguiente cliente cercano al límite y así sucesivamente.
• Si en cierto momento se vuelven a pagar todos los créditos, el estado es seguro y la solicitud original debe ser aprobada.

Inicio:   Fin:

El Algoritmo del Banquero (de Dijkstra) Para Varios Recursos

Acá también los procesos deben establecer sus necesidades totales de recursos antes de su ejecución y dada una matriz de recursos asignados, el S. O. debe poder calcular en cualquier momento la matriz de recursos necesarios (ver Tabla 6.4 [23, Tanenbaum]).

Se dispone de:

• “E”: vector de recursos existentes.
• “P”: vector de recursos poseídos.
• “A”: vector de recursos disponibles.

1. Se busca un renglón “R” cuyas necesidades de recursos no satisfechas sean menores o iguales que “A”:
• Si no existe tal renglón, el sistema se bloqueará en algún momento y ningún proceso podrá concluirse.
2. Supongamos que el proceso del renglón elegido solicita todos los recursos que necesita y concluye:
• Se señala el proceso como concluido y se añaden sus recursos al vector “A”.
3. Se repiten los pasos 1 y 2:
• Hasta que todos los procesos queden señalados como concluidos, en cuyo caso, el estado inicial era seguro, o
• Hasta que ocurra un bloqueo, en cuyo caso, no lo era.

Inicio:   Fin:

Asignación de Recursos por el Algoritmo del Banquero

Se permiten las condiciones de “exclusión mutua”, “espera por” y “no apropiatividad” [7, Deitel].

Los procesos reclaman uso exclusivo de los recursos que requieren.

Los procesos mantienen los recursos mientras piden y esperan por otros recursos adicionales, pero no pueden apropiarse de un proceso que mantenga esos recursos.

Las peticiones son de un recurso a la vez.

El S. O. puede conceder o negar cada una de las peticiones; si se niega una petición:

• El proceso retiene los recursos que ya tiene asignados.
• Espera un tiempo finito hasta que le sea atendida la petición.

Dado que el sistema se mantiene siempre en estado seguro, todas las peticiones serán atendidas en un tiempo finito.

Inicio:   Fin:

Debilidades del Algoritmo del Banquero

Requiere que exista un número fijo de recursos asignables, pero generalmente no se puede contar con que el número de recursos se mantenga siempre constante [7, Deitel].

Requiere que la población de usuarios se mantenga constante, lo cual es irrazonable.

Requiere que el S. O. garantice que todas las peticiones serán concedidas en un tiempo finito, pero en la realidad se requieren mayores garantías.

Requiere que los procesos reintegren los recursos en un tiempo finito, pero en la realidad se requieren mayores garantías.

Requiere que los procesos indiquen sus necesidades máximas de recursos por adelantado, lo cual generalmente no ocurre.

Generalmente no es utilizado en S. O. reales.

Inicio:   Fin:

Prevención de Bloqueos

Si se puede garantizar que al menos una de las cuatro condiciones de Coffman para el bloqueo nunca se satisface, entonces los bloqueos serán imposibles por razones estructurales (enunciado de Havender) [23, Tanenbaum].

Havender sugirió las siguientes estrategias para evitar varias de las condiciones de bloqueo:

• Cada proceso [7, Deitel]:
• Deberá pedir todos sus recursos requeridos de una sola vez.
• No podrá proceder hasta que le hayan sido asignados.
• Si a un proceso que mantiene ciertos recursos se le niega una nueva petición, este proceso deberá:
• Liberar sus recursos originales.
• En caso necesario, pedirlos de nuevo junto con los recursos adicionales.
• Se impondrá la ordenación lineal de los tipos de recursos en todos los procesos:
• Si a un proceso le han sido asignados recursos de un tipo dado, en lo sucesivo solo podrá pedir aquellos recursos de los tipos que siguen en el ordenamiento.

Inicio:   Fin:

Prevención de la Condición de Exclusión Mutua

Si ningún recurso se asignara de manera exclusiva a un solo proceso, nunca tendríamos bloqueos, pero esto es imposible de aplicar, en especial en relación a ciertos tipos de recursos, que en un momento dado no pueden ser compartidos (ej.: impresoras).

Se debe:

• Evitar la asignación de un recurso cuando no sea absolutamente necesario.
• Intentar asegurarse de que los menos procesos posibles puedan pedir el recurso.

Inicio:   Fin:

Prevención de la Condición “detenerse y esperar” o “espera por”

Si se puede evitar que los procesos que conservan recursos esperen más recursos, se pueden eliminar los bloqueos.

Una forma es exigir a todos los procesos que soliciten todos los recursos antes de iniciar su ejecución; si un proceso no puede disponer de todos los recursos, deberá esperar, pero sin retener recursos afectados.

Un problema es que muchos procesos no saben el número de recursos necesarios hasta iniciar su ejecución.

Otro problema es que puede significar desperdicio de recursos, dado que todos los recursos necesarios para un proceso están afectados al mismo desde su inicio hasta su finalización.

Otro criterio aplicable consiste en:

• Exigir a un proceso que solicita un recurso que libere en forma temporal los demás recursos que mantiene en ese momento.
• Hacer que el proceso intente luego recuperar todo al mismo tiempo.

Inicio:   Fin:

Prevención de la Condición de “no apropiación”

Una de las estrategias de Havender requiere que cuando a un proceso que mantiene recursos le es negada una petición de recursos adicionales; deberá liberar sus recursos y si es necesario pedirlos de nuevo junto con los recursos adicionales.

La implementación de esta estrategia niega la condición de “no apropiación” y los recursos pueden ser retirados de los procesos que los retienen antes de la terminación de los procesos.

El problema consiste en que el retiro de ciertos recursos de un proceso puede significar:

• La pérdida del trabajo efectuado hasta ese punto.
• La necesidad de repetirlo luego.

Inicio:   Fin:

Prevención de la Condición de “espera circular”

Una forma es que un proceso solo está autorizado a utilizar un recurso en cada momento:

• Si necesita otro recursos, debe liberar el primero.
• Esto resulta inaceptable para muchos procesos.

• Todos los recursos se numeran globalmente.
• Los procesos pueden solicitar los recursos en cualquier momento:
• Las solicitudes se deben hacer según un cierto orden numérico (creciente) de recurso; debido a lo cual la gráfica de asignación de recursos no tendrá ciclos.
• En cada instante uno de los recursos asignados tendrá el número más grande:
• El proceso que lo posea no pedirá un recurso ya asignado.
• El proceso terminará o solicitará recursos con números mayores , que estarán disponibles:
• Al concluir liberará sus recursos.
• Otro proceso tendrá el recurso con el número mayor y también podrá terminar.
• Todos los procesos podrán terminar y no habrá bloqueo.

• Ningún proceso debe solicitar un recurso con número menor al que posee en el momento.

Inicio:   Fin:

Otros Aspectos

Los métodos para prevenir el bloqueo pueden resumirse según se indica en la Tabla 6.5 [23, Tanenbaum].
 

Otros aspectos interesantes relacionados con bloqueos son [23, Tanenbaum]:

• La cerradura de dos fases.
• Los bloqueos sin recursos.
• La inanición.

Inicio:   Fin:

Cerradura de Dos Fases

Una operación frecuente en sistemas de bases de datos consiste en:

• Solicitar el cierre de varios registros.
• Actualizar todos los registros cerrados.
• Ante la ejecución de varios procesos al mismo tiempo, existe un grave riesgo de bloqueo.

• Primer fase: el proceso intenta cerrar todos los registros necesarios, uno a la vez.
• Segunda fase: se actualiza y se liberan las cerraduras.
• Si durante la primer fase se necesita algún registro ya cerrado:
• El proceso libera todas las cerraduras y comienza en la primer fase nuevamente.
• Generalmente esto no resulta aplicable en la realidad:
• No resulta aceptable dejar un proceso a la mitad y volver a comenzar.
• El proceso podría haber actualizado archivos, enviado mensajes en la red, etc.

Inicio:   Fin:

Bloqueos Sin Recursos

Los bloqueos también pueden aparecer en situaciones que no están relacionadas con los recursos.

Puede ocurrir que dos procesos se bloqueen en espera de que el otro realice cierta acción, por ej.: operaciones efectuadas sobre semáforos (indicadores o variables de control) en orden incorrecto.

Inicio:   Fin:

Inanición

En un sistema dinámico permanentemente hay solicitudes de recursos.

Se necesita un criterio (política) para decidir:

• Quién obtiene cual recurso.
• En qué momento.

La inanición se puede evitar mediante el criterio de asignación de recursos FIFO “el primero en llegar es el primero en despachar (ser atendido)”.

El proceso que ha esperado el máximo tiempo se despachará a continuación:

• En el transcurso del tiempo, cualquiera de los procesos dados:
• Será el más antiguo.
• Obtendrá el recurso necesario.

Inicio:   Fin:

Tendencias del Tratamiento del Bloqueo

Generalmente los S. O. han considerado al bloqueo como una incomodidad limitada [7, Deitel].

Muchos S. O. implementan métodos básicos de prevención de bloqueos sugeridos por Havender y los resultados son satisfactorios en gran número de casos.

La tendencia es a que el bloqueo tenga una consideración mucho mayor en los nuevos S. O., debido a:

• Orientación hacia la operación asincrónica en paralelo:
• Incremento del multiprocesamiento y de las operaciones concurrentes.
• Asignación dinámica de recursos:
• Capacidad de los procesos de adquirir y liberar recursos según las necesidades.
• Ignorancia a priori de los procesos respecto de sus necesidades de recursos.
• Consideración de los datos como un recurso:
• Significa incrementar la capacidad del S. O. para administrar gran número de recursos.

Para mayor información, seleccione una opción:

• Página principal.
• Página anterior.
• Página siguiente.
• Indice general.
• Indice detallado.
• Contactos.

Estadísticas diarias desde el 10/07/2002:  

Número de visitantes actuales disponible desde el 14/07/2002:

 

Autor: lrmdavid@exa.unne.edu.ar

Ó FACENA - http://exa.unne.edu.ar

Servicios WEB: webmaster@exa.unne.edu.ar