Concurrence – Synchronisation

Un processus est une instance d'un programme en cours d'exécution. Chaque processus possède son propre espace mémoire et peut contenir plusieurs threads (ou fils d'exécution), qui partagent cet espace mémoire mais s'exécutent indépendamment.

L'exécution des threads est non déterministe : l'ordonnancement du processeur varie selon la charge du système, ce qui entraîne des résultats imprévisibles si des threads accèdent simultanément aux mêmes ressources sans synchronisation.

Programmation avec les Threads

Bibliothèque pthread en C

pthread est une bibliothèque standard pour gérer les threads en C.

Voici les principales directives et instructions de pthread :

• include <pthread.h> : inclus la bibliothèque ;
• pthread_create() : crée un thread ;
• pthread_join() : attend la fin du thread ;
• pthread_exit() : termine un thread proprement.

Bibliothèque Thread d'OCaml

OCaml supporte les threads via le module Thread.

Voici les principales fonctions de Thread :

• Thread.create f arg : crée un thread exécutant f arg ;
• Thread.join t : attend la fin du thread t ;
• Thread.exit () : termine un thread.

Interblocage

Un interblocage (ou deadlock) est une situation où plusieurs threads se bloquent indéfiniment en attendant une ressource détenue par un autre thread. Aucun ne peut avancer, créant un blocage total du système.

Solutions possibles pour éviter les situations d'interblocage :

• Ordonnancement strict : forcer un ordre de prise des ressources ;
• Timeouts : forcer un thread à relâcher une ressource après un certain temps ;
• Hiérarchie de verrouillage : imposer un ordre dans l'acquisition des ressources.

Modèle de synchronisation

La synchronisation des threads est essentielle pour garantir un accès contrôlé aux ressources partagées, et éviter l'interblocage. Plusieurs modèles classiques permettent d'organiser l'exécution des threads et d'éviter les conflits.

Rendez-vous

Le rendez-vous est un mécanisme où deux threads doivent attendre l'un l'autre avant de poursuivre leur exécution. Il est utilisé lorsqu'un thread ne peut avancer qu'après avoir échangé des informations avec un autre. On le retrouve dans le modèle client-serveur notamment.

Producteur-Consommateur

Ce modèle synchronise deux types de threads :

• Les producteurs génèrent des données et les placent dans un tampon partagé.
• Les consommateurs récupèrent ces données et les traitent.

Un problème clé est d'éviter les conditions de course (accès concurrent au tampon) et la surcharge (le producteur ne doit pas remplir un tampon déjà plein).

Exclusion Mutuelle

L'exclusion mutuelle est un principe garantissant que seul un thread ou un processus accède à une ressource partagée à un instant donné. Cela prévient les conditions de course, où plusieurs threads modifient simultanément une variable, entraînant des erreurs imprévisibles.

Les solutions d'exclusion mutuelle peuvent être matérielles (instructions atomiques) ou logicielles (algorithmes comme Peterson ou Lamport).

Section critique

Une section critique est une portion de code où un thread accède à une ressource partagée et dont l'exécution simultanée par plusieurs threads peut entraîner des erreurs ou des incohérences.

Mutex

Un mutex (Mutual Exclusion Lock) est un verrou utilisé pour protéger une section critique en empêchant plusieurs threads d'y accéder en même temps.

Principe :

• Un thread qui veut accéder à une ressource verrouille le mutex ;
• Si un autre thread tente d'accéder à la même ressource, il doit attendre que le premier déverrouille le mutex ;
• Une fois la ressource libérée, un autre thread peut l'acquérir et exécuter son code critique.

Un mutex peut causer un interblocage si plusieurs threads attendent mutuellement un mutex détenu par l'autre.

Algorithme de Peterson

L'algorithme de Peterson est une solution logicielle permettant à deux threads d'accéder à une section critique sans se chevaucher.

Principe :

• Chaque thread signale son intention d'entrer dans la section critique via une variable (flag) ;
• Une autre variable (tour) indique quel thread a la priorité ;
• Un thread ne peut entrer dans la section critique que si l'autre ne réclame pas l'accès ou si c'est son tour.

Algorithme de Lamport

L'algorithme de Lamport étend l'idée de Peterson à plusieurs threads en utilisant un système de tickets inspiré des files d'attente aux guichets.

Principe :

• Chaque thread prend un numéro de ticket plus grand que ceux des autres ;
• Il attend que tous les threads ayant un ticket plus petit terminent avant d'entrer dans la section critique ;
• Une fois terminé, il remet son ticket à zéro, permettant aux autres threads d'avancer.

Sémaphores

Un sémaphore est une variable synchronisée permettant de contrôler l'accès à une ressource partagée par plusieurs threads. Deux types de sémaphores existent :

• Binaire : fonctionne comme un verrou simple (valeurs 0 ou 1), équivalent au mutex.
• Compteur : permet de gérer plusieurs ressources disponibles simultanément.

Principe :

• Un thread diminue la valeur du sémaphore avant d'entrer en section critique.
• Il l'augmente après avoir terminé, libérant ainsi la ressource pour un autre thread.