8 Propiedad de Corrección en los programas concurrentes¶
Introducción¶
El orden parcial e indeterminismo en la ejecución de las instrucciones conllevan que conseguir que un programa concurrente sea correcto es más difícil que en un programa secuencial.
Para que un programa concurrente sea correcto, además de satisfacer los requisitos funcionales correspondientes, debe cumplir una serie de propiedades inherentes a la concurrencia: las propiedades de seguridad y las propiedades de viveza.
Propiedades de Seguridad¶
Relacionadas con que no debe producirse algo que haga entrar al programa en un estado erróneo:
Exclusión mutua¶
Hay recursos en el sistema que deben ser accedidos en exclusión mutua tal y como hemos visto anteriormente, garantizando que si un proceso adquiere el recurso, el resto deberá esperar a que sea liberado.
Condición de sincronización¶
Hay situaciones en las que un proceso debe esperar por la ocurrencia de un evento para poder seguir ejecutándose. Cuando esto ocurre, hay que garantizar que el proceso no prosigue hasta que no se produce el evento. De lo contrario, el resultado puede ser imprevisto.
Interbloqueo (deadlock)¶
Se produce una situación de interbloqueo o interbloqueo pasivo cuando todos los procesos están suspendidos esperando en una condición de sincronización a un evento que nunca se producirá, dado que hay una espera circular. Hay que garantizar que la condición de sincronización llegará a cumplirse en algún momento. Se suele conocer también como abrazo mortal. Por ejemplo la tarea 1 obtiene en exclusión mutua el recurso A, y es bloqueado hasta que obtenga el recurso B, mientras que la tarea 2 obtiene el recurso B y es suspendido hasta que obtenga el recurso A. La condición necesaria para que alguno de ellos termina de ejecutar su cometido nunca va a darse y ambas tareas terminarán suspendidas indefinidamente.
Coffman definió las cuatros condiciones que deben darse simultáneamente en el sistema que para se produzca un interbloqueo:
- Que los recursos se encuentren en exclusión mutua.
- Que la tareas no libere un recurso obtenido en exclusión mutua mientras espera otro recurso.
- Que los recursos sólo puedan ser liberados por las tareas que los han obtenido en exclusión mutua.
- Que se produzca una espera circular.
Para evitar el interbloqueo, la estrategia más habitual es analizar los recursos que deben ser obtenidos por las tareas, de manera que podamos decidir en qué orden se obtienen y si deben obtener dependiendo de ciertas condiciones. Otra alternativa es que a la hora de tratar de adquirir un recurso se establezca un tiempo máximo transcurrido el cuál se liberen todos los recursos que hubiéramos adquirido.
Propiedades de viveza¶
Relacionados con que cada sentencia que se ejecute conduce en algún modo a un avance constructivo para alcanzar el objetivo funcional del programa. Son, en general, muy dependientes de la política de planificación que se utilice:
Interbloqueo activo (livelock)¶
Se produce un interbloqueo activo cuando varios procesos se están ejecutando pero ninguno es capaz de finalizar su ejecución. Por ejemplo imaginemos que la tarea 1, obtiene el recurso A y la tarea 2 obtiene el recurso B. Como la tarea 1 necesita también el recurso B y éste está siendo usado por la tarea 2, la tarea 1 libera el recurso A. Sin embargo, a la vez, como la tarea 2 necesita también el recurso A y éste está siendo (en ese momento) usado por la tarea 1, la tarea 2 libera el recurso B. Y ambas tareas vuelven a intentar otra vez lo mismo, produciéndose el mismo efecto indefinidamente. Se diferencia del deadlock en que en el livelock las tareas están siempre ejecutándose y cambiando de estado, aunque a pesar de ello no pueden terminar su cometido. Sin embargo en el deadlock las tareas están suspendidas (no en ejecución), esperando algo que no va a suceder. La detección de los livelock es muy compleja.
Inanición (starvation)¶
Se produce cuando un proceso nunca tiene acceso a un recurso que necesita, ya que el sistema siempre se lo concede a algún otro proceso. Para evitar la inanición se suele aplicar en los algoritmos el concepto de fairness (justicia), que implica que cualquier proceso que requiera un recurso lo obtendrá en algún momento, para lo que normalmente el sistema tiene en cuenta el momento en el que el proceso realizó la solicitud del mismo.
Inversión de prioridad (priority inversion)¶
Se produce cuando una tarea de poca prioridad obtiene un recurso por delante de una de mayor prioridad, de manera que la menos prioritaria siempre termina su ejecución antes que la más prioritaria.
