c++ - venezuela - Ordenamiento básico de ejecución de exclusión de giro de bloqueo

oea

Question

Existe una versión popular de giro mutuo mutex que se propaga a través de Internet y que se puede encontrar en el libro de Anthony Williams (C ++ Concurrencia en Acción). Aquí está:

class SpinLock
{
    std::atomic_flag locked;
public:
    SpinLock() :
        locked{ATOMIC_FLAG_INIT}
    {
    }
    void lock() 
    {
        while(locked.test_and_set(std::memory_order_acquire));
    }
    void unlock() 
    {
        locked.clear(std::memory_order_release);
    }
};

Lo que no entiendo es por qué todo el mundo usa std::memory_order_acquire para el test_and_set que es una operación de RMW. ¿Por qué no es std::memory_acq_rel ? Supongamos que tenemos 2 hilos al mismo tiempo tratando de adquirir un bloqueo:

T1: test_and_set -> ret false
T2: test_and_set -> ret false

La situación debería ser posible ya que tenemos 2 operaciones de acquire que no forman ninguna sync with relación entre ellas. Sí, después de que hayamos desbloqueado el mutex, tenemos una operación de release que encabeza una release sequence posterior y la vida se vuelve colorida y todos están contentos. Pero, ¿por qué es seguro antes de release sequence se dirija la release sequence ?

Dado que muchas personas mencionan exactamente esa implementación, supongo que debería funcionar correctamente. Entonces, ¿qué me estoy perdiendo?

ACTUALIZACIÓN 1:

Entiendo perfectamente que la operación es atómica, que las operaciones entre lock y unlock no pueden salir de la sección crítica. Esto no es un problema. El problema es que no veo cómo el código anterior evita que 2 mutex entren simultáneamente en la sección crítica. Para evitar que esto ocurra, debe suceder antes de la relación entre 2 lock s. ¿Podría alguien mostrarme, usando las nociones estándar de C ++, que el código es perfectamente seguro?

ACTUALIZACIÓN 2:

Ok, estamos cerca de la respuesta correcta, creo. He encontrado lo siguiente en el estándar:

[atomics.order] cláusula 11

Las operaciones atómicas de lectura-modificación-escritura siempre deben leer el último valor ( en el orden de modificación ) escrito antes de la escritura asociada con la operación de lectura-modificación-escritura.

Y en esta nota importante, felizmente podría cerrar la pregunta, pero todavía tengo mis dudas. ¿Qué pasa in the modification order parte de in the modification order ? El estándar es bastante claro al respecto:

[intro.multithread] cláusula 8

Todas las modificaciones a un objeto atómico M particular ocurren en algún orden total particular, llamado el orden de modificación de M. Si A y B son modificaciones de un objeto atómico M y A sucede antes (como se define a continuación) B, entonces A precederá a B en el orden de modificación de M, que se define a continuación.

Entonces, de acuerdo con esa cláusula para que una operación de RMW tenga el último valor escrito, la última operación de escritura debe ocurrir antes de la parte de lectura o la operación de RMW. Que no es el caso en la pregunta. ¿Derecha?

ACTUALIZACIÓN 3:

Cada vez pienso más que el código para un bloqueo de giro está roto. Aquí está mi razonamiento. C ++ especifica 3 tipos de operaciones:

• Adquirir, liberar, adquirir-liberar: estas son operaciones de sincronización.
• Relajado - estas no son operaciones de sincronización
• RMW - son operaciones con características "especiales"

Comencemos con RMW y descubramos qué tan especial tiene sobre ellos. Primero, son un activo valioso en la formación de la release sequence , segundo, tienen una cláusula especial ([atomics.order] cláusula 11) citada anteriormente. Nada más especial que encontré.

Adquirir / liberar son operaciones de sincronización y release sync with acquire por lo que se forma una relación de happens before . Las operaciones relajadas son simplemente atómicas y no participan en absoluto en el orden de modificación.

¿Qué tenemos en nuestro código? Tenemos una operación de RMW que utiliza la semántica de memoria adquirida, por lo que cada vez que se alcanza el primer desbloqueo (versión), cumple 2 roles:

1. Forma una sync with relación con la release anterior.
2. Participa en la release sequence . Pero eso es cierto solo después de que el primer unlock haya terminado.

Antes de eso, si tenemos más de 2 subprocesos que ejecutan simultáneamente nuestro código de lock , entonces podemos ingresar el lock simultánea, ya que 2 operaciones de acquire no forman ningún tipo de relación. Están tan desordenados como lo harían las operaciones relajadas. Dado que no están ordenados, no podemos usar cláusulas especiales sobre las operaciones de RMW, ya que no se happens before ninguna relación happens before relación y, por lo tanto, no hay un orden de modificación para el indicador locked .

Entonces, o mi lógica es defectuosa o el código está roto. Por favor, quien sepa la verdad - comenta sobre esto.

Answer 1

¿Podría alguien mostrarme, usando las nociones estándar de C ++, que el código es perfectamente seguro?

Inicialmente tuve las mismas preocupaciones que tú. Creo que la clave es comprender que las operaciones en la variable std::atomic_flag son atómicas con respecto a todos los procesadores / núcleos. Dos operaciones atómicas de ''prueba y conjunto'' en hilos separados no pueden tener éxito simultáneamente, independientemente del orden de memoria especificado, ya que entonces no podrían ser atómicas; la operación debe aplicarse a la variable real, no a una copia local en caché (que, en mi opinión, ni siquiera es un concepto en C ++).

Una cadena completa de razonamiento:

29.7 p5 (hablando de la operación de prueba y ajuste):

Efectos: establece atómicamente el valor apuntado por objeto o por esto a verdadero. La memoria se ve afectada según el valor del pedido. Estas operaciones son operaciones atómicas de lectura-modificación-escritura (1.10). Devoluciones: Atómicamente, el valor del objeto inmediatamente antes de los efectos.

1.10 p6:

Todas las modificaciones a un objeto atómico M particular ocurren en algún orden total particular, llamado orden de modificación de M ...

Entonces, si en este caso dos hilos intentan bloquear el bloqueo de giro al mismo tiempo, uno de ellos debe ser el primero y el otro el segundo. Ahora solo tenemos que mostrar que el segundo por necesidad devolverá que la bandera ya estaba establecida, lo que evitará que el hilo entre en la sección crítica.

El párrafo 6 continúa diciendo:

... Si A y B son modificaciones de un objeto atómico M y A sucede antes (como se define a continuación) B, entonces A precederá a B en el orden de modificación de M, que se define a continuación. [Nota: Esto indica que las órdenes de modificación deben respetar la relación "sucede antes" ”. - nota final]

No hay una relación "sucede antes" entre las dos operaciones de prueba y conjunto que ocurren en las dos hebras, por lo que no podemos determinar cuál viene primero en el orden de modificación; sin embargo, debido a la primera oración en p6 (que establece que hay un orden total), una debe definitivamente venir antes que la otra. Ahora, desde 29.3 p12:

Las operaciones atómicas de lectura-modificación-escritura siempre deben leer el último valor (en el orden de modificación) escrito antes de la escritura asociada con la operación de lectura-modificación-escritura.

Esto muestra que el segundo ordenado de prueba y conjunto debe ver el valor escrito por el ordenado de prueba y conjunto primero. Cualquier elección de adquisición / liberación no afecta esto.

Por lo tanto, si dos operaciones de prueba y ajuste se realizan "simultáneamente", se les dará un orden arbitrario, y el segundo verá el valor del indicador que fue establecido por el primero. Como tales, las restricciones de orden de memoria especificadas para la operación de prueba y ajuste no importan; se utilizan para controlar el orden de las escrituras en otras variables durante el período en que se adquiere el spinlock.

Respuesta a la "Actualización 2" de la pregunta:

Entonces, de acuerdo con esa cláusula para que una operación de RMW tenga el último valor escrito, la última operación de escritura debe ocurrir antes de la parte de lectura o la operación de RMW. Que no es el caso en la pregunta. ¿Derecha?

Corrija que no hay una relación "suceda antes", pero incorrecto que una operación de RMW necesita tal relación para garantizar el último valor escrito. La declaración que enumera como "cláusula [atomics.order] 11" no requiere una relación "sucede antes", solo que una operación es anterior a la otra en el "orden de modificación" para el indicador atómico. La cláusula 8 establece que habrá una orden de este tipo, y será una ordenación total:

Todas las modificaciones a un objeto atómico M particular ocurren en algún orden total particular, llamado orden de modificación de M ...

... luego continúa diciendo que el orden total debe ser consistente con cualquier relación "sucede antes":

... Si A y B son modificaciones de un objeto atómico M y A sucede antes (como se define a continuación) B, entonces A precederá a B en el orden de modificación de M, que se define a continuación.

Sin embargo, en ausencia de una relación "sucede antes", todavía hay una ordenación total; es solo que esta ordenación tiene un grado de arbitrariedad. Es decir, si no hay una relación "sucede antes" entre A y B, entonces no se especifica si A se ordena antes o después de B. Pero debe ser una o la otra, porque hay un orden total en particular .

¿Por qué se necesita memory_order_acquire, entonces?

Un mutex, como un spinlock, se usa a menudo para proteger otras variables y estructuras de datos no atómicas. El uso de memory_order_acquire cuando se bloquea el spinlock garantiza que una lectura de dichas variables verá los valores correctos (es decir, los valores escritos por cualquier otro hilo que haya contenido previamente el spinlock). Para el desbloqueo, memory_order_release también es necesario para permitir que otros subprocesos vean los valores escritos.

La adquisición / liberación evita que el compilador re-ordene las lecturas / escrituras pasadas la adquisición / liberación del bloqueo, y asegura que se generen las instrucciones necesarias para asegurar los niveles adecuados de coherencia de caché.

Más evidencia:

Primero, esta nota del 29.3:

Nota: Las operaciones atómicas que especifican memory_order_relaxed se relajan con respecto al orden de memoria. Las implementaciones todavía deben garantizar que cualquier acceso atómico dado a un objeto atómico particular sea indivisible con respecto a todos los demás accesos atómicos a ese objeto. - nota final

Esto significa esencialmente que el orden de memoria especificado no afecta la operación atómica en sí. El acceso debe ser "indivisible con respecto a todos los demás accesos atómicos", incluidos los de otros subprocesos . Permitir que dos operaciones de prueba y ajuste lean el mismo valor sería dividir efectivamente al menos uno de ellos, de modo que ya no fuera atómico.

Asimismo, a partir del 1.10 apartado 5:

Además, hay operaciones atómicas relajadas, que no son operaciones de sincronización, y operaciones atómicas de lectura-modificación-escritura, que tienen características especiales.

(Un test-and-set cae en esta última categoría) y especialmente:

Las operaciones atómicas "relajadas" no son operaciones de sincronización, aunque, como las operaciones de sincronización, no pueden contribuir a las carreras de datos .

(énfasis mío). Un caso en el que dos subprocesos ejecutaron simultáneamente una prueba-y-conjunto atómica (y ambos realizaron la parte del ''conjunto'') sería una carrera de datos de este tipo, por lo que este texto nuevamente indica que esto no puede suceder.

1.10 p8:

Nota: Las especificaciones de las operaciones de sincronización definen cuándo uno lee el valor escrito por otro. Para los objetos atómicos, la definición es clara.

Significa que un hilo lee el valor escrito por otro. Dice que para los objetos atómicos, la definición es clara, lo que significa que no es necesaria ninguna otra sincronización ; es suficiente para realizar la operación en el objeto atómico; El efecto será visto inmediatamente por otros hilos.

En particular, 1.10 p19:

[Nota: los cuatro requisitos de coherencia anteriores no permiten la reordenación de las operaciones atómicas de un compilador a un solo objeto, incluso si ambas operaciones son cargas relajadas. Esto hace que la garantía de coherencia de caché provista por la mayoría del hardware esté disponible para las operaciones atómicas de C ++. - nota final]

Tenga en cuenta la mención de la coherencia de caché incluso en presencia de cargas relajadas. Esto muestra claramente que la prueba y el conjunto solo pueden tener éxito en un subproceso a la vez, ya que para que uno falle, la coherencia del caché se rompe o la operación no es atómica.

Answer 2

Como dijiste, test_and_set es una operación de RMW. Sin embargo, para la prueba, solo es importante que se lea el valor correcto. Por lo tanto, memory_order_acquire parece suficiente.

Consulte también la tabla Constants en http://en.cppreference.com/w/cpp/atomic/memory_order

Answer 3

Creo que lo que te falta es que test_and_set es atómico, punto. No hay ningún ajuste de orden de memoria que haga que esta operación no sea atómica. Si todo lo que necesitábamos era una prueba atómica y un conjunto, podríamos especificar cualquier orden de memoria.

Sin embargo, en este caso, necesitamos algo más que una operación atómica de "prueba y ajuste". Debemos asegurarnos de que las operaciones de memoria que realizamos después de que confirmamos que el bloqueo era nuestro para tomar, no se vuelvan a ordenar antes de que observemos que el mutex está desbloqueado. (Porque esas operaciones no serán operaciones atómicas).

Considerar:

1. Algunas lecturas de datos no protegidos por el mutex.
2. Algunos escriben en datos no protegidos por el mutex.
3. Intentamos bloquear el mutex.
4. Vemos el mutex como bloqueado y no lo cerramos.
5. Vemos el mutex como desbloqueado y bloqueado atómicamente.
6. Algunas lecturas de datos protegidos por el mutex.
7. Algunos escriben a datos protegidos por el mutex.

¿Qué es lo único que no debe pasar? Es que las lecturas y escrituras en los pasos 6 y 7 de alguna manera se vuelven a ordenar antes del paso 5, pisando otro hilo que accede a los datos compartidos bajo la protección del mutex.

La operación test_and_set ya es atómica, por lo que los pasos 4 y 5 son intrínsecamente seguros. Y los pasos 1 y 2 no pueden modificar los datos protegidos (porque se producen incluso antes de que intentemos bloquearlos), por lo que no hay ningún problema en reordenarlos alrededor de nuestra operación de bloqueo.

Pero los pasos 6 y 7: no se deben reordenar antes de que observemos que el bloqueo se desbloqueó para que podamos bloquearlo atómicamente. Eso sería una catástrofe.

La definición de memory_order_acquire: " Una operación de carga con este orden de memoria realiza la operación de adquisición en la ubicación de memoria afectada: no se pueden reordenar los accesos de memoria en el hilo actual antes de esta carga " .

Exactamente lo que necesitamos.