Algoritmo de Dekker - Dekker's algorithm

El algoritmo de Dekker es la primera solución correcta conocida al problema de exclusión mutua en la programación concurrente . 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 y su manuscrito sobre procesos secuenciales cooperantes. 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 ingenuo de toma de turnos y fue uno de los primeros algoritmos de exclusión mutua que se inventó.

Visión general

Si dos procesos intentan ingresar a una sección crítica al mismo tiempo, el algoritmo permitirá que entre solo un proceso, según de quién sea el turno. Si un proceso ya se encuentra en la sección crítica, el otro proceso estará ocupado esperando a que salga el primer proceso. Esto se hace mediante el uso de dos banderas, want_to_enter [0] y wants_to_enter [1] , que indican una intención de ingresar a la sección crítica por parte de los procesos 0 y 1, respectivamente, y una variable turno que indica quién tiene prioridad entre los dos procesos.

Algoritmo de Dekker

El algoritmo de Dekker se puede expresar en pseudocódigo , como sigue. 

    variables
        wants_to_enter : array of 2 booleans
        turn : integer

    wants_to_enter[0] ← false
    wants_to_enter[1] ← false
    turn ← 0   // or 1

p0:
   wants_to_enter[0] ← true
   while wants_to_enter[1] {
      if turn ≠ 0 {
         wants_to_enter[0] ← false
         while turn ≠ 0 {
           // busy wait
         }
         wants_to_enter[0] ← true
      }
   }

   // critical section
   ...
   turn ← 1
   wants_to_enter[0] ← false
   // remainder section

p1:
   wants_to_enter[1] ← true
   while wants_to_enter[0] {
      if turn ≠ 1 {
         wants_to_enter[1] ← false
         while turn ≠ 1 {
           // busy wait
         }
         wants_to_enter[1] ← true
      }
   }
 
   // critical section
   ...
   turn ← 0
   wants_to_enter[1] ← false
   // remainder section

Los procesos indican una intención de entrar en la sección crítica que es probada por el ciclo externo while. Si el otro proceso no ha marcado la intención, se puede ingresar a la sección crítica de manera segura independientemente del turno actual. La exclusión mutua seguirá estando garantizada, ya que ninguno de los procesos puede volverse crítico antes de establecer su bandera (lo que implica que al menos un proceso entrará en el ciclo while). Esto también garantiza el progreso, ya que no habrá espera en un proceso que ha retirado la intención de volverse crítico. Alternativamente, si se estableció la variable del otro proceso, se ingresa el ciclo while y la variable de turno establecerá quién puede convertirse en crítico. Los procesos sin prioridad retirarán su intención de entrar en la sección crítica hasta que vuelvan a tener prioridad (el bucle interno while). Los procesos con prioridad se romperán del ciclo while y entrarán en su sección crítica.

El algoritmo de Dekker garantiza la exclusión mutua , la ausencia de bloqueo y la ausencia de inanición . Veamos por qué se mantiene la última propiedad. Suponga que p0 está atascado dentro del ciclo "while wants_to_enter [1]" para siempre. Hay libertad de 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 progrese). Eventualmente, p0 saldrá del bucle interno "while turn ≠ 0" (si alguna vez estuvo atascado en él). Después de eso, establecerá want_to_enter [0] en verdadero y esperará a que wants_to_enter [1] se convierta en falso (dado que turn = 0, nunca hará las acciones en el ciclo while). La próxima vez que p1 intente ingresar a su sección crítica, se verá obligado a ejecutar las acciones en su ciclo "while wants_to_enter [0]". En particular, eventualmente establecerá want_to_enter [1] en falso y se atascará en el ciclo "while turn ≠ 1" (ya que turn sigue siendo 0). La próxima vez que el control pase a p0, saldrá del ciclo "while wants_to_enter [1]" y entrará en su sección crítica.

Si el algoritmo fue modificado realizando las acciones en el ciclo "while wants_to_enter [1]" sin verificar si turn = 0, entonces existe la posibilidad de inanición. Por tanto, todos los pasos del algoritmo son necesarios.

Notas

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 portátil entre lenguajes y arquitecturas de máquina. Una desventaja es que se limita a dos procesos y utiliza la espera ocupada en lugar de la suspensión del proceso. (El uso de espera ocupada sugiere 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 exclusión mutua que son más generales y flexibles que el algoritmo de Dekker. Sin embargo, en ausencia de una disputa real entre los dos procesos, la entrada y salida de la sección crítica es extremadamente eficiente cuando se usa el algoritmo de Dekker.

Muchas CPU modernas ejecutan sus instrucciones de forma desordenada; incluso los accesos a la memoria se pueden reordenar (ver orden 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 de optimización 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 want_to_enter [0] y wants_to_enter [1] nunca se acceden en el bucle. A continuación, puede eliminar las escrituras en esas variables del bucle, utilizando un proceso llamado movimiento de código invariante de bucle . También sería posible para muchos compiladores detectar que la variable turn nunca es modificada por el bucle interno y realizar una transformación similar, lo que da como resultado un bucle infinito potencial . Si se realiza alguna de estas transformaciones, el algoritmo fallará, independientemente de la arquitectura.

Para aliviar este problema, las variables volátiles deben marcarse como modificables fuera del alcance del contexto que se está ejecutando actualmente. Por ejemplo, en 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 genera 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 orden adecuados; de forma predeterminada, las operaciones en las variables atómicas son secuencialmente coherentes, por lo que si las variables want_to_enter y turn son atómicas, una implementación ingenua "simplemente funcionará". Alternativamente, el pedido puede garantizarse mediante el uso explícito de vallas separadas, con las operaciones de carga y almacenamiento utilizando un pedido relajado.

Ver también

Referencias