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

4. CONCURRENCIA: EXCLUSIÓN MUTUA Y SINCRONIZACIÓN.

 

 

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.

 

EXCLUSIÓN MUTUA: SOLUCIONES POR SOFTWARE.

 

ALGORITMOS DE SINCRONIZACIÓN CON ESPERA ACTIVA (BUSY WAITING)

 

Solución simple

 

       Se utiliza una variable global que indica el estado de la región crítica, la cual es consultada cuando se requiere entrar. Esta solución no funciona si se produce una interrupción inmediatamente antes de que la variable antes mencionada se active. (Similar al Segundo Intento de Dekker)

 

 

 

Espera ocupada por turnos (alternancia)

 

Utiliza una variable global, la cual si posee valor i indica que le proceso Pi puede entrar. Asegura que haya sólo un proceso en la región crítica. Exige alternancia estricta. Si la variable está en 0 y P1 está listo para entrar entonces debe esperar, aunque P0 no esté en la región crítica. (Similar al Primer Intento de Dekker)

 

Algoritmo de Dekker

 

Primer intento

Utilizaremos para su descripción el “protocolo del iglú”. Un proceso (P0 o P1) que desee ejecutar su sección crítica entra primero en el iglú y examina la pizarra. Si su número está escrito en ella, el proceso puede abandonar el iglú y continuar con su sección crítica. En caso contrario, abandona el iglú y se ve obligado a esperar, ingresando de vez en cuando para mirar la pizarra hasta que se le permita entrar a su sección crítica. Un proceso frustrado no puede hacer nada productivo hasta que obtiene permiso para entrar a su sección crítica (por ello, el nombre de espera activa), debiendo persistir y comprobar periódicamente el iglú, consumiendo tiempo del procesador mientras espera su oportunidad.

Después de que un proceso haya obtenido acceso a su sección crítica y tras terminar con ella, debe volver al iglú y escribir el número del otro proceso en la pizarra.

      

       PROCESO 0       PROCESO 1

 

       .......       .......

       while (turno ¹ 0) do (nada);       while (turno ¹ 1) do (nada);

       <sección crítica>;       <sección crítica>;

       turno:=1;       turno:=0;

       .......       .......

-         Ventaja: garantiza el cumplimiento de la exclusión mutua.      

-         Inconveniente 1: los procesos deben alternarse en forma estricta en el uso de sus secciones críticas; así pues, el ritmo de ejecución viene dado por el más lento.

-         Inconveniente 2: si un proceso falla (tanto dentro como fuera de su sección crítica), el otro proceso se bloquea permanentemente.

Segundo intento

En el primer intento se almacenaba el nombre del proceso que podía entrar en su sección crítica cuando, en realidad, lo que hacía falta era tener información del estado de ambos procesos. En realidad, cada proceso debería tener su propia llave de la sección crítica para que si en uno se produce un error, el otro pueda seguir accediendo a su sección crítica. Cada proceso tiene ahora su propio iglú y puede mirar la pizarra del otro, pero no modificarla. Cuando un proceso desea entrar en su sección crítica, comprueba periódicamente la pizarra del otro hasta que encuentra escrito en ella ”Falso”, lo que indica que el otro proceso no está en su sección crítica. Entonces, se dirige rápidamente hacia su propio iglú, entra y escribe “Cierto” en la pizarra, continuando ahora con su sección crítica.

       PROCESO 0       PROCESO 1

       ......       ......

       while (señal_b) do (nada);       while (señal_a) do (nada);

       señal_a = True;       señal_b = True;

       < sección crítica >;       < sección crítica >;

       señal_a = False;       señal_b = False;

       ......       ......

 

-         Ventaja: si uno de los procesos falla fuera de la sección crítica, el otro proceso no queda bloqueado.

-         Inconveniente 1: si uno de los procesos falla dentro de su sección crítica, el otro proceso quedará bloqueado permanentemente.

-         Inconveniente 2: no soluciona el problema de la exclusión mutua. Consideremos la siguiente secuencia:

. P0 ejecuta la sentencia while y encuentra señal_b a falso

. P1 ejecuta la sentencia while y encuentra señal_a a falso

. P0 pone señal_a a true y entra en su sección crítica

. P1 pone señal_b a true y entra en su sección crítica

Puesto que ambos procesos están en sus secciones críticas, el programa Es incorrecto. Este intento falla porque un proceso puede cambiar su estado después de que el otro proceso lo ha comprobado, pero antes de que pueda entrar en su sección crítica.

Tercer intento

       PROCESO 0       PROCESO 1

       ......       ......

       señal_a = True;       señal_b = True;

       while (señal_b) do (nada);       while (señal_a) do (nada);

       < sección crítica >;       < sección crítica >;

       señal_a = False;       señal_b = False;

       ......       ......

 

Como antes, si un proceso falla dentro de la sección crítica, incluyendo el código para dar valor a las señales que controlan el acceso a la sección crítica, el otro proceso se bloquea y si un proceso falla fuera de su sección crítica, el otro proceso no se bloquea.

-         Ventaja: garantiza la exclusión mutua

-         Inconveniente: si ambos procesos ponen sus señales a “true” antes de que ambos hayan ejecutado la sentencia while, cada uno pensará que el otro ha entrado en su sección crítica. El resultado es un interbloqueo.

Cuarto intento

El inconveniente en el tercer intento era que un proceso fijaba su estado sin conocer el estado del otro. Se puede intentar arreglar esto haciendo que los procesos sean más educados: deben activar su señal para indicar que desean entrar en la sección crítica, pero deben estar listos para desactivar la señal y ceder la preferencia al otro proceso.

       PROCESO 0       PROCESO 1

       ......                  ......

       señal_a = True;       señal_b = True;

       while (señal_b) do       while (señal_a)

            begin         begin

                   señal_a = Falso;             señal_b = Falso;

                 < espera cierto tiempo >                < espera cierto tiempo >;

                   señal_a = True;               señal_b = True;

            end;            end;

       < sección crítica >;  < sección crítica >;

       señal_a = Falso;       señal_b = Falso;

       ......                  ......

 

-         Ventaja: la exclusión mutua está garantizada

-         Inconveniente: se produce un problema ante un “exceso de cortesía” por parte de ambos procesos. Veamos la siguiente secuencia:

. P0 pone señal_a a cierto

. P1 pone señal_b a cierto

. P0 comprueba señal_b

. P1 comprueba señal_a

. P0 pone señal_a a falso

. P1 pone señal_b a falso

. P0 pone señal_a a cierto

. P1 pone señal_b a cierto

 

Esta secuencia podría prolongarse indefinidamente y ningún proceso podría entrar en su sección crítica. Estrictamente hablando, esto no es un interbloqueo, porque cualquier cambio en la velocidad relativa de los dos procesos rompería este ciclo y permitiría a uno entrar en la sección crítica. Aunque no es probable que esta situación se mantenga por mucho tiempo, es una situación posible. Así entonces, se rechaza el cuarto intento.

Una solución correcta

Hay que poder observar el estado de ambos procesos, que viene dado por la variable señal. Y de algún modo, se hace necesario imponer algún orden en la actividad de los dos procesos para evitar el problema de “cortesía mutua” que se observó en el cuarto intento. La variable turno del primer intento puede usarse en esta labor; en este caso, la variable indica qué proceso tiene prioridad para exigir la entrada a la sección crítica. Ahora hay un iglú “árbitro” con una pizarra llamada “turno”. Cuando P0 quiere entrar en su sección crítica, pone su señal a cierto. A continuación, va y mira la señal de P1. Si ésta está puesta a falso, P0 puede entrar inmediatamente en su sección crítica. En otro caso, P0 va a consultar al árbitro. Si encuentra turno = 0, sabe que es momento de insistir y comprueba periódicamente el iglú de P1. Este otro se percatará en algún momento de que es momento de ceder y escribirá “falso” en su pizarra, permitiendo continuar a P0. Después de que P0 haya ejecutado su sección crítica, pone su señal a “falso” para liberar la sección crítica y pone turno = 1 para traspasar el derecho de insistir a P1.

              PROCESO 0       PROCESO 1

       begin                   begin

            repeat                    repeat

                   señal_a = True;               señal_b = True;

                   while (señal_b) do              while (señal_a) do

                     if (turno) then                 if (!turno) then

                            begin                          begin

                            señal_a = Falso;                    señal_b = Falso;

                            while (turno) do (nada);                        while (!turno) do (nada);

                            señal_a = True;                      señal_b = True;

                            end;                     end; 

                 < sección crítica >;              < sección crítica >

                   turno = 1;             turno = 0;

                   señal_a = Falso;             señal_b = Falso;

                 < resto >;               < resto >;

              forever;                  forever;

       end;                end;

 

Algoritmo de Peterson

El algoritmo de Dekker resuelve el problema de la exclusión mutua, pero con un programa complejo. Entonces, Peterson desarrolló una solución más simple: la variable global señal indica la posición de cada proceso con respecto a la exclusión mutua y la variable global turno resuelve los conflictos de simultaneidad. Este algoritmo puede generalizarse para el caso de n procesos.

PROCESO 0        PROCESO 1

begin                     begin

       repeat                  repeat

              señal_a = True;               señal_b = True;

            turno = 1;                turno = 0;

            while (señal_b and turno) do (nada);       while (señal_a and !turno) do (nada);

            < sección crítica >;  < sección crítica >;

              señal_a = Falso;       señal_b = Falso;

            < resto >;    < resto >;

       forever;           forever;

end;                       end;