Synchronisation (multitâches) - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Description de quelques problèmes - Synchronisation de donnée - Synchronisation de processus - Implémentation - Efficacité et limites - Problèmes et applications

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

`1: function Dep(a, b) 2: c := a·b 3: d := 2·c 4: end function`	L'opération 3 dans Dep (a, b) ne peut pas être exécuté 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 function`	Dans cet exemple, il n'y a pas de dépendances entre les instructions, de sorte qu'elles puissent être exécutés 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 technique 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 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.

Synchronisation de processus

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.