Si un conjunto de procesos esta en estado de espera por recursos y nunca cambia de estado porque los recursos por los que espera están siendo utilizados por otros procesos en estado de espera tenemos un DEADLOCK. Los recursos son la memoria, dispositivos de E/S, semáforos, archivos, etc. La forma en que un proceso hace uso de un recurso es:
Solicitud: si el recurso esta disponible se le otorga, si no el proceso pasa a estado de espera.
Uso: El proceso utiliza el recurso
Liberación: el proceso debe liberar el recurso.
Condiciones Necesarias para que se produzca DEADLOCK
Si se presentan simultáneamente las cuatro siguientes condiciones el sistema esta en DEADLOCK.
- EXCLUSION MUTUA: Por lo menos un proceso que tenga otorgado un recurso en forma exclusiva.
- USO Y ESPERA: Debe existir al menos un proceso que este haciendo uso de un recurso y que este esperando por otros recursos asignados a otros procesos.
- NO INTERRUPCION: Los recursos no pueden ser retirados al proceso. Si un proceso hace uso de un recurso no le podrá ser retirado hasta que voluntariamente el proceso lo libere.
- ESPERA CIRCULAR: Debe existir un conjunto de procesos {P1.....Pn} tal que P1 espera por un recurso utilizado por P2,......,Pn espera por un recurso utilizado por P1.
Conjunto de Vértices: U =P U R
P={P1,P2,....,Pn}
R={R1,R2,...,Rn}
Conjunto de Aristas:
Una arista de un proceso Pi a un Recurso Rj significa que el proceso i esta haciendo una solicitud por el recurso Rj.
Una arista del recurso Rj al proceso Pi, significa que el recurso esta asignado al proceso.
Si un RAG no tiene ciclos el sistema no esta en DEADLOCK, sis si los tiene no se puede afirmar nada.
Mecanismos para tratar con Deadlocks
Evasion de Deadlocks
Si se tiene cuidado al en la forma de asignar los recursos se pueden evitar situaciones de Deadlock. Supongamos un ambiente en el que todos los procesos declaren a priori la cantidad máxima de recursos que habá de usar.
Estado Seguro: un estado es seguro si se pueden asignar recursos a cada proceso (hasta su máximo) en algún orden sin que se genere Deadlock. El estado es seguro si existe un ordenamiento de un conjunto de procesos {P1...Pn} tal que para cada Pi los recursos que Pi podrá utilizar pueden ser otorgados por los recursos disponibles mas los recursos utilizados por los procesos Pj,j<i. Si los recursos solicitados por Pi no pueden ser otorgados, Pi espera a que todos los procesos Pj hayan terminado.
Algoritmo del banquero de Dijkstra
Asigna peticiones de recursos siempre que las mismas den como resultado estados seguros. Solicitudes que den como resultado estados inseguros serán negadas hasta que puedan ser satisfechas. Este algoritmos evita situaciones de Deadlock asignando los recursos en forma correcta.
Las debilidades del algoritmo son: que requiere que la cantidad de recursos del sistema sea constante, requiere una cantidad de procesos constante y requiere que los procesos garanticen que los recursos van a ser devueltos en un intervalo finito de tiempo.
En el área de la informática, el problema del deadlock ha provocado y producido una serie de estudios y técnicas muy útiles, ya que éste puede surgir en una sola máquina o como consecuencia de compartir recursos en una red.
En el área de las bases de datos y sistemas distribuidos han surgido técnicas como el 'two phase locking' y el 'two phase commit' que van más allá de este trabajo. Sin embargo, el interés principal sobre este problema se centra en generar técnicas para detectar, prevenir o corregir el deadlock.
Las técnicas para prevenir el deadlock consisten en proveer mecanismos para evitar que se presente una o varias de las cuatro condiciones necesarias del deadlock. Algunas de ellas son:
· Asignar recursos en orden lineal: Esto significa que todos los recursos están etiquetados con un valor diferente y los procesos solo pueden hacer peticiones de recursos 'hacia adelante'. Esto es, que si un proceso tiene el recurso con etiqueta '5' no puede pedir recursos cuya etiqueta sea menor que '5'. Con esto se evita la condición de ocupar y esperar un recurso.
· Asignar todo o nada: Este mecanismo consiste en que el proceso pida todos los recursos que va a necesitar de una vez y el sistema se los da solamente si puede dárselos todos, si no, no le da nada y lo bloquea.
· Algoritmo del banquero: Este algoritmo usa una tabla de recursos para saber cuántos recursos tiene de todo tipo. También requiere que los procesos informen del máximo de recursos que va a usar de cada tipo. Cuando un proceso pide un recurso, el algoritmo verifica si asignándole ese recurso todavía le quedan otros del mismo tipo para que alguno de los procesos en el sistema todavía se le pueda dar hasta su máximo. Si la respuesta es afirmativa, el sistema se dice que está en 'estado seguro' y se otorga el recurso. Si la respuesta es negativa, se dice que el sistema está en estado inseguro y se hace esperar a ese proceso.
Para detectar un deadlock, se puede usar el mismo algoritmo del banquero, que aunque no dice que hay un deadlock, sí dice cuándo se está en estado inseguro que es la antesala del deadlock. Sin embargo, para detectar el deadlock se pueden usar las 'gráficas de recursos'. En ellas se pueden usar cuadrados para indicar procesos y círculos para los recursos, y flechas para indicar si un recurso ya está asignado a un proceso o si un proceso está esperando un recurso. El deadlock es detectado cuando se puede hacer un viaje de ida y vuelta desde un proceso o recurso. Por ejemplo, suponga los siguientes eventos: evento 1: Proceso A pide recurso 1 y se le asigna.
evento 2: Proceso A termina su time slice.
evento 3: Proceso B pide recurso 2 y se le asigna.
evento 4: Proceso B termina su time slice.
evento 5: Proceso C pide recurso 3 y se le asigna.
evento 6: Proceso C pide recurso 1 y como lo está ocupando el proceso A, espera.
evento 7: Proceso B pide recurso 3 y se bloquea porque lo ocupa el proceso C.
evento 8: Proceso A pide recurso 2 y se bloquea porque lo ocupa el proceso B.
En la figura 5.1 se observa como el 'resource graph' fue evolucionando hasta que se presentó el deadlock, el cual significa que se puede viajar por las flechas desde un proceso o recurso hasta regresar al punto de partida. En el deadlock están involucrados los procesos A,B y C.
Una vez que un deadlock se detecta, es obvio que el sistema está en problemas y lo único que resta por hacer es una de dos cosas: tener algún mecanismo de suspensión o reanudación [Deitel93] que permita copiar todo el contexto de un proceso incluyendo valores de memoria y aspecto de los periféricos que esté usando para reanudarlo otro día, o simplemente eliminar un proceso o arrebatarle el recurso, causando para ese proceso la pérdida de datos y tiempo.
Deadlock
- Un S.O. tiene un número limitado de recursos y procesos que solicitan los recursos.
- ¶Como diseñador de un sistema operativo, ¿cuál es el problema para ti si algunos procesos un tu sistema están en deadlock esperando recursos?
- Los recursos retenidos por los procesos en deadlock no están disponibles para otros procesos, y los procesos en deadlock no pueden avanzar (es mal para los dueños de los procesos).
- Muchos SS.OO. modernos no tienen apoyo especial para prevenir deadlock (porque cuesta), pero es común en programación de sistemas en general (e.g., en programación distribuida).
Características de deadlock
- El sistema tiene recursos de varios tipos: memoria, archivos, grabadores, impresoras, etc. Podemos tener más de un ejemplar de un tipo de recurso (e.g., tres impresoras). Cada uno de los ejemplares pueden satisfacer un solicitud de un proceso para el recurso.
- Los recursos son compartibles y permiten acceso a muchos procesos (e.g., los archivos de sólo lectura) o no compartibles (e.g., un grabador).
- Ejemplo: Tres procesos en un sistema con tres grabadores, cada proceso tiene un grabador y cada uno necesita uno más.
- Condiciones necesarias de deadlock:
- ¶ Exclusión mutua. Por lo menos un recurso debe retenerse no compartido. ¿Por qué?
- Retención y espera. Debe haber un proceso que retenga por lo menos un recurso y espere adquirir más recursos retenidos por otros.
- No apropiación. Los recursos no se pueden expropiar. Los procesos liberan recursos sólo voluntariamente.
- Espera circular. Debe haber un conjunto {P0, P1, ..., Pn} de procesos en espera tales que P0 espere un recurso de P1, P1 un recurso de P2, ..., y Pn un recurso de P0.
- Podemos usar un grafo de asignación de recursos para describir deadlock. Tenemos procesos (círculos), recursos (rectángulos con un punto para cada ejemplar), aristas de solicitud y de asignación (cambio instantáneamente).
- Un grafo sin ciclos implica que no hay deadlock. Si hay un ciclo, es posible que exista deadlock. Un ciclo es una condición necesaria pero no suficiente para deadlock.
Análisis.
Definición. Abraso Mortal (Dead lock) o también llamado ínter bloqueo. En un contexto de procesos concurrentes, si el análisis de recursos a compartir no se hace cuidadosamente, se puede tener el riesgo de que dos o más procesos acaparen algún recurso y que se pongan en espera de que otro u otros liberen los recursos para poder continuar su ejecución, de tal manera que cada proceso permanecerá en una espera indefinida (infinita), observe el ejemplo de la figura # 23 Ejemplo: Se tienen 2 procesos P1 y P2. Se tiene 2 recursos Impresora y Unidad de disco:
Dead Lock.
Cuando un proceso espera un evento que nunca se va a dar y el otro también lo espera Dead lock de un recurso simple.
Muchos de los dead lock se deben a que un proceso retiene un recurso que debe ser usado en forma exclusiva. Es decir, el proceso tiene un recurso que sólo puede ser usado por un usuario a la vez. A estos recursos se les conoce como reutilizables en serie.
Dead lock en sistemas de spool.
Los sistemas de spool suelen ser los más propensos al dead lock. Varios trabajos parcialmente complejos que generan líneas de impresión a un archivo de spool pueden interbloquearse si el espacio disponible para trabajar se llena antes de completarse alguno de esos trabajos. La solución más común es limitar los spoolers de entrada de modo que no se lean más archivos cuando se llega al límite de su capacidad.
Postergación indefinida.
En los sistemas que mantienen procesos en espera mientras realizan la asignación de recursos y/o procesan la planificación de decisiones, es posible que un proceso sea postergado de manera indefinida mientras otro reciben la atención del sistema. A esta situación se le conoce como postergación indefinida, es diferente del dead lock pero sus consecuencias son igual de negativas.
En algunos sistemas la postergación indefinida se evita aumentando la prioridad de un proceso mientras espera por un recurso, a esto se le llama envejecimiento.
Conceptos sobre recursos.
Un sistema operativo es sobre todo un administrador de recursos, existen básicamente dos tipos de recursos:
* Recursos no apropiativos. Un recurso que no se puede liberar antes de completar su actividad sin perder la validez del proceso que lo usa, se dice que un recurso no apropiativo. Una impresora o una unidad de cinta no pueden ser liberados hasta que no termine su trabajo.
* Recursos apropiativos. Un recurso que puede ser usado temporalmente por varios procesos sin comprometer el correcto funcionamiento de dichos procesos se dice que es un recurso apropiativo. El CPU y la memoria principal (mediante las técnicas de paginación) son recursos que pueden ser asignados temporalmente por varios procesos. La apropiatividad de recursos es extremadamente importante en los sistemas de multiprogramación.
Los datos y los programas son recursos que tienen características especiales. En un sistema multiusuario donde se pueden compartir editores, compiladores y programas en general, es ineficiente cargar una copia de ellos para cada usuario que lo solicite. En lugar de ello se carga una sola vez a la memoria y se hacen varias copias de los datos, una por cada usuario.
El código que no cambia mientras está en uso se llama código reéntrate. El código que puede ser cambiado pero que se inicializa cada vez que se usa se llama reutilizable en serie. El código reéntrate puede ser compartido simultáneamente por varios procesos mientras que el reutilizable en serie sólo puede ser usado por un proceso a la vez.
Métodos para manejar los Dead Lock,
Figura # 24. Prevención de Dead Lock.
En principio existen cuatro áreas importantes en la investigación del dead lock, a saber:
1) Prevención:
En las técnicas de prevención el interés se centra en condicionar un sistema para que elimine toda probabilidad de que ocurra un dead lock (normalmente a costa de recursos).
2) Evitación:
En las técnicas para evitar, la idea es poner condiciones menos estrictas que la prevención, para lograr una mejor utilización de los recursos, pero procurando no caer en un dead lock.
3) Detección:
Los métodos de detección se usan en sistemas que permiten la ocurrencia de un dead lock de forma voluntaria o involuntaria.
4) Recuperación:
Los métodos de recuperación se usan para romper los dead lock en un sistema, para poder liberarlo de ellos y los procesos estancados pueden continuar y llegar a su fin.
Modelo del sistema.
Un sistema se compone de un número finito de recursos que se distribuyen entre varios procesos que compiten por ellos. Los recursos se dividen en varios tipos, cada uno de los cuales consiste en varios ejemplares idénticos. Los ciclos del UCP, el espacio de memoria, los archivos y los dispositivos de E/S (como impresoras y unidades de cinta) son ejemplos de tipos de recursos.
Un proceso debe solicitar un recurso antes de usarlo, y liberarlo al terminar su uso. Un proceso puede solicitar cuantos recursos quiera para llevar a cabo su tarea. Obviamente, el número no puede exceder del total de recursos disponibles del sistema. En otras palabras, un proceso no puede solicitar tres impresoras si el sistema solo dispone de dos.
En el modo de operación normal, un proceso solo puede utilizar un recurso en la secuencia siguiente:
1. Solicitud. Si la solicitud no puede atenderse de inmediato (por ejemplo, otro proceso está utilizando ese recurso), entonces el proceso solicitante debe esperar hasta que pueda adquirir el recurso.
2. Utilización. El proceso puede trabajar con el recurso (por ejemplo, si el recurso es una impresora, el proceso puede imprimir en ella).
3. Liberación. El proceso libera el recurso.
La solicitud y liberación de recursos son llamadas al sistema. Algunos ejemplos son las llamadas Solicitar y Liberar dispositivos, Abrir y Cerrar archivos, y Asignar y Liberar memoria. La solicitud y liberación de otros recursos puede lograrse atreves de las operaciones espera (P) y señal (V) sobre semáforos. Además la utilización de recursos solo puede conseguirse mediante llamadas al sistema (por ejemplo, para leer o escribir en un archivo o dispositivo de E/S), de modo que para cada utilización, el sistema operativo verifica que el proceso que dispone del recurso ya lo había solicitado y ya se le había asignado. Una tabla del sistema registra si cada uno de los recursos está libre o asignado y, de estar asignado, a qué proceso. Si un proceso solicita un recurso que se encuentra asignado a otro, puede añadirse a la cola de procesos que esperan tal recurso.
Un conjunto de procesos se encuentra en estado de bloqueo mutuo cuando cada uno de ellos espera un suceso que sólo puede originar otro proceso del mismo conjunto.
Caracterización.
Debe ser obvio que los bloqueos mutuos son indeseables, pues cuando se dan, los procesos nunca terminan su ejecución y los recursos del sistema se paralizan, impidiendo que se inicien otros procesos. Antes de analizar los distintos métodos para tratar el problema del bloqueo mutuo se describirán las circunstancias que los caracterizan.
Condiciones necesarias para que ocurra un Dead Lock.
Coffman, Elphick y Shoshani. Establecieron las cuatro condiciones necesarias para que se produzca un dead lock.
1.- Los procesos reclaman control exclusivo de los recursos que solicitan (exclusión mutua).
2.- Los procesos mantienen los recursos que se les han asignado mientras esperan por recursos adicionales (condición de espera).
3.- No se pueden tomar los recursos que los procesos tienen hasta su completa utilización (condición de no apropiatividad).
4.- Existe una cadena circular de procesos en la cual cada uno de ellos mantiene uno o más recursos que son requeridos por el siguiente proceso de la cadena (condición de espera circular).
Se deben presentar las cuatro condiciones para que puede aparecer un Dead Lock. 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.
No hay comentarios:
Publicar un comentario