Modèles de concurrence et de mémoire
Les modèles de concurrence et de mémoire définissent la structure des programmes concurrents et la manière dont leurs fils d'exécution (threads) interagissant observent la mémoire partagée, ce qui est fondamental pour un logiciel parallèle correct.
Definition
Les modèles de concurrence décrivent comment des calculs s'exécutant indépendamment sont composés et communiquent, tandis qu'un modèle de mémoire spécifie les valeurs que les lectures peuvent observer lorsque des fils d'exécution concurrents accèdent à la mémoire partagée, définissant ainsi le contrat entre le programmeur, le langage et le matériel.
Scope
Ce domaine couvre le langage et la théorie de la concurrence : les calculs de processus et les modèles de concurrence pour la communication et la synchronisation, les modèles de cohérence de la mémoire qui spécifient les ordonnancements autorisés des opérations de mémoire, les mécanismes de synchronisation et l'absence de courses de données (data-race freedom), ainsi que les systèmes de types pour la concurrence tels que les types de session. Il aborde la manière dont les langages donnent un sens aux programmes qui s'exécutent simultanément et partagent un état.
Sub-topics
Core questions
- Comment les processus concurrents communicants peuvent-ils être modélisés et analysés ?
- Quels ordonnancements d'opérations de mémoire un programme peut-il observer ?
- Comment l'absence de courses de données est-elle garantie ou spécifiée ?
- Comment les types peuvent-ils encadrer la communication et prévenir les erreurs de concurrence ?
Key theories
- Calculs de processus
- Le CSP de Hoare, le CCS de Milner et le pi-calcul fournissent des théories algébriques des processus concurrents et communicants, avec des opérateurs de composition et de synchronisation et des notions d'équivalence comportementale telles que la bisimulation.
- Cohérence séquentielle
- Lamport a défini la cohérence séquentielle comme l'exigence qu'une exécution multiprocesseur apparaisse comme un certain entrelacement des opérations de chaque processeur dans l'ordre du programme, constituant la référence par rapport à laquelle les modèles de mémoire plus faibles sont comparés.
- Modèles de cohérence de la mémoire
- Adve et Gharachorloo systématisent le spectre des modèles de cohérence de la mémoire partagée, expliquant comment les ordonnancements relâchés (relaxed orderings) permettent d'améliorer les performances tout en compliquant le raisonnement sur les programmes concurrents.
Clinical relevance
Les modèles de mémoire font désormais partie des spécifications de langage courantes (par exemple en C++ et Java) car le matériel multicœur a rendu les ordonnancements relâchés observables ; leur bonne compréhension est essentielle pour un logiciel concurrent correct et portable. Les calculs de processus et les types de session éclairent la conception des langages et protocoles de passage de messages.
History
La théorie de la concurrence est née des réseaux de Petri et des travaux des années 1970 de Hoare (CSP) et Milner (CCS), puis du pi-calcul pour les processus mobiles. Lamport a défini la cohérence séquentielle en 1979 ; à mesure que le matériel à ordonnancement relâché (relaxed hardware) se répandait, les modèles de mémoire ont été formalisés pour des langages tels que Java et C++ dans les années 2000, et la sémantique de la mémoire faible (weak-memory semantics) est devenue un domaine de recherche actif.
Debates
- Cohérence de la mémoire forte versus relâchée
- Les concepteurs arbitrent entre la simplicité intuitive des modèles forts comme la cohérence séquentielle et les performances des modèles relâchés qui permettent le réordonnancement, ce qui complique le raisonnement et exige une sémantique de langage rigoureuse.
Key figures
- C. A. R. Hoare
- Robin Milner
- Leslie Lamport
- Sarita Adve
Related topics
Seminal works
- hoare1978
- milner1989
- lamport1979
- adve1996
Frequently asked questions
- Qu'est-ce qu'un modèle de mémoire ?
- Un modèle de mémoire est le contrat formel qui spécifie les valeurs qu'une lecture peut retourner lorsque plusieurs fils d'exécution accèdent à la mémoire partagée, définissant les réordonnancements que le compilateur et le matériel peuvent effectuer et ce sur quoi le programmeur peut compter.
- Qu'est-ce que la cohérence séquentielle ?
- La cohérence séquentielle exige qu'une exécution concurrente se comporte comme un unique entrelacement des opérations des fils d'exécution qui respecte l'ordre du programme de chaque fil, ce qui en fait le modèle de mémoire le plus intuitif (mais souvent relâché).