Algoritmo de dekker / peterson

ALGORITMO DE DEKKER
El algoritmo de Dekker (alternancia estricta): es un algoritmo de programación concurrente para exclusión mutua, que permite a dos procesos o hilos de ejecución compartir un recurso sin conflictos. Fue uno de los primeros algoritmos de exclusión mutua inventados, implementado por Edsger Dijkstra.
Si ambos procesos intentan acceder a la sección crítica simultáneamente, elalgoritmo 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.
Idea de partida: No se puede acceder simultáneamente (desde varios procesadores) a ninguna localidad de memoria.

Espera activa:
•Se utiliza una variable global “turno” para controlar la entrada en la sección crítica.
•Cualquier proceso que deseeentrar en su sección crítica comprobará primero el valor de la variable “turno”:
•Mientras sea distinto al de su identificador de proceso debe esperar.
•Cuando coincida entrará en la sección crítica.
•Cuando un proceso sale de la sección crítica, actualiza “turno “con el código de otro proceso en espera.

Algoritmo de Dekker (1er intento):

Proceso 0 Proceso 1
......
/*esperar*/ /*esperar*/
while(turno!=0); while (turno!=1);
/*sección crítica*/ /*sección crítica*/
... ...
turno=1; turno=0;
... ...

Diseñados para poder pasar el control deejecución entre ellos, no es una técnica apropiada para dar soporte al procesamiento concurrente.
Cuando hay diferencias grandes de velocidad es el proceso más lento el que marca el ritmo.

Algoritmo de Dekker (2º intento):
Verifico la sección crítica del otro proceso y coloco una señal al entrar y salir en su sección crítica:

Proceso 0 Proceso 1
......
/*esperar*//*esperar*/
while(señal[1]); while(señal[0]);
señal[0] = cierto; señal[1]=cierto;
/*sección crítica*/ /*sección crítica*/
... ...
señal[0] = falso; señal[1] = falso;
... ...

Algoritmo de Dekker (2º intento):
Se solucionan los problemas anteriores, sin embargo, ahora surgen otrosnuevos:
•Si uno de los procesos falladentro de su sección crítica el otro quedará bloqueado permanentemente.

•No se garantiza la Exclusión Mutua como vemos en la secuencia:
•1. P0 ejecuta el while y encuentra señal[1] a falso.
•2. P1 ejecuta el whiley encuentra señal[0] a falso.
•3. P0 pone señal[0] a cierto y entra en su sección crítica.
•4. P1 pone señal[1] a cierto y entra en su seccióncrítica.

•Ambos procesos están en su sección crítica, esto se debe a que esta solución no es independiente de la velocidad de ejecución relativa de los procesos.

Algoritmo de Dekker (3° intento):

Proceso 0 Proceso 1
... ...
señal[0] = cierto; señal[1]=cierto;
/*esperar*/ /*esperar*/
while(señal[1]);while(señal[0]);
/*sección crítica*/ /*sección crítica*/
......
señal[0] = falso; señal[1] = falso;
......

Una vez que un proceso ha puesto su señal en cierto, el otro no puede entrar a su sección críticahasta que el primero salga de ella.
Se garantiza la EM, sin embargo, se generará interbloqueosi ambos procesos ponen su señal a cierto antes de amboshayan ejecutado el while. Además, si un proceso fallaen su sección crítica, el otro queda bloqueado permanentemente.

Algoritmo de Dekker (4º intento):
El interbloqueose había originado porque cada proceso establecía su señal sin conocer el estado del otro proceso. Para solucionarlo haremos que los procesos activen y desactiven su señal:

Proceso 0 Proceso 1
......