Pouvez-vous éviter le blocage en garantissant que plusieurs threads n'aurez pas accès à la même mémoire?

Question

Dire que j'ai un grand tableau et je veux traiter le contenu avec plusieurs threads. Si je délègue chaque thread à une section spécifique, garantissant aucun chevauchement, le fait d'éliminer la nécessité pour le verrouillage, en supposant que les fils n'ont pas accès à toute la mémoire d'autres à l'extérieur de la matrice?

Quelque chose comme ceci (pseudo-code):

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

Dans une conformation de C++11 compilateur c'est sûr, [intro.mémoire] (§1.7):

Un emplacement de mémoire est soit un objet de type scalaire ou un maximum de séquence de bits adjacents-champs de tous les non-largeur nulle. [...] Deux les threads d'exécution (1.10) peut mettre à jour et d'accès mémoire séparé emplacements sans interférer les uns avec les autres.

C11 donne des garanties équivalentes (ils ont même utiliser la même formulation) dans le §3.14.

En C++03 compilateur ce n'est pas garanti par la norme, mais il pourrait encore fonctionner si le compilateur fournit des garanties similaires comme une extension.

Answer 2

Oui: si vous pouvez garantir que deux threads accèdent au même élément, alors il n'y a pas de raison de la synchronisation.

Il y a seulement un conflit (et donc un potentiel de données de course) si deux threads accèdent à la même emplacement de mémoire (avec au moins l'un d'entre eux modification) sans synchronisation.

(NOTE: cette réponse est fondée sur le C++11 modèle de mémoire. J'ai juste remarqué que vous êtes également demander à propos d'une deuxième langue; je crois que C11 spécifie très semblable à la mémoire de modèle, mais ne peut pas dire à coup sûr que la réponse est aussi valable pour C. Pour les versions plus anciennes de ces deux langues, fil-sécurité a été dépendant de l'implémentation.)

Answer 3

Oui, vous pouvez en effet.

TCMalloc est un bon exemple.

Answer 4

Oui.

Vous n'avez même pas besoin de garantie de l'absence de deux threads d'accéder au même emplacement de mémoire. Tous vous avez besoin pour garantir, c'est que pas un seul thread modifie tout endroit qu'un autre accès (peu importe qu'il s'agisse de lecture ou d'écriture).

Donné soit pas de l'accès simultané à tous ou en lecture seule accès simultanés, vous êtes bon pour aller sans verrouillage.

Answer 5

Important problème de performance !

À droite, vous n'a pas besoin explicite de verrouillage, car, comme dit par d'autres, pas de l'emplacement de la mémoire est partagée.

Mais vous pouvez déclencher implicite synchronisation matérielle, depuis arbitraire morceaux sont susceptibles d'entraîner des lignes de cache à usage en commun (pas beaucoup avec les chiffres utilisés dans votre exemple, si). Il est connu comme faux partage.

Approche de plus haut niveau comme OpenMP résout ce genre de problème :

• des morceaux d'alignement (nombre de threads et de chiffres) sont réglés selon le matériel sous-jacent.
• il fournit un meilleur contrôle sur le pool de threads, par exemple, d'amortir le coût de fil instanciations.
• il est plus facile d'écrire, et moins intrusive.