Algoritmo de Dekker

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 de turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización.

Condiciones

No hay prioridad entre procesos.
La capacidad de los equipos es irrelevante.
Si un proceso muere fuera de la región crítica, el algoritmo sigue funcionando.
Un bloqueo mutuo no se considera como solución válida.

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 crítica.
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;  // Está listo para acceder a la Sección Crítica
    while (bandera[1-proc_id] == cierto) { // Mientras el otro esté procesando
       if (turno == 1-proc_id) {           // si es su turno
          bandera[proc_id] = 0;            // indicar que no está listo y
          while (turno == (1-proc_id)) {}  // esperar activamente.
          bandera[proc_id] = 1;            // Cuando terminó de esperar, está listo
       }
    }
    /* ''Sección crítica'' */
    turno = 1-proc_id; // Indicar el turno del otro proceso
    bandera[proc_id] = 0;  // Indicar que ya no está listo (para acceder a la Sección Crítica)
    /* ''Sección no crítica'' */
 }

Ventajas

Este algoritmo garantiza la exclusión mutua.
Garantiza la libertad de bloqueos mutuos.
Garantiza la libertad de inanición.
Es un algoritmo simple y portable.

Desventajas

Hace uso de espera activa.
No suspende a los procesos que están esperando acceso.
Puede llegar a entrar en ciclos infinitos.

Historia

Surgió a finales del siglo XIX y principios del siglo XX a partir de las necesidades ferroviarias de la época. En realidad, el problema a resolver era muy simple: ¿Cómo evitar que los trenes chocaran entre sí al pasar por un cierto segmento de las vías? Es aquí donde surge el uso de los semáforos. Otro campo de aplicación fue el de la Telegrafía. La problemática a resolver era manejar múltiples transmisiones con un número limitado de canales. La respuesta fue un multiplexor.

Ya en la década de los 60's, en la época del auge del cómputo, la problemática era el acceso a los recursos compartidos. E.W.Dijkstra dedicó tres años de su vida a encontrar la primera solución.

Véase también

Enlaces externos

Algoritmo de Dekker Versión 1 para N procesos en Java

Datos: Q1183654