Synchronisation (informatique)

En informatique , la synchronisation est la tâche consistant à coordonner plusieurs processus pour qu'ils se rejoignent ou s'échangent des informations à un moment donné, afin de parvenir à un accord ou de s'engager dans une certaine séquence d'actions.

Le besoin de synchronisation ne se pose pas uniquement dans les systèmes multiprocesseurs, mais également pour tout type de processus simultanés, même dans les systèmes monoprocesseurs. Voici quelques-uns des principaux besoins en matière de synchronisation :

Forks et Joins : Lorsqu'un job arrive à un point de fork, il est divisé en N sous-jobs qui sont ensuite traités par n tâches. Après avoir été traité, chaque sous-job attend que tous les autres sous-jobs aient terminé leur traitement. Ensuite, ils sont à nouveau joints et quittent le système. Ainsi, la programmation parallèle nécessite une synchronisation car tous les processus parallèles attendent que plusieurs autres processus se produisent.

Producteur-Consommateur : Dans une relation producteur-consommateur, le processus consommateur dépend du processus producteur jusqu'à ce que les données nécessaires aient été produites.

Ressources à usage exclusif : lorsque plusieurs processus dépendent d'une ressource et doivent y accéder en même temps, le système d'exploitation doit s'assurer qu'un seul processeur y accède à un moment donné. Cela réduit la concurrence.

La synchronisation des threads est définie comme un mécanisme qui garantit que deux ou plusieurs processus ou threads simultanés n'exécutent pas simultanément un segment de programme particulier appelé section critique . L'accès des processus à la section critique est contrôlé à l'aide de techniques de synchronisation. Lorsqu'un thread commence à exécuter la section critique (segment sérialisé du programme), l'autre thread doit attendre que le premier thread termine. Si des techniques de synchronisation appropriées ne sont pas appliquées, cela peut provoquer une situation de concurrence où les valeurs des variables peuvent être imprévisibles et varier en fonction des timings des changements de contexte des processus ou des threads.

Par exemple, supposons qu'il existe trois processus, à savoir 1, 2 et 3. Tous les trois s'exécutent simultanément et doivent partager une ressource commune (section critique) comme illustré dans la Figure 1. La synchronisation doit être utilisée ici pour éviter tout conflit d'accès à cette ressource partagée. Par conséquent, lorsque les processus 1 et 2 tentent tous deux d'accéder à cette ressource, celle-ci ne doit être attribuée qu'à un seul processus à la fois. Si elle est attribuée au processus 1, l'autre processus (processus 2) doit attendre que le processus 1 libère cette ressource (comme illustré dans la Figure 2).

Une autre exigence de synchronisation à prendre en compte est l'ordre dans lequel des processus ou des threads particuliers doivent être exécutés. Par exemple, on ne peut pas monter à bord d'un avion avant d'avoir acheté un billet. De même, on ne peut pas consulter ses e-mails avant d'avoir validé les informations d'identification appropriées (par exemple, le nom d'utilisateur et le mot de passe). De la même manière, un distributeur automatique de billets ne fournira aucun service tant qu'il n'aura pas reçu un code PIN correct.

Outre l’exclusion mutuelle, la synchronisation traite également des éléments suivants :

• blocage , qui se produit lorsque de nombreux processus attendent une ressource partagée (section critique) détenue par un autre processus. Dans ce cas, les processus continuent d'attendre et ne s'exécutent plus ;
• la famine , qui se produit lorsqu'un processus attend d'entrer dans la section critique, mais que d'autres processus monopolisent la section critique et que le premier processus est obligé d'attendre indéfiniment ;
• inversion de priorité , qui se produit lorsqu'un processus de priorité élevée se trouve dans la section critique et qu'il est interrompu par un processus de priorité moyenne. Cette violation des règles de priorité peut se produire dans certaines circonstances et peut entraîner de graves conséquences dans les systèmes en temps réel ;
• attente en cours , qui se produit lorsqu'un processus interroge fréquemment pour déterminer s'il a accès à une section critique. Ces interrogations fréquentes privent d'autres processus de temps de traitement.

L'un des défis de la conception d'algorithmes exascale est de minimiser ou de réduire la synchronisation. La synchronisation prend plus de temps que le calcul, en particulier dans le calcul distribué. La réduction de la synchronisation a attiré l'attention des informaticiens pendant des décennies. Or, cela devient un problème de plus en plus important récemment, car l'écart entre l'amélioration du calcul et la latence augmente. Des expériences ont montré que les communications (globales) dues à la synchronisation sur des ordinateurs distribués occupent une part dominante dans un solveur itératif clairsemé. Ce problème reçoit une attention croissante après l'émergence d'une nouvelle mesure de référence, le High Performance Conjugate Gradient (HPCG), pour classer les 500 meilleurs supercalculateurs.

Voici quelques problèmes classiques de synchronisation :

• Le problème du producteur-consommateur (également appelé problème du tampon borné) ;
• Le problème des lecteurs et des écrivains ;
• Le problème des philosophes du dîner .

Ces problèmes sont utilisés pour tester presque tous les nouveaux schémas ou primitives de synchronisation proposés.

De nombreux systèmes fournissent un support matériel pour le code de section critique .

Un système à processeur unique ou monoprocesseur pourrait désactiver les interruptions en exécutant le code en cours d'exécution sans préemption , ce qui est très inefficace sur les systèmes multiprocesseurs . « La capacité clé dont nous avons besoin pour implémenter la synchronisation dans un multiprocesseur est un ensemble de primitives matérielles avec la capacité de lire et de modifier atomiquement un emplacement de mémoire. Sans une telle capacité, le coût de construction des primitives de synchronisation de base sera trop élevé et augmentera à mesure que le nombre de processeurs augmente. Il existe un certain nombre de formulations alternatives des primitives matérielles de base, qui offrent toutes la capacité de lire et de modifier atomiquement un emplacement, ainsi qu'un moyen de savoir si la lecture et l'écriture ont été effectuées de manière atomique. Ces primitives matérielles sont les blocs de construction de base qui sont utilisés pour construire une grande variété d'opérations de synchronisation au niveau de l'utilisateur, y compris des éléments tels que des verrous et des barrières . En général, les architectes ne s'attendent pas à ce que les utilisateurs utilisent les primitives matérielles de base, mais s'attendent plutôt à ce que les primitives soient utilisées par les programmeurs système pour construire une bibliothèque de synchronisation, un processus souvent complexe et délicat. » De nombreux composants matériels modernes fournissent de telles instructions atomiques, deux exemples courants étant : test-and-set , qui fonctionne sur un seul mot mémoire, et compare-and-swap , qui échange le contenu de deux mots mémoire.

En Java , une façon d'empêcher les interférences entre threads et les erreurs de cohérence de la mémoire consiste à préfixer une signature de méthode avec le mot clé synchronisé , auquel cas le verrou de l'objet déclarant est utilisé pour forcer la synchronisation. Une deuxième façon consiste à encapsuler un bloc de code dans une section synchronisée (someObject) {...} , qui offre un contrôle plus précis. Cela force tout thread à acquérir le verrou de someObject avant de pouvoir exécuter le bloc contenu. Le verrou est automatiquement libéré lorsque le thread qui a acquis le verrou quitte ce bloc ou entre dans un état d'attente au sein du bloc. Toutes les mises à jour de variables effectuées par un thread dans un bloc synchronisé deviennent visibles pour les autres threads lorsqu'ils acquièrent de la même manière le verrou et exécutent le bloc. Quelle que soit l'implémentation, n'importe quel objet peut être utilisé pour fournir un verrou, car tous les objets Java ont un verrou intrinsèque ou un verrou de surveillance qui leur est associé lorsqu'ils sont instanciés.

Les blocs synchronisés Java , en plus de permettre l'exclusion mutuelle et la cohérence de la mémoire, permettent la signalisation, c'est-à-dire l'envoi d'événements depuis les threads qui ont acquis le verrou et exécutent le bloc de code vers ceux qui attendent le verrou dans le bloc. Les sections synchronisées Java combinent donc les fonctionnalités des mutex et des événements pour assurer la synchronisation. Une telle construction est connue sous le nom de moniteur de synchronisation .

Le .NET Framework utilise également des primitives de synchronisation. « La synchronisation est conçue pour être coopérative, exigeant que chaque thread suive le mécanisme de synchronisation avant d'accéder aux ressources protégées pour des résultats cohérents. Le verrouillage, la signalisation, les types de synchronisation légers, le spinwait et les opérations verrouillées sont des mécanismes liés à la synchronisation dans .NET. »

De nombreux langages de programmation prennent en charge la synchronisation et des langages spécialisés entiers ont été écrits pour le développement d'applications embarquées où une synchronisation strictement déterministe est primordiale.

Une autre façon efficace d'implémenter la synchronisation consiste à utiliser des verrous rotatifs. Avant d'accéder à une ressource partagée ou à un morceau de code, chaque processeur vérifie un indicateur. Si l'indicateur est réinitialisé, le processeur définit l'indicateur et continue d'exécuter le thread. Mais, si l'indicateur est défini (verrouillé), les threads continueront à tourner en boucle et à vérifier si l'indicateur est défini ou non. Mais les verrous rotatifs ne sont efficaces que si l'indicateur est réinitialisé pour des cycles inférieurs, sinon cela peut entraîner des problèmes de performances car cela gaspille de nombreux cycles de processeur en attente.

Les barrières sont simples à mettre en œuvre et offrent une bonne réactivité. Elles reposent sur le concept de mise en œuvre de cycles d'attente pour assurer la synchronisation. Considérons trois threads exécutés simultanément, en commençant par la barrière 1. Après le temps t, le thread1 atteint la barrière 2 mais il doit encore attendre que les threads 2 et 3 atteignent la barrière 2 car il n'a pas les bonnes données. Une fois que tous les threads atteignent la barrière 2, ils recommencent tous. Après le temps t, le thread 1 atteint la barrière 3 mais il devra à nouveau attendre les threads 2 et 3 et les bonnes données.

Ainsi, dans la synchronisation de barrière de plusieurs threads, il y aura toujours quelques threads qui finiront par attendre d'autres threads comme dans l'exemple ci-dessus, le thread 1 continue d'attendre les threads 2 et 3. Cela entraîne une grave dégradation des performances du processus.

La fonction d'attente de synchronisation de barrière pour le i ^-ème thread peut être représentée comme :

(Wbarrière)i=f ((Tbarrière)i, (Rthread)i)

Où Wbarrier est le temps d'attente d'un thread, Tbarrier est le nombre de threads arrivés et Rthread est le taux d'arrivée des threads.

Les expériences montrent que 34 % du temps d’exécution total est consacré à attendre d’autres threads plus lents.

Les sémaphores sont des mécanismes de signalisation qui peuvent permettre à un ou plusieurs threads/processeurs d'accéder à une section. Un sémaphore possède un indicateur auquel est associée une certaine valeur fixe et chaque fois qu'un thread souhaite accéder à la section, il décrémente l'indicateur. De même, lorsque le thread quitte la section, l'indicateur est incrémenté. Si l'indicateur est nul, le thread ne peut pas accéder à la section et est bloqué s'il choisit d'attendre.

Certains sémaphores n'autorisent qu'un seul thread ou processus dans la section de code. De tels sémaphores sont appelés sémaphores binaires et sont très similaires à Mutex. Ici, si la valeur du sémaphore est 1, le thread est autorisé à accéder et si la valeur est 0, l'accès est refusé.

La synchronisation était à l'origine un concept basé sur les processus, par lequel un verrou pouvait être obtenu sur un objet. Son utilisation principale était dans les bases de données. Il existe deux types de verrous (de fichier) : en lecture seule et en lecture-écriture. Les verrous en lecture seule peuvent être obtenus par de nombreux processus ou threads. Les verrous en lecture-écriture sont exclusifs, car ils ne peuvent être utilisés que par un seul processus/thread à la fois.

Bien que les verrous aient été créés pour les bases de données de fichiers, les données sont également partagées en mémoire entre les processus et les threads. Parfois, plusieurs objets (ou fichiers) sont verrouillés à la fois. S'ils ne sont pas verrouillés simultanément, ils peuvent se chevaucher, provoquant une exception de blocage.

Java et Ada n'ont des verrous exclusifs que parce qu'ils sont basés sur des threads et s'appuient sur l' instruction de comparaison et d'échange du processeur.

Le monoïde historique constitue une base mathématique abstraite pour les primitives de synchronisation . Il existe également de nombreux dispositifs théoriques de niveau supérieur, tels que les calculs de processus et les réseaux de Petri , qui peuvent être construits sur la base du monoïde historique.

Voici quelques exemples de synchronisation par rapport à différentes plates-formes.

Windows fournit :

• masques d'interruption , qui protègent l'accès aux ressources globales (section critique) sur les systèmes monoprocesseurs ;
• verrous de rotation , qui empêchent, dans les systèmes multiprocesseurs, le thread de verrouillage de rotation d'être préempté ;
• répartiteurs dynamiques , qui agissent comme des mutex , des sémaphores , des événements et des minuteries .

Linux fournit :

• sémaphores ;
• verrou tournant ;
• barrières ;
• mutex ;
• verrous lecteurs-écrivains , pour la section la plus longue des codes à laquelle on accède très fréquemment mais qui ne changent pas très souvent ;
• lecture-copie-mise à jour (RCU).

L'activation et la désactivation de la préemption du noyau ont remplacé les verrous rotatifs sur les systèmes monoprocesseurs. Avant la version 2.6 du noyau, Linux désactivait l'interruption pour implémenter de courtes sections critiques. Depuis la version 2.6 et les versions ultérieures, Linux est entièrement préemptif.

Solaris fournit :

• sémaphores
• variables de condition
• mutex adaptatifs – sémaphores binaires implémentés différemment selon les conditions
• verrous lecteurs-écrivains
• tourniquets – file d'attente de threads qui attendent le verrou acquis

Pthreads est une API indépendante de la plateforme qui fournit :

• mutex;
• variables de condition;
• verrous lecteurs-écrivains ;
• verrous rotatifs;
• barrières .