Les «courses de données» et la «condition de concurrence» sont-elles en fait la même chose dans le contexte de la programmation simultanée

Réponses:

138

Non, ils ne sont pas la même chose. Ils ne sont pas un sous-ensemble les uns des autres. Elles ne sont ni la condition nécessaire ni la condition suffisante l'une pour l'autre.

La définition d'une course aux données est assez claire et, par conséquent, sa découverte peut être automatisée. Une course aux données se produit lorsque 2 instructions de threads différents accèdent au même emplacement mémoire, au moins un de ces accès est une écriture et il n'y a pas de synchronisation qui impose un ordre particulier parmi ces accès.

Une condition de concurrence est une erreur sémantique. C'est une faille qui se produit dans la synchronisation ou dans l'ordre des événements qui conduit à un comportement erroné du programme. De nombreuses conditions de concurrence peuvent être causées par des courses de données, mais ce n'est pas nécessaire.

Prenons l'exemple simple suivant où x est une variable partagée:

Thread 1    Thread 2

 lock(l)     lock(l)
 x=1         x=2
 unlock(l)   unlock(l)

Dans cet exemple, les écritures sur x à partir des threads 1 et 2 sont protégées par des verrous, elles se produisent donc toujours dans un certain ordre imposé par l'ordre dans lequel les verrous sont acquis au moment de l'exécution. Autrement dit, l'atomicité des écritures ne peut pas être rompue; il y a toujours une relation qui se produit avant entre les deux écritures dans toute exécution. On ne peut tout simplement pas savoir quelle écriture se passe avant l'autre a priori.

Il n'y a pas d'ordre fixe entre les écritures, car les verrous ne peuvent pas fournir cela. Si l'exactitude des programmes est compromise, par exemple lorsque l'écriture sur x par le thread 2 est suivie de l'écriture sur x dans le thread 1, nous disons qu'il y a une condition de concurrence, bien que techniquement il n'y ait pas de course aux données.

Il est beaucoup plus utile de détecter les conditions de course que les courses de données; cependant, cela est également très difficile à réaliser.

Construire l'exemple inverse est également trivial. Cet article de blog explique également très bien la différence, avec un simple exemple de transaction bancaire.

Baris Kasikci
la source
"course aux données (...) pas de synchronisation qui impose un ordre particulier parmi ces accès." Je suis un peu confus. Dans votre exemple, les opérations peuvent se produire dans les deux ordres (soit = ​​1 puis = 2, soit l'inverse). Pourquoi n'est-ce pas une course aux données?
josinalvo
5
@josinalvo: il s'agit d'un artefact de la définition technique d'une course aux données.Le point clé est qu'entre les deux accès, il y aura un déverrouillage et un verrouillage d'acquisition (pour l'une ou l'autre des commandes possibles). Par définition, un déverrouillage et une acquisition de verrou établissent un ordre entre les deux accès, et il n'y a donc pas de course aux données.
Baris Kasikci
La synchronisation n'exige jamais un ordre particulier entre les opérations, ce n'est donc pas une manière très heureuse de l'exprimer. D'autre part, le JMM spécifie que pour chaque opération de lecture, il doit y avoir une opération d'écriture définie qu'il observe, même dans une course aux données. Il est difficile d'éviter de mentionner explicitement l'ordre des événements avant et de synchronisation, mais même la définition JLS a tort de mentionner juste avant : par sa définition, deux écritures volatiles simultanées constituent une course aux données.
Marko Topolnik
@BarisKasikci "établit un ordre" n'a pas de sens réel, en ce qui me concerne. Ce ne sont que des mots farfelus. Honnêtement, je ne crois pas que la "course aux données" soit un concept utile à distance, car littéralement chaque emplacement mémoire auquel plusieurs threads accèdent peut être considéré comme faisant partie d'une "course aux données"
Noldorin
Les paires libération-acquisition établissent toujours un ordre. Une explication générale est longue, mais un exemple trivial est une paire signal-attente. @Noldorin «Etablit un ordre» fait référence à un ordre qui arrive avant, qui est un concept clé de la théorie de la concurrence (voir l'article fondateur de Lamport sur la relation qui s'est passé avant) et des systèmes distribués. Les courses de données sont un concept utile, en ce que leur présence pose de nombreux problèmes (par exemple, une sémantique non définie selon le modèle de mémoire C ++, une sémantique très complexe en Java, etc.). Leur détection et leur élimination constituent une vaste littérature de recherche et de pratique.
Baris Kasikci
20

Selon Wikipédia, le terme «condition de course» est utilisé depuis l'époque des premières portes logiques électroniques. Dans le contexte de Java, une condition de concurrence peut concerner n'importe quelle ressource, telle qu'un fichier, une connexion réseau, un thread d'un pool de threads, etc.

Le terme «course aux données» est mieux réservé à sa signification spécifique définie par le JLS .

Le cas le plus intéressant est une condition de concurrence très similaire à une course aux données, mais qui n'en est toujours pas une, comme dans cet exemple simple:

class Race {
  static volatile int i;
  static int uniqueInt() { return i++; }
}

Puisqu'il iest volatile, il n'y a pas de course aux données; cependant, du point de vue de l'exactitude du programme, il y a une condition de concurrence due à la non-atomicité des deux opérations: lecture i, écriture i+1. Plusieurs threads peuvent recevoir la même valeur de uniqueInt.

Marko Topolnik
la source
1
pouvez-vous laisser tomber une ligne dans votre réponse décrivant ce que data racesignifie réellement dans JLS?
Geek
@geek Le mot "JLS" est un hyperlien vers la section correspondante du JLS.
Marko Topolnik
@MarkoTopolnik Je suis un peu confus par l'exemple. Pouvez-vous expliquer: "Puisque i est volatile, il n'y a pas de course aux données"? Voltility garantit seulement qu'il est visible mais toujours: 1) il n'est pas synchronisé et plusieurs threads peuvent lire / écrire en même temps et 2) il s'agit d'un champ non final partagé Donc, selon Java Concurrency in Practice (cité ci-dessous également) , c'est une course aux données et non une condition de course, n'est-ce pas?
aniliitb10
@ aniliitb10 Au lieu de vous fier à des citations de seconde main arrachées à leur contexte, vous devriez consulter la section JLS 17.4 à laquelle j'ai lié dans ma réponse. L'accès à une variable volatile est une action de synchronisation telle que définie au §17.4.2.
Marko Topolnik
@ aniliitb10 Les votants ne causent pas de course aux données, car leurs accès peuvent être commandés. Autrement dit, vous pouvez raisonner leur ordre de cette manière ou de cette manière, conduisant à un résultat différent. Avec la course aux données, vous n'avez aucun moyen de raisonner la commande. Par exemple, l'opération i ++ de chaque thread peut simplement se produire sur leur valeur i en cache locale respective. Globalement, vous n'avez aucun moyen d'ordonner ces opérations (du point de vue du programmeur) - à moins que vous n'ayez un certain modèle de mémoire de langage en place.
Xiao-Feng Li
3

Non, ils sont différents et aucun d'eux n'est un sous - ensemble de l'un ou vice-versa.

Le terme condition de concurrence est souvent confondu avec le terme associé race de données, qui survient lorsque la synchronisation n'est pas utilisée pour coordonner tous les accès à un champ non final partagé. Vous risquez une course de données chaque fois qu'un thread écrit une variable qui pourrait ensuite être lue par un autre thread ou lit une variable qui pourrait avoir été écrite pour la dernière fois par un autre thread si les deux threads n'utilisent pas la synchronisation; le code avec des courses de données n'a pas de sémantique définie utile sous le modèle de mémoire Java. Toutes les conditions de course ne sont pas des courses de données, et toutes les courses de données ne sont pas des conditions de course, mais elles peuvent toutes deux provoquer l'échec de programmes concurrents de manière imprévisible.

Tiré de l'excellent livre - Java Concurrency in Practice de Joshua Bloch & Co.

Shirgill Farhan
la source
Notez que la question a une balise indépendante de la langue.
martinkunev
1

TL; DR: La distinction entre la race des données et la condition de race dépend de la nature de la formulation du problème et de l'endroit où tracer la frontière entre un comportement indéfini et un comportement bien défini mais indéterminé. La distinction actuelle est conventionnelle et reflète le mieux l'interface entre l'architecte de processeur et le langage de programmation.

1. Sémantique

La course aux données se réfère spécifiquement aux "accès à la mémoire" conflictuels non synchronisés (ou actions, ou opérations) au même emplacement mémoire. S'il n'y a pas de conflit dans les accès à la mémoire, alors qu'il existe encore un comportement indéterminé causé par l'ordre des opérations, c'est une condition de concurrence.

Notez que les "accès mémoire" ont ici une signification spécifique. Ils font référence aux actions de chargement ou de stockage de mémoire "pure", sans aucune sémantique supplémentaire appliquée. Par exemple, un magasin de mémoire d'un thread ne sait pas (nécessairement) combien de temps il faut pour que les données soient écrites dans la mémoire, et se propage finalement à un autre thread. Pour un autre exemple, un stockage en mémoire à un emplacement avant un autre stockage à un autre emplacement par le même thread ne garantit pas (nécessairement) que les premières données écrites dans la mémoire soient en avance sur la seconde. En conséquence, l'ordre de ces accès à la mémoire pure ne peut pas (nécessairement) être «raisonné» , et tout peut arriver, à moins d'être bien défini.

Lorsque les "accès mémoire" sont bien définis en termes d'ordonnancement par synchronisation, une sémantique supplémentaire peut garantir que, même si le timing des accès mémoire est indéterminé, leur ordre peut être "raisonné" travers les synchronisations. Notez que bien que l'ordre entre les accès mémoire puisse être raisonné, ils ne sont pas nécessairement déterminés, d'où la condition de concurrence.

2. Pourquoi cette différence?

Mais si l'ordre est encore indéterminé en condition de race, pourquoi se donner la peine de le distinguer de la course aux données? La raison est d'ordre pratique plutôt que théorique. C'est parce que la distinction existe dans l'interface entre le langage de programmation et l'architecture du processeur.

Une instruction de chargement / stockage de mémoire dans l'architecture moderne est généralement implémentée comme un accès mémoire "pur", en raison de la nature du pipeline hors service, de la spéculation, de plusieurs niveaux de cache, de l'interconnexion cpu-ram, en particulier multicœur, etc. De nombreux facteurs mènent à des délais et à des commandes indéterminés. Faire appliquer la commande pour chaque instruction de mémoire entraîne une pénalité énorme, en particulier dans une conception de processeur prenant en charge le multicœur. Ainsi, la sémantique de commande est fournie avec des instructions supplémentaires telles que diverses barrières (ou clôtures).

La course aux données est la situation d'exécution des instructions du processeur sans barrières supplémentaires pour aider à raisonner l'ordre des accès mémoire conflictuels. Le résultat est non seulement indéterminé, mais aussi peut-être très étrange, par exemple, deux écritures au même emplacement de mot par des threads différents peuvent résulter avec chaque écriture de la moitié du mot, ou peuvent uniquement fonctionner sur leurs valeurs mises en cache localement. - Ce sont des comportements indéfinis, du point de vue du programmeur. Mais ils sont (généralement) bien définis du point de vue de l'architecte du processeur.

Les programmeurs doivent avoir un moyen de raisonner exécution de leur code. La course aux données est quelque chose qu'ils n'ont pas de sens, ils devraient donc toujours éviter (normalement). C'est pourquoi les spécifications de langage de niveau suffisamment bas définissent généralement la course aux données comme un comportement indéfini, différent du comportement mémoire bien défini de la condition de course.

3. Modèles de mémoire de langue

Différents processeurs peuvent avoir un comportement d'accès à la mémoire différent, c'est-à-dire un modèle de mémoire de processeur. Il est difficile pour les programmeurs d'étudier le modèle de mémoire de chaque processeur moderne et de développer ensuite des programmes qui peuvent en bénéficier. Il est souhaitable que le langage puisse définir un modèle de mémoire afin que les programmes de ce langage se comportent toujours comme prévu, comme le définit le modèle de mémoire. C'est pourquoi Java et C ++ ont leurs modèles de mémoire définis. Il incombe au compilateur / développeurs d'exécution de s'assurer que les modèles de mémoire de langage sont appliqués à travers différentes architectures de processeur.

Cela dit, si un langage ne veut pas exposer le comportement de bas niveau du processeur (et est prêt à sacrifier certains avantages en termes de performances des architectures modernes), il peut choisir de définir un modèle de mémoire qui cache complètement les détails de «pure» accès à la mémoire, mais applique la sémantique de classement pour toutes leurs opérations de mémoire. Ensuite, les développeurs du compilateur / du runtime peuvent choisir de traiter chaque variable de mémoire comme volatile dans toutes les architectures de processeur. Pour ces langages (qui prennent en charge la mémoire partagée entre les threads), il n'y a pas de courses de données, mais peuvent toujours être des conditions de concurrence, même avec un langage de cohérence séquentielle complète.

D'autre part, le modèle de mémoire du processeur peut être plus strict (ou moins détendu, ou à un niveau supérieur), par exemple, en mettant en œuvre une cohérence séquentielle comme le faisait le processeur des débuts. Ensuite, toutes les opérations de mémoire sont ordonnées et aucune course de données n'existe pour les langues exécutées dans le processeur.

4. Conclusion

De retour à la question d'origine, à mon humble avis, il est bien de définir la course aux données comme un cas particulier de condition de course, et la condition de course à un niveau peut devenir une course aux données à un niveau supérieur. Cela dépend de la nature de la formulation du problème et de l'endroit où tracer la frontière entre un comportement indéfini et un comportement bien défini mais indéterminé. Seule la convention actuelle définit la limite à l'interface langage-processeur, ne signifie pas nécessairement que c'est toujours et doit être le cas; mais la convention actuelle reflète probablement le mieux l'interface (et la sagesse) de pointe entre l'architecte de processeur et le langage de programmation.

Xiao-Feng Li
la source