c++ multithreading c++11 atomic

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



multithreading c++11 (4)

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

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

Pero lo que me desconcierta es lo que se dice en C ++ 11 Standard (ISO / IEC 14882),

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

¿Por qué tiene que estar en un bucle en casi todos los usos ? ¿Eso significa que haremos un bucle cuando falle debido a fallas espurias? Si ese es el caso, ¿por qué nos molestamos en usar compare_exchange_weak() y escribir el loop nosotros mismos? Solo podemos usar compare_exchange_strong() que creo que debería deshacerse de fallas compare_exchange_strong() para nosotros. ¿Cuáles son los casos de uso común 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é se !expected allí en la 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 las plataformas en las que no existe una única instrucción CAS de hardware, tanto la versión débil como la sólida 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(..)) { .. }

Vengo con esta última pregunta, ustedes mencionan que quizás haya una diferencia de rendimiento dentro de un bucle. También se menciona en el estándar C ++ 11 (ISO / IEC 14882):

Cuando una comparación e intercambio está en un bucle, la versión débil ofrecerá un mejor rendimiento en algunas plataformas.

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

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

Porque si no haces un bucle y falla falsamente, tu programa no ha hecho nada útil: no actualizaste el objeto atómico y no sabes cuál es su valor actual (Corrección: mira el comentario a continuación de Cameron). Si la llamada no sirve de nada, ¿cuál es el sentido de hacerlo?

¿Eso significa que haremos un bucle cuando falle debido a fallas espurias?

Sí.

Si ese es el caso, ¿por qué nos molestamos en usar compare_exchange_weak() y escribir el loop nosotros mismos? Solo podemos usar compare_exchange_strong () que creo que debería deshacerse de fallas espúreas para nosotros. ¿Cuáles son los casos de uso común de compare_exchange_weak ()?

En algunas arquitecturas, compare_exchange_weak es más eficiente, y las fallas compare_exchange_weak 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 ciclo.

En general, probablemente sea mejor usar la versión fuerte si su algoritmo no necesita bucle, ya que no necesita preocuparse por fallas espurias. Si es necesario realizar un bucle de todos modos, incluso para la versión fuerte (y muchos algoritmos necesitan hacer bucles de todos modos), usar la forma débil puede ser más eficiente en algunas plataformas.

¿Por qué se !expected allí en la condición de bucle?

El valor podría haberse establecido en true por otro hilo, por lo que no desea seguir haciendo bucles intentando establecerlo.

Editar:

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

Seguramente es obvio que en las plataformas donde es posible la falla espuria, la implementación de compare_exchange_strong tiene que ser más complicada, para verificar fallas falsas y volver a intentar.

La forma débil simplemente regresa en falla espuria, no vuelve a intentarlo.

¿Por qué hacer intercambio en un bucle?

Por lo general, quiere que su trabajo se realice antes de continuar, por lo tanto, pone compare_exchange_weak en un bucle para que intente intercambiar hasta que tenga éxito (es decir, devuelve true ).

Tenga en cuenta que también se usa compare_exchange_strong en un bucle. No falla debido a fallas espurias, pero falla debido a escrituras concurrentes.

¿Por qué usar weak lugar de strong ?

Muy fácil: fallas espurias no ocurren a menudo, por lo que no es un gran golpe de rendimiento. En contraposición, tolerar tal falla permite una implementación mucho más eficiente de la versión weak (en comparación con la strong ) en algunas plataformas: el strong siempre debe verificar fallas falsas y enmascararlas. Esto es caro.

Por lo tanto, se usa weak porque es mucho más rápido que strong en algunas plataformas

¿Cuándo deberías usar weak y strong ?

Los estados de reference indican cuándo usar weak y cuándo usar strong :

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

Entonces, la respuesta parece ser bastante simple de recordar: si tuviera que introducir un bucle solo por falla espuria, no lo haga; usa strong Si tiene un bucle de todos modos, use weak .

¿Por qué se !expected En el ejemplo

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

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

Acerca de su última pregunta

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

De la Wikipedia :

Las implementaciones reales de LL / SC no siempre tienen éxito si no hay actualizaciones concurrentes en la ubicación de la 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 carga o operación de tienda, provocará que el condicional de tienda falle falsamente. Las implementaciones anteriores fallarán si hay actualizaciones transmitidas por el bus de memoria.

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

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 versión strong , el control de falla se realiza dos veces; una vez por compare_exchange_strong (que es más complicado ya que debe distinguir la falla espuria y el acceso simultáneo) y una vez por su ciclo. Este cheque costoso es innecesario y la razón por weak cual weak será 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 más importante aún), tenga en cuenta que std::atomic debe 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 usar compare_exchange en esto. Incluso cuando en una CPU que tiene CAS, no puede CAS diez millones de bytes, por lo que el compilador generará otras instrucciones (probablemente bloquear adquirir, seguido de una comparación no atómica y cambio, seguido de una liberación de bloqueo). Ahora, piense en cuántas cosas pueden suceder al intercambiar diez millones de bytes. Entonces, aunque 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" ( weak ) y una "lo haré seguro, no importa cuántas cosas malas puedan pasar entre" uno ( strong ). Cómo estos 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 usted pueda tener en cuenta. La única conclusión general que podemos extraer es que garantizar el éxito suele ser más difícil (y, por lo tanto, puede requerir trabajo adicional) que simplemente intentar y dejar espacio para una posible falla.

Intento 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 dadas aquí.

Las preguntas relacionadas se fusionan (por ejemplo, " ¿por qué se espera? " 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

Necesitas lograr una actualización atómica basada en el valor en la variable atómica. Una falla 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 la escritura concurrente o falla espuria. Pero nos importa que somos nosotros los que hacemos este cambio.

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

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

Otro ejemplo es implementar mutex usando std::atomic<bool> . Como máximo, un subproceso puede ingresar a la sección crítica a la vez, dependiendo de qué subproceso primero establece la current en true y sale 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. Mientras no esté actualizado, intente de nuevo. Esto se usa típicamente con variables booleanas. Por ejemplo, necesita implementar un disparador para que una máquina de estado avance. Qué hilo tira del gatillo es sin importar.

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, múltiples hilos pueden estar dentro de la sección crítica al mismo tiempo.

Dicho esto, debería ser raro usar compare_exchange_weak() fuera de un bucle. Por el contrario, hay casos en que la versión fuerte está en uso. 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 muerto de hambre?

Un punto que vale la pena mencionar es lo que sucede si las fallas espurias continúan sucediendo y se muere de hambre. Teóricamente podría suceder en plataformas cuando compare_exchange_XXX() se implemente como una secuencia de instrucciones (por ejemplo, LL / SC). El acceso frecuente de 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 entrelazan 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 pasar?

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

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

¿Por qué nos molestamos en usar compare_exchange_weak () y escribir el loop nosotros mismos? Solo podemos usar compare_exchange_strong ().

Depende.

Caso 1: cuando ambos necesitan ser utilizados dentro de un bucle. C ++ 11 dice:

Cuando una comparación e intercambio está en un bucle, la versión débil ofrecerá un mejor rendimiento en algunas plataformas.

En x86 (al menos en la actualidad. Tal vez recurra a un esquema similar a LL / SC un día para el rendimiento cuando se introducen más núcleos), la versión débil y fuerte es esencialmente la misma porque ambos se reducen a la instrucción única cmpxchg . En algunas otras plataformas donde compare_exchange_XXX() no se implementa atómicamente (lo que significa que no existe una única primitiva de hardware), la versión débil dentro del ciclo puede ganar la batalla porque la fuerte tendrá que manejar las fallas espurias y volver a intentar en consecuencia.

Pero,

raramente, podemos preferir compare_exchange_strong() sobre compare_exchange_weak() incluso 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 es necesario repetir el cálculo costoso para cada error espurio. En cambio, podemos esperar que compare_exchange_strong() "absorba" tales fallas y solo repitamos el cálculo cuando falla debido a un cambio de valor real.

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

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

Este suele ser el caso cuando se realiza un bucle solo para eliminar fallas espurias de la versión débil. Vuelve a intentar 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, reinventa las ruedas y realiza lo mismo que compare_exchange_strong() . ¿Peor? Este enfoque no aprovecha al máximo las máquinas que proporcionan comparación e intercambio no espurios en el hardware .

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

Muy bien, entonces necesito una función que realice cambios atómicos a la izquierda. Mi procesador no tiene una operación nativa para esto, y la biblioteca estándar no tiene una función para él, así que parece que estoy escribiendo la mía. 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 bien, hay dos razones por las que el ciclo se puede ejecutar más de una vez.

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

Honestamente, no me importa cuál. El cambio a la izquierda es lo suficientemente rápido para que también pueda hacerlo nuevamente, 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 al débil CAS para ser fuerte. Ese código no hace mucho cuando el CAS débil tiene éxito ... pero cuando falla, un CAS fuerte necesita hacer un trabajo de detective para determinar si era 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 que tu profesor de algoritmos te está mirando en este momento.

Y como mencioné anteriormente, ¡no me importa el resultado de ese trabajo de detective! De cualquier manera voy a estar rehaciendo el CAS. Así que usar CAS fuerte no me aporta precisamente nada, y me pierde una pequeña pero medible cantidad de eficiencia.

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