El algoritmo de Dekker es la primera solución correcta conocida al problema de exclusión mutua en programación concurrente , donde los procesos solo se comunican a través de la memoria compartida. La solución se atribuye al matemático holandés Th. J. Dekker por Edsger W. Dijkstra en un artículo inédito sobre descripciones de procesos secuenciales [1] y su manuscrito sobre procesos secuenciales cooperativos [2] . Permite que dos subprocesos compartan un recurso de un solo uso sin conflictos, utilizando solo la memoria compartida para la comunicación.
Evita la alternancia estricta de un algoritmo de turnos ingenuo y fue uno de los primeros algoritmos de exclusión mutua que se inventaron.
Si dos procesos intentan entrar en una sección crítica al mismo tiempo, el algoritmo permitirá que entre solo un proceso, en función de a quién le toque el turno . Si un proceso ya está en la sección crítica, el otro proceso esperará a que salga el primer proceso. Esto se hace mediante el uso de dos indicadores, wants_to_enter[0] y wants_to_enter[1] , que indican una intención de entrar en la sección crítica por parte de los procesos 0 y 1, respectivamente, y una variable turn que indica quién tiene prioridad entre los dos procesos.
El algoritmo de Dekker se puede expresar en pseudocódigo de la siguiente manera. [3]
Los procesos indican una intención de entrar en la sección crítica que se prueba mediante el bucle while externo. Si el otro proceso no ha marcado su intención, se puede entrar en la sección crítica de forma segura independientemente del turno actual. La exclusión mutua seguirá estando garantizada, ya que ningún proceso puede volverse crítico antes de establecer su bandera (lo que implica que al menos un proceso entrará en el bucle while). Esto también garantiza el progreso, ya que no habrá espera en un proceso que haya retirado su intención de volverse crítico. Alternativamente, si se estableció la variable del otro proceso, se entra en el bucle while y la variable de turno establecerá quién tiene permitido volverse crítico. Los procesos sin prioridad retirarán su intención de entrar en la sección crítica hasta que se les dé prioridad nuevamente (el bucle while interno). Los procesos con prioridad saldrán del bucle while e ingresarán en su sección crítica.
El algoritmo de Dekker garantiza la exclusión mutua , la libertad de bloqueo y la libertad de inanición . Veamos por qué se cumple la última propiedad. Supongamos que p0 está atascado dentro del bucle while wants_to_enter[1] para siempre. No hay bloqueo, por lo que eventualmente p1 procederá a su sección crítica y establecerá turn = 0 (y el valor de turn permanecerá sin cambios mientras p0 no avance). Finalmente, p0 saldrá del bucle interno while turn ≠ 0 (si alguna vez estuvo atascado en él). Después de eso, establecerá wants_to_enter[0] en verdadero y se establecerá en esperar a que wants_to_enter[1] se vuelva falso (ya que turn = 0 , nunca realizará las acciones en el bucle while). La próxima vez que p1 intente ingresar a su sección crítica, se verá obligado a ejecutar las acciones en su bucle while wants_to_enter[0] . En particular, eventualmente establecerá wants_to_enter[1] en falso y se quedará atascado en el bucle while turn ≠ 1 (ya que turn sigue siendo 0). La próxima vez que el control pase a p0, saldrá del bucle while wants_to_enter[1] y entrará en su sección crítica.
Si se modificara el algoritmo realizando las acciones del bucle while wants_to_enter[1] sin comprobar si turn = 0 , entonces existe la posibilidad de que se produzca una inanición. Por lo tanto, todos los pasos del algoritmo son necesarios.
Una ventaja de este algoritmo es que no requiere instrucciones especiales de prueba y configuración (lectura/modificación/escritura atómicas) y, por lo tanto, es muy portátil entre lenguajes y arquitecturas de máquinas. Una desventaja es que está limitado a dos procesos y utiliza la espera activa en lugar de la suspensión del proceso. (El uso de la espera activa sugiere que los procesos deberían pasar una cantidad mínima de tiempo dentro de la sección crítica).
Los sistemas operativos modernos proporcionan primitivas de exclusión mutua que son más generales y flexibles que el algoritmo de Dekker. Sin embargo, en ausencia de una contención real entre los dos procesos, la entrada y salida de la sección crítica es extremadamente eficiente cuando se utiliza el algoritmo de Dekker.
Muchas CPU modernas ejecutan sus instrucciones de forma desordenada; incluso los accesos a la memoria pueden reordenarse (consulte ordenación de la memoria ). Este algoritmo no funcionará en máquinas SMP equipadas con estas CPU sin el uso de barreras de memoria .
Además, muchos compiladores optimizadores pueden realizar transformaciones que harán que este algoritmo falle independientemente de la plataforma. En muchos lenguajes, es legal que un compilador detecte que las variables de bandera wants_to_enter[0] y wants_to_enter[1] nunca son accedidas en el bucle. Luego puede eliminar las escrituras a esas variables del bucle, utilizando un proceso llamado código invariante de bucle motion . También sería posible que muchos compiladores detecten que la variable turn nunca es modificada por el bucle interno y realicen una transformación similar, lo que resultará en un potencial bucle infinito . Si se realiza cualquiera de estas transformaciones, el algoritmo fallará, independientemente de la arquitectura.
Para aliviar este problema, las variables volátiles deben marcarse como modificables fuera del ámbito del contexto de ejecución actual. Por ejemplo, en C, C++, C# o Java, se anotarían estas variables como "volátiles". Sin embargo, tenga en cuenta que el atributo "volátil" de C/C++ solo garantiza que el compilador genere código con el orden adecuado; no incluye las barreras de memoria necesarias para garantizar la ejecución en orden de ese código. Las variables atómicas de C++11 se pueden utilizar para garantizar los requisitos de ordenación adecuados: de forma predeterminada, las operaciones sobre variables atómicas son secuencialmente consistentes, por lo que si las variables wants_to_enter y turn son atómicas, una implementación ingenua "simplemente funcionará". Alternativamente, el orden se puede garantizar mediante el uso explícito de vallas separadas, con las operaciones de carga y almacenamiento utilizando un orden relajado.