El algoritmo de Dekker

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 mediante memoria compartida. La solución fue atribuida al matemático neerlandés Th. J. Dekker por Edsger W. Dijkstra en un artículo inédito sobre descripciones de procesos secuenciales ^{[ 1 ]} y en su manuscrito sobre procesos secuenciales cooperativos ^{[ 2 ]} . Permite que dos hilos compartan un recurso de uso único sin conflicto, utilizando únicamente memoria compartida para la comunicación.

Evita la alternancia estricta de un algoritmo ingenuo de toma de turnos, 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 solo permitirá el acceso a uno, según el turno que le corresponda. Si un proceso ya se encuentra en la sección crítica, el otro esperará ocupado a que el primero salga. Esto se logra mediante dos indicadores, wants_to_enter[0] y wants_to_enter[1] , que señalan la intención de los procesos 0 y 1 de entrar en la sección crítica, respectivamente, y una variable llamada turn que indica la prioridad entre ambos procesos.

El algoritmo de Dekker se puede expresar en pseudocódigo , como sigue. ^{[ 3 ]}

Los procesos indican su intención de entrar en la sección crítica, la cual es comprobada por el bucle while externo. Si el otro proceso no ha indicado su intención, se puede entrar en la sección crítica de forma segura, independientemente del turno actual. La exclusión mutua se garantiza, ya que ningún proceso puede volverse crítico antes de establecer su indicador (lo que implica que al menos un proceso entrará en el bucle while). Esto también garantiza el progreso, ya que no se esperará a un proceso que haya retirado su intención de volverse crítico. Alternativamente, si la variable del otro proceso está establecida, se entra en el bucle while y la variable de turno determinará quién tiene permiso para volverse crítico. Los procesos sin prioridad retirarán su intención de entrar en la sección crítica hasta que se les asigne prioridad nuevamente (el bucle while interno). Los procesos con prioridad saldrán del bucle while y entrarán en su sección crítica.

El algoritmo de Dekker garantiza la exclusión mutua , la ausencia de interbloqueo y la ausencia de inanición . Veamos por qué se cumple la última propiedad. Supongamos que p0 se queda atascado indefinidamente dentro del bucle while wants_to_enter[1] . Hay ausencia de interbloqueo, por lo que eventualmente p1 pasará a su sección crítica y establecerá turn = 0 (y el valor de turn permanecerá sin cambios mientras p0 no avance). Eventualmente, p0 saldrá del bucle interno while turn ≠ 0 (si alguna vez se quedó atascado en él). Después de eso, establecerá wants_to_enter[0] en verdadero y 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 entrar en su sección crítica, se verá obligado a ejecutar las acciones en su bucle while wants_to_enter[0] . En concreto, eventualmente establecerá wants_to_enter[1] en falso y se quedará atascado en el bucle while turn ≠ 1 (ya que turn permanece en 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 el algoritmo se modificara realizando las acciones en el bucle while wants_to_enter[1] sin comprobar si turn = 0 , entonces existe la posibilidad de que se produzca 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 altamente portable entre lenguajes y arquitecturas de máquina. Una desventaja es que está limitado a dos procesos y utiliza espera activa en lugar de suspensión de procesos. (El uso de la espera activa sugiere que los procesos deben pasar un tiempo mínimo dentro de la sección crítica).

Los sistemas operativos modernos ofrecen primitivas de exclusión mutua más generales y flexibles que el algoritmo de Dekker. Sin embargo, en ausencia de contención real entre los dos procesos, la entrada y salida de la sección crítica resulta extremadamente eficiente cuando se utiliza el algoritmo de Dekker.

Muchos procesadores modernos ejecutan sus instrucciones de forma desordenada; incluso los accesos a memoria pueden reordenarse (véase ordenación de memoria ). Este algoritmo no funcionará en máquinas SMP equipadas con estos procesadores sin el uso de barreras de memoria .

Además, muchos compiladores optimizadores pueden realizar transformaciones que provocarán el fallo de este algoritmo independientemente de la plataforma. En muchos lenguajes, es válido que un compilador detecte que las variables de bandera ` wants_to_enter[0]` y `wants_to_enter[1]` nunca se acceden dentro del bucle. En ese caso, puede eliminar las escrituras en dichas variables del bucle mediante un proceso denominado movimiento de código invariante al bucle . También sería posible que muchos compiladores detectaran que la variable `turn` nunca se modifica dentro del bucle interno y realizaran una transformación similar, lo que podría generar un bucle infinito . Si se realiza cualquiera de estas transformaciones, el algoritmo fallará, independientemente de la arquitectura.

Para mitigar 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, estas variables se anotarían como 'volatile'. Sin embargo, cabe señalar que el atributo 'volatile' de C/C++ solo garantiza que el compilador genere código con el orden correcto; no incluye las barreras de memoria necesarias para garantizar la ejecución en orden de dicho código. Las variables atómicas de C++11 pueden utilizarse para garantizar los requisitos de ordenación adecuados; por defecto, las operaciones con variables atómicas son secuencialmente consistentes, por lo que si las variables `wants_to_enter` y `turn` son atómicas, una implementación simple funcionará sin problemas. Como alternativa, la ordenación puede garantizarse mediante el uso explícito de barreras separadas, con las operaciones de carga y almacenamiento utilizando un ordenación menos estricta.

• Algoritmo de Eisenberg y McGuire
• El algoritmo de Peterson
• Algoritmo de la panadería de Lamport
• El algoritmo de Szymański
• Semáforos