Synchronisation et absence de course aux données

Les mécanismes de synchronisation coordonnent les fils d'exécution concurrents afin que les données partagées soient accédées en toute sécurité, et l'absence de course aux données est la propriété qui rend les programmes concurrents prévisibles.

Definition

La synchronisation est la coordination d'activités concurrentes pour imposer un ordre ou une exclusion mutuelle sur des ressources partagées, et l'absence de course aux données est la propriété selon laquelle aucun fil d'exécution n'accède simultanément à la même adresse mémoire avec au moins une écriture sans synchronisation intermédiaire.

Scope

Ce sujet aborde les mécanismes et les propriétés qui garantissent la correction de l'accès concurrent à l'état partagé : l'exclusion mutuelle, les verrous, les sémaphores et les moniteurs, les variables de condition, les algorithmes sans verrou (lock-free) et sans attente (wait-free), la mémoire transactionnelle, la relation d'ordre temporel (happens-before), et la détection des courses aux données. Il traite des interblocages (deadlock), de l'atomicité et de la discipline nécessaire pour maintenir les programmes exempts de courses aux données.

Core questions

• Comment l'exclusion mutuelle est-elle réalisée et quels sont ses risques (interblocage, famine) ?
• Qu'est-ce qui distingue la synchronisation basée sur les verrous de la synchronisation sans verrou ?
• Comment la relation d'ordre temporel (happens-before) définit-elle les courses aux données ?
• Comment les courses aux données peuvent-elles être détectées automatiquement ?

Key theories

Exclusion mutuelle

La solution de Dijkstra au problème du contrôle concurrent a établi l'exclusion mutuelle comme l'exigence fondamentale de synchronisation, garantissant que les sections critiques ne sont pas exécutées simultanément.

Mémoire transactionnelle

Herlihy et Moss ont proposé la mémoire transactionnelle, dans laquelle des groupes d'opérations mémoire s'exécutent de manière atomique, offrant une alternative composable au verrouillage à grain fin pour la construction de structures de données concurrentes.

Relation d'ordre temporel (happens-before) et détection dynamique des courses

S'appuyant sur la relation d'ordre temporel (happens-before) de Lamport, le détecteur Eraser a montré comment trouver dynamiquement les courses aux données en vérifiant une discipline de verrouillage, illustrant la détection automatisée des courses.

Clinical relevance

Une synchronisation correcte est essentielle pour des logiciels concurrents et parallèles fiables ; les courses aux données sont à l'origine de certains des bogues les plus insaisissables en pratique. Les détecteurs de course, la mémoire transactionnelle et les modèles de synchronisation disciplinés sont des outils centraux pour la construction de systèmes multithreadés fiables.

History

La solution d'exclusion mutuelle de Dijkstra en 1965 et ses sémaphores ultérieurs ont fondé la synchronisation, suivis par les moniteurs de Hoare et Brinch Hansen. La relation d'ordre temporel (happens-before) de Lamport en 1978 sous-tend les définitions modernes des courses aux données ; Herlihy et Moss ont introduit la mémoire transactionnelle en 1993, et les détecteurs de course dynamiques tels qu'Eraser (1997) et les outils ultérieurs basés sur la relation d'ordre temporel sont devenus la norme pour le débogage de la concurrence.

Debates

Verrous contre approches sans verrou et transactionnelles

Les concepteurs débattent de la synchronisation traditionnelle basée sur les verrous, qui est simple mais sujette aux interblocages et à une faible composabilité, par rapport aux algorithmes sans verrou et à la mémoire transactionnelle, qui améliorent la composabilité et les garanties de progression au prix d'une complexité ou d'une surcharge.

Key figures

• Edsger Dijkstra
• Leslie Lamport
• Maurice Herlihy
• C. A. R. Hoare
• Stefan Savage

Seminal works

• dijkstra1965
• herlihy1993
• savage1997
• lamport1978

Frequently asked questions

Qu'est-ce qu'une course aux données ?

Une course aux données se produit lorsque deux fils d'exécution accèdent simultanément à la même adresse mémoire, au moins un accès est une écriture, et que les accès ne sont pas ordonnés par synchronisation, ce qui conduit à un comportement indéfini ou imprévisible dans la plupart des modèles de mémoire.

Quelle est la différence entre la synchronisation basée sur les verrous et la synchronisation sans verrou ?

La synchronisation basée sur les verrous utilise l'exclusion mutuelle de sorte qu'un seul fil d'exécution entre dans une section critique à la fois, tandis que la synchronisation sans verrou utilise des opérations atomiques pour garantir qu'un fil d'exécution progresse toujours sans détenir de verrous, évitant ainsi les interblocages.