Synchronisation (multitâches)

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.

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écute. 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.

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. 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 :

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.

La synchronisation de processus cherche par exemple à d'empêcher un programme d'exécuter la même portion de code en même temps, ou au contraire forcer l'exécution de deux partie 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 entrain d'être exécuter, se met en attente. Le processus libère l'accès en sortant de la partie du code. Ce mécanisme peut être implémenter de multiple manière.

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.

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 permette de déterminer les conditions sur les données lorsque deux parties de programme peuvent êtres exécuter en parallèle. Ceci se formalise ainsi :

Soit P_i et P_j deux fragments de programme. Pour P_i, avec I_i les variables d'entrées et O_i les variables de sorties, et de même façon pour P_j. P _i et P_j sont indépendants s'ils satisfont les conditions suivantes :

• $I_j\cap O_i=\varnothing ,$
• $I_i\cap O_j=\varnothing ,$
• $O_i\cap O_j=\varnothing .$

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 conditions 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.

Considérons les fonctions suivantes, qui démontrent plusieurs sortes de dépendances :

Les conditions de Bernstein ne permettent pas de gérer l'accès à la mémoire entre différents processus, ce sont les technique de synchronisation qui vont permettre de le faire.

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 ou 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écrit 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.

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âche. Autrement lorsque le nombre de tâche 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  ⇔  ralentissement parallèle.

D'ailleurs les applications sont souvent classées en fonction 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 dite fine-grained à grain fin, celle qui ont au contraire peu d'échanges et de synchronisations sont dite 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.

Voici, un tableau récapitulatif de l'implémentation de la synchronisation pour les processus lourds et les processus légers.

• Modèle producteur-consommateur
• Problème des lecteurs et des rédacteurs
• parallélisme