Synchronisation (multitâches)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie 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.


Description de quelques problèmes[modifier | modifier le code]

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 puisqu'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'elles 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 mortelle » ou « étreinte fatale ». Un fort couplage augmente le risque de bugs.

Synchronisation de processus[modifier | modifier le code]

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[modifier | modifier le code]

La connaissance des dépendances entre les données est fondamentale 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[3]

  •  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 que la première opération 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écuté en dernier[4].

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é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 function

Dans 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[modifier | modifier le code]

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 concurrente 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 tâches 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, 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.

En occam, le plus efficace est la mise en parallèle d'un traitement avec des entrées/sorties.

Implémentation[modifier | modifier le code]

Pour les processus légers, en occam la synchronisation est ramenée à un émission/réception de valeur sur canal interne, synchronisée par un mécanisme de rendez-vous. L'axiomatisation du langage permet de vérifier à la compilation diverses conditions de bonne fin.

channel c ;
PAR
  SEQ
    x:= y+z*t
-- émission de x sur c
    c ! x
    ...
  SEQ
    p := q*r+s
-- réception en w de la valeur transmise par c
    c ? w
    ...

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

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[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

  1. Définitions lexicographiques et étymologiques de « atome » du Trésor de la langue française informatisé, sur le site du Centre national de ressources textuelles et lexicales .
  2. Bernstein, A. J. (October 1966). "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers". EC-15, pp. 757–62.
  3. [1]Roscoe A.W., C.H.R. Hoare, 1986, The laws of occam programming, Oxford University Computing Lab., Technical Monograph PRG-53
  4. Roosta, Seyed H. (2000). "Parallel processing and parallel algorithms: theory and computation". Springer, p. 114. ISBN 0-387-98716-9.