Algoritmo de Dekker

El algoritmo de Dekker es la primera solución correcta conocida al problema de exclusión mutua en la 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 y su manuscrito sobre procesos secuenciales cooperativos. Permite que dos subprocesos compartan un recurso de un solo uso sin conflicto, 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 inventaron.

Resumen

Si dos procesos intentan ingresar a una sección crítica al mismo tiempo, el algoritmo solo permitirá la entrada de un proceso, según el turn de quién sea. Si un proceso ya está en la sección crítica, el otro proceso esperará a que el primer proceso salga. Esto se hace mediante el uso de dos indicadores, quiere_ingresar[0] y quiere_ingresar[1], que indican la intención de ingresar. 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

El algoritmo de Dekker se puede expresar en pseudocódigo, de la siguiente manera.

 variables
quiere_to_enter: matriz de 2 booleanos
giro: entero

quiere_to_enter[0] ← false
quiere_to_enter[1] ← false
← 0 // o 1

p0:
← verdadero
mientras que quiere_to_enter[1] {
si se convierte en
quiere_to_enter[0] ← false
mientras girar 0
// ocupado espera
}
← verdadero
}
}

// sección crítica
...
← 1
quiere_to_enter[0] ← false
// sección restante

p1:
quiere_to_enter[1] ← verdadero
mientras que quiere_to_enter [0] {
si se convierte en
quiere_to_enter[1] ← false
mientras girar 1 {
// ocupado espera
}
quiere_to_enter[1] ← verdadero
}
}

// sección crítica
...
← 0
quiere_to_enter[1] ← false
// sección restante

Los procesos indican una intención de ingresar a la sección crítica que es probada por el ciclo while externo. 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 ingresará al ciclo while). Esto también garantiza el progreso ya que no se producirá una espera en un proceso que ha retirado la intención de volverse crítico. Alternativamente, si se configuró la variable del otro proceso, se ingresa el ciclo while y la variable turn establecerá quién puede 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 ciclo 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 puntos muertos y la ausencia de inanición. Veamos por qué se cumple la última propiedad. Supongamos que p0 está atascado dentro del bucle while want_to_enter[1] para siempre. Hay libertad de interbloqueo, 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 lo haga). progreso). Eventualmente, p0 saldrá del ciclo interno while turn ≠ 0 (si alguna vez estuvo 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 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 bucle while want_to_enter[0]. En particular, eventualmente establecerá wants_to_enter[1] en false y se atascará en el ciclo while turn ≠ 1 (desde turn sigue siendo 0). La próxima vez que el control pase a p0, saldrá del ciclo while want_to_enter[1] e ingresará a su sección crítica.

Si el algoritmo se modificara realizando las acciones en el bucle while want_to_enter[1] sin comprobar si turn = 0, entonces existe la posibilidad de inanición. Por lo tanto, todos los pasos del algoritmo son necesarios.