Soutenance mémoire
La concurrence dans les langages de programmation
Nous nous intéressons ici au problème de la concurrence dans les langages de programmation. Nous dirons qu’un système est concurrent s’il est constitué de comportements partiellement non ordonnés. Plus pragmatiquement, un système est concurrent lorsqu’il fait plusieurs choses « en même temps ». Par exemple, un métro doit, de façon concurrente, gérer sa vitesse, la signalisation, l’ouverture des différentes portes, la ventilation, l’éclairage, etc. Un navigateur internet est aussi un système concurrent, qui doit à la fois écouter les commandes de l’utilisateur par le clavier et la souris, gérer le rafraichissement de l’interface, la connexion avec les serveurs et le téléchargement des pages, etc. Il s’agit donc bien d’une notion d’un modèle, et non d’implémentation. Il ne faut en particulier pas la confondre avec la notion de parallélisme. Le parallélisme concerne l’exécution du point de vue matériel de plusieurs fils d’exécution ou threads en simultané . Le parallélisme est un des moyens pour implémenter la concurrence, mais il est également possible d’implémenter la concurrence de façon séquentielle. Les ordinateurs ont été capables d’effectuer plusieurs tâches de façon concurrente bien avant que les processeurs multi-cœurs n’apparaissent. Le but du parallélisme est d’exécuter les programmes plus rapidement en répartissant le travail entre les différentes unités de calcul. A l’opposé, nous chercherons ici à utiliser la concurrence comme moyen de simplifier l’écriture des programmes, puisque de nombreux problèmes s’expriment naturellement de façon concurrente. Nous parlerons tout de même de parallélisme dans ce manuscrit, mais il sera un moyen parmi d’autres pour exécuter les programmes et de façon transparente pour le programmeur. Il restera toujours possible d’exécuter les programmes de manière complètement séquentielle.
On trouve plusieurs approches traditionnelles pour programmer la concurrence :
Les threads systèmes Les systèmes d’exploitation fournissent un moyen de créer plusieurs fils d’exécution par programme, aussi appelés processus légers ou threads. Chaque thread dispose de son propre contexte, ce qui rend leur création et le passage d’un thread à l’autre coûteux. Ils peuvent accéder à un espace mémoire commun qu’ils utilisent pour communiquer et se synchroniser. Il est alors nécessaire d’utiliser des primitives d’exclusion mutuelle comme les verrous ou encore des instructions matérielles spéciales comme le compare-and-swap pour gérer les accès simultanés au même emplacement mémoire. Ce style de programmation est notoirement complexe. Il peut aboutir à des inter-blocages ou deadlocks et rend la mise au point des programmes difficile de par sa nature non déterministe et non reproductible. Dans [Lee06], E. Lee écrit un réquisitoire contre les threads en expliquant en détail ces problèmes.
La programmation événementielle L’idée de ce style de programmation, très utilisé pour la programmation d’interfaces graphiques, est de centrer le programme autour d’une boucle d’événements. Chaque partie du programme enregistre des fonctions qui seront appelées lorsqu’un événement (comme un clic de souris) sera émis, ce qu’on appelle des callbacks. La boucle d’événements récolte les différents événements puis appelle les callbacks correspondants, qui vont à leur tour ajouter de nouveaux callbacks, et ainsi de suite. Cette approche de la concurrence permet de gérer efficacement de très nombreux comportements concurrents. Son gros inconvénient est que le code de chaque comportement est séparé en de nombreuses fonctions (une par événement) qui sont appelées par la boucle d’événements, ce que l’on appelle l’inversion du contrôle. Il devient donc difficile de comprendre la structure du programme, qui est éparpillé dans de nombreuses fonctions.
Les threads légers coopératifs (ou coroutines) Cette dernière approche tente de concilier le meilleur des deux approches précédentes. L’idée est de proposer un modèle de programmation direct, sans inversion du contrôle, mais sans la lourdeur des threads. Pour cela, on requiert des fils d’exécution qu’ils rendent régulièrement la main à l’ordonnanceur pour que les autres fils d’exécution puissent s’exécuter. C’est ce que l’on appelle l’ordonnancement coopératif. Cela permet une implémentation séquentielle efficace de la concurrence. C’est le modèle utilisé par des bibliothèques comme LWT [Vou08] en OCAML ou CONCURRENT HASKELL [JGF96].
Ces approches peuvent être utilisées dans tous les langages généralistes. Une autre alternative est d’intégrer la concurrence dans le langage. Cela permet à la fois de simplifier la vie du programmeur en proposant une syntaxe plus agréable et aussi d’offrir des garanties plus importantes. En effet, les bibliothèques de threads légers sont très souvent accompagnées de règles de bonne programmation à suivre pour obtenir un résultat correspondant à ses attentes. En intégrant la concurrence dans le langage, ces règles de bonne formation peuvent devenir des analyses statiques permettant de garantir la sûreté des programmes au moment de la compilation, de la même manière qu’un système de types évite de nombreuses erreurs. Les langages ADA et ERLANG sont par exemple des langages utilisés dans l’industrie qui intègrent la concurrence. Plusieurs langages généralistes font de même depuis peu, avec notamment les calculs asynchrones en F# [SPL11] et C#. Dans le monde académique, on peut citer notamment deux extensions de ML : CONCURENTML [Rep93] étend ML avec des primitives d’envoi de messages, alors que JOCAML [FLFMS04] s’inspire des constructions du join-calculus [FG02]. Nous allons nous intéresser dans ce manuscrit à une famille de langages intégrant la concurrence et le temps : les langages synchrones.
Les langages synchrones
Cadre
Les langages synchrones [BCE+03] sont des langages apparus au début des années 80 et dédiés à la programmation de systèmes embarqués (ce sont des Domain Specific Languages ou DSL). Par rapport aux langages traditionnellement utilisés dans ce domaine tels que C, les langages synchrones ont la particularité de mettre le temps et la concurrence au centre du langage. Ils reposent sur une sémantique définie formellement. Cela permet notamment d’utiliser des méthodes formelles pour la vérification automatique de propriétés des programmes. Les langages synchrones s’intéressent plus particulièrement aux systèmes suivants :
Réactifs Un système réactif interagit en permanence avec son environnement. Dans le cas d’un système embarqué, le programme va lire en continu les données des capteurs, puis calculer une commande appropriée pour les différents actionneurs. Cela est fait de façon périodique, le plus souvent en suivant une exécution dite en boucle simple, qui répète le cycle suivant :
– Attendre le déclenchement.
– Lire les entrées.
– Calculer la réaction.
– Écrire les sorties.
D’autres exemples de systèmes réactifs sont les interfaces graphiques (ou GUI) et les jeux vidéos. On les distingue des systèmes dits transformationnels [HP85] qui n’interagissent avec l’environnement qu’au début du programme. C’est le cas par exemple d’un compilateur ou d’un logiciel de compression de fichiers.
Temps-Réel Les systèmes réactifs ont souvent des impératifs de temps-réel. Le temps d’exécution du programme est alors une propriété fonctionnelle du système, c’est-à-dire qu’il influe sur la correction du programme. Dans le cas d’un compilateur par exemple, le temps d’exécution est une variable que l’on cherchera à optimiser pour faciliter la vie de l’utilisateur, mais cela se fait de façon indépendante de la correction du programme. A l’opposé, un système embarqué confronté au monde physique doit respecter des contraintes strictes de temps de réponse. Un exemple typique est l’injection dans les moteurs à combustion, qui doit respecter un échéancier très précis.
Critiques Un système est dit critique lorsque des vies humaines dépendent de son bon fonctionnement. C’est par exemple le cas d’un avion, d’un train ou encore d’une centrale nucléaire. Il faut donc souvent pouvoir garantir avant l’exécution le temps de réaction du logiciel et pouvoir calculer le temps d’exécution pire-cas (Worst-Case Execution Time ou WCET) [WEE+08] d’un pas de la boucle d’interaction. En conséquence, l’expressivité des langages synchrones est volontairement réduite à des programmes statiques, sans aucune allocation dynamique de mémoire ni boucles non bornées. Ces langages ne sont donc pas Turing-complets.
Historiquement, on distingue deux grandes familles de langages synchrones :
– Les langages flot de données (data-flow) comme LUSTRE [CPHP87], SIGNAL [BLGJ91], LUCID SYNCHRONE [CP96] ou SCADE dans lesquels on écrit des équations sur des suites infinies de valeurs appelées flots.
– Les langages impératifs comme ESTEREL [Ber97] ou QUARTZ [Sch09] qui proposent une programmation plus classique avec une notion de séquence. La frontière entre ces deux mondes s’est estompée dans les langages plus récents comme ESTEREL v7 ou SCADE 6. Nous allons dans la suite présenter plus en détail ces deux approches. Mais avant cela, nous allons présenter le point commun entre ces langages, c’est-à-dire le principe du synchrone.
L’hypothèse synchrone
L’approche synchrone [BCE+03] consiste à voir l’exécution d’un programme comme une succession d’instants logiques discrets. Dans un premier temps, on oublie donc totalement le temps réel : on ne parle que du premier instant, du deuxième instant, etc. L’autre point commun de ces langages est la présence d’un opérateur de composition parallèle synchrone, permettant de lancer de façon concurrente plusieurs processus. Il s’agit bien ici de concurrence logique, pas de parallélisme d’exécution. Cette concurrence dans le programme disparait généralement au moment de l’exécution, puisque le code généré est le plus souvent séquentiel. Comme pour le produit synchrone d’automates, la composition parallèle synchrone fait avancer les processus au même rythme, en lock-step. La notion d’instant logique est globale et partagée par tous les processus et permet donc une synchronisation implicite. C’est pour faire le lien avec le temps-réel de l’exécution du programme que l’on va faire appel à l’hypothèse synchrone. L’idée est de supposer initialement que les calculs et communications au sein d’un instant sont instantanées, comme si l’on disposait d’un ordinateur infiniment rapide.
|
Table des matières
INTRODUCTION
I Présentation informelle
1 Introduction
1.1 La concurrence dans les langages de programmation
1.2 Les langages synchrones
1.3 Présentation du travail
2 Un cours accéléré de REACTIVEML
2.1 Introduction à REACTIVEML
2.2 La programmation orientée agent en REACTIVEML
2.3 Une première extension : les signaux à mémoire
2.4 Vers les domaines réactifs
3 Une présentation informelle des domaines réactifs
3.1 Les domaines réactifs
3.2 Programmation avec les domaines réactifs
3.3 Exemples
II Sémantique
4 Sémantique comportementale
4.1 Syntaxe abstraite du langage
4.2 Notations
4.3 Sémantique comportementale
4.4 Exemples
4.5 Discussion
5 Sémantique opérationnelle
5.1 Sémantique opérationnelle
5.2 Équivalence des sémantiques
5.3 Travaux similaires
III Systèmes de types et analyses statiques
6 Calcul d’horloges
6.1 Introduction sur les systèmes de types-et-effets
6.2 Bonne formation des expressions
6.3 Système de types
6.4 Preuve de sûreté
6.5 Limites du système de types
7 Analyse de réactivité
7.1 Intuitions et limites
7.2 Le langage des comportements
7.3 Système de types
7.4 Preuve de sûreté
7.5 Discussion
8 Extensions des systèmes de types
8.1 Polymorphisme de rang supérieur dans le calcul d’horloges
8.2 Analyse de réactivité avec rangées
8.3 Calcul d’horloges avec rangées
IV Implémentation et applications
9 Implémentation
9.1 Implémentation séquentielle de REACTIVEML
9.2 Implémentation séquentielle des domaines réactifs
9.3 Implémentation parallèle de REACTIVEML
9.4 Implémentation parallèle avec domaines réactifs
9.5 Implémentation distribuée des domaines réactifs
10 Interprétation dynamique d’ESTEREL
10.1 Un interprète ESTEREL en REACTIVEML avec domaines réactifs
10.2 Les domaines réactifs en ESTEREL
11 Conclusion et Perspectives
11.1 Extensions et perspectives
11.2 Conclusion
CONCLUSION
Annexes
