Algoritmos de Dekker

Algoritmo de DekkerEl algoritmo de Dekker 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, 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.

Primer algoritmo de Dekker

Repeat Repeat

Hace_Cosas(); Hace_Algo();

While turno = 2 Do; While turno = 1 Do;

REGION_CRITICA(); REGION_CRITICA();

turno = 2; turno = 1;

Hace_mas_cosas(); Hace_algo_mas();

Until Fin Until Fin

PROCESO UNO PROCESO DOS

PROGRAMA UNO;Variables turno: Entero;Inicialización turno = 1;

La variable turno obliga a que los procesos tengan que alternar turnos de

acceso a la RC, si existen procesos lentos y rápidos se tiene el problema que

los procesos lentos atrasen a los procesos rápidos, por

lo que se presenta el problema de

SINCRONIZACIÓN FORZADA.

Segundo algoritmo de Dekker

Repeat Repeat

Hace_Cosas(); Hace_Cosas();

P1QE = true; P2QE = true;

While P2QE Do; While P1QE Do;

REGION_CRITICA(); REGION_CRITICA();

P1QE = False; P2QE = False;

Hace_mas_cosas(); Hace_mas_cosas();

Until Fin Until Fin

PROCESO UNO PROCESO DOS

PROGRAMA DOS;Variables P1QE, P2QE: Bool;Inicialización P1QE = false; P2QE = false;

Si el Quantum de tiempo de los procesos finaliza

precisamente después del cambio de la variable

P#QE, pero antes de la validación del While, puede

darse que las dos condiciones sean

verdaderas y los procesos se queden en un ciclo

infinito, a este problema se le conoce como

INTERBLOQUEO.

Tercer algoritmo de Dekker

Repeat Repeat

Hace_Cosas(); Hace_Cosas();

While P2A Do; While P1A Do;

P1A = true; P2A = true;

REGION_CRITICA(); REGION_CRITICA();

P1A = False; P2A = False;

Hace_mas_cosas(); Hace_mas_cosas();

Until Fin Until Fin

PROCESO UNO PROCESO DOS

PROGRAMA TRES;Variables P1A, P2A: Bool;Inicialización P1A = false; P2A = false;

Si el Quantum de tiempo de los procesos finaliza precisamente

después de la validación del While justo cuando ambas banderas tiene como valor “false” , pero antes del cambio en la variable

P#A, puede presentarse el problema que ambos procesos ingresen a la región crítica al mismo tiempo, por lo que este algoritmo NO GARANTIZA

EXCLUSIÓN MUTUA.

Cuarto algoritmo de Dekker

Repeat Repeat

Hace_Cosas(); Hace_Cosas();

P1QE = true; P2QE = true;

While P2QE Do Begin P1QE = false; Delay (random()); P1QE = true; end;

While P1QE Do Begin P2QE = false; Delay (random()); P2QE = true; end;

REGION_CRITICA(); REGION_CRITICA();

P1QE = False; P2QE = False;

Hace_mas_cosas(); Hace_mas_cosas();

Until Fin Until Fin

PROCESO UNO PROCESO DOS

PROGRAMA CUATRO;Variables P1QE, P2QE: Bool;Inicialización P1QE = false; P2QE = false;

El utilizar un tiempo random para forzar la salida en el ciclo While

puede ser un tiempo muy largo o corto de

sincronización que podría no darse en el peor de los casos, a este problema se

le conoce como POSTERGACIÓN

INDEFINIDA.

Quinto algoritmo de DekkerEl quinto algoritmo de Dekker es la versión optimizada y que no presenta problemas como las cuatro versiones anteriores, para su estructuración se hace una combinación de dos algoritmos de acuerdo al orden de prioridad de desempeño y funcionamiento de las cuatro versiones conocidas.

Criterio:Algoritmo Problema Priorida

d de Uso

Algoritmo Uno Sincronización forzada 1

Algoritmo Cuatro

Postergación Indefinida 2

Algoritmo Dos Interbloqueo 3

Algoritmo Tres No garantiza exclusión mutua

4

Quinto algoritmo de Dekker

Repeat Repeat

Hace_Cosas(); Hace_Cosas();

P1QE = true; P2QE = true;

While P2QE Do Begin if(turno = 2) Begin P1QE = false; Delay (random()); P1QE = true; end; end;

While P1QE Do Begin if(turno = 1) Begin P2QE = false; Delay (random()); P2QE = true; end; end;

REGION_CRITICA(); REGION_CRITICA();

turno = 2; P1QE = False;

turno = 1; P2QE = False;

Hace_mas_cosas(); Hace_mas_cosas();

Until Fin Until Fin

PROCESO UNO PROCESO DOS

PROGRAMA CINCO;Variables P1QE, P2QE: Bool; turno: Entero;Inicialización P1QE = false; P2QE = false; turno = 1;

Combinación entre el

algoritmo 1 y algoritmo 4