El algoritmo de Dekker es la primera solución correcta conocida al problema de exclusión mutua en programación paralela . Edsger Dijkstra se refiere al matemático holandés T. Dekker como el autor de este algoritmo en su trabajo sobre la comunicación entre procesos [1] . Permite que dos subprocesos de ejecución compartan un recurso no compartido sin conflictos, utilizando solo la memoria compartida para la comunicación.
Si dos procesos intentan entrar en la sección crítica al mismo tiempo, el algoritmo solo permitirá que uno de ellos lo haga, en función de a quién le toque en ese momento. Si un proceso ya ha entrado en la sección crítica, el otro esperará hasta que el primero la abandone. Esto se hace mediante el uso de dos banderas (indicadores de "intención" de entrar en la sección crítica) y una variable de turno (que indica de qué proceso es el turno).
| bandera[0] := falso bandera[1] := falso turno := 0 // o 1 | |
| p0: flag[0] := true while flag[1] = true { if turno = 1 { bandera[0] := falso mientras gira = 1 {} bandera[0] := verdadero } } // sección crítica ... turno := 1 bandera[0] := falso // fin de la sección crítica ... | p1: flag[1] := true while flag[0] = true { if turno = 0 { bandera[1] := falso mientras gira = 0 {} bandera[1] := verdadero } } // sección crítica ... turno := 0 bandera[1] := falso // fin de la sección crítica ... |
Los procesos anuncian su intención de entrar en la sección crítica; esto se comprueba mediante el bucle "while" exterior. Si ningún otro proceso ha declarado tal intención, es seguro ingresar a la sección crítica (sin importar de quién sea el turno). La exclusión mutua aún estará garantizada, ya que ningún proceso puede ingresar a la sección crítica hasta que se establezca este indicador (suponiendo que al menos un proceso ingrese al ciclo while). También garantiza el progreso, ya que no habrá que esperar a que el proceso salga de la "intención" para entrar en el tramo crítico. De lo contrario, si se ha configurado otra variable de proceso, ingrese un ciclo "while" y la variable de giro indicará quién puede ingresar a la sección crítica. Un proceso cuyo turno no ha llegado deja la intención de entrar en la sección crítica hasta que llega su turno (el ciclo interno "while"). El proceso cuyo turno sea saldrá del ciclo while y entrará en la sección crítica.
El algoritmo de Dekker garantiza la exclusión mutua , la imposibilidad de que se produzca un interbloqueo o un cuelgue. Veamos por qué la última propiedad es verdadera. Digamos que p0 permanece dentro del bucle "while flag[1]" para siempre. Como no puede ocurrir interbloqueo, tarde o temprano p1 llegará a su sección crítica y establecerá giro = 0 (el valor de giro permanecerá constante hasta que avance p0). p0 saldrá del ciclo interno "while turn = 1" (si estaba allí). Luego establecerá flag[0] en verdadero y esperará a que flag[1] sea falso (dado que turn = 0, nunca ejecuta el ciclo while). La próxima vez que p1 intente ingresar a la sección crítica, se verá obligado a ejecutar las acciones en el bucle "while flag[0]". Específicamente, establecerá flag[1] en falso y ejecutará el bucle "while turn = 0" (porque turn sigue siendo 0). La próxima vez que el control pase a p0, saldrá del bucle "while flag[1]" y entrará en la sección crítica.
Si el algoritmo se modifica para que las acciones en el ciclo "while flag[1]" se realicen sin verificar la condición "turn = 0", entonces habrá una posibilidad de bloqueo ( inanición en inglés ). Por lo tanto, todos los pasos del algoritmo son necesarios.
Una de las ventajas del algoritmo es que no requiere comandos especiales de "verificar configuración " (operaciones atómicas de lectura, actualización y escritura) y, como resultado, es fácilmente portátil entre diferentes lenguajes de programación y arquitecturas informáticas. Las desventajas son su aplicabilidad solo al caso con dos procesos y el uso de un ciclo de espera en lugar suspender el proceso: el uso de un ciclo de espera implica que los procesos deben pasar una cantidad mínima de tiempo dentro de la sección crítica.
Los sistemas operativos modernos proporcionan primitivas de sincronización que son más generales y flexibles que el algoritmo Dekker. Sin embargo, cabe señalar que en ausencia de una simultaneidad real entre dos procesos, las operaciones de entrada y salida de la sección crítica serán muy eficientes al utilizar este algoritmo.
Muchos microprocesadores modernos ejecutan instrucciones desordenadas, incluso puede que no se respete el orden de acceso a la memoria (ver orden de acceso a la memoria ). El algoritmo no funcionará en máquinas SMP equipadas con dichos procesadores a menos que se utilicen barreras de memoria .
Además, los compiladores de optimización pueden realizar tales transformaciones del programa que el algoritmo dado dejará de funcionar independientemente de los problemas de la plataforma de hardware. Dicho compilador puede encontrar que las variables indicadoras flag[0] y flag[1] no se leen dentro del bucle. Luego, con la ayuda de un proceso llamado eliminación del invariante del bucle , eliminará las escrituras en estas variables del código de operación generado, considerándolas redundantes. Si el compilador detecta que la variable turn nunca cambia en el ciclo interno, entonces puede realizar una conversión similar, lo que da como resultado un ciclo infinito potencial . Si se realiza alguna de estas transformaciones, el algoritmo dejará de funcionar independientemente de la arquitectura del hardware. El lenguaje de programación puede proporcionar palabras clave (directivas) que prohíban al compilador realizar las optimizaciones descritas para la variable especificada.