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)
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.
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;
