Algoritmos Dekker
Este algoritmo fue implementado por Edsger Dijktra, es un algoritmo de programación para
la concurrencia el cual es para exclusión mutua, este permite que dos procesos ohilos de
ejecución puedan compartir recursos sin que haya un conflicto entre ambos. Este algoritmo
es uno de los primero implementados para la concurrencia. Si en un caso ambos procesos
intentanacceder a la misma porción de memoria o sección critica al mismo tiempo, el
algoritmo se basa en una variable de turno. Si el otro proceso se está ejecutando en la
sección crítica el primero deberáesperar a que este finalice para empezar con su tarea.
Hay 5 variantes del algoritmo de Dekker, donde las primeras 4 presentaron fallos. La quinta
versión del mismo es el que trabaja de forma eficiente,en este se logró una combinación
del primero con el cuarto.
Primer Algoritmo
Se garantiza la exclusión mutua, pero los procesos se encuentran fuertemente acoplados,
esto significa que un procesolento puede retrasar a uno rápido.
La variable turno obliga a que los procesos alternen turnos de acceso.
Variables
turno: Entero;
Inicialización
turno = 1;
Proceso UNO
Repeat
Hace_Cosas();While turno = 2 Do;
Region_Critica();
turno = 2;
Hace_mas_cosas();
Until Fin
Proceso Dos
Repeat
Hace_Algo();
While turno = 1 Do;
Region_Critica();
turno = 1;
Hace_algo_mas();
Until FinSegundo Algoritmo
Problema interbloqueo. En este no existe la alternación entre ambos y los procesos caen en
un mismo estado y no logran salir de este.
Si el Quantum de tiempo de los procesosfinaliza precisamente después del cambio de la
variable P#QE, pero antes de la validación While, puede que ambos queden en un ciclo
infinito y se genere el interbloqueo.
Variables
P1QE, P2QE: Bool;Inicialización
P1QE = false;
P2QE = false;
Proceso UNO
Proceso Dos
Repeat
Hace_Cosas();
P1QE = true;
While P2QE Do;
REGION_CRITICA();
P1QE = False;
Hace_mas_cosas();
Until Fin...
Regístrate para leer el documento completo.