Contrastando los algoritmos de Peterson y Dekker

Estoy tratando de entender los algoritmos de Peterson y Dekker que son muy similares y muestran muchas simetrías.

Traté de formular los algoritmos en lenguaje informal como sigue:

Peterson's: "I want to enter."                 flag[0]=true;
            "You can enter next."              turn=1;
            "If you want to enter and          while(flag[1]==true&&turn==1){
            it's your turn I'll wait."         }
            Else: Enter CS!                    // CS
            "I don't want to enter any more."  flag[0]=false;

Dekker's:   "I want to enter."                 flag[0]=true;
            "If you want to enter              while(flag[1]==true){
             and if it's your turn               if(turn!=0){
             I don't want to enter any more."      flag[0]=false;
            "If it's your turn                     while(turn!=0){
             I'll wait."                           }
            "I want to enter."                     flag[0]=true;
                                                 }
                                               }
            Enter CS!                          // CS
            "You can enter next."              turn=1;
            "I don't want to enter any more."  flag[0]=false;

La diferencia parece ser el punto donde "You can enter next."ocurre y el hecho que "if it's your turn I don't want to enter any more."ocurre en Dekker's.

En el algoritmo de Peterson, los dos procesos parecen ser dominantes. Un proceso parece abrirse paso en la sección crítica a menos que sea el turno del otro.

Por el contrario, en el algoritmo de Dekker, los dos procesos parecen ser sumisos y educados. Si ambos procesos desean ingresar a la sección crítica, y es el turno del otro, el proceso decide que ya no desea ingresar. (¿Es esto necesario para la libertad de hambre? ¿Por qué?)

¿Cómo difieren exactamente estos algoritmos? Me imagino que cuando ambos procesos intentan ingresar a la sección crítica, en Peterson, el proceso dice "Entro", mientras que en Dekker el proceso dice "Puedes ingresar". ¿Alguien puede aclarar la forma en que se comportan los procesos en cada algoritmo? ¿Es correcta mi forma de expresarlo en términos informales?

Sus descripciones informales de los algoritmos son maravillosas.

Creo que en ambos casos el autor estaba tratando de encontrar la solución más simple que pudieran pensar que garantizara tanto la exclusión mutua como la libertad de punto muerto. Ninguno de los algoritmos está libre de hambre o es justo.[ed: como se señaló en los comentarios, el algoritmo de Peterson es libre de hambre y justo]. La solución de Dekker fue el primer algoritmo de exclusión mutua que usaba solo instrucciones de carga y almacenamiento. Fue introducido en Dijkstra, Edsger W .; "Procesos secuenciales cooperantes", en F. Genuys, ed., Lenguajes de programación: Instituto de Estudios Avanzados de la OTAN , págs. 43-112, Academic Press, 1968 . Si lee el documento, verá que Dijkstra trabaja en varios intentos, reconoce el problema con cada uno y luego agrega un poco más para la próxima versión. Parte de la ineficiencia de su algoritmo proviene del hecho de que comienza con un algoritmo de turno y luego trata de modificarlo para permitir que los procesos progresen en cualquier orden. (No solo 0,1,0,1, ...)

El algoritmo de Peterson se publicó en 1981, después de más de una década de experiencia y retrospectiva sobre el algoritmo de Dekker. Peterson quería un algoritmo mucho más simple que Dekker para que la prueba de corrección sea mucho más fácil. Puedes ver que él sentía cierta frustración con la comunidad por el título de su artículo. Peterson, GL; "Mitos sobre el problema de exclusión mutua", Inf. Proc. Letón. , 12 (3): 115-116, 1981. Lectura muy rápida y muy bien escrita. (Y los comentarios sarcásticos sobre los métodos formales no tienen precio). El artículo de Peterson también analiza el proceso mediante el cual construyó su solución a partir de intentos más simples. (Dado que su solución es más simple, requirió menos pasos intermedios). Tenga en cuenta que la principal diferencia (lo que llama "dominio" en lugar de "sumisión") es que Peterson comenzó de nuevo (no desde el algoritmo de turno que Dijkstra comenzó con ) su ciclo de espera es más simple y más eficiente. Se da cuenta de que puede salirse con la suya con simples pruebas en bucle, mientras que Dijkstra tuvo que retroceder y volver a intentarlo cada vez.

Siento que también debo mencionar el clásico papel de algoritmo de panadería de Lamport : Lamport, Leslie; "Una nueva solución del problema de programación concurrente de Dijkstra", Comm ACM 17 (8): 453-455, 1974 . El algoritmo Bakery es posiblemente más simple que el algoritmo de Dekker (y ciertamente más simple en el caso de más de 2 procesadores), y está específicamente diseñado para ser tolerante a fallas. Lo menciono específicamente por dos razones. Primero, porque proporciona un poco de historia sobre la definición del problema de exclusión mutua e intenta resolverlo hasta 1974. Segundo, porque el algoritmo de Bakery demuestra que no se requiere atomicidad de hardware para resolver el problema de exclusión mutua.

Finalmente, uno de mis favoritos en particular es Lamport, Leslie; "Un algoritmo rápido de exclusión mutua", ACM Trans. Comp. Sys. , 5 (1): 1-11, 1987. En este documento, Lamport estaba tratando de optimizar una solución al problema de exclusión mutua en el caso (común) de que hay poca controversia para la sección crítica. Nuevamente, garantiza la exclusión mutua y la libertad de punto muerto, pero no la justicia. Es (creo) el primer algoritmo de exclusión mutua que usa solo lecturas y escrituras normales que pueden sincronizar N procesadores en O (1) cuando no hay contención. (Cuando hay contención, recurre a una prueba O (N)). Da una demostración informal de que lo mejor que puede hacer en el caso libre de contención es siete accesos a la memoria. (Dekker y Peterson lo hacen con 4, pero solo pueden manejar 2 procesadores, cuando extiendes sus algoritmos a N tienen que agregar accesos O (N) adicionales).

En general: diría que el algoritmo de Dekker en sí es interesante principalmente desde una perspectiva histórica. El artículo de Dijkstra explicó la importancia del problema de exclusión mutua y demostró que podría resolverse. Pero con muchos años de retrospectiva, se han encontrado soluciones más simples (y más eficientes) que las de Dekker.

En el siguiente documento damos modelos formales para los algoritmos de Peterson y Dekker (y algunos otros) y utilizamos el verificador de modelos para probar sus propiedades. Encuentre nuestros resultados en la tabla a continuación (las columnas "Punto muerto" y "Divergente" se refieren a nuestros modelos, "ME" = VERDADERO significa que el algoritmo es correcto, "Adelantamiento" = VERDADERO significa que es justo).

R. Meolic, T. Kapus, Z. Brezočnik. ACTLW: una lógica de árbol de cómputo basada en la acción con un operador a menos. Information Sciences, 178 (6), págs. 1542-1557, 2008.

https://doi.org/10.1016/j.ins.2007.10.023

El algoritmo de Peterson tiene una presión más estricta al ingresar a la sección crítica, donde el algoritmo de dekker es relativamente más suave y menos agresivo. Para que quede más claro, veamos un ejemplo sobre la cultura iraní. Antes de entrar en este ejemplo, ¡es bueno saber que las personas iraníes tienen un comportamiento realmente suave entre sí al ingresar a algún lugar! Supongo que dos hombres iraníes van a entrar en una casa, y esa casa solo tiene una puerta para entrar.

Ahora imagine a dos hombres de otra cultura ( Cultura Zombian ) que en realidad no se preocupan demasiado el uno por el otro al ingresar a algún lugar ( es cuestión de respeto preguntarle a alguien si quiere ingresar o no ).

Para aclarar la información sobre el problema podemos decir que:

• Dos iraníes = dos procesos que utilizan el algoritmo de Dekker
• Two Zombians = Dos procesos usando el algoritmo Peterson

Así que veamos qué se hace en cada algoritmo ( cultura ). Los siguientes comentarios son para el primer hombre iraní que entrará a la casa mientras usa el algoritmo Dekker :

p0:
   wants_to_enter[0] ← true // Goes through the house entrance
   while wants_to_enter[1] { // If the other man wants to enter too
      if turn ≠ 0 { // Then see if it is your turn or not
         wants_to_enter[0] ← false // If it is not your turn don't go furthur
         while turn ≠ 0 { // and wait until it is your turn
           // busy wait
         }
         wants_to_enter[0] ← true // when it is your turn go through the door
      }
   }

   // critical section
   ...
   turn ← 1
   wants_to_enter[0] ← false // Set the turn for the other man
   // remainder section

También tenemos dos zombis que entrarán en la casa usando el algoritmo Peterson . Este va de la siguiente manera:

P0:     
  flag[0] = true; // Goes through the house entrance
  turn = 1; // Set the turn for himself
  while (flag[1] && turn == 1) // Wait until the other one is going in
  {
   // busy wait
  }
   // critical section
      ...
   // end of critical section
  flag[0] = false; // Done going inside

Es importante mencionar que ambos no entran mientras el otro lo hace ( exclusión mutua ), pero el pueblo iraní es mucho más suave.