Algoritmo De Dekker Y Peterson

ALGORITMO DE DEKKER

La solución al problema de la exclusión mutua que sigue se atribuye al matemático holandés T. Dekker, y fue presentada por Dijkstra en 1968. Se utiliza, al igual que en la solución de Peterson, una variable turno. Ahora la variable sirve para establecer la prioridad relativa de los dos procesos y su actualización se realiza en la sección crítica, lo que evita que pueda haber interferencias entre los procesos.

Si ambos procesos intentan acceder a la sección crítica simultáneamente, el algoritmo elige un proceso según una variable turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización.

Existen cinco versiones del algoritmo Dekker, teniendo ciertos fallos los primeros cuatro. La versión 5 es la que trabaja más eficientemente, siendo una combinación de la 1 y la 4.

• Versión 1: Alternancia estricta. Garantiza la exclusión mutua, pero su desventaja es que acopla los procesos fuertemente, esto significa que los procesos lentos atrasan a los procesos rápidos.

• Versión 2: Problema interbloqueo. No existe la alternancia, aunque ambos procesos caen a un mismo estado y nunca salen de ahí.

• Versión 3: Colisión región crítica no garantiza la exclusión mutua. Este algoritmo no evita que dos procesos puedan acceder al mismo tiempo a la región critica.

• Versión 4: Postergación indefinida. Aunque los procesos no están en interbloqueo, un proceso o varios se quedan esperando a que suceda un evento que tal vez nunca suceda.

(* Exclusión Mutua:Solución de Dekker*)

moduleExclusion_Mutua_D;

varflag1,flag2: boolean;

turno: integer;

procedure bloqueo(var mi_flag, su_flag: boolean; su_turno: integer);

begin

mi_flag := true;

while su_flag do (* otro proceso en la sección crítica *)

if turno = su_turno then

mi_flag := false;

while turno =su_turno do

; (* espera a que el otro acabe *)

end;

mi_flag := true;

end;

end;

end bloqueo;

procedure desbloqueo (var mi_flag: boolean; su_turno: integer);

begin

turno := su_turno;

mi_flag := false

end desbloqueo;

process P1

begin

loop

bloqueo(flag1,flag2,2);

(* Uso del recurso Sección Crítica *)

desbloqueo(flag1);

(* resto del proceso *)

end

end P1;

process P2

begin

loop

bloqueo(flag2,flag1,1);

(* Uso del recurso Sección Crítica *)

desbloqueo(flag2);

(* resto del proceso *)

end

end P2;

begin (* Exclusion_Mutua_P*)

flag1 := FALSE;

flag2 := FALSE;

turno := 1;

cobegin

P1;

P2;

coend

end Exclusion_Mutua_D.

El programa se inicia con el valor de turno igual a 1 lo que da prioridad al proceso P1. Si ambos procesos piden a la vez el acceso a su sección crítica, ponen en activo sus respectivos indicadores y comprueban si el indicador del otro está activado. Ambos encuentran que sí, por lo que pasan a evaluar el turno. El segundo se encuentra con que no es su turno, desactiva su indicador y se queda en espera de que lo sea. P1 comprueba que sí es su turno y pasa a valorar el estado del indicador de P2, entrará en su sección crítica y dará el turno a P2 antes de desactivar su indicador. Esto permite que el proceso P2 gane el acceso a su sección crítica aunque el proceso P1 haga una nueva solicitud de entrar a la región crítica inmediatamente después de desactivar su indicador.

Conclusión: El algoritmo de Dekker y Peterson tienen un fin en común que ambos son algoritmos de programación concurrente para exclusión mutua. Ambos permiten

...