Synchronisation (multitâches)

En programmation concurrente, la synchronisation se réfère à deux concepts distincts mais liés : la synchronisation de processus et la synchronisation de données. La synchronisation de processus est un mécanisme qui vise à bloquer l'exécution de certains processus à des points précis de leur flux d'exécution, de manière que tous les processus se rejoignent à des étapes relais données, tel que prévu par le programmeur. La synchronisation de données, elle, est un mécanisme qui vise à conserver la cohérence des données telles que vues par différents processus, dans un environnement multitâche. Initialement, la notion de synchronisation est apparue pour la synchronisation de données.

Ces problèmes dits « de synchronisation » et même plus généralement ceux de communication inter-processus dont ils dépendent, rendent pratiquement toujours la programmation concurrente plus difficile. Certaines méthodes de programmation, appelées synchronisation non-bloquante, cherchent à éviter d'utiliser des verrous, mais 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

Dans l'illustration suivante, le résultat n'est pas prévisible, du fait que l'on ne peut savoir quand les threads A et B s'exécutent. Dans l'hypothèse la plus simple ou les threads A et B s'exécutent une fois, l'ordre d'exécution des instructions peut être par exemple : lire, lire, ajouter, ajouter, écrire, écrire ou lire, ajouter, écrire, lire, ajouter, é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 la variable V	1B : lire la variable V
2A : ajouter 1 à la variable V	2B : ajouter 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 puissent 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, « que l'on ne peut diviser ». Il existe concrètement plusieurs techniques pour obtenir des verrous et des sections critiques où l'accès aux 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 : ajouter 1 à la variable V	3B : ajouter 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, aussi appelé d'« étreinte mortelle » 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 partie 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 premier processus bloque l'accès à la section critique avant d'y entrer et libère l'accès après en être sorti. Ce mécanisme peut être implémenté de multiples manières.

Ces mécanismes sont par exemple la barrière de synchronisation, l'usage conjoint des sémaphores et des verrous, les spinlocks, le moniteur, les mutex.

Synchronisation de données

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 permettent de déterminer les conditions sur les données lorsque deux parties de programme peuvent être exécutées en parallèle.

Conditions de Bernstein

Soient P_i et P_j deux parties de programme. On note I_i et I_j les variables d'entrées et O_i et O_j les variables de sorties de P_i et P_j respectivement. P_i et P_j sont indépendantes si elles satisfont les conditions suivantes :

1. $O_{i}\cap I_{j}=\varnothing .$
2. $I_{i}\cap O_{j}=\varnothing .$
3. $O_{i}\cap O_{j}=\varnothing .$

La violation de la première condition implique une dépendance des flux, c'est-à-dire que la première partie écrit une variable utilisée par la seconde partie. La violation de la seconde condition implique une anti-dépendance des flux, c'est-à-dire que la seconde partie écrit une variable utilisée par la première partie. La violation de la dernière condition implique que les deux parties écrivent une même variable.

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 le résultat de l'opération 2. Cette dépendance de flux viole la première condition de Bernstein.
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

D'une manière générale, plus le nombre de sous-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 ces sous-tâches. Autrement dit, lorsque le nombre de sous-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 sous-tâches qui le composent et à écrire des informations qui permettent l'échange d'information entre ces sous-tâches. Ce phénomène est appelé le ralentissement parallèle (parallel slowdown en anglais).

D'ailleurs, les programmes sont souvent classées en fonction de la fréquence à laquelle leurs sous-tâches dialoguent ou se synchronisent. Les programmes qui pratiquent beaucoup d'échanges ou de synchronisations entre leurs sous-tâches sont dites à grains fins (fine-grained en anglais), les programmes qui pratiquent peu d'échanges et de synchronisations sont dites à grains gros (coarse-grained en anglais) et les programmes qui ne pratiquent aucune interaction entre leurs sous-tâches sont dits parallèles à en être gênant (embarrassingly parallel en anglais). Cette dernière classe de programme est la plus simple à implémenter.

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

Implémentation

Pour les processus légers, en occam la synchronisation est ramenée à une é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	clé IPC	interne	clé IPC	clé IPC	les objets
Nombre d'activités	2	N	2	N	N	N
Appel bloquant	wait()	p()	read()	receive()	non	synchronized/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

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