Ejemplos de Sistemas Operativos que controlen Deadlocks

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

Introducción

Deadlock

Deadlock: Es un bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros. Se produce cuando cada proceso retiene un recurso solicitado por otro.

Que se produzca o no un deadlock, depende tanto de la dinámica de la ejecución como de los detalles de la aplicación. Puede haber deadlock tanto en recursos reutilizables como en los consumibles.

Tipos de recursos:

  • Reutilizables:Puede ser utilizado por el proceso sin que se agote ,cuando se libera está disponible para ser usado por otro proceso.
  • Consumibles:Puede ser creado(producido) y destruido(consumido).Cuando un proceso “adquiere” un recurso de este tipo, es destruido.Ejemplos:Interrupciones, señales, mensajes, etc.

Condiciones de deadlock: Un deadlock puede surgir si y solo si en un sistema se presenta simultáneamente las siguientes cuatro condiciones:

  • Exclusión mutua:Los recursos compartidos son adquiridos y utilizados de modo mútuamente exclusivo, es decir , por un proceso como máximo en cada momento.
  • Retención y espera: Cada proceso retiene los recursos que ya le han sido asignado mientras espera para adquirir el resto de recursos.
  • No expropiación:Los recursos no se pueden quitar a los procesos.Un recurso sólo puede ser liberado voluntariamente por el proceso que lo retiene.
  • Espera circular:Debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera por uno o más recursos en poder del siguiente miembro de la cadena.

La condición de espera circular implica la condición de retención y espera, por lo que las cuatro condiciones no son completamente independientes.


Existen tres métodos para manejar deadlock:

  • Utilizar un protocolo que asegure que el sistema nunca llegará a un estado de deadlock.
  • Permitir que el sistema entre en bloqueo mutuo y luego se recupere.
  • Desentenderse del problema y hacer como si nunca ocurrieran bloqueos mutuos en el sistema. Esta solución es la que adopta la mayor parte de los sistemas operativos, incluido Windows y UNIX.

Los sistemas operativos mencionados anteriormente dan la opción de matar un proceso, eliminando la condición de deadlock si es que llegase a existir.

Ahora veremos algunos detalles de 3 Sistemas Operativos para los deadlocks:

Solaris

Sistema Operativo Solaris

El kernel de Solaris es mediante módulos, un módulo interactúa con otro mediante interfaces y está diseñado para prevenir deadlocks causados por la interrupción de hebras. Esto se realiza bloqueando la hebra que ha sido interrumpida, si es que una variable de sincronización bloqueada es encontrada, y se espera que la sección critica se libere. La estrategia de bloqueo de kernel utilizada es un bloqueo basado en datos. En este método, cada pieza de datos compartido es protegida por un objeto de sincronización.

El kernel también implementa prevención de deadlock usando bloqueo de exclusión mutua (mutex) para prevenir que más de una hebra se ejecute cuando un bloqueo es encontrado. Esto previene una "condición de carrera", es decir que compitan por llegar a los datos, cuando se accede a datos compartidos.Si un mutex no puede setear un bloqueo porque ya está siendo usado, la política de bloqueo por defecto es hacerlo girar mientras el dueño del bloqueo esté corriendo en un procesador. Se le pregunta el estado del dueño en un loop de espera y si el dueño termina de correr el proceso bloqueado, termina de girar y duerme.Esto da una respuesta rápida y una sobrecarga baja.

La detección de deadlock también está implementada. Los deadlock causados por violación de jerarquía son detectados en tiempo de ejecución por el mecanismo prioritario de herencia utilizado. Debido que este mecanismo no mantiene una lista completa de hebras que tienen un bloqueo de lectura, sin embargo, esto no es capaz de detectar todos los deadlocks, algunos deadlocks con variables de condición no son detectados.

El kernel de Solaris utiliza numerosos enfoques para tratar deadlocks: prevención, detección y resolución y no hacer nada.


Windows

Sistema Operativo Windows

Si bien Windows no posee herramientas para controlar directamente los deadlocks, claramente debía presentar algo que permitiera a los usuarios actuar en caso de uno. Para esto hay herramientas específicas que apuntan principalmente al debug del sistema:

WINDBG: esta herramienta es un debugger que permite al usuario realizar debug de sus aplicaciones, de los driver o bien del propio sistema operativo (esto último en el modo kernel). Una de sus habilidades es poder cargar los archivos que contienen los debug symbols (archivos con extensión PDB), los cuales van almacenando a través de símbolos las instancias del sistema y por medio de esta herramienta podemos descubrir en que momento ocurrió el deadlock ya que la línea común de símbolos cambia y por medio de las coincidencias de los timestamp o el avance del procesador sabremos específicamente cual fue el problema. I386KD: Con esta herramienta cargamos un archivo del sistema que contiene información muy importante. Este es MEMORY.DMP, el cual va almacenando en el tiempo todos los momentos en el cual el sistema se mantiene íntegro o no. Así, podemos cargar todo lo necesario para saber cuando el sistema cambió de estado y por supuesto encontrar la falla que dejó al sistema inestable.

Estas son 2 de las herramientas que usa windows para enfrentar los deadlocks. Así, este sistema operativo nos da la posibilidad de estar al tanto de lo que sucede en tiempo real más allá de saber como arreglar el problema, por lo que sí se puede considerar como forma de enfrentar o mitigar los problemas.



Unix

Sistema Operativo Unix

Sistema operativo portable, multitarea y multiusuario.

Es un sistema operativo de tiempo compartido, controla los recursos de una computadora y los asigna entre los usuarios. Permite a los usuarios correr sus programas. Controla los dispositivos de periféricos conectados a la máquina.

Esta formado por una serie de elementos que pueden representarse en forma de capas concéntricas donde, en primer lugar alrededor del hardware, aislando a este de los usuarios, además de adaptar el resto del sistema operativo a la maquina debido a la portabilidad que existe en el mismo.

El núcleo del sistema operativo Unix (llamado Kernel) es un programa escrito casi en su totalidad en lenguaje C, con excepción de una parte del manejo de interrupciones, expresada en el lenguaje ensamblador del procesador en el que opera.

Las funciones del núcleo son permitir la existencia de un ambiente en el que sea posible atender a varios usuarios y múltiples tareas en forma concurrente, repartiendo al procesador entre todos ellos, e intentando mantener en grado óptimo la atención individual.

El Kernel opera como asignador de recursos para cualquier proceso que necesite hacer uso de las facilidades de cómputo. Es el componente central de Unix y tiene las siguientes funciones: Creación de procesos, asignación de tiempos de atención y sincronización. Asignación de la atención del procesador a los procesos que lo requieren. Administración de espacio en el sistema de archivos, que incluye: acceso, protección y administración de usuarios; comunicación entre usuarios v entre procesos, y manipulación de E/S y administración de periféricos. Supervisión de la transmisión de datos entre la memoria principal y los dispositivos periféricos.

Deadlock en Unix

En Unix, como en otros SO se ignora la ocurrencia de deadlock.

Esta estrategia resulta ser la más sencilla y es denominada algoritmo del avestruz (Ostrich): esconder la cabeza en la tierra y pretender que no existe problema alguno.

La justificación de este método es que si el deadlock se presenta con una frecuencia baja en comparación con los fallos del sistema por otras razones (errores en el sistema operativo, fallos en el hardware, etc.), no tiene sentido tomar medidas para evitar el problema a costa de reducir el rendimiento del sistema. Cada tabla del sistema en Unix (tabla de procesos) es un recurso finito que puede ser fuente de un posible deadlock. El planteamiento de UNIX es ignorar el problema, bajo la hipótesis de que la mayoría de los usuarios preferiría un bloqueo ocasional en vez de una regla que restringiera el uso de los recursos. Esta decisión tiene su motivación en el hecho de que la eliminación del deadlock es muy costosa.

Una vez que se decide afrontar el problema, existen dos estrategias principales para tratar el deadlock:

  • Usar un protocolo que garantice que el sistema nunca entre en un estado de deadlock.
  • Permitir que el sistema entre en deadlock y luego se recupere. 


En el primero de los casos existen dos métodos generales, que son conocidos como y evitación de deadlock. El segundo requiere el empleo técnicas de detection complementadas con técnicas de recuperación .


Sistemas Operativos en tiempo real

Prevención de deadlock en los RTOS

Los deadlock son prevenidos utilizando un diseño cuidadosamente implementado dentro de estos sistemas operativos. Además se utilizan semáforos "de piso", los cuales pasan el control de un semáforo a la tarea de mayor prioridad en condiciones definidas (como se mencionará posteriormente las hebras están priorizadas).

Un sistema operativo en tiempo real (RTOS) consta de dos componentes "Tiempo Real" y "Sistema Operativo", esto quiere decir que este sistema soporta aplicaciones en tiempo real dando resultados correctamente lógicos dentro del límite requerido.La estructura básica es similar a un sistema operativo pero adicionalmente provee de mecanismos que permiten la programación en tiempo real de las tareas. Los sistemas operativos RTOS puede o no puede que implementen la velocidad de ejecución pero lo que si proveen es un ritmo más preciso y predecible que un sistema operativo de propósito general.

RTOS

En general, los RTOS requieren:

  • Multitasking.
  • Hebras de proceso que pueden ser priorizadas.
  • Un número suficiente de niveles de interrupción.

Clasificación de los RTOS

Basado en un grado de tolerancia en cumplir los tiempos límites, los RTOS se clasifican en las siguientes categorías:

  • Tiempo real duro: Si se falla una fecha límite puede resultar en una falla catastrófica en el sistema.
  • Tiempo real firme: Faltar una fecha límite puede resultar en una reducción de calidad inaceptable.
  • Tiempo real suave: Fechas límites pueden ser faltadas ocacionalmente, el sistema no fallará y la calidad es aceptable.

Ejemplos de RTOS

  • LynxOS
  • OSE
  • QNX
  • RTLinux
  • VxWorks
  • Windows CE
  • Chorus OS
  • ERIKA Enterprise, entre otros.


Sistemas Operativos de tiempo compartido

Los mayores problema en los sistemas operativos de tiempo compartido respecto a deadlock, son los problemas de concurrencia.

En los sistemas de tiempo compartido (aquellos con varios usuarios, procesos, tareas, trabajos que reparten el uso de CPU entre estos) se presentan muchos problemas debido a que los procesos compiten por los recursos del sistema.

Los programas concurrentes a diferencia de los programas secuenciales tienen una serie de problemas muy particulares derivados de las caracteristicas de la concurrencia:

  • Violacion de la exclusion mutua: En ocasiones ciertas acciones que se realizan en un programa concurrente no proporcionan los resultados deseados.

Esto se debe a que existe una parte del programa donde se realizan dichas acciones que constituye una region critica, es decir, es una parte del programa en la que se debe garantizar que si un proceso accede a la misma, ningun otro podra acceder. Se necesita pues garantizar la exclusion mutua.

  • Bloqueo mutuo o deadlock: Un proceso se encuentra en estado de deadlock si esta esperando por un suceso que no ocurrira nunca. Se puede producir en la comunicacion de procesos y mas frecuentemente en la gestion de recursos.
  • Retraso indefinido : Un proceso se encuentra en starvation si es retrasado indefinidamente esperando un suceso que no puede ocurrir. Esta situacion se puede producir si la gestion de recursos emplea un algoritmo en el que no se tenga en cuenta el tiempo de espera del proceso.

Por nombrar algunas.

Técnicas para prevenir el deadlock

Las técnicas para prevenir el deadlock en estos sistemas consisten en proveer mecanismos para evitar que se presente una o varias de las cuatro condiciones necesarias de deadlock mencionadas en la introducción.

  • Asignar recursos en orden lineal: Esto significa que todos los recursos estan etiquetados con un valor diferente y los procesos solo pueden hacer peticiones de recursos hacia adelante.
  • Algoritmo del banquero.
  • Asignar todo o nada: Este mecanismo consiste en que el proceso pida a todos los recursos que van a necesitar de una vez y el sistema se los da solamente si puede darselos todos, sino, no le da nada y lo bloquea.

Ejemplos de SO de tiempo compartido

  • Multics
  • OS/360
  • DEC-10, entre otros.

Referencias

[1] "Sistemas Operativos, Séptima edición, 2005" Galvin,Silberschatz,Gagne

[2] "Sun-Solaris-by-Mike-Henry-James-Sheasley-David-Waterman-Alex-Blood-2002-FALL"

[3] "Deadlock" Deadlock

[4] "Sistemas Operativos en tiempo real" Sistemas Operativos en tiempo real 1

[5] "Sistemas Operativos en tiempo real" Sistemas Operativos en tiempo real 2

[6] "Prevención Deadlock" [1]

[7] "Problemas de concurrencia" [2]

[8] "Interbloqueo en distintos SO" [3]

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas