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

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