Worldlex Wiki Il s'agit d'une propriété d'un système — qu'il s'agisse d'un programme , d'un ordinateur ou d'un réseau — où chaque processus dispose d'un point d'exécution ou « fil de contrôle » distinct. Un système concurrent est un système dans lequel un calcul peut progresser sans attendre la fin de tous les autres calculs.
Le calcul concurrent est une forme de programmation modulaire . Dans son paradigme, un calcul global est décomposé en sous-calculs pouvant être exécutés simultanément. Parmi les pionniers du calcul concurrent figurent Edsger Dijkstra , Per Brinch Hansen et CAR Hoare .
parallèle bien que les deux puissent être décrits comme « plusieurs processus s'exécutant simultanément ». En calcul parallèle, l'exécution a lieu au même instant physique : par exemple, sur des processeurs distincts d'une machine multiprocesseur , dans le but d'accélérer les calculs. Le calcul parallèle est impossible sur un processeur monocœur, car un seul calcul peut avoir lieu à un instant donné (pendant un cycle d'horloge). [ l'inverse, le calcul concurrent consiste en des durées de vie de processus qui se chevauchent, mais l'exécution n'a pas lieu au même instant. L'objectif est ici de modéliser des processus qui s'exécutent simultanément, comme plusieurs clients accédant à un serveur en même temps. Structurer les systèmes logiciels comme étant composés de plusieurs parties concurrentes et communiquant entre elles peut s'avérer utile pour gérer la complexité, que ces parties puissent ou non être exécutées en parallèle.Par exemple, l'exécution simultanée de processus sur un seul cœur peut être réalisée en entrelaçant les étapes d'exécution de chaque processus via des tranches de temps partagées : un seul processus s'exécute à la fois, et s'il ne se termine pas dans son intervalle de temps, il est suspendu , un autre processus démarre ou reprend, puis le processus initial est relancé ultérieurement. De cette manière, plusieurs processus sont en cours d'exécution simultanément, mais un seul processus est exécuté à cet instant précis.en distribuant un calcul sur un réseau.
Le moment précis d'exécution des tâches dans un système concurrent dépend de l' ordonnancement , et les tâches ne sont pas nécessairement exécutées simultanément. Par exemple, considérons deux tâches, T1 et T2 :sérialisable , ce qui simplifie le contrôle de la concurrence .le contrôle de la concurrence : garantir le bon enchaînement des interactions ou communications entre les différentes exécutions de calcul, et coordonner l’accès aux ressources partagées entre ces exécutions. Les problèmes potentiels incluent les conditions de concurrence , les interblocages et la pénurie de ressources . Par exemple, considérons l’algorithme suivant permettant d’effectuer des retraits sur un compte courant représenté par la ressource partagéebalance :
booléen retrait ( int retrait ){si ( solde >= retrait ){solde -= retrait ;renvoyer vrai ;}renvoyer faux ;}
Supposons balance = 500que deux threads concurrents effectuent les appels withdraw(300)et withdraw(350). Si la ligne 3 des deux opérations s'exécute avant la ligne 5, les deux opérations constateront que balance >= withdrawalest évalué à true, et l'exécution se poursuivra par la soustraction du montant du retrait. Cependant, puisque les deux processus effectuent leurs retraits, le montant total retiré sera supérieur au solde initial. Ce type de problème lié aux ressources partagées est résolu par l'utilisation du contrôle de concurrence, ou algorithmes non bloquants .
Avantages
Modèles
Introduits en 1962, les réseaux de Petri constituèrent une des premières tentatives de codification des règles d'exécution concurrente. La théorie du flux de données s'appuya par la suite sur ces réseaux, et des architectures de flux de données furent créées pour implémenter physiquement les concepts de cette théorie. À partir de la fin des années 1970, des calculs de processus tels que le calcul des systèmes communicants (CCS) et le calcul des processus séquentiels communicants (CSP) furent développés pour permettre un raisonnement algébrique sur les systèmes composés d'éléments interagissant. Le π-calcul ajouta la capacité de raisonner sur les topologies dynamiques.
Les automates d'entrée/sortie ont été introduits en 1987.
Des logiques telles que TLA+ de Lamport , et des modèles mathématiques tels que les traces et les diagrammes d'événements d'acteurs , ont également été développés pour décrire le comportement des systèmes concurrents.
La mémoire transactionnelle logicielle emprunte à la théorie des bases de données le concept de transactions atomiques et l'applique aux accès mémoire.
Modèles de cohérence
L'un des premiers modèles de cohérence fut le modèle de cohérence séquentielle de Leslie Lamport . La cohérence séquentielle est la propriété d'un programme selon laquelle son exécution produit les mêmes résultats qu'un programme séquentiel. Plus précisément, un programme est séquentiellement cohérent si « les résultats de toute exécution sont les mêmes que si les opérations de tous les processeurs étaient exécutées dans un ordre séquentiel donné, et les opérations de chaque processeur apparaissent dans cette séquence dans l'ordre spécifié par son programme ».
processus du système d'exploitation , ou implémenter les processus de calcul comme un ensemble de threads au sein d'un seul processus du système d'exploitation.Interaction et communication
Dans certains systèmes de calcul concurrents, la communication entre les composants concurrents est masquée au programmeur (par exemple, par l'utilisation de futures ), tandis que dans d'autres, elle doit être gérée explicitement. La communication explicite peut être divisée en deux catégories :
- Communication de mémoire partagée
- Les composants concurrents communiquent en modifiant le contenu d' emplacements de mémoire partagée (comme en Java et C# ). Ce style de programmation concurrente nécessite généralement l'utilisation d'un mécanisme de verrouillage (par exemple, des mutex , des sémaphores ou des moniteurs ) pour coordonner les threads. Un programme qui implémente correctement l'un de ces mécanismes est dit thread-safe .
- communication par transmission de messages
- Les composants concurrents communiquent par échange de messages (un mécanisme illustré par MPI , Go , Scala , Erlang et occam ). Cet échange peut être asynchrone ou synchrone, selon un principe de « rendez-vous » où l'expéditeur est bloqué jusqu'à la réception du message. L'échange asynchrone peut être fiable ou non (parfois qualifié de « s'en remettre à la chance »). La concurrence par échange de messages est généralement plus facile à appréhender que la concurrence à mémoire partagée et est considérée comme une forme plus robuste de programmation concurrente. De nombreuses théories mathématiques permettent de comprendre et d'analyser les systèmes à échange de messages, notamment le modèle d'acteurs et divers calculs de processus . L'échange de messages peut être implémenté efficacement via le multiprocessus symétrique , avec ou sans cohérence du cache à mémoire partagée .
La gestion de la mémoire partagée et la gestion de la concurrence par messages présentent des caractéristiques de performance différentes. Généralement (mais pas toujours), la surcharge mémoire par processus et la surcharge liée aux changements de tâches sont moindres dans un système à messages, mais la surcharge globale de la gestion de la concurrence par messages est supérieure à celle d'un appel de procédure. Ces différences sont souvent masquées par d'autres facteurs de performance.
Histoire
Le calcul simultané s'est développé à partir de travaux antérieurs sur les chemins de fer et la télégraphie , datant du XIXe et du début du XXe siècle, et certains termes remontent à cette période, comme celui de sémaphore. Ces technologies ont été mises au point pour répondre à la question de la gestion de plusieurs trains sur un même réseau ferroviaire (en évitant les collisions et en optimisant l'efficacité) et de la gestion de plusieurs transmissions sur un même ensemble de câbles (en améliorant l'efficacité), notamment grâce au multiplexage temporel (années 1870).
L'étude académique des algorithmes concurrents a commencé dans les années 1960, avec l'exclusion mutuelle .
Prévalence
La concurrence est omniprésente en informatique, depuis les composants matériels de bas niveau sur une seule puce jusqu'aux réseaux mondiaux. Exemples ci-dessous.
Au niveau du langage de programmation :
Au niveau du système d'exploitation :
- Le multitâche informatique , incluant le multitâche coopératif et le multitâche préemptif
- Le temps partagé , qui a remplacé le traitement séquentiel par lots des tâches par l'utilisation simultanée d'un système
- Processus
- Fil
Au niveau du réseau, les systèmes en réseau sont généralement concurrents par nature, puisqu'ils sont constitués de dispositifs distincts.
Langages prenant en charge la programmation concurrente
Les langages de programmation concurrents sont des langages de programmation qui utilisent des constructions de langage pour la concurrence . Ces constructions peuvent inclure le multithreading , la prise en charge du calcul distribué , le passage de messages , les ressources partagées (y compris la mémoire partagée ) ou les futures et les promesses . Ces langages sont parfois décrits comme des langages orientés concurrence ou des langages de programmation orientés concurrence (COPL).
Aujourd'hui, les langages de programmation les plus couramment utilisés et disposant de mécanismes spécifiques pour la concurrence sont Java et C# . Ces deux langages utilisent fondamentalement un modèle de concurrence à mémoire partagée, avec un verrouillage assuré par des moniteurs (bien que des modèles à passage de messages puissent être implémentés, et l'aient été, par-dessus le modèle à mémoire partagée sous-jacent). Parmi les langages utilisant un modèle de concurrence à passage de messages, Erlang était probablement le plus répandu dans l'industrie en 2010.Pict ) que comme langages destinés à la production. Cependant, des langages tels qu'Erlang , Limbo et Occam ont été utilisés industriellement à différentes périodes au cours des 20 dernières années. Voici une liste non exhaustive de langages qui utilisent ou offrent des fonctionnalités de programmation concurrente :
- Ada – usage général, avec prise en charge native du passage de messages et de la concurrence basée sur les moniteurs
- Alef – programmation concurrente, avec threads et passage de messages, pour la programmation système dans les premières versions de Plan 9 des Bell Labs.
- Alice , une extension de Standard ML , ajoute la prise en charge de la concurrence via les futures.
- Ateji PX – extension de Java avec des primitives parallèles inspirées du π-calcul
- Axum – un système dédié au domaine, concurrent, basé sur un modèle d'acteurs et le Common Language Runtime .NET, utilisant une syntaxe similaire au C.
- Machine de flux de données modulaire binaire (BMDFM)
- C++ – bibliothèques de support des threads et des coroutines
- Cω (Commega) – pour la recherche, étend C#, utilise la communication asynchrone
- C# prend en charge le calcul concurrent grâce à l'utilisation de `lock` et `yield` , et introduit depuis la version 5.0 les mots-clés `async` et `await`.Clojure – un dialecte de programmation fonctionnelle moderne de Lisp sur la plateforme Java
- Concurrent Clean – programmation fonctionnelle, similaire à Haskell
- Collections concurrentes (CnC) – réalise un parallélisme implicite indépendant du modèle de mémoire en définissant explicitement le flux de données et le contrôle
- Haskell concurrent – un langage fonctionnel pur et paresseux qui gère des processus concurrents sur une mémoire partagée
- Apprentissage automatique concurrent – extension concurrente de l' apprentissage automatique standard
- Pascal concurrent – par Per Brinch Hansen
- Curry
- D – langage de programmation système multi-paradigme avec prise en charge explicite de la programmation concurrente ( modèle d'acteurs )
- E – utilise des promesses pour éviter les blocages
- ECMAScript – utilise des promesses pour les opérations asynchrones
- Eiffel – grâce à son mécanisme SCOOP basé sur les concepts de conception par contrat
- Elixir est un langage de métaprogrammation dynamique et fonctionnel qui s'exécute sur la machine virtuelle Erlang et utilise la transmission de messages asynchrone sans mémoire partagée.
- Erlang – langage dynamique et fonctionnel s'exécutant sur la machine virtuelle Erlang, utilisant un système de messagerie asynchrone sans mémoire partagée.
- FAUST – compilateur fonctionnel temps réel pour le traitement du signal, assure une parallélisation automatique via OpenMP ou un ordonnanceur de vol de travail spécifique.
- Fortran – les tableaux croisés dynamiques et les opérations concurrentes font partie de la norme Fortran 2008
- Go – pour la programmation système, avec un modèle de programmation concurrente basé sur des processus séquentiels communicants (CSP)
- Haskell – langage de programmation fonctionnelle concurrent et parallèle
- Hume – fonctionnel, concurrent, pour les environnements spatio-temporels limités où les processus d'automates sont décrits par des modèles de canaux synchrones et un système d'échange de messages.
- Io – concurrence basée sur les acteurs
- Janus – propose des interlocuteurs et des répondants distincts pour les variables logiques et les canaux de communication ; est purement déclaratif.
- Java – classe thread ou interface Runnable
- Julia – primitives de programmation concurrente : tâches, attente asynchrone, canaux
- JavaScript – via les web workers , dans un environnement de navigateur, les promesses et les fonctions de rappel
- JoCaml – un système de traitement concurrent et distribué basé sur les canaux, extension d' OCaml , implémente le calcul de jointure des processus
- Rejoignez Java – concurrent, basé sur le langage Java
- Joule – basé sur le flux de données, communique par passage de messages
- Joyce – processus concurrent et pédagogique, basé sur Concurrent Pascal et intégrant des fonctionnalités de CSP par Per Brinch Hansen
- LabVIEW – interface graphique, flux de données ; les fonctions sont représentées par des nœuds dans un graphe, les données par des connexions entre les nœuds ; inclut un langage orienté objet
- Limbo – parent d' Alef , pour la programmation système dans Inferno (système d'exploitation)
- Locomotive BASIC – variante Amstrad de BASIC contenant les commandes EVERY et AFTER pour les sous-routines concurrentes
- MultiLisp – Variante de Scheme étendue pour prendre en charge le parallélisme
- Modula-2 – pour la programmation système, par Niklaus Wirth , successeur de Pascal avec prise en charge native des coroutines
- Modula-3 – membre moderne de la famille ALGOL offrant une prise en charge étendue des threads, des mutex et des variables de condition
- Newsqueak – pour la recherche, avec des chaînes comme valeurs de premier ordre ; prédécesseur d' Alef
- occam – fortement influencé par les processus séquentiels communicants (CSP)
- occam-π – variante moderne d' occam , incluant des idées du π-calcul de Milner
- Object REXX (ooRexx) – échange de messages orienté objet pour la communication et la synchronisation
- Orc – hautement concurrent, non déterministe, basé sur l'algèbre de Kleene
- Oz-Mozart – multiparadigme, prend en charge la concurrence par état partagé et par passage de messages, et les futures
- ParaSail – orienté objet, parallèle, sans pointeurs, sans conditions de concurrence
- PHP – prise en charge du multithreading avec extension parallèle implémentant le passage de messages inspiré de Go
- Pict – essentiellement une implémentation exécutable du π-calcul de Milner
- Python – utilise le parallélisme basé sur les threads et le parallélisme basé sur les processus
- Raku – inclut par défaut des classes pour les threads, les promesses et les canaux
- Reia – utilise la transmission asynchrone de messages entre des objets sans partage
- Rouge/Système – pour la programmation système, basé sur Rebol
- Rust – pour la programmation système, utilisant le passage de messages avec sémantique de déplacement et la mémoire partagée (immuable et mutable)
- Scala – langage généraliste, conçu pour exprimer les modèles de programmation courants de manière concise, élégante et sûre en termes de types.
- SequenceL est un langage fonctionnel généraliste dont les principaux objectifs sont la facilité de programmation, la clarté et la lisibilité du code, ainsi que la parallélisation automatique pour optimiser les performances sur les architectures multicœurs. Il est garanti sans conditions de concurrence.
- SR – pour la recherche
- SuperPascal – concurrent, pour l'enseignement, basé sur Concurrent Pascal et Joyce de Per Brinch Hansen
- Swift – prise en charge intégrée de l’écriture de code asynchrone et parallèle de manière structurée
- Unicon – pour la recherche
- Le langage de spécification et de description de TeleNokia ( TNSDL ) – utilisé pour le développement des centraux de télécommunications – utilise la transmission de messages asynchrone.
- Langage de description matérielle VHSIC ( VHDL ) – IEEE STD-1076
- XC est un sous-ensemble du langage C étendu pour la concurrence, développé par XMOS . Il repose sur des processus séquentiels communicants et intègre des structures pour les E/S programmables.
De nombreux autres langages offrent une prise en charge de la concurrence sous forme de bibliothèques , à des niveaux à peu près comparables à ceux de la liste ci-dessus.