Entendiendo std :: atomic :: compare_exchange_weak () en C ++ 11

bool compare_exchange_weak (T& expected, T val, ..);

compare_exchange_weak()es una de las primitivas de intercambio de comparación proporcionada en C ++ 11. Es débil en el sentido de que devuelve falso incluso si el valor del objeto es igual a expected. Esto se debe a una falla espuria en algunas plataformas donde se usa una secuencia de instrucciones (en lugar de una como en x86) para implementarlo. En tales plataformas, el cambio de contexto, la recarga de la misma dirección (o línea de caché) por otro hilo, etc. pueden fallar en la primitiva. Es spuriousporque no es el valor del objeto (no igual a expected) lo que falla en la operación. En cambio, es una especie de problemas de tiempo.

Pero lo que me desconcierta es lo que dice el estándar C ++ 11 (ISO / IEC 14882),

29.6.5 .. Una consecuencia de la falla espuria es que casi todos los usos de la comparación e intercambio débiles estarán en un bucle.

¿Por qué tiene que estar en bucle en casi todos los usos ? ¿Significa eso que haremos un bucle cuando falle debido a fallas espúreas? Si ese es el caso, ¿por qué nos molestamos en usar compare_exchange_weak()y escribir el bucle nosotros mismos? Podemos usar compare_exchange_strong()lo que creo que debería deshacernos de los fracasos falsos. ¿Cuáles son los casos de uso comunes de compare_exchange_weak()?

Otra pregunta relacionada. En su libro "C ++ Concurrency In Action", Anthony dice:

//Because compare_exchange_weak() can fail spuriously, it must typically
//be used in a loop:

bool expected=false;
extern atomic<bool> b; // set somewhere else
while(!b.compare_exchange_weak(expected,true) && !expected);

//In this case, you keep looping as long as expected is still false,
//indicating that the compare_exchange_weak() call failed spuriously.

¿Por qué !expectedhay una condición de bucle? ¿Está ahí para evitar que todos los hilos se mueran de hambre y no progresen durante algún tiempo?

Editar: (una última pregunta)

En plataformas en las que no existe una sola instrucción CAS de hardware, tanto la versión débil como la fuerte se implementan utilizando LL / SC (como ARM, PowerPC, etc.). Entonces, ¿hay alguna diferencia entre los siguientes dos bucles? ¿Por qué, si hay alguno? (Para mí, deberían tener un rendimiento similar).

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_weak(..))
{ .. }

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_strong(..)) 
{ .. }

Se me ocurre con esta última pregunta, todos ustedes mencionan que tal vez haya una diferencia de rendimiento dentro de un ciclo. También se menciona en el estándar C ++ 11 (ISO / IEC 14882):

Cuando se realiza una comparación e intercambio, la versión débil producirá un mejor rendimiento en algunas plataformas.

Pero como se analizó anteriormente, dos versiones en un bucle deberían ofrecer el mismo rendimiento o similar. ¿Qué es lo que extraño?

¿Por qué intercambiar en bucle?

Por lo general, desea que su trabajo esté terminado antes de continuar, por lo tanto, lo coloca compare_exchange_weaken un bucle para que intente intercambiar hasta que tenga éxito (es decir, regrese true).

Tenga en cuenta que también compare_exchange_strongse usa a menudo en un bucle. No falla debido a fallas espúreas, pero falla debido a escrituras concurrentes.

¿Por qué usar en weaklugar de strong?

Muy fácil: las fallas espúreas no ocurren a menudo, por lo que no es un gran impacto en el rendimiento. En contraste, tolerar tal falla permite una implementación mucho más eficiente de la weakversión (en comparación con strong) en algunas plataformas: strongsiempre debe verificar si hay fallas espúreas y enmascararlas. Esto es caro.

Por lo tanto, weakse usa porque es mucho más rápido que strongen algunas plataformas.

¿Cuándo debería usarlo weaky cuándo strong?

La referencia indica sugerencias sobre cuándo usar weaky cuándo usar strong:

Cuando se realiza una comparación e intercambio, la versión débil producirá un mejor rendimiento en algunas plataformas. Cuando una comparación e intercambio débil requeriría un bucle y uno fuerte no, es preferible el fuerte.

Entonces, la respuesta parece ser bastante simple de recordar: si tuviera que introducir un bucle solo debido a una falla falsa, no lo haga; utilizar strong. Si tiene un bucle de todos modos, utilice weak.

Por que esta !expecteden el ejemplo

Depende de la situación y su semántica deseada, pero por lo general no es necesario para la corrección. Omitirlo produciría una semántica muy similar. Solo en un caso en el que otro hilo pueda restablecer el valor false, la semántica podría volverse ligeramente diferente (sin embargo, no puedo encontrar un ejemplo significativo en el que lo desee). Consulte el comentario de Tony D. para obtener una explicación detallada.

Es simplemente una vía rápida cuando otro hilo escribe true: luego abortamos en lugar de intentar escribir de truenuevo.

Sobre tu última pregunta

Pero como se analizó anteriormente, dos versiones en un bucle deberían dar el mismo / similar rendimiento. ¿Qué es lo que extraño?

De Wikipedia :

Las implementaciones reales de LL / SC no siempre tienen éxito si no hay actualizaciones simultáneas en la ubicación de memoria en cuestión. Cualquier evento excepcional entre las dos operaciones, como un cambio de contexto, otro enlace de carga o incluso (en muchas plataformas) otra operación de carga o almacenamiento, hará que el condicional de almacenamiento falle de forma espuria. Las implementaciones más antiguas fallarán si hay actualizaciones transmitidas por el bus de memoria.

Entonces, LL / SC fallará de manera falsa en el cambio de contexto, por ejemplo. Ahora, la versión fuerte traería su "propio bucle pequeño" para detectar esa falla falsa y enmascararla volviendo a intentarlo. Tenga en cuenta que este propio bucle también es más complicado que un bucle CAS habitual, ya que debe distinguir entre fallas espúreas (y enmascararlas) y fallas debidas al acceso concurrente (que da como resultado un retorno con valor false). La versión débil no tiene ese bucle propio.

Dado que proporciona un bucle explícito en ambos ejemplos, simplemente no es necesario tener el bucle pequeño para la versión fuerte. En consecuencia, en el ejemplo con la strongversión, la verificación de fallas se realiza dos veces; una vez por compare_exchange_strong(que es más complicado ya que debe distinguir fallas espúreas y accesos concurrentes) y una vez por su ciclo. Este costoso cheque es innecesario y la razón por la cual weakserá más rápido aquí.

También tenga en cuenta que su argumento (LL / SC) es solo una posibilidad para implementar esto. Hay más plataformas que tienen incluso diferentes conjuntos de instrucciones. Además (y lo que es más importante), tenga en cuenta que std::atomicdebe admitir todas las operaciones para todos los tipos de datos posibles , por lo que incluso si declara una estructura de diez millones de bytes, puede usarla compare_exchange. Incluso cuando está en una CPU que tiene CAS, no puede CAS diez millones de bytes, por lo que el compilador generará otras instrucciones (probablemente adquisición de bloqueo, seguido de una comparación e intercambio no atómicos, seguido de una liberación de bloqueo). Ahora, piense en cuántas cosas pueden suceder al intercambiar diez millones de bytes. Entonces, si bien un error espurio puede ser muy raro para intercambios de 8 bytes, podría ser más común en este caso.

Entonces, en pocas palabras, C ++ te da dos semánticas, una de "mejor esfuerzo" una ( weak) y una de "Lo haré seguro, sin importar cuántas cosas malas puedan pasar entre" una ( strong). Cómo se implementan en varios tipos de datos y plataformas es un tema totalmente diferente. No vincule su modelo mental a la implementación en su plataforma específica; la biblioteca estándar está diseñada para trabajar con más arquitecturas de las que podría conocer. La única conclusión general que podemos sacar es que garantizar el éxito suele ser más difícil (y por lo tanto puede requerir trabajo adicional) que simplemente intentarlo y dejar espacio para un posible fracaso.

¿Por qué tiene que estar en bucle en casi todos los usos ?

Porque si no realiza un bucle y falla de manera espuria, su programa no ha hecho nada útil; no actualizó el objeto atómico y no sabe cuál es su valor actual (Corrección: vea el comentario de Cameron a continuación). Si la llamada no hace nada útil, ¿qué sentido tiene hacerlo?

¿Significa eso que haremos un bucle cuando falle debido a fallas espúreas?

Si.

Si ese es el caso, ¿por qué nos molestamos en usar compare_exchange_weak()y escribir el bucle nosotros mismos? Podemos usar compare_exchange_strong () que creo que debería deshacerse de las fallas falsas para nosotros. ¿Cuáles son los casos de uso comunes de compare_exchange_weak ()?

En algunas arquitecturas compare_exchange_weakes más eficiente, y las fallas espúreas deberían ser bastante poco comunes, por lo que podría ser posible escribir algoritmos más eficientes usando la forma débil y un bucle.

En general, probablemente sea mejor usar la versión fuerte en su lugar si su algoritmo no necesita realizar un ciclo, ya que no necesita preocuparse por fallas espúreas. Si necesita hacer un bucle de todos modos incluso para la versión fuerte (y muchos algoritmos necesitan hacerlo de todos modos), entonces usar la forma débil podría ser más eficiente en algunas plataformas.

¿Por qué !expectedhay una condición de bucle?

El valor podría haber sido establecido truepor otro hilo, por lo que no querrá seguir repitiendo tratando de establecerlo.

Editar:

Pero como se analizó anteriormente, dos versiones en un bucle deberían ofrecer el mismo rendimiento o similar. ¿Qué es lo que extraño?

Seguramente es obvio que en plataformas donde es posible una falla espuria, la implementación de compare_exchange_strongtiene que ser más complicada, para verificar fallas espúreas y reintentar.

La forma débil simplemente regresa en caso de falla falsa, no vuelve a intentarlo.

Estoy tratando de responder a esto yo mismo, después de revisar varios recursos en línea (por ejemplo, este y este ), el Estándar C ++ 11, así como las respuestas que se dan aquí.

Las preguntas relacionadas se fusionan (por ejemplo, " ¿por qué! ¿Se esperaba? " Se fusiona con "¿por qué poner compare_exchange_weak () en un bucle? ") Y las respuestas se dan en consecuencia.

¿Por qué compare_exchange_weak () tiene que estar en un bucle en casi todos los usos?

Patrón típico A

Necesita lograr una actualización atómica basada en el valor de la variable atómica. Un error indica que la variable no se actualiza con nuestro valor deseado y queremos volver a intentarlo. Tenga en cuenta que realmente no nos importa si falla debido a una escritura concurrente o una falla falsa. Pero nos importa que seamos nosotros los que hagamos este cambio.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

Un ejemplo del mundo real es que varios subprocesos agreguen un elemento a una lista enlazada individualmente al mismo tiempo. Cada hilo primero carga el puntero de la cabeza, asigna un nuevo nodo y agrega la cabeza a este nuevo nodo. Finalmente, intenta intercambiar el nuevo nodo con la cabeza.

Otro ejemplo es implementar mutex usando std::atomic<bool>. A lo sumo un hilo puede entrar en la sección crítica a la vez, dependiendo de la rosca primero establecer currenta truey salir del bucle.

Patrón típico B

Este es en realidad el patrón mencionado en el libro de Anthony. A diferencia del patrón A, desea que la variable atómica se actualice una vez, pero no le importa quién lo haga. Siempre que no esté actualizado, vuelve a intentarlo. Esto se usa normalmente con variables booleanas. Por ejemplo, necesita implementar un disparador para que una máquina de estado siga adelante. Qué hilo aprieta el gatillo es independiente.

expected = false;
// !expected: if expected is set to true by another thread, it's done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Tenga en cuenta que generalmente no podemos usar este patrón para implementar un mutex. De lo contrario, varios subprocesos pueden estar dentro de la sección crítica al mismo tiempo.

Dicho esto, debería ser raro usarlo compare_exchange_weak()fuera de un bucle. Por el contrario, hay casos en los que se está utilizando la versión fuerte. P.ej,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak no es apropiado aquí porque cuando regresa debido a una falla falsa, es probable que nadie ocupe la sección crítica todavía.

¿Hilo hambriento?

Un punto que vale la pena mencionar es que ¿qué sucede si continúan ocurriendo fallas espúreas y así el hilo se muere de hambre? En teoría, podría ocurrir en plataformas cuando compare_exchange_XXX()se implementa como una secuencia de instrucciones (por ejemplo, LL / SC). El acceso frecuente a la misma línea de caché entre LL y SC producirá fallas falsas continuas. Un ejemplo más realista se debe a una programación tonta en la que todos los subprocesos simultáneos se intercalan de la siguiente manera.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

Puede suceder

No sucederá para siempre, afortunadamente, gracias a lo que requiere C ++ 11:

Las implementaciones deben asegurar que las operaciones débiles de comparación e intercambio no devuelvan constantemente falso a menos que el objeto atómico tenga un valor diferente al esperado o haya modificaciones concurrentes en el objeto atómico.

¿Por qué nos molestamos en usar compare_exchange_weak () y escribir el bucle nosotros mismos? Podemos simplemente usar compare_exchange_strong ().

Depende.

Caso 1: Cuando ambos deben usarse dentro de un bucle. C ++ 11 dice:

Cuando se realiza una comparación e intercambio, la versión débil producirá un mejor rendimiento en algunas plataformas.

En x86 (al menos actualmente. Quizás algún día recurra a un esquema similar al LL / SC para mejorar el rendimiento cuando se introduzcan más núcleos), la versión débil y la fuerte son esencialmente iguales porque ambas se reducen a una sola instrucción cmpxchg. En algunas otras plataformas donde compare_exchange_XXX()no se implementa de forma atómica (aquí lo que significa que no existe una sola primitiva de hardware), la versión débil dentro del ciclo puede ganar la batalla porque la fuerte tendrá que manejar las fallas espúreas y reintentar en consecuencia.

Pero,

En raras ocasiones, es posible que prefieren compare_exchange_strong()más compare_exchange_weak()aún en un bucle. Por ejemplo, cuando hay muchas cosas que hacer entre la variable atómica se carga y se intercambia un nuevo valor calculado (ver function()arriba). Si la variable atómica en sí misma no cambia con frecuencia, no necesitamos repetir el costoso cálculo para cada falla espuria. En cambio, podemos esperar compare_exchange_strong()"absorber" tales fallas y solo repetimos el cálculo cuando falla debido a un cambio de valor real.

Caso 2: Cuando solo compare_exchange_weak() necesita usarse dentro de un bucle. C ++ 11 también dice:

Cuando una comparación e intercambio débil requeriría un bucle y uno fuerte no, es preferible el fuerte.

Este suele ser el caso cuando se realiza un ciclo solo para eliminar fallas falsas de la versión débil. Vuelva a intentarlo hasta que el intercambio sea exitoso o fallido debido a la escritura simultánea.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

En el mejor de los casos, se trata de reinventar las ruedas y funcionar igual que compare_exchange_strong(). ¿Peor? Este enfoque no logra aprovechar al máximo las máquinas que brindan comparación e intercambio no espurios en hardware .

Por último, si hace un bucle para otras cosas (por ejemplo, vea el "Patrón típico A" más arriba), entonces hay una buena posibilidad de que compare_exchange_strong()también se coloque en un bucle, lo que nos lleva de vuelta al caso anterior.

Muy bien, necesito una función que realice un desplazamiento atómico a la izquierda. Mi procesador no tiene una operación nativa para esto, y la biblioteca estándar no tiene una función para ello, así que parece que estoy escribiendo la mía propia. Aquí va:

void atomicLeftShift(std::atomic<int>* var, int shiftBy)
{
    do {
        int oldVal = std::atomic_load(var);
        int newVal = oldVal << shiftBy;
    } while(!std::compare_exchange_weak(oldVal, newVal));
}

Ahora, hay dos razones por las que ese bucle se puede ejecutar más de una vez.

1. Alguien más cambió la variable mientras yo hacía mi turno a la izquierda. Los resultados de mi cálculo no deben aplicarse a la variable atómica, porque efectivamente borraría la escritura de otra persona.
2. Mi CPU eructó y el CAS débil falló espurio.

Honestamente, no me importa cuál. El cambio a la izquierda es lo suficientemente rápido como para que pueda hacerlo de nuevo, incluso si la falla fue falsa.

Lo que es menos rápido, sin embargo, es el código adicional que CAS fuerte necesita para envolver CAS débil para ser fuerte. Ese código no hace mucho cuando el CAS débil tiene éxito ... pero cuando falla, el CAS fuerte necesita hacer un trabajo de detective para determinar si fue el Caso 1 o el Caso 2. Ese trabajo de detective toma la forma de un segundo ciclo, efectivamente dentro de mi propio bucle. Dos bucles anidados. Imagina a tu profesor de algoritmos mirándote ahora mismo.

Y como mencioné anteriormente, ¡no me importa el resultado de ese trabajo de detective! De cualquier manera, rehaceré el CAS. Por lo tanto, usar CAS fuerte no me gana precisamente nada y me pierde una pequeña pero medible cantidad de eficiencia.

En otras palabras, CAS débil se utiliza para implementar operaciones de actualización atómica. El CAS fuerte se utiliza cuando le preocupa el resultado de CAS.

Creo que la mayoría de las respuestas anteriores abordan "fallas espúreas" como algún tipo de problema, compensación entre rendimiento y corrección.

Puede verse como la versión débil es más rápida la mayoría de las veces, pero en caso de fallas espúreas, se vuelve más lenta. Y la versión fuerte es una versión que no tiene posibilidad de fallas falsas, pero casi siempre es más lenta.

Para mí, la principal diferencia es cómo estas dos versiones manejan el problema ABA:

La versión débil tendrá éxito solo si nadie ha tocado la línea de caché entre la carga y el almacenamiento, por lo que detectará al 100% el problema de ABA.

La versión fuerte fallará solo si falla la comparación, por lo que no detectará el problema de ABA sin medidas adicionales.

Entonces, en teoría, si usa una versión débil en una arquitectura de orden débil, no necesita un mecanismo de detección ABA y la implementación será mucho más simple, brindando un mejor rendimiento.

Pero, en x86 (arquitectura de orden fuerte), la versión débil y la versión fuerte son iguales, y ambas sufren un problema de ABA.

Entonces, si escribe un algoritmo completamente multiplataforma, debe abordar el problema de ABA de todos modos, por lo que no hay beneficio de rendimiento al usar la versión débil, pero hay una penalización de rendimiento por manejar fallas espúreas.

En conclusión, por razones de portabilidad y rendimiento, la versión fuerte es siempre una opción mejor o igual.

La versión débil solo puede ser una mejor opción si le permite omitir por completo las contramedidas ABA o si su algoritmo no se preocupa por ABA.