Site hosted by Angelfire.com: Build your free website today!

CONCURRENCIA. INTERBLOQUEO (Deadlock) E INANICION (Starvation).

DEADLOCK

       Los procesos no son ejecutados constantemente desde que se inician hasta que son finalizados. Un proceso puede estar identificado con tres estados diferentes: leyendo (ready), ejecutando (running) o bloqueado (blocked). En el estado de lectura, un proceso está parado, concediendo que otro proceso sea ejecutado; en el estado de ejecución, un proceso está utilizando algún recurso; y en el estado de bloqueo, el proceso está parado y no se ejecutará mientras algo lo restaure.

 

       Una condición común no deseable es descripta como deadlock, que es cuando dos procesos están en un estado de ejecución, y requieren intercambiar recursos entre sí para continuar. Ambos procesos están esperando por la liberación del recurso requerido, que nunca será realizada; como no hay ningún resultado, tomará un camino que llevará a un estado de deadlock.

      

Muchos escenarios han sido construidos para ilustrar las condiciones de deadlock, siendo el más popular el Problema de Comida de los Filósofos. Cinco filósofos tienen cinco platos de fideos enfrente suyo y cinco tenedores, uno a cada lado del plato. Los filósofos necesitan ambos tenedores (derecha e izquierda) para comer. Durante la comida realizarán solo dos operaciones mutuamente excluyentes, pensar o comer. El problema es un paralelismo simplista entre procesos (los filósofos) tratando de obtener recursos (tenedores); mientras están en estado de ejecución (comiendo) o de lectura (pensando). Una condición posible de deadlock puede ocurrir, si todos los filósofos quieren coger el tenedor de la derecha y, a la vez, el de la izquierda: la comida terminará en estado de deadlock.

      

Se dice que dos procesos se encuentran en estado de deadlock (interbloqueo, bloqueo mutuo o abrazo mortal) cuando están esperando por condiciones que nunca se van a cumplir. Se podría hablar de deadlock como el estado permanente de bloqueo de un conjunto de procesos que están compitiendo por recursos del sistema.

 

CONDICIONES DE COFFMAN

       Los autores Silberchatz, Jensen y Tanenbaum, coinciden en que para que se produzca un estado de deadlock las cuatro condiciones de Coffman son condiciones necesarias y suficientes y deben producirse simultáneamente. Stallines, mientras tanto indica que las tres primeras condiciones son necesarias, pero no suficientes, y que la cuarta condición ocurre como consecuencia de las otras tres.

1.       Mutua exclusión: sólo un proceso a la vez puede usar el recurso

2.       Retener y esperar: el proceso retiene los recursos que ya tiene asignados mientras espera por nuevos a adquirir del conjunto de recursos del sistema

3.       No expropiación: el proceso está reteniendo los recursos concedidos y solo puede liberarlos y devolverlos al sistema como resultado de una acción voluntaria de ese proceso. El S.O. no puede obligarle a devolverlos.

4.       Espera circular: los procesos están esperando mutuamente a que el otro libere el recurso requerido, formando una cadena circular entre dos o más procesos, en la que cada uno de ellos está esperando un recurso que tiene el próximo miembro de la cadena.

 

PREVENCIÓN DEL INTERBLOQUEO

 

       Esta estrategia resuelve el problema limitando el uso de los recursos e imponiendo restricciones a los procesos. Siendo las cuatro condiciones necesarias para que ocurra un deadlock, basta con asegurarnos que una de ellas no ocurrirá.

 

- Exclusión mutua: aquellos recursos que son compartidos, no causan problemas, ya que los mismo pueden ser utilizados por cualquier proceso en cualquier momento. Las soluciones para aquellos recursos que no pueden ser compartidos se basan en que un proceso no quede esperando en caso de la falta de disponibilidad de dicho recurso.

 

- Control y espera: para solucionar este problema, se trata de garantizar que cuando un proceso tenga un recurso asignado no pueda solicitar otro. Hay dos caminos para lograrlo:

. Los procesos solicitan todos los recursos en el momento previo a comenzar la ejecución, de no poder ser entregados el proceso queda bloqueado. Uno de los problemas que surgen es la ineficiencia. Los procesos quedan esperando sin poder realizar tarea alguna hasta no poder obtener la totalidad de los recursos solicitados. Más grave aún sería la posibilidad de que la espera se convirtiese en una espera infinita debido a la popularidad de algún recurso solicitado, derivando así en estado de inanición (starvation).

 

. Un proceso primero debe liberar aquellos recursos que posee y luego recién podrá solicitar otros, es decir solo está en condiciones de solicitar un recurso cuando no tiene ninguno asignado. El mayor inconveniente aquí es que hay casos en que los procesos necesitan al menos, dos recursos a la vez para su ejecución.

 

- No expropiación: para ésta condición existen dos métodos:

. Si el proceso solicita un recurso que no está disponible, éste debe devolver todos aquellos recursos que tenía previamente asignados. De ser necesario deberá pedirlos nuevamente.

 

. Si un proceso pide un recurso que tiene otro proceso, el Sistema Operativo puede obligar a liberar los recursos al otro proceso.                

- Espera circular: consiste en imponer un orden lineal de ejecución que evita las espera circulares.

 

Es muy difícil determinar cuando un sistema esta por causar un deadlock, simplemente porque es casi imposible predecir que un proceso va a requerir un recurso, antes de que lo deje de usar otro proceso. Algunas pruebas han sido realizadas para posibles modelos y pronósticos del estado de sistemas futuros usando trayectorias de recursos. Otras pruebas han sido hechas para identificar y clasificar estados de sistemas en: Safe, Unsafe, y Deadlock. Cuando el sistema está en el estado “safe” se refiera que no ocurrió un deadlock, y que el sistema puede aún dar servicio a los procesos pendientes requeridos. Cuando el sistema está en estado “unsafe”, esto se refiere a que algunos de los procesos pendientes no ha sido servido, y la posibilidad de que se produzca un deadlock es inminente. Que este en estado “unsafe”, no garantiza que ocurra en un futuro un deadlock, ya que el sistema posiblemente nunca tenga un requerimiento de proceso ofensivo y así se transforme en un deadlock.

       Williams Stallings clasifica  los métodos de prevención en:

           Métodos indirectos: consisten en impedir la aparición de las tres condiciones necesarias.

           Métodos directos: consisten en evitar la aparición del círculo vicioso de espera.

 

PREDICCION DEL INTERBLOQUEO (AVOIDANCE)

      

Un estado es seguro es cuando existe un orden tal en el que los procesos pueden llevarse a cabo por completo, sin resultar un deadlock. Se dice que un estado es seguro si existe una secuencia de otros estados que lleva a que todos los procesos obtengan sus recursos y terminen su ejecución en un cierto tiempo.

      

La estrategia de avoidance se basa en asegurar que los procesos y los recursos permanezcan en un estado seguro: cuando un proceso solicita un recurso, se asume que le fue otorgado, entonces se chequea el sistema y se determina en qué estado se encuentra el mismo. De ser un estado seguro, el recurso es efectivamente entregado al proceso, ya que de lo contrario el proceso queda bloqueado hasta que sea seguro entregárselo.

       Para ello se cuenta con dos protocolos:

1.       No comenzar un proceso si las demandas pueden incurrir en deadlock (Negativa de iniciación de procesos)

2.       No asignarle a un proceso en ejecución otro recurso si eso lo puede conducir a un deadlock (Negativa de asignación de recursos)

      

Para el desarrollo de esta estrategia varios autores definen matrices para guardar la información. Por ejemplo, Crocus presenta tres matrices. La primera describe el estado inicial del sistema, proporcionando la cantidad total de recursos que existen en cada clase. La segunda, los recursos asignados a los procesos y la tercera, los recursos solicitados. Así cada vez que se solicite un recurso se modificarán los datos de las matrices y mediante una ecuación se determinará si el estado del sistema es seguro o no. La ecuación a la que se hace referencia es A – B £ C + D, siendo:

       A = cantidad de recursos solicitados

       B = recursos asignados

       C = cantidad de recursos disponibles

       D = cantidad de recursos liberados por procesos terminados

 

       El algoritmo del banquero dice que los clientes quieren obtener dinero prestado. Los clientes serían los procesos y el dinero a prestar los recursos. El banco tiene una reserva limitada de dinero para prestar y un conjunto de clientes con líneas de crédito. Un cliente puede elegir pedir dinero a cargo de la línea de crédito en un instante dado y no hay garantía de que el cliente realice ninguna reposición hasta después de sacar la cantidad máxima. El banquero puede rechazar un préstamo a un cliente si hay riesgo de que el banco no tenga fondos suficientes para hacer préstamos futuros que los clientes finalmente repondrán. 

 

DETECCIÓN DEL INTERBLOQUEO

      

Consiste en abortar un proceso cuando se detecta o se presupone que puede ocurrir un deadlock. Hay varios métodos para recuperar a los procesos y a los recursos una vez detectada la situación:

Método 1: Abortar todos los procesos involucrados. Es una solución riesgosa, ya que puede abortarse un proceso que estaba a punto de finalizar su tarea.

 

Método 2: Se coloca un límite superior de tiempo para que un proceso termine su tarea o para que un recurso ea poseído por un proceso. Si se excede el tiempo el sistema toma como si el proceso está en deadlock, entonces aborta el mismo devolviendo todos los recursos. Se denomina time out.

 

Método 3: Minimiza el riesgo de abortar recursos innecesariamente. Cuando se expira el time out el proceso no se aborta, sino hasta que se vea un potencial bloqueo. Se denomina time stamping.

 

Método 4: Hacer un backup de cada proceso en un punto anterior: CkekPoint. En este se graban el estado de los recursos, los recursos asignados, y el estado del proceso entre otros, para poder reiniciarlo. A este proceso de reinicio se lo llama Rollback. Consiste en llevar el proceso a un punto anterior al de haber asignado el recursos causante del deadlock. El inconveniente que presenta es la posibilidad de que el deadlock vuelva a ocurrir. Algunos autores dicen que la aleatoriedad del procesamiento concurrente asegurará la no repetición de dicha situación.

 

Método 5: Abortar los procesos uno a uno, hasta que el deadlock desaparezca. Luego de abortar un proceso se debe aplicar nuevamente el algoritmo de detección.

     Se produce una gran pérdida de tiempo, ya que cada vez que se aborta un proceso hay que correr el algoritmo de detección hasta que el deadlock desaparezca, utilizando gran cantidad de overhead.

 

Método 6: Quitar un recurso a un proceso y entregárselo a otro que lo haya solicitado. Aquí también hay que ejecutar el algoritmo de detección luego de que se quitó algún recurso. El proceso al que se le quita el recurso se vuelve al punto anterior a la adquisición de ese recurso (Rollback).

     El principal problema que se presenta es la selección de la víctima. Es decir, cuál será el proceso que será abortado o a cuál proceso se le quitará un recurso. El S.O. decide cuál es el proceso víctima según alguno de los siguientes criterios:

     . Menor cantidad de uso de CPU hasta el momento

     . Menor cantidad de salidas producidas hasta el momento

     . Mayor tiempo de CPU restante

     . Menor cantidad y tipo de recursos asignados.

     . Menor prioridad

            . Aquel que su reiniciación no incurra en pérdidas significativas

 

volver a la pagina principal