Bloqueos.

Bloqueos.
 




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

  14.  
Introducción y ejemplos de bloqueo (o interbloqueo)

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:

Los sistemas de cómputos tienen muchos recursos que solo pueden ser utilizados por un proceso a la vez: Ej. de bloqueo (deadlock): Ejemplo de interbloqueo de tráfico:

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:


Un interbloqueo simple.

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):

Varios trabajos en ejecución que generan líneas de spool pueden interbloquearse si el espacio disponible se llena antes de completarse alguno de estos trabajos: Un problema relacionado: postergación indefinida:

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

En algunos sistemas, la postergación indefinida se evita al permitir que la prioridad de un proceso aumente mientras espera por un recurso; a esto se llama envejecimiento.

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:

También son recursos compartibles (de uso compartido) ciertos programas: El código reentrante puede ser compartido simultáneamente por varios procesos.

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.
Si el recurso no está disponible cuando se lo solicita: Un bloqueo se puede definir formalmente como sigue: Las condiciones necesarias para el bloqueo son (Coffman) [7, Deitel]: 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]).

Gráficas de asignación de recursos.

Las gráficas tienen dos tipos de nodos:


Ejemplo de ocurrencia de un bloqueo y la forma de evitarlo.
 
 

Ejemplo de ocurrencia de un bloqueo y la forma de evitarlo.

Las estrategias utilizadas para enfrentar los bloqueos son:


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:


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:

Algunos S. O. soportan potencialmente bloqueos que ni siquiera se detectan, ya que se rompen automáticamente.

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

El problema es que se debe pagar un cierto precio para encarar el problema del bloqueo: Se presenta una contradicción entre la conveniencia y lo que es correcto.

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:


Inicio:   Fin:

Detección de Bloqueos

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

La detección del bloqueo es el proceso de: Los algoritmos de detección de bloqueos implican cierta sobrecarga en tiempo de ejecución, por lo cual surge el siguiente interrogante: ¿ compensa la sobrecarga implícita en los algoritmos de detección de bloqueos, el ahorro potencial de localizarlos y romperlos ?.

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]).

Gráfica de asignación y petición de recursos.

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:

Si una gráfica puede ser reducida por todos sus procesos, entonces no hay interbloqueo.

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]).

Reducciones de gráficas.

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”):


Gráfica de recursos y procesos.

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:
  3. Se añade el nodo activo al final de “L” y se verifica si el nodo aparece en “L” dos veces:
  4. Desde el nodo dado se verifica si existen arcos que salgan de dicho nodo y no estén marcados:
  5. Se elige al azar un arco de salida no marcado y se le marca:
  6. Se ha llegado a un punto donde no se puede continuar:
La aplicación del algoritmo precedente al ejemplo anterior de gráfica dirigida es la siguiente:


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, “P1hasta “Pn.

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

En todo momento algunos de los recursos están asignados y por lo tanto no están disponibles.

Se considera un vector “A” de recursos disponibles:

Se utilizan: El renglón i -ésimo de “C” indica el número de instancias de cada clase “Pi poseídas en ese momento.

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

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].

Estructuras de datos necesarias para el algoritmo de detección de bloqueos.

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

Los procesos no están marcados al principio.

Al avanzar el algoritmo los procesos se marcarán:

Los pasos básicos del algoritmo de detección de bloqueos son los siguientes:
  1. Se busca un proceso no marcado “Pi , 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.
En el ejemplo tenemos 3 procesos y 4 clases de recursos (ver Figura 6.8 [23, Tanenbaum]).

Un ejemplo del algoritmo de detección de bloqueos.

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:

Se ejecuta el proceso 2, el cual regresa sus recursos, obteniéndose: A = (4 2 2 1).

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

Si se considera la siguiente variante:


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:


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:

Generalmente la recuperación suele realizarse: Los procesos pueden ser retirados (cancelados) de acuerdo a un orden de prioridades, existiendo las siguientes dificultades: Algunas formas de recuperación ante bloqueos son [23, Tanenbaum]:


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.:

La recuperación de recursos de esta forma depende en gran medida de la naturaleza del recurso.

La elección del proceso a suspender depende mucho:


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:

Al detectarse un bloqueo es fácil ver cuáles son los recursos necesarios.

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


Inicio:   Fin:

Recuperación Mediante la Eliminación de Procesos
 


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]:

El objetivo es evitar el bloqueo haciendo la elección correcta todo el tiempo, pero para evitar los bloqueos se requiere de cierta información de antemano.

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]).

Trayectorias de recursos de dos procesos.

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


Inicio:   Fin:

Estados Seguros e Inseguros

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

Un estado es seguro si: Ejemplo con un recurso para demostrar que el estado en (a) es seguro:

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 de estado seguro en (a).

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

Ejemplo de estado inseguro.

Un estado inseguro [7, Deitel]: La diferencia entre estado seguro e inseguro es que: Ejemplo de una transición de estado seguro a estado inseguro (ver Tabla 6.3 [7, Deitel]).

Ejemplo de una transición de estado seguro a estado inseguro.


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:

Un estado inseguro no tiene que llevar a un bloqueo.

El algoritmo del banquero consiste en:


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]).

El algoritmo del banquero con varios recursos.

Se dispone de:

El algoritmo para determinar si un estado es seguro es el siguiente [23, Tanenbaum]:
  1. Se busca un renglón “R” cuyas necesidades de recursos no satisfechas sean menores o iguales que “A”:
  2. Supongamos que el proceso del renglón elegido solicita todos los recursos que necesita y concluye:
  3. Se repiten los pasos 1 y 2:


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 S. O. concede peticiones que den como resultado solo estados seguros.

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:

Havender no presenta una estrategia contra el uso exclusivo de recursos por parte de los procesos, pues se desea permitir el uso de recursos dedicados.

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:


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:


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:

Una consecuencia seria es la posible postergación indefinida de un proceso.

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:

Otra forma es la siguiente: Una variante consiste en eliminar el requisito de adquisición de recursos en orden creciente: El problema es que en casos reales podría resultar imposible encontrar un orden que satisfaga a todos los procesos.

Inicio:   Fin:

Otros Aspectos

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

Condición
Método
Exclusión mutua
Realizar un spooling general
Detenerse y esperar
Solicitar todos los recursos al principio
No apropiación
Retirar los recursos
Espera circular
Ordenar los recursos en forma numérica
Tabla 6.5: Resumen de los métodos para prevenir el bloqueo.

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


Inicio:   Fin:

Cerradura de Dos Fases

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

El método de la cerradura de dos fases consiste en:


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:

Podría suceder que ciertos procesos nunca lograran el servicio, aún sin estar bloqueados, porque se privilegia en el uso del recurso a otros procesos.

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:


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:

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

Número de visitas efectuadas desde el 17/12/2001: 

Estadísticas diarias desde el 10/07/2002:   Free counter and web stats

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

 

AddFreeStats.com Free Web Stats in real-time !  

 

 

 

Autor: lrmdavid@exa.unne.edu.ar

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

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