En quoi les commandes de mémoire «acquérir» et «consommer» diffèrent-elles et dans quels cas «consommer» est-il préférable?

Question

Le C++11 norme définit un modèle de mémoire (1.7, 1.10) qui contient la mémoire des ordonnancements, qui sont, en gros, "de manière séquentielle-compatible", "acquérir", "consommer", "libération", et "relax". Également à peu près, un programme est correct que si c'est de la course libre, ce qui se produit si toutes les actions peuvent être mis dans l'ordre dans lequel l'action se passe-avant un autre. La façon dont une action X-passe-avant une action Y est que soit X est séquencée avant de Y (dans un thread), ou X inter-thread-de-passe-avant d'Y. La dernière condition est donnée, entre autres, lors de l'

• X se synchronise avec Y, ou
• X est la dépendance-commandé avant d' Y.

La synchronisation avec advient-il lorsque X est un atomique magasin avec la "libération" de la commande sur certains variable atomique, et Y est atomique de charge avec "acquérir" de la commande sur la même variable. En cours de dépendance-commandé-avant de passe pour la situation analogue où Y est la charge avec "consommer" de la commande (et un accès à la mémoire). La notion de synchronise avec s'étend le passe-avant de manière transitive de la relation à travers des actions séquencé-devant l'un de l'autre dans un thread, mais le fait de la dépendance-commandé-avant est élargie de manière transitive uniquement par l'intermédiaire d'un sous-ensemble strict de séquencé-devant appelé porte-dépendance, qui suit un largish ensemble de règles, et notamment peut être interrompue par l' std::kill_dependency.

Alors, quel est le but de la notion de "dépendance de commande"? Quels sont les avantages d'elle au cours de la plus simple séquencé-avant / synchronise avec la commande? Étant donné que les règles sont plus strictes, je suppose que peut être mis en œuvre de manière plus efficace.

Pouvez-vous donner un exemple d'un programme où la commutation de la sortie/acquisition de la libération/consommer est à la fois correct et fournit un non-trivial avantage? Et quand souhaitez - std::kill_dependency fournir une amélioration? De haut niveau, les arguments de la être gentil, mais des points de bonus pour le matériel de différences spécifiques.

Answer 1

La dépendance de données de la commande a été introduit par N2492 avec fondé sur le raisonnement suivant:

Il y a deux grands cas d'utilisation où l'actuel projet de travail (N2461) ne prend pas en charge l'évolutivité près que possible sur certains matériels existants.

• l'accès en lecture à rarement écrite simultanée des structures de données

Rarement écrite simultanée de structures de données sont tout à fait commun, dans le système d'exploitation de noyaux et le serveur d'applications de type. Les exemples incluent des structures de données représentant à l'extérieur de l'état (tels que les tables de routage), la configuration de logiciels (modules actuellement chargés), la configuration du matériel (périphérique de stockage actuellement en cours d'utilisation), et les politiques de sécurité (autorisations de contrôle d'accès, règles de pare-feu). Lire-écrire des ratios bien au-delà d'un milliard de dollars à un sont tout à fait commun.

• publish-subscribe sémantique pour le pointeur de la médiation de la publication

Beaucoup de communication entre les threads est pointeur de la médiation, dans laquelle le producteur publie un pointeur à travers lequel le consommateur peut accéder à l'information. L'accès à ces données est possible sans la pleine acquisition de la sémantique.

Dans de tels cas, l'utilisation des inter-thread de données-la dépendance de la commande a abouti à des ordres de grandeur les accélérations et des améliorations similaires dans d'évolutivité sur les ordinateurs qui prennent en charge inter-thread de données-la dépendance de la commande. Ces accélérations sont possibles parce que ces machines peuvent éviter le coûteux verrouillage acquisitions, atomique instructions, ou de la mémoire des clôtures qui sont par ailleurs nécessaires.

c'est moi qui souligne

le cas d'utilisation de motivation présentées il y a rcu_dereference() depuis le noyau Linux

Answer 2

La charge de consommer est un peu comme la charge d'acquérir, sauf qu'elle induit se passe-avant des relations uniquement pour les évaluations d'expression qui sont dépendants des données sur la charge de consommer. Habillage d'une expression avec kill_dependency donne une valeur qui n'est plus porteur d'une dépendance de la charge de consommer.

Les principaux cas d'utilisation est l'auteur de faire construire une structure de données de manière séquentielle, puis balancer un pointeur partagé à la nouvelle structure (à l'aide d'un release ou acq_rel atomique). Le lecteur utilise la charge de consommer pour lire le pointeur, et déréférence pour arriver à la structure de données. Le déréférencement de crée une dépendance de données, de sorte que le lecteur est assuré de voir les données initialisées.

std::atomic<int *> foo {nullptr};
std::atomic<int> bar;

void thread1()
{
    bar = 7;
    int * x = new int {51};
    foo.store(x, std::memory_order_release);
}

void thread2()
{
    int *y = foo.load(std::memory_order_consume)
    if (y)
    {
        assert(*y == 51); //succeeds
        // assert(bar == 7); //undefined behavior - could race with the store to bar 
        // assert(kill_dependency(*y) + bar == 58) // undefined behavior (same reason)
        assert(*y + bar == 58); // succeeds - evaluation of bar pulled into the dependency 
    }
}

Il y a deux raisons pour offrir à charge de consommer. La principale raison est que les BRAS et les charges de courant sont garantis à consommer, mais exigent d'autres clôtures pour les transformer en acquiert. (Sur x86, toutes les charges sont acquiert, donc consommer fournit pas directement de la performance de l'avantage en vertu de l'naïf de compilation.) L'autre raison est que le compilateur peut se déplacer plus tard activités sans dépendance de données jusqu'à l'avant de la consommer, il ne peut pas faire pour l'acquérir. (Permettre à ces optimisations est la grande raison de la construction de la totalité de cette mémoire de la commande dans la langue.)

Habillage d'une valeur, kill_dependency permet le calcul d'une expression qui dépend de la valeur à être déplacé à l'avant de la charge-consommer. C'est utile par exemple lorsque la valeur est un index dans un tableau qui a déjà été lu.

Notez que l'utilisation de consommer des résultats dans un passe-avant la relation qui n'est plus transitive (si elle est encore garantie d'être acyclique). Par exemple, le magasin d' bar arrive devant le magasin à toto, qui se produit avant le déréférencement d' y, ce qui se passe avant la lecture de l' bar (dans l'commenté de l'affirmer), mais le magasin de bar ne se produit pas avant la lecture de l' bar. Cela conduit à un peu plus compliqué définition de passe-avant, mais vous pouvez imaginer comment il fonctionne (démarrer avec séquencé-avant, avant de se propager par le biais de n'importe quel nombre de la libération-consommer-dataDependency ou de la libération-acquérir-sequencedBefore liens)

Answer 3

J'aimerais enregistrer une partielle à trouver, même si ce n'est pas une vraie réponse et ne veut pas dire qu'il n'y aura pas une grande générosité pour une réponse appropriée.

Après avoir regarder 1.10 pendant un certain temps, et en particulier la très utile note au paragraphe 11, je pense que ce n'est en fait pas si difficile. La grande différence entre les synchronise avec (ci-après: s/w) et de la dépendance-commandé-avant (dob) est qu'un passe-avant la relation peut être établie par la concaténation de séquencé-avant (s/b) et s/w arbitrairement, mais pas tellement pour le dob. Remarque l'une des définitions inter-thread qui se passe avant:

A synchronise avec X et X est séquencée avant de B

Mais l'analogie de déclaration pour l' A est la dépendance-commandé avant X est manquant!

Donc, avec la libération/acquisition (i.e. s/w), nous pouvons ordre arbitraire des événements:

A1    s/b    B1                                            Thread 1
                   s/w
                          C1    s/b    D1                  Thread 2

Mais considérons maintenant une suite arbitraire des événements comme celui-ci:

A2    s/b    B2                                            Thread 1
                   dob
                          C2    s/b    D2                  Thread 2

Dans ce sequenece, il est toujours vrai qu' A2 -passe-avant C2 (parce qu' A2 s/b B2 et B2 inter-thread qui se passe avant C2 sur le compte de la date de naissance; mais on pourrait dire que vous ne pouvez jamais dire!). Cependant, il n'est pas vrai qu' A2 -passe-avant D2. Les événements A2 et D2 ne sont pas ordonnées à l'égard l'un de l'autre, à moins qu' il détient que l' C2 porte de dépendance à l' D2. C'est une exigence plus stricte, et en l'absence de cette exigence, A2-D2 ne peut pas être commandé "à travers" la presse/consommer paire.

En d'autres termes, un album/consommer paire ne se propage une commande d'actions qui portent une dépendance de l'un à l'autre. Tout ce qui n'est pas dépendante n'est pas ordonné à travers la presse/consommer paire.

En outre, notez que l'ordre est rétabli si nous ajoutons un dernier, plus de presse/acquisition de la paire:

A2    s/b    B2                                                         Th 1
                   dob
                          C2    s/b    D2                               Th 2
                                             s/w
                                                    E2    s/b    F2     Th 3

Maintenant, par la cité de la règle, D2 inter-thread qui se passe avant F2,, et par conséquent, ne C2 et B2, et ainsi de A2 -passe-avant F2. Mais notez qu'il n'y a toujours pas de commande entre A2 et D2 — la commande est seulement entre A2 et plus tard des événements.

En résumé et en conclusion, la dépendance comptable est un sous-ensemble strict de général de séquençage et de la libération/consommer paires de fournir une commande uniquement parmi les actions qui portent de la dépendance. Aussi longtemps que pas plus la commande est requise (par exemple en passant à travers un presse/acquérir une paire), il est théoriquement un potentiel d'optimisation supplémentaires, puisque tout ce qui n'est pas dans la chaîne de dépendances peuvent être réorganisées librement.

---

Peut-être ici est un exemple qui fait sens?

std::atomic<int> foo(0);

int x = 0;

void thread1()
{
    x = 51;
    foo.store(10, std::memory_order_release);
}

void thread2()
{
    if (foo.load(std::memory_order_acquire) == 10)
    {
        assert(x == 51);
    }
}

Comme l'écrit, le code de la course libre et l'assertion se tenir, car la libération/acquisition de la paire orderes le magasin x = 51 avant de le charger dans l'affirmation. Cependant, en changeant "acquérir" en "consommer", ce ne serait plus vrai et l'émission de données de course sur x, depuis x = 51 porte pas de dépendance dans le magasin pour foo. L'optimisation, c'est que ce magasin peuvent être réorganisés librement, sans souci de ce qu' foo est en train de faire, car il n'y a pas de dépendance.