El algoritmo de Dekker del es un algoritmo de la programación concurrente para la exclusión mutua derivada por el holandés T. Dekker del matemático que permite que dos procesos (hilos de rosca) compartan un recurso single-use sin conflicto, usando solamente la memoria compartida para la comunicación.

Evita la alternación terminante de un algoritmo dar vuelta-que toma ingenuo, y era uno de los primeros algoritmos de la exclusión mutua que se inventarán.

Introducción

Si dos procesos intentan incorporar una sección crítica al mismo tiempo, el algoritmo permitirá solamente un proceso adentro, basado en cuyos es la vuelta él. Si un proceso está ya en la sección crítica, el otro proceso la espera ocupada para el primer proceso saldrá. Esto es hecha por el uso de dos banderas f0 y f1 que indiquen una intención de incorporar la sección crítica y una variable de la vuelta que indique quién tiene prioridad entre los dos procesos.

Pseudocode

f0: = falso f1: = falso vuelta: = 0 // o 1 p0: p1: f0: = f1 verdadero: = verdad mientras que f1 { mientras que f0 { si ≠ 0 de la vuelta de { si ≠ 1 de la vuelta de { f0: = f1 falso: = falso mientras que ≠ 0 de la vuelta de { mientras que ≠ 1 de la vuelta de { }} f0: = f1 verdadero: = verdad }} }} sección crítica de // de la sección crítica de // … … sección del resto de // de la sección del resto de // vuelta: = 1 vuelta: = 0 f0: = f1 falso: = falso

Los procesos indican una intención de incorporar la sección crítica que es probada por el externo mientras que lazo. Si el otro proceso no ha señalado intento por medio de una bandera, la sección crítica se puede incorporar con seguridad con independencia de la vuelta actual. La exclusión mutua todavía será garantizada como ninguno de los dos procesos puede llegar a ser críticos antes de fijar su bandera (la implicación por lo menos de un proceso incorporará el lazo del rato). Esto también garantiza progreso pues el esperar no ocurrirá en un proceso cuál ha retirado intento para llegar a ser crítico. Alternativo, si la otra variable de proceso fue fijada se incorpora el lazo del rato y la variable de la vuelta establecerá quién se permite llegar a ser crítico. Los procesos sin prioridad retirarán su intención de incorporar la sección crítica hasta que se den prioridad otra vez (el interno mientras que lazo). Los procesos con prioridad se romperán del lazo del rato e incorporarán su sección crítica.

El algoritmo de Dekker garantiza la exclusión mutua, la libertad del callejón sin salida, y la libertad del hambre. Veamos porqué la característica pasada se sostiene. Suponer que p0 está pegado dentro del " mientras que f1" lazo por siempre. Hay libertad del callejón sin salida, p1 procederá a su sección crítica y fijará tan eventual vuelta = 0 (y el valor de la vuelta permanecerá sin cambiar mientras no lo haga p0 progreso). P0 explotará eventual del " interno; mientras que ≠ 0" de la vuelta; lazo (si era nunca stuck en él). Después que fijará f0: = verdad y colocar abajo para a f1 que espera para llegar a ser falso (desde vuelta = 0, nunca hará las acciones en el lazo del rato). La próxima vez que p1 intenta incorporar su sección crítica, será forzado a ejecutar las acciones en su " mientras que f0" lazo. Particularmente, fijará f1 = falso y conseguirá eventual stuck en el " mientras que ≠ 1" de la vuelta; lazo (puesto que la vuelta sigue siendo 0). La próxima vez que el control pasa a p0, saldrá el " mientras que f0" colocar e incorporar su sección crítica.

Si el algoritmo fue modificado realizando las acciones en el " mientras que f0" colocar sin la comprobación de si vuelta = 0, después hay una posibilidad del hambre. Así todos los pasos en el algoritmo son necesarios.

Nota

Una ventaja de este algoritmo es que no requiere el especial Prueba-y-fijó instrucciones de (atómicos leídos/se modifican/escriben) y es por lo tanto alto portable entre las idiomas y las arquitecturas de la máquina. Una desventaja es que está limitada a dos procesos y hace uso que espera ocupado en vez de la suspensión de proceso. (El uso de esperar ocupado sugiere que los procesos pasen un mínimo de tiempo dentro de la sección crítica.)

Los sistemas operativos modernos proporcionan los primitivos de la exclusión mutua que son más generales y flexibles que el algoritmo de Dekker. Sin embargo, debe ser observado que en la ausencia de contención real entre los dos procesos, la entrada y la salida de la sección crítica es extremadamente eficientes cuando se utiliza el algoritmo de Dekker.

Muchas CPU modernas ejecutan sus instrucciones en una manera fuera de servicio. Este algoritmo no trabajará en las máquinas del SMP equipadas de estas CPU sin el uso de las barreras de la memoria

Además, muchos recopiladores de optimización pueden realizar las transformaciones que harán este algoritmo fallar sin importar la plataforma. En muchas idiomas, es legal para que un recopilador detecte que el f0 de las variables de la bandera y el f1 nunca están alcanzados en el lazo. Puede entonces quitar escribe a esas variables del lazo, usar un llamado de proceso el movimiento Lazo-invariante del código. También sería posible que muchos recopiladores detectar que la variable de la vuelta del nunca es modificada por el lazo interno, y realicen una transformación similar, dando por resultado un bucle infinito potencial. Si cualquiera de estas transformaciones se realiza, el algoritmo fallará, sin importar arquitectura.

Para aliviar este problema, las variables volátiles se deben marcar como modificable fuera del alcance del contexto actual de la ejecución. Por ejemplo, en Java, uno anotaría estas variables como “volátil”. Observar sin embargo eso el " de C/C++; volatile" la cualidad garantiza solamente que el recopilador genera código con ordenar apropiada; no incluye las barreras necesarias de la memoria para garantizar la ejecución del de la en-orden de ese código.

Ver también

.