Algoritmo de Dekker
De Wikipedia, la enciclopedia libre
El 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.
Existen 5 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 critica 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.
shared int cierto = 1; ''/* Definición de variables compartidas */ '' shared int bandera[2] = {0,0}; shared int turno = 0; while (cierto) { bandera[proc_id] = cierto; while (bandera[1-proc_id] == cierto) { if (turno == 1-proc_id) { bandera[proc_id] = 0; while (turno == (1-proc_id)) /* espera a que sea su turno de intentar */; bandera[proc_id] = 1; } /* ''Sección crítica'' */ turno = 1-proc_id; /* es el turno del otro proceso */ bandera[proc_id] = 0; /* ''Sección no crítica'' */ } }
