- Synchronisation (multitâches)
-
Pour les articles homonymes, voir Synchronisation.Dans le contexte de la programmation concurrente, le terme de synchronisation se réfère à deux concepts distincts mais liés : la synchronisation de processus et la synchronisation de données. Alors que la synchronisation de processus est un mécanisme qui vise à bloquer l'exécution des différents processus à des points précis de leur programme de manière à ce que tous les processus passent les étapes bloquantes au moment prévu par le programmeur, la synchronisation de donnée est un mécanisme qui vise à conserver la cohérence entre différentes données dans un environnement multitâche. Initialement cette notion de synchronisation est apparue pour la synchronisation de données.
Ces problèmes dit de « synchronisation » et même plus généralement ceux de communication inter-processus dont ces derniers dépendent, rendent pratiquement toujours la programmation plus difficile. Certaines méthodes de programmation cherchent à éviter d'utiliser ces verrous, appelées Non-blocking synchronization, elles sont encore plus difficiles à mettre en œuvre et nécessitent la mise en place de structure de données très particulières. La mémoire transactionnelle logicielle en est une.
Sommaire
Description de quelques problèmes
Dans l'illustration suivante, le résultat n'est pas prévisible, du fait que vous ne pouvez savoir quand les Thread A et B s'exécutent. Dans l'hypothèse la plus simple ou les thread A et B s'exécutent une fois, l'ordre d'exécution des instructions peut être par exemple : Lire, Lire, Add, Add, Écrire, Écrire ou Lire, Add, Écrire, Lire, Add, Écrire. Le résultat dans ces deux hypothèses n'est pas le même puisque au final dans le second cas la variable est augmentée de 2 alors qu'elle n'est augmentée que de un dans le premier.
Exemple d'erreur d'accès sur une variable Thread A Thread B 1A: Lire variable V 1B: Lire variable V 2A: Add 1 à la variable V 2B: Add 1 à la variable V 3A: Écrire la variable V 3B: Écrire la variable V Si l'instruction 1B est exécutée entre 1A et 3A, ou si l'instruction 1A est exécutée entre 1B et 3B, le programme produira des données incorrectes. Ce phénomène est connu sous le nom de situation de compétition. Pour résoudre ce genre de problème, le système doit permettre au programmeur d'utiliser un verrou d'exclusion mutuelle, c'est-à-dire de pouvoir bloquer, en une seule instruction, tous les processus tentant d'accéder à cette donnée, puis, que ces processus puisse y accéder enfin lorsque la variable est libérée. La tâche attendant la levée du verrou est dite « mise en sommeil ». Ces opérations de verrouillage en une instruction sont dites « atomique », du grec ατομος [atomos], qui signifie que l'on ne peut diviser[1]. Il existe concrètement plusieurs techniques pour obtenir des verrous et des sections critiques où l'accès au données est « sécurisé » comme ceci :
Exemple d'erreur d'accès sur plusieurs variables Thread A Thread B 1A: Verrouiller la variable V 1B: Verrouiller la variable V 2A: Lire la variable V 2B: Lire la variable V 3A: Add 1 à la variable V 3B: Add 1 à la variable V 4A: Écrire la variable V 4B: Écrire la variable V 5A: déverrouiller la variable V 5B: déverrouiller la variable V Ce genre de mécanismes est cependant source potentiel de bug informatique, en effet si deux tâches doivent chacune lire et écrire deux variables et qu'il y accèdent en même temps, cela doit être fait avec précaution. En effet, la première tâche verrouille la première variable pendant que la seconde tâche verrouille la seconde, les deux tâches seront mise en sommeil. Il s'agit la d'un cas d'interblocage, autrement appelé d'« étreinte mortel » ou « étreinte fatale ». Un fort couplage augmente le risque de bugs.
Synchronisation de processus
La synchronisation de processus cherche par exemple à empêcher des programmes d'exécuter la même portion de code en même temps, ou au contraire forcer l'exécution de deux parties de code en même temps. Dans la première hypothèse, le processus bloque l'accès au code en avant d'entrer dans la portion de code critique ou si cette section est en train d'être exécutée, se met en attente. Le processus libère l'accès en sortant de la partie du code. Ce mécanisme peut être implémenté de multiples manières.
Ces mécanismes sont par exemple la barrière de synchronisation, l'usage conjointe des Sémaphores et verrou, les Spinlocks, le moniteur, les mutex.
Synchronisation de donnée
La connaissance des dépendances entre les données est fondamental dans la mise en œuvre d'algorithmes parallèles, d'autant qu'un calcul peut dépendre de plusieurs calculs préalables. Les conditions de Bernstein[2] permettent de déterminer les conditions sur les données lorsque deux parties de programme peuvent être exécutées en parallèle. Ceci se formalise ainsi :
Soit Pi et Pj deux fragments de programme. Pour Pi, avec Ii les variables d'entrées et Oi les variables de sorties, et de même façon pour Pj. P i et Pj sont indépendants s'ils satisfont les conditions suivantes :
La violation de la première de ces conditions implique une dépendance des flux, c'est-à-dire le premier fragment ⇔ statement produit un résultat utilisé par le second. La seconde condition est une condition d'« anti-dépendance », le premier fragment écrase (i.e. remplace) une variable utilisée par le second. La dernière condition est une condition sur les sorties, lorsque les deux fragments écrivent une même données, la valeur finale est celle produit par le fragment exécuter en dernier[3].
Considérons les fonctions suivantes, qui démontrent plusieurs sortes de dépendances :
1: function Dep(a, b)
2: c := a·b
3: d := 2·c
4: end functionL'opération 3 dans Dep (a, b) ne peut pas être exécutée avant (ou même en parallèle avec) l'opération 2, car l'opération 3 utilise un résultat d'exploitation 2. Il viole la condition 1, et introduit ainsi une dépendance de flux. 1: function NoDep(a, b)
2: c := a·b
3: d := 2·b
4: e := a+b
5: end functionDans cet exemple, il n'y a pas de dépendances entre les instructions, de sorte qu'elles puissent être exécutées en parallèle. Les conditions de Bernstein ne permettent pas de gérer l'accès à la mémoire entre différents processus, ce sont les techniques de synchronisation qui vont permettre de le faire.
Leslie Lamport est le premier à avoir défini la cohérence séquentielle.
Pour accélérer les traitements effectués par les différentes unités de calcul, il est efficace de multiplier les données, c'est typiquement le cas lors de l'utilisation des caches. Ainsi l'unité de calcul travaille à partir d'une mémoire, spécialisée si possible, qui n'est pas la mémoire partagée par l'ensemble des unités de calculs. Lorsque le programme modifie une donnée dans ce cache, le système doit en fait la modifier dans l'espace commun et répercuter cette modification au sein de tous les caches où cette donnée est présente. Des mécanismes sont mis en place pour que les données restent cohérentes. Ces mécanismes peuvent être décrits par de complexes modèles d'algèbres de processus et ces derniers peuvent être décrits de plusieurs manières au sein de divers langages formels. Le mécanisme à mémoire transactionnelle logicielle est le plus courant des modèles de cohérence, il emprunte à la théorie des systèmes de gestion de base de données la notion de transactions atomiques et les applique aux accès mémoire.
Efficacité et limites
Articles détaillés : Extensibilité et speedup.D'une manière générale, plus le nombre de tâches est élevé dans un programme, plus ce programme passe son temps à effectuer des verrouillages et plus il passe son temps à échanger des messages entre tâches. Autrement dit lorsque le nombre de tâches augmente trop, la programmation concourante ne permet plus d'augmenter la vitesse d'exécution du programme ou plus précisément de diminuer la durée de son chemin critique car le programme passe son temps à mettre en sommeil les taches qui le composent et à écrire des informations qui permettent l'échange d'information entre tâches. Ce phénomène est appelé le parallel slowdown.
D'ailleurs, les applications sont souvent classées en fonction de la fréquence à laquelle ses tâches dialoguent ou se synchronisent. Les applications ayant beaucoup d'échanges ou de synchronisations entre ses sous-tâches sont dites fine-grained (à grain fin), celles qui ont au contraire peu d'échanges et de synchronisations sont dites coarse-grained (c'est-à-dire à gros grain). L'algorithme est dit Embarrassingly parallel, c'est-à-dire de « parallélisme embarrassant » s'il n'y a aucun contact entre les sous-tâches. Ce dernier est le plus simple à programmer.
Implémentation
Voici, un tableau récapitulatif de l'implémentation de la synchronisation pour les processus lourds et les processus légers.
Type processus lourd, fork wait processus lourd, sémaphore IPC processus lourd, tube processus lourd, message IPC processus lourd, segment partagé Java Thread système de nommage PID / getPId cle IPC interne cle IPC cle IPC les objets nombre d'activités 2 N 2 N N N appel bloquant wait() p() read() receive() non syncronized/wait() communication exit(p) non stream message taille du segment les objets volume de la communication 2 octets non non limité taille de la boite aux lettres non limité machine virtuelle Problèmes et applications
Voir aussi
- Définitions lexicographiques et étymologiques de « atome » du CNRTL.
- Bernstein, A. J. (October 1966). "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers". EC-15, pp. 757–62.
- Roosta, Seyed H. (2000). "Parallel processing and parallel algorithms: theory and computation". Springer, p. 114. ISBN 0387987169.
Wikimedia Foundation. 2010.
