2.4.1 Exclusión mutua de secciones criticas.

Exclusión Mutua.

            Consiste en garantizar que durante la ejecución de una región crítica los recursos compartidos solo se asignen a uno y solo a uno de los procesos.

            Si un recurso compartido es una variable, la exclusión mutua asegura que a lo más un proceso a la vez ha accedido a ella durante la actualización crítica que conduce a valores temporalmente inestables. Consecuentemente los otros procesos ven solamente valores estables de las variables compartidas. Con los dispositivos compartidos la necesidad para la exclusión mutua puede ser incluso más obvia cuando uno considera el problema que puede provocar sus usos.

            Por ejemplo, supongamos que en el sistema existe un archivo formado por registros compuestos por 5 campos. 

 Registro de 5 campos.

Para que un registro sea valido debe estar totalmente actualizado, es decir, si se modifica el valor del campo A, el resto de los campos deben ser coherentes con el nuevo valor de dicho campo, ya que de otro modo el registro sería inconsistente.

            Si en el momento en que un proceso escribe o modifica un registro y existe otro proceso que realiza la lectura de ese mismo registro, y el primero de ellos sólo hubiese tenido tiempo de modificar el campo A, la información obtenida por el segundo proceso seria inconsistente. Para evitar esto se deben sincronizar los procesos de manera que mientras uno escribe, otro pueda leer.

            Esto no ocurre en aquellos casos en que dos procesos tratan de leer en el mismo archivo, aún coincidiendo en el mismo registro.

            Generalizando. Supongamos que los dos procesos que coinciden en el mismo registró, uno esta escribiendo y el otro leyendo, llamados ESCRIBIR y LEER,  se encuentran en un sistema monoprocesador multiprogramado y son los únicos presentes en ese momento. 

Concurrencia

En el momento de un cambio de proceso del uno al otro se pueden producir las siguientes situaciones:

. Sin sincronización entre procesos. Puede darse el caso de que ESCRIBIR esté actualizando un registro y se quede a medías, sorprendiéndole el cambio de proceso, por tanto, terminará de escribirlo cuando vuelva a hacer uso del procesador. Con el cambio le tocará el turno al proceso LEER, que accederá a dicho registro pudiendo leerlo completamente. Es evidente que los datos leídos serán inconsistentes.

. Con sincronización entre procesos.  Supongamos algún mecanismo que prohíba la lectura (bloqueo de registros) a cualquier proceso, mientras el proceso ESCRIBIR esté realizando alguna operación. En este caso, LEER, al hacer uso del procesador que se encuentra bloqueado, quedaría en espera de que el registro quede totalmente escrito y se proceda a su desbloqueo, LEER pasaría a estado bloqueado, ESCRIBIR terminaría su trabajo sobre el registro y en el siguiente cambio LEER procedería a hacer el suyo.

            Esta sincronización por la cual una actividad impide que otras puedan tener acceso a un dato mientras se encuentra realizando una operación sobre el mismo es lo que se conoce como exclusión mutua.

            La zona de código de un proceso que no puede ser interrumpida por otro, por los motivos expuestos anteriormente se le llama Región Crítica.

Regiones críticas.

Es el conjunto de actividades elementales cuya ejecución exige el monopolio de recursos. Por ejemplo, para indicar que alguna acción se realizará con acceso exclusivo a ciertos datos compartidos.

                                               Región  datos - compartidos   do   acción

            ¿Como evitar la región critica?. La clave para prevenir el problema aquí y en muchas otras situaciones en que interviene la memoria compartida, archivos compartidos y todo lo que se comparte, consiste en determinar alguna manera de prohibir que un proceso lea y escriba los datos compartidos al mismo tiempo.

De otra manera lo que se necesita es la sincronización. Una manera de asegurar de que si un proceso ésta utilizando una variable o archivo compartido, es que los otros procesos no pueden hacer lo mismo.

            Para tener una solución adecuada a la región crítica se necesita que se cumplan cuatro condiciones:

1. Nunca dos procesos pueden encontrarse simultáneamente dentro de sus regiones críticas.

2. No se hacen suposiciones acerca de las velocidades relativas de los procesos o del

     Número  de CPU.

3. Ningún proceso suspendido fuera de la región crítica debe bloquear a otros procesos.

4. Nunca un proceso debe querer entrar en forma arbitraria en su región crítica.

           

 Representación de regiones criticas

Cuando se diseña un  proceso que debe contener una o varias regiones críticas se deben  de tomar en cuenta las siguientes consideraciones:

            . La región crítica debe ser ejecutada lo más rápido posible.

            . Un programa no debe ínter bloquearse en una región crítica.

            . Las regiones críticas deben ser programadas con mucho cuidado (no se permiten

              Ciclos indefinidos).

            . Mientras un proceso está en su región crítica otros procesos pueden continuar

              Ejecutándose  fuera de las regiones críticas.

            . Cuando se tienen procesos que comparten datos, si un proceso deja la región

              Crítica otro de los procesos que espera a entrar en su región crítica puede proceder.

            Cuando el proceso termina, voluntaria o involuntariamente, el sistema operativo debe de realizar la limpieza propia de fin de proceso y liberar la exclusión mutua de otros procesos.

La exclusión mutua: Forma de asegurar que si un proceso está usando una variable o archivo compartido, los otros procesos quedarán excluidos de hacer lo mismo.
Los procesos pueden tener en su código secciones en que realizan cálculos internos y operaciones que no dan lugar a condiciones de competencia. Sin embargo existen secciones de programa en que el proceso está accediendo a recursos compartidos que pueden dar pié a condiciones de competencia.
La parte del programa en que se accede a un recurso compartido se denomina sección o región crítica (requisito necesario, pero no suficiente). Los requisitos para que procesos paralelos cooperen de manera correcta usando datos compartidos son los siguientes:

• Dos procesos nunca pueden estar simultáneamente dentro de sus regiones críticas.
• No se puede suponer nada acerca de las velocidades de ejecución de los procesos o el número de las CPU.
• Ningún proceso que se ejecute fuera de su región crítica puede bloquear a otros procesos.
• Ningún proceso deberá tener una espera indefinida para entrar en su región crítica.

La exclusión mutua debe ponerse en práctica sólo cuando los procesos obtienen acceso a datos compartidos modificables; cuando los procesos realizan operaciones que no entran en conflicto con otras, deben permitirse que procedan concurrentemente. Cuando un proceso obtiene acceso a datos compartidos modificables, se dice que se encuentra en una sección crítica. Es evidente que, para evitar la clase de problemas observados en la sección anterior, debe asegurarse que cuando un proceso se encuentre en una sección crítica, los demás procesos (o al menos los que tengan acceso a los datos compartidos) no pueden entrar a sus propias secciones críticas.
Mientras un proceso se encuentra en su sección crítica, otros procesos pueden, claro está, seguir ejecutándose fuera de sus secciones críticas. Cuando un proceso abandona su región crítica, otro proceso que espera entrar en su propia sección crítica (si existe algún proceso en espera). Lograr que se cumpla la exclusión mutua es uno de los problemas fundamentales de la programación concurrente. Se han propuesto muchas soluciones, algunas de software y otras de hardware, algunas sencillas y otras complejas, y algunas que requieren la cooperación voluntaria de los procesos y otras que exigen un escrito ajuste a rígidos protocolos.
Encontrarse dentro de una región crítica es un estado especial concedido a un proceso. El proceso tiene acceso exclusivo a los datos compartidos y los demás procesos que requieran acceso a los datos en ese momento deben esperar. Así pues, las secciones críticas deben ejecutarse tan rápido como sea posible; un proceso no se debe bloquear dentro de su propia sección crítica y las secciones críticas deben codificarse con mucho cuidado (para evitar, por ejemplo, la posibilidad de ciclos infinitos).
Si un proceso de una sección crítica termina, ya sea voluntaria o involuntariamente, el sistema operativo, al realizar su mantenimiento de terminaciones, debe liberar la exclusión mutua de manera que otros procesos puedan entrar en sus regiones críticas.
El problema de la Sección Crítica

• n procesos compitiendo para utilizar algún dato compartido.
• Cada proceso tiene un segmento de código, llamado sección crítica, en el que se accede al dato compartido.
• Problema – asegurarse de que cuando un proceso esta ejecutándose en su sección crítica, a ningún otro proceso se le permite ejecutar la suya.
• Estructura del proceso Pi

repeat
entry section
sección crítica
exit section
sección restante
until false;

Solución al problema de la Sección Crítica

• Una solución al problema de la sección crítica debe satisfacer los siguientes tres requerimientos:
1. Exclusión Mútua. Si un proceso Pi esta ejecutandose en su sección crítica, entonces ninguno de los otros procesos puede estar en su sección crítica
2. Progreso. Si ningún proceso esta ejecutándose en su sección crítica y existen procesos que quieren entrar en su sección crítica, entonces la selección del próximo proceso que entrará a la sección crítica no puede ser pospuesta indefinidamente.
3. Espera limitada. Debe existir un límite del número de veces que se les permite a otros procesos entrar en sus secciones críticas en el intervalo entre que un proceso ha hecho un requerimiento para entrar en su sección crítica y que se le concede el permiso.
• Se supone que cada proceso se ejecuta a velocidad distinta de cero.
• Ninguna suposición respecto a la velocidad relativa de los n procesos.

Intentos iniciales para resolver el problema

• Inhibir las interrupciones.
• Solo dos procesos, P0 and P1
• Estructura general del proceso Pi

repeat
entry section
sección crítica
exit section
sección restante
until false;

• Los procesos pueden compartir algunas variables comunes para sincronizar sus acciones.

Algoritmo 1

Variables compartidas:
– var turn: (0..1);
inicialmente turn = 0
– turn = i ? Pi puede entrar en su sección crítica
Proceso Pi
repeat
while turn ? i do no-op;
sección crítica
turn := j;
sección restante
until false;
Satisface la condición de exclusión mútua, pero no la de progreso (si turn=0 y P1 esta listo para entrar en su sección crítica, P1 no puede hacerlo, incluso aunque P0 este en la sección restante)
Algoritmo 2
Variables compartidas
– var flag: array [0..1] of boolean;
inicialmente flag [0] = flag [1] = false.
– flag [i] = true ? Pi listo para entrar en su sección crítica
Proceso Pi
repeat
flag[i] := true;
while flag[j] do no-op;
sección crítica
flag [i] := false;
sección restante
until false;

Satisface la exclusión mútua, pero no el requerimiento de progreso. (P0 pone flag[0 ] =true y P1 pone flag[1 ] =true; cada uno esperando al otro indefinidamente)

Algoritmo 3
- Combinación de las variables compartidas de los algoritmos 1 y 2.
- Proceso Pi

repeat
flag [i] := true;
turn := j;
while (flag [j] and turn = j) do no-op;
sección crítica
flag [i] := false;
sección restante
until false;

- Cumple los tres requerimientos; resuelve el problema de la sección crítica para dos procesos.

Algoritmo del panadero

• Antes de entrar a su sección crítica, los procesos reciben unnúmero. El que posea el número menor entra en la sección crítica.
• Si los procesos Pi y Pj reciben el mismo número, si i < j, entonces Pi es servido primero; si no lo es Pj .
• El esquema de numeración siempre genera números en orden creciente; por ejemplo 1,2,3,3,3,3,4,5...