c++ - ¿Se puede evitar el bloqueo garantizando que múltiples hilos no tendrán acceso a la misma memoria?

multithreading lock-free

Question

Supongamos que tengo una gran matriz y quiero procesar los contenidos con múltiples hilos. Si delego cada hilo en una sección específica, garantizando que no haya superposición, ¿elimina eso la necesidad de bloqueo, suponiendo que los hilos no acceden a ninguna otra memoria fuera de la matriz?

Algo así (pseudo-código):

global array[9000000];

do_something(chunk) {
    for (i = chunk.start; i < chunk.end; i++)
        //do something with array
}

main() {
    chunk1 = {start: 0, end: 5000000};
    chunk2 = {start: 5000000, end: 9000000};

    start_thread(thread1, do_something(chunk1));
    start_thread(thread2, do_something(chunk2));

    wait_for_join(thread1);
    wait_for_join(thread2);
    //do something else with the altered array
}

Answer 1

¡Importante problema de rendimiento!

Correcto, no necesita bloqueo explícito, ya que, como dijeron otros, no se comparte ninguna ubicación de memoria.

Pero puede desencadenar sincronización de hardware implícita , ya que es probable que los fragmentos arbitrarios conduzcan a compartir las líneas de caché (sin embargo, no mucho con las cifras utilizadas en su ejemplo). Se lo conoce como intercambio falso .

El enfoque de nivel superior como OpenMP resuelve este tipo de problema:

• la alineación de los trozos (y los números de los hilos) se ajustan según el hardware subyacente.
• proporciona un mejor control sobre el conjunto de subprocesos, por ejemplo, la amortización del costo de las instancias de subprocesos.
• es más fácil de escribir, y en realidad menos intrusivo.

Answer 2

En un compilador C ++ 11 conforme, esto es seguro [intro.memory] (§1.7):

Una ubicación de memoria es un objeto de tipo escalar o una secuencia máxima de campos de bits adyacentes que tienen un ancho distinto de cero. [...] Dos hilos de ejecución (1.10) pueden actualizar y acceder a ubicaciones de memoria separadas sin interferir entre sí.

C11 ofrece garantías idénticas (incluso usan la misma redacción) en §3.14.

En un compilador C ++ 03, no se garantiza que funcione con el estándar, pero podría funcionar si el compilador proporciona garantías similares a una extensión.

Answer 3

Sí, puedes de hecho.

TCMalloc es un buen ejemplo.

Answer 4

Sí.

Ni siquiera necesita garantizar que no haya dos subprocesos que accedan a la misma ubicación de memoria. Todo lo que necesita para garantizar es que ningún hilo único modifica ninguna ubicación a la que otro accede (independientemente de si eso significa leer o escribir).

Dado que no hay acceso simultáneo o acceso concurrente de solo lectura, puede continuar sin bloquear.

Answer 5

Sí: si puede garantizar que no hay dos subprocesos que accedan al mismo elemento, entonces no hay necesidad de ninguna otra sincronización.

Solo hay un conflicto (y por lo tanto una posible carrera de datos) si dos subprocesos acceden a la misma ubicación de memoria (con al menos uno de ellos modificándola) sin sincronización.

(NOTA: esta respuesta se basa en el modelo de memoria C ++ 11. Me acabo de dar cuenta de que también está preguntando por un segundo idioma, creo que C11 especifica un modelo de memoria muy similar, pero no puede decir con certeza que la respuesta también es válida para C. Para versiones anteriores de ambos lenguajes, la seguridad de hilos dependía de la implementación).