Programmation concurrente
| Sommaire |
Définition
La programmation concurrente est un style de programmation tenant compte, dans un programme, de l'existence de plusieurs flots de contrôle. Ces flots de contrôle multiples peuvent être appelés threads, processus ou tâches. Ils sont matérialisés en machine par une pile d'exécution et un ensemble de données privées. Les threads disposent d'une zone de mémoire partagée alors que les processus sont strictement isolés.
La concurrence est indispensable lorsqu'on souhaite écrire des programmes interagissant avec le monde réel (qui est concurrent) ou tirant parti de multiples unités centrales (couplées, comme dans un système multiprocesseurs, ou distribués, éventuellement en grille ou en grappe).
On distingue trois types de concurrence :
- disjointe : les entités concurrentes ne communiquent et n'interragissent pas, c'est le degré zéro,
- compétitive : un ensemble d'entités concurrentes en compétition pour l'accès à certaines ressources partagées (par exemple le temps CPU, des données partagées),
- coopérative : un ensemble d'entités concurrentes qui coopèrent pour atteindre un objectif commun.
Classification
La programmation concurrente est plus complexe et difficile que la programmation impérative, fonctionnelle ou encore déclarative. En fait, à chacun de ces modèles de programmation on peut associer une version concurrente, par extension de la sémantique du langage de programmation associé. Par exemple, Prolog a été étendu en Concurrent Prolog, Haskell avec Concurrent Haskell, Java et Ada sont des langages à objets avec des primitives pour la concurrence, etc.
Les techniques spécifiques pour le traitement de la concurrence peuvent être étudiées en allant de la moins expressive (mais la plus facile à utiliser) à la plus expressive. On peut utiliser les niveaux suivants :
- concurrence déclarative (langage fonctionnel étendu avec des threads)
- concurrence en programmation logique
- concurrence déclarative avec des ports et envoi de messages
- concurrence impérative avec ports et envoi de messages
- concurrence impérative avec mémoire partagée
Problèmes
Le phénomène central introduit par la concurrence est le suivant : dans un programme non concurrent, ou séquentiel, l'ordre d'exécution des instructions élémentaires du programme est un ordre total qui reste le même d'une exécution à l'autre pour les mêmes paramètres en entrée. Dans un programme concurrent, l'exécution forme un ordre partiel. Comme la politique d'ordonnancement est généralement inconnue (elle est déterminée par le noyau du système d'exploitation par exemple) ou incontrôlée, on parle de l'indéterminisme de l'ordre d'exécution.
Les problèmes induits par la concurrence se manifestent dans les cas de la concurrence compétitive et coopérative. À cause de l'indéterminisme de l'exécution, l'accès à des données partagées par les entités concurrentes peut conduire à des inconsistances au niveau des relations liant ces données. Pour cela, on utilise différentes techniques comme les verrous, les mutex, les moniteurs ou encore les sémaphores. À leur tour, l'utilisation de ces mécanismes peut conduire à deux types de problèmes :
- interblocages (ou deadlocks) entre processus concurrents qui attendent, par exemple, que l'autre relâche un verrou acquis pour pouvoir progresser,
- famines (ou livelocks) d'un processus essayant d'acquérir une ressource, mais jamais ordonnancé au moment où elle est dispobible.
Solutions
De nombreux types de solutions sont possibles pour maîtriser la programmation concurrente.
Il existe des calculs formels pour la concurrence : CCS, gamma-calcul, Chemical Abstract Machine, pi-calcul ...
Les systèmes transactionnels, utilisés principalement pour des bases de données partagées, s'appuient sur la théorie de la sérialisabilité pour garantir un accès concurrent à des ressources partagées (concurrence de type 4 et 5).
Des langages de programmation modernes comme Erlang ou Oz permettent d'écrire des applications concurrentes, avec un soin très particulier apporté aux questions de gestion d'exception concurrente et distribuée.
Voir aussi
La concurrence est souvent liée à la distribution : un programme dont l'exécution est distribué sur plusieurs hôtes est intrinsèquement concurrent. Pourtant, ce n'est pas toujours le cas ; l'utilisation de protocoles de communication entre parties distribuées d'un programme, comme les RPC (appels de procédure à distance) ou RMI (invocation de méthode à distance), peut rendre non-concurrent un programme ditribué.
Voir aussi