¿Por qué el número de consenso para test-and-set, 2?

17

De acuerdo con Wikipedia ,

La operación de prueba y configuración puede resolver el problema de consenso sin esperas para no más de dos procesos concurrentes.

¿Por qué no puede resolver el problema durante más de dos procesos?

ben
fuente

Respuestas:

17

Solo para asegurarnos de que estamos en la misma página, primero consideremos estas tres definiciones:

Definición. Test-and-set es una instrucción de lectura-modificación-escritura en algún registro binario (digamos que 0 y 1 son valores posibles) donde un hilo obtiene el valor anterior y escribe 1.

Definición. Se llega a un consenso entre subprocesos si todos los subprocesos deciden sobre el mismo valor (el requisito de coherencia) y todos los subprocesos deciden sobre un valor que fue realmente propuesto por uno de los subprocesos (el requisito de validez).nn

Definición. Un protocolo de consenso no requiere espera si cada llamada a un método finaliza en un número finito de pasos.

Ahora siga dos bocetos de prueba.

Reclamación 1. El número de consenso de prueba y conjunto es al menos 2. Prueba. Supongamos que tenemos dos hilos 0 y 1 que necesitan llegar a un consenso. Podríamos hacer esto dejando que cada hilo siga el protocolo de consenso a continuación:

  1. Escriba su valor propuesto en , donde es el id del subproceso y es una matriz de tamaño 2.A[t]tA
  2. Realice la instrucción de prueba y ajuste en algún registro , con inicializado a 0.RR
  3. Si el valor de retorno es 0, usted fue primero: devuelva . De lo contrario, fue el segundo: devuelva .A[t]A[|t1|]

Puede verificar usted mismo que el consenso y la libertad de espera estén satisfechos.

(Para la próxima prueba, anidaré algunas pruebas y definiciones porque creo que será más fácil de seguir).

Reclamación 2. El número de consenso de prueba y conjunto es como máximo 2. Prueba. Por contradicción. Supongamos que tenemos tres hilos , y que deseen decidir sobre los valores de , y , respectivamente, y que tenemos algún protocolo de consenso sin esperar válida que se implementa mediante la prueba-y-juego (y lee y escribe atómica )ABCabc

Podemos visualizar el proceso de consenso como un árbol dirigido, donde:

  • La raíz es el estado donde ninguno de los hilos ha "hecho un movimiento";
  • El hijo izquierdo de un nodo representa el estado que resulta después de un movimiento de , el hijo del medio representa el estado que resulta después de un movimiento de , y el hijo derecho representa el estado que resulta después de un movimiento de ;ABC
  • Un nodo hoja representa un estado en el que todos los hilos han terminado. Asociado con un nodo hoja hay un valor , o , donde el valor depende de qué valor se decidió para esa ejecución particular.abc

Definición. Deje que un estado sea multivalente si el resultado del proceso de consenso aún no está determinado. En otras palabras, no todas las posibles entrelazadas de los movimientos restantes conducen al mismo resultado. Deje que un estado sea univalente cuando el resultado del proceso de consenso se determinó.

La raíz es multivalente. Prueba. Si solo un subproceso está activo y los otros subprocesos permanecen inactivos para siempre, entonces terminará en un número finito de pasos (garantizado por el supuesto de ausencia de espera) y decidirá (porque solo tiene acceso a este valor y su la decisión satisfará el requisito de validez del consenso). Así, por nuestra situación, , y son todos los resultados posibles. XXxabc

Definición. Supongamos que un estado crítico es un estado multivalente, con la propiedad adicional de que un movimiento por determinará , y un movimiento por determinará .AaBb

Existe un estado crítico. Prueba. Desde arriba sabemos que comenzamos en un estado multivalente. Deje que no haga ningún movimiento. Mientras o no fuercen al árbol a un estado univalente, déjelo hacer un movimiento. La falta de espera garantiza que el árbol es finito, por lo que en algún momento se debe encontrar un estado crítico. CUNsi

Ahora considere un escenario en el que estamos en un estado crítico. Hay al menos dos posibilidades:

1) hace su movimiento (determinando así ) y se detiene. luego hace su movimiento y se detiene. La siguiente ejecuta hasta que termina, y finalmente decide a .a B CUNunsiCun

2) hace su movimiento (determinando así b ) y se detiene. La siguiente C se ejecuta hasta que termina, y finalmente decide b . A no hace un movimiento.sisiCsiUN

Dado que las lecturas y escrituras atómicas tienen el consenso número 1, los movimientos de y B tenían que ser instrucciones de prueba y ajuste en el mismo registro (si los registros son diferentes, entonces C no podría decir el orden en que A y Los movimientos de B ocurrieron). Desde la perspectiva de C , entonces, los escenarios 1 y 2 son indistinguibles, por lo que debemos tener que C decide tanto a como b . Esto es imposible. UNsiCUNsiCCunsi

Que la instrucción test-and-set tiene el consenso número 2 se deduce de las reivindicaciones 1 y 2.

Roy O.
fuente
Gracias por la respuesta Roy. ¿Puede señalar algún material sobre este tema que sea tan lúcido como su explicación? :). Todo el material que encontré fue demasiado formal.
sanatana
@sanatana: Olvidé responder a tu pregunta, lo siento. Si aún es relevante: sugiero 'El arte de la programación multiprocesador' de Herlihy y Shavit (capítulo 5 en particular) y el material del curso del curso de concurrencia y subprocesamiento múltiple de Fokkink: cs.vu.nl/~tcs/cm (que se basa El libro de Herlihy y Shavit). En la parte inferior de la página encontrará un enlace a las conferencias en video de Herlihy (la conferencia del 27 de septiembre trata sobre el consenso). Después de revisar el material, me doy cuenta de que es suficiente considerar un árbol binario para este tipo de prueba. Quizás actualizaré mi respuesta más tarde.
Roy O.
@RoyO. Veo que su respuesta sugiere que no hay forma de llegar a un consenso con 3 procesos. ¿Solo quería entender si de alguna manera hemos demostrado que aún podemos llegar a un consenso, pero ese protocolo no sería libre de esperas?
causa final
6

El artículo de wikipedia tiene una referencia que responde a su pregunta, pero tal vez no quiera leer ese documento de 26 páginas. Daré una versión simplificada de la prueba (bastante técnica), que muestra que test-and-set no puede resolver el consenso binario para 3 procesos. Este tipo de argumento se usa ampliamente para probar los números de consenso.

Supongamos que tenemos un algoritmo de consenso que utiliza registros TAS para 3 procesos.

En cualquier momento, cada proceso tendrá un movimiento (instrucción) listo para ejecutarse. ¿Cuál de las tres instrucciones se ejecutará no es determinista?

Supongamos que estamos en un estado bivalente (un estado en el que todavía es posible una decisión 0 o 1) y cualquier proceso que se mueva a continuación, el estado posterior será univalente. Tal estado finalmente debe alcanzarse debido a la condición de espera libre.

Suponga (wlg) que si el proceso 1 se mueve, el estado será 0-valent, y que si el proceso 2 se mueve, el estado será 1-valent. Ambos movimientos deben ser una operación TAS (o al menos: algún tipo de escritura) en el mismo registro, ya que si fueran operaciones TAS en registros distintos no podríamos saber si el proceso 1 se movió primero o el proceso 2 se movió primero.

Consideremos estas dos ejecuciones posibles:

  • El proceso 1 se mueve primero, luego el proceso 2 se mueve, luego el proceso 3 se ejecuta solo
  • El proceso 2 se mueve primero, luego el proceso 3 se ejecuta solo

Desde el punto de vista del proceso 3, estos estados son indistinguibles ya que solo ve el valor escrito por el proceso 2. Sin embargo, en el primer caso debería dar 0 como salida, y en el segundo 1 como salida. Claramente, esto es una contradicción.

Los procesos 1 y 2 pueden decidir entre ellos qué se movió primero (porque pueden ver qué valor tenía en el registro antes de su escritura), pero un proceso de tercer espectador no puede.

Tom van der Zanden
fuente
1

Otra forma de demostrar que prueba y conjunto no se puede usar para resolver el consenso de 3 procesadores es mostrar que la prueba y el conjunto se pueden implementar usando el consenso de 2 procesadores. Luego, asumir que probar y configurar puede resolver el consenso de 3 procesadores lleva a una contradicción: suponga que probar y configurar puede resolver el consenso de 3 procesadores; luego, al reemplazar test-and-set por su implementación usando el consenso de 2 procesadores, se obtiene una implementación del consenso de 3 procesadores usando el consenso de 2 procesadores, lo cual es imposible. Por lo tanto, probar y configurar no puede resolver el consenso de 3 procesadores.

Para implementar la prueba y el set para n-procesadores usando el consenso de 2 procesadores, deje que los procesadores determinen un ganador de la prueba y el set usando un torneo en el que cada partido se implemente usando el consenso de 2 procesadores (en un partido, los procesadores proponer su identificador y el resultado del consenso les dice quién gana).

nano
fuente
0

En sentido práctico, una definición de consenso menos estricta podría ser suficiente (aquí lo llamo consenso ligero):

Definición . Se llega a un consenso ligero entre n subprocesos si f (a) cada subproceso decide el mismo valor o el valor se desconoce para él, (b) al menos un subproceso conoce el valor y (c) este valor fue realmente propuesto por uno de los hilos

Por lo tanto, este consenso en su sentido más ligero permite que algún hilo no conozca el consenso, el valor que se decide.

Corolario : en este sentido más ligero, prueba y conjunto tiene un número infinito de consenso de luz.

Afirmación : este sentido más ligero es práctico. Por ejemplo, para seleccionar el hilo para ingresar a la sección crítica, no es necesario crear consenso en sentido estricto. Es decir: cada subproceso debe saber si ha sido seleccionado o no, sin embargo, si no está seleccionado, no tendrá que saber cuál fue seleccionado. En otras palabras, para la exclusión mutua no es necesario un consenso estricto, la luz es suficiente.

Gyula Csom
fuente