2.7. Principios Generales de concurrencia.

Es aparente que las nociones de procesos y recursos están estrechamente vinculadas. Un proceso es una tarea, identificada como una secuencia de instrucciones ejecutándose, o una colección de instrucciones formando un programa. Un recurso, por otra parte, es un término incluido en el sistema operativo, como también impresoras, discos, cintas de discos, procesos y repartos de la capacidad de memoria. Sin embargo, los recursos no son tratados en forma igualitaria por el S.O. y dependiendo de su cinta, tratará los procesos en forma diferente.

       Los recursos no expropiables (No Preemption) son usados por los procesos que requieren una utilización de recursos ininterrumpidos. Los recursos expropiables (Preemption) requieren un control del S.O. para cambiar correctamente la utilización de los recursos.

       En un sistema multiprogramado (se llama multiprogramación a la gestión de varios procesos dentro de un sistema monoprocesador), los procesos se intercalan en el tiempo para dar la apariencia de ejecución simultánea, aunque no se consigue un proceso paralelo real y aunque se produce una cierta sobrecarga en los intercambios de procesos de un sitio a otro, la ejecución intercalada produce beneficios importantes en la eficiencia del procesamiento y en la estructuración de los programas.

       En un sistema con varios procesadores, no sólo es posible intercalar los procesos, sino también superponerlos. Ambas técnicas, la intercalación y la superposición, pueden contemplarse como ejemplos de proceso concurrente y ambas plantean los mismos problemas. En el caso de un sistema monoprocesador, los problemas creados por la multiprogramación parten del hecho de que la velocidad relativa de ejecución de los procesos no puede predecirse. Depende de la actividad de otros procesos, de la forma en que el sistema operativo trata las interrupciones y de las políticas de planificación.

       La concurrencia comprende un gran número de cuestiones de diseño, incluyendo la comunicación entre procesos, compartición y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador a los procesos.

Labores del Sistema Operativo

       Hay algunos elementos de gestión y diseño que surgen por causa de la concurrencia. Se pueden enumerar los siguientes:

-          El S.O. debe ser capaz de seguir la pista de los distintos procesos activos. Esto lo hace por medio de los PCB.

-          El S.O. debe asignar y quitar los distintos recursos a cada proceso activo.

-          El S.O. debe proteger los datos y los recursos físicos de cada proceso contra injerencias no intencionadas de otros procesos

-          Los resultados de un proceso deben ser independientes de la velocidad relativa a la que se realiza la ejecución con respecto a otros procesos concurrentes.

Condiciones de concurrencia (Berstein)

       Debe darse un conjunto de condiciones para que se puedan ejecutar varios procesos a la vez.

       Un conjunto de lectura R(S_i) de la sentencia S_i es aquel formado por todas las variable que son referenciadas por la sentencia S_i durante su ejecución sin sufrir cambios.

       Un conjunto de escritura W (S_i) de la sentencia S_i es aquel formado por todas las variable cuyos valores son modificados durante su ejecución.

       Dos sentencias Si y Sj pueden ejecutarse concurrentemente (produciendo igual resultado que la ejecución secuencial) si y solo si cumplen las siguientes condiciones:

R (Si) Ç W (Sj) = Æ

R (Sj) Ç W (Si) = Æ    

W (Si) Ç W (Sj) = Æ   

       Existen diversas notaciones para especificar actividades concurrentes. Entre ellas, las instrucciones fork-join (no estructurados) y cobegin-coend (estructurados).

       Un proceso es independiente si no puede afectar o ser afectado por otros procesos corriendo en el sistema. Un proceso es interactuante si puede afectar o ser afectado por otros procesos.

       Los procesos que se ejecutan, no lo hacen a la misma velocidad. Por ello, aparece una race condition (condición de carrera o de concurso), que es la situación en la cual el resultado de la ejecución de dos o más procesos interactuantes depende del orden de ejecución de los mismos.

INTERACCIÓN ENTRE PROCESOS

       Es posible clasificar las interacciones entre procesos en función del nivel de conocimiento que cada proceso tiene de la existencia de los demás. Existen tres niveles de conocimientos:

§         Los procesos no tienen conocimiento de los demás: estos son procesos independientes que no están pensados para operar juntos. El S.O. tiene que encargarse de la competencia por los recursos. Los resultados de un proceso son independientes de las acciones de los otros procesos.

§         Los procesos tienen un conocimiento indirecto de los otros: los procesos no conocen a los otros por su nombre, pero comparte el acceso a algunos objetos, tales como un buffer de E/S o un archivo o una porción de memoria. Estos procesos muestran cooperación para compartir el objeto común. Los resultados de un proceso pueden depender de la información obtenida de los otros. Este es el nivel de conocimiento menos frecuente, pero el más grave porque debemos tener la información actualizada. Podemos permitir lecturas simultáneas y para ello se hacen copias para que cada proceso lea de su propia copia. Las escrituras se hacen en una copia primaria y el S.O. debe actualizar todas las otras copias para mantener la actualización y coherencia de datos.

§         Los procesos tienen conocimiento directo de los otros: los procesos son capaces de comunicarse con los demás por el nombre y están diseñados para trabajar conjuntamente en alguna actividad. Estos procesos muestran cooperación por comunicación. Los resultados de un proceso pueden depender de la información obtenida de los otros.

Competencia entre los procesos por los recursos

       Los procesos concurrentes entran en conflicto cuando compiten por el uso del mismo recurso. Cada proceso debe dejar tal y como esté el estado de cualquier recurso que utilice. Aunque no hay intercambio de información entre los procesos en competencia, la ejecución de un proceso puede influir en el comportamiento de los procesos que compiten. En particular, si dos procesos desean acceder a un único recurso, el S.O. le asignará el recurso a uno de ellos y el otro tendrá que esperar. Por lo tanto, el proceso al que se le niega el acceso quedará bloqueado y se retrasará. En el peor caso, el proceso bloqueado puede que no consiga nunca acceder al recurso y, por tanto, no terminará con éxito nunca.

       En el caso que haya procesos en competencia, se deben solucionar tres problemas de control:

1.       Exclusión mutua: supóngase que dos procesos quieren acceder a un único recurso no compartible. A estos recursos se los llama recursos críticos y la parte del programa que los utiliza se conoce como sección crítica del programa. Es importante que sólo un programa pueda acceder a su sección crítica en un momento dado. Hacer que se cumpla la exclusión mutua crea los dos problemas mencionados a continuación.

2.       Interbloqueo (deadlock): considérese dos procesos P1 y P2 y dos recursos críticos R1 y R2. Supóngase que cada proceso necesita acceder a ambos recursos para llevar a cabo una parte de su función. En tal caso, es posible que el S.O. asigne R1 a P2 y R2 a P1. Cada proceso está esperando a uno de los dos recursos y ninguno liberará el recurso que ya posee hasta que adquiera el otro y ejecute su sección crítica. Ambos procesos están interbloqueados. En otra situación que se da interbloqueo es cuando dos procesos están bloqueados en un receive() y esperan un mensaje que nunca les va a llegar.

3.       Inanición (starvation): es cuando un proceso se queda esperando un recurso indefinidamente. Esto se soluciona asignándoles mayor prioridad a los procesos para que obtengan pronto el recurso que solicitan y no caigan en inanición (Envejecimiento o Aging).

Cooperación entre procesos por compartición

       Varios procesos pueden tener acceso a variables compartidas, archivos o bases de datos compartidas. Los procesos pueden emplear y actualizar los datos compartidos sin hacer referencia a los otros procesos, pero son conscientes de que estos otros pueden tener acceso a los mismos datos. Así pues, los procesos deben cooperar para asegurar que los datos que se comparten se gestionen correctamente. Los mecanismos de control deben garantizar la integridad de los datos. Puesto que los datos se guardan en recursos (dispositivos, memoria), también se presentan los problemas de control de exclusión mutua, interbloqueo e inanición. La única diferencia es que se puede acceder a los datos de dos formas distintas, para lectura y para escritura. Sólo las operaciones de escritura deben ser mutuamente excluyentes. Sin embargo, antes que estos problemas, se debe introducir un nuevo requisito: la coherencia de los datos. En este caso, la secuencia completa de cada proceso se puede declarar como sección crítica para garantizar la integridad de los datos, incluso aunque ningún recurso crítico se vea involucrado.

Cooperación entre procesos por comunicación

      

En los dos casos ya expuestos cada proceso posee su propio entorno aislado, que no incluye a los otros procesos; las interacciones entre los procesos son indirectas. Cuando los procesos cooperan por comunicación, en cambio, los distintos procesos participan en una labor común que une a todos los procesos. La comunicación es una manera de sincronizar o coordinar las distintas actividades. Normalmente, la comunicación puede caracterizarse por estar formada por mensajes de algún tipo. Las primitivas para enviar y recibir mensajes pueden venir dadas como parte del lenguaje de programación o por el núcleo del S.O.

Grado de Conocimiento	Relación	Posibles problemas de control
Los procesos no tienen conocimiento de los demás	Competencia	Exclusión mutua Interbloqueo Inanición
Los procesos tienen conocimiento indirecto de los otros	Cooperación por compartición	Exclusión mutua Interbloqueo Inanición Coherencia de datos
Los procesos tienen conocimiento directo de los otros	Cooperación por comunicación	Interbloqueo Inanición

Región Crítica. Protocolo de sincronización.

       Los puntos de entrada de un recurso indican la cantidad de procesos que pueden utilizar simultáneamente al mismo. Si un recurso tiene sólo un punto de entrada, se lo denomina recurso crítico o recurso no compartible.

       Región crítica de un proceso es la fase o etapa en la vida de ese proceso concurrente en la cual accede a un recurso crítico para modificarlo o alterarlo.

       El uso adecuado de la concurrencia entre procesos exige la capacidad de definir secciones críticas y hacer cumplir la exclusión mutua. Cualquier servicio o capacidad que dé soporte para la exclusión mutua debe cumplir con un protocolo de sincronización, que tiene los requisitos siguientes:

Debe cumplirse la exclusión mutua: sólo un proceso de entre todos los que poseen secciones críticas por el mismo recurso u objeto compartido, debe tener permiso para entrar en ella en un instante dado.

Un proceso que se interrumpe en una sección no crítica debe hacerlo sin estorbar a los otros. Es decir que si se cuelga un proceso que está usando un recurso, los demás procesos que esperan deben poder acceder al recurso de todas formas (el S.O. mata al proceso que se colgó y así libera al recurso). 

No se puede demorar indefinidamente la entrada de un proceso a un cierto recurso; no debe permitirse el interbloqueo y la inanición. Todos los procesos deben poder acceder al recurso que solicitan, sino se van a morir sin usarlo y no es justo.

Cuando ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin dilatación. Es decir, si nadie está usando un cierto recurso, entonces se le otorga al primer proceso que lo solicite.

No se pueden hacer suposiciones sobre la velocidad relativa de los procesos o su número (cantidad de procesadores). Nunca se puede saber a priori si a un proceso le falta mucho o poco para terminar.

Un proceso permanece en su sección crítica sólo por un tiempo finito. Esto sirve para evitar que un proceso se quede con un recurso por mucho tiempo y para que un recurso no se quede trabado sin sentido.