Rappel et première notion

Un programme séquentiel exécute les instructions l’une après l’autre, dans un ordre linéaire déterministe. Il possède un seul flux d’exécution (main) qui débute et s’achève, sans interruption ni parallélisme.

#include <stdio.h>
#include <unistd.h>

int main() {
    printf("Étape 1\n");
    sleep(1);
    printf("Étape 2\n");
    sleep(1);
    printf("Étape 3\n");
    return 0;
}

L’exécution prend au minimum 2 secondes puisque les étapes s’enchaînent strictement. Le flux de contrôle commence à main(), exécute chaque instruction dans l’ordre prescrit, puis se termine. Ce modèle est prévisible mais limité : pas d’exploitation des architectures modernes multi-cœurs et “perte” de temps sur les opération d’I/O.

Le modèle fork

Depuis les origines d’Unix (1971), la création de parallélisme repose sur fork(), un appel système qui crée un processus enfant en dupliquant entièrement le processus parent. Chaque processus possède son propre espace mémoire, ses propres variables globales, sa pile, son tas, et son identifiant de processus (PID) unique. C’est ce que nous avons vue dans le cours précédent.

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

int main() {
    pid_t pid = fork();

    if (pid == 0) {
        // Bloc enfant : pid == 0
        printf("Enfant: mon PID est %d\n", getpid());
        return 0;
    } else if (pid > 0) {
        // Bloc parent : pid contient le PID de l'enfant
        printf("Parent: PID de l'enfant est %d\n", pid);
        wait(NULL);  // Attend la fin de l'enfant
    }
    return 0;
}

Après fork(), deux processus indépendants s’exécutent en parallèle. Les modifications faites par l’enfant (variables globales, allocations mémoire) n’affectent jamais le parent et vice-versa. Cette isolation est une force (pas d’interaction accidentelle, sécurité) mais aussi une faiblesse : la communication entre processus passe par des mécanismes “complexes” (IPC : pipes, sockets, fichiers, memory-mapped regions). Ou tout du moins, peu pratique et lent.

Le modèle fork est souvent difficile à concevoir pour les étudiants. On lance un seul programme, on sait qu’il y a deux processus, mais on a des difficultés à comprendre ce qu’il se passe, car on « voit » du code entrelacé qui correspond aux deux processus. Dans cette situation une “solution” consiste à écrire une fonction correspondent a chaque processus.

int main() {
    pid_t child_pid = fork();

    if (child_pid == 0) {
        return child_process_function();
    } else if (pid > 0) {
        return main_process_function(child_pid);
    } else  {
        // error handling
        return 1;
    } 

    return 0;
}

Caractéristiques de fork() :

• Copie l’image du processus complet (virtualité de la mémoire gérée par copy-on-write, CoW)
• Coûteux en création (~ms)
• Idéal pour créer des tâches entièrement isolées
• Pas d’accès direct aux variables globales du parent
  • Nécéssite des mécanisme IPC (fichier, socket, pipe, etc)

Les threads

Les threads POSIX (Pthreads) offrent une approche radicalement différente : tous les threads d’un même processus partagent exactement la même mémoire. Au lieu de dupliquer toute l’image mémoire (opération coûteuse), on crée simplement une nouvelle pile, un nouvel état de registres, et un nouvel identifiant de thread (fils d’éxécution dans ce processus).

Un thread est représenté par la structure task_struct voir doc … c’est une parenthese

#include <pthread.h>
#include <stdio.h>

void* f_thread(void* arg) {
    printf("Hello du thread !\n");
    return NULL;
}

int main() {
    pthread_t tid;
    pthread_create(&tid, NULL, f_thread, NULL);
    pthread_join(tid, NULL);
    return 0;
}

Lors de la création d’un thread avec pthread_create(), le noyau crée une nouvelle structure TCB (Thread Control Block) contenant l’adresse d’instruction, le pointeur de pile, les registres généraux, et un identifiant unique. Mais tous les threads partagent les mêmes sections de données du processus, la même heap et tout le reste (ressources ouvertes, …).

Comparaison fork() vs pthread :

Aspect	fork() (processus)	pthread (thread)
Espace mémoire	Copie complète (CoW)	Partagé
Création	Coûteuse (~ms)	Rapide (~µs)
Communication	IPC complexe (pipes, sockets)	Accès direct aux variables globales et ptr
Isolation	Forte (sécurité)	Aucune (risque de race conditions)
Surcoût contexte	Lourd	Léger

Avantages des threads par rapport à fork() :

• Communication directe et efficace via variables globales ou pointeurs
• Création rapide, permettant de créer des dizaines/centaines de threads
• Possibilité de persistance des threads, avec mise en attente ou redémarage (gain de perf)
• Partage d’état applicatif sans sérialisation IPC

Introduction à Pthreads

La fonction pthread_create prend quatre arguments : adresse de la variable stockant l’ID du thread, attributs (souvent NULL permettant un controle fin sur les protiétées d’éxécution : coeur, cpu, prio, …), pointeur vers la fonction à exécuter (prototype imposé void* func(void*)), et un argument optionnel qui sera donné un paramètre le void*.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

void* tache(void* arg) {
    int id = *(int*)arg;
    printf("Je suis le thread %d\n", id);
    free(arg);
    return NULL;
}

int main() {
    pthread_t t1, t2;

    int id1 = 1;
    int id2 = 2;

    // Créer deux threads
    pthread_create(&t1, NULL, tache, &id1);
    pthread_create(&t2, NULL, tache, &id2);

    // Attendre la fin des deux threads
    pthread_join(t1, NULL); // on peu récupérer la sortie de la fonction : le paramètre NULL est associé au return NULL
    pthread_join(t2, NULL); // si c'est un ptr alors la donné sera copier, sinon ici NULL indique de ne rien récupérer

    printf("Tous les threads ont terminé\n");
    return 0;
}

Ordre critique : Le modèle correct est de créer tous les threads d’abord, puis de les joindre. Joindre immédiatement chaque thread après sa création annule les bénéfices du parallélisme -> créé, attend, créé, attend, créé, attend, …

// MAUVAIS : pas de parallélisme
pthread_create(&t1, NULL, tache, NULL);
pthread_join(t1, NULL);   // Attend ici, t2 ne s'exécute pas
pthread_create(&t2, NULL, tache, NULL);
pthread_join(t2, NULL);

// ✓ BON : vrai parallélisme
pthread_create(&t1, NULL, tache, NULL);
pthread_create(&t2, NULL, tache, NULL);
pthread_join(t1, NULL);   // Attend les deux en parallèle
pthread_join(t2, NULL);

Dans la première approche, t2 n’est créé que quand t1 se termine, donc pas d’exécution parallèle. Dans la deuxième, les deux threads s’exécutent simultanément sur une machine multi-cœur, puis le main attend les deux avant de terminer.

Race condition

Une race condition est un bug de concurrence qui survient lorsque plusieurs threads (ou processus) accèdent simultanément à une ressource partagée, et que le résultat dépend de l’ordre d’exécution non déterministe de ces threads. Ci-dessous en exemple typique. Si la fonction incrementer est executer par plusieurs threads, en meme temps, l’ordre d’éxecution n’est pas garanti, au contraire, ils peuvent etre entrelacer.

#include <thread>
#include <iostream>

int compteur = 0;

void incrementer() {
    // correspond explicitment a compteur++ en asm
    int tmp = compteur;   // LOAD
    tmp = tmp + 1;        // ADD
    compteur = tmp;       // STORE
}

L’ordonnanceur du système d’exploitation (scheduler) peut interrompre un thread à n’importe quel moment, même au milieu d’une instruction logique en langage de haut niveau. Ce context switch survient généralement quand :

1. Quantum épuisé : chaque thread reçoit une tranche de temps (quantum, 10~40ms). À l’expiration, le scheduler l’interrompt.
2. Priorité plus élevée : un thread de priorité supérieure devient prêt à s’exécuter.
3. Attente d’une ressource : le thread appelle sleep(), attend un I/O, ou attend un verrou.

Notez egalement que LOAD et STORE peuvent egalement etre decomposer en plusieurs instructions en fonction du materiel, de l’allignement memoire et de la quantiter dínformation manipuler. Voir plus complexe dans certains cas plus exotique.

Mauvaise solution

Beaucoup de programmeurs débutants pensent qu’une simple variable booléenne suffit à protéger une ressource partagée. C’est faux : cela crée une race condition, un bug subtil où deux threads peuvent entrer en même temps dans une section critique, car les accès mémoires ne sont pas atomiques. (Cela dit des mecanisme similaire pourrait etre mis en place telque https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange.html)

Voici un exemple typique :

bool lock = false;
int compteur = 0;

void* incrementer(void* arg) {
    for (int i = 0; i < 1000000; i++) {
        while (lock) ;     // Attendre que le verrou se libère (spinlock mal implémenté)
        lock = true;       // Prendre le verrou (NON ATOMIQUE)
        compteur++;        // Section critique
        lock = false;      // Libérer le verrou
    }
    return NULL;
}

À première vue, cela semble fonctionner. Mais la lecture et l’écriture de lock (et de compteur) ne sont pas atomiques. Rien ne garantit que deux threads ne feront pas :

1. while(lock) → lisent false
2. lock = true → presque simultanément
3. entrent tous deux dans la zone protégée

Même compteur++ n’est pas atomique. Elle se décompose en plusieurs instructions, comme vue plus haut :

mov eax, [compteur_global]    ; LOAD : lecture en mémoire
add eax, 1                    ; ADD  : incrémentation
mov [compteur_global], eax    ; STORE : écriture en mémoire

Deux threads exécutant ce trio d’instructions en parallèle peuvent provoquer :

• lecture de la même valeur,
• calcul de la même valeur,
• écriture de la même valeur,
• resultant en une incrémentation perdue ou pire.

Synchronisation avec mutex

Un mutex (MUTual EXclusion) est une primitive du noyau qui fournit une exclusion mutuelle garantie au niveau système et matériel. Contrairement aux variables booléennes, les opérations sur un mutex utilisent des instructions CPU spéciales (comme compare-and-swap ou test-and-set) qui sont indivisibles.

Quand un thread tente de verrouiller un mutex déjà verrouillé, le noyau le place dans une file d’attente et le met en sommeil (sans consommer CPU). Quand le mutex se libère, le noyau réveille automatiquement le thread suivant dans la file. (Cela prend un peu de temps, mais pas le choix).

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t verrou = PTHREAD_MUTEX_INITIALIZER;
int compteur = 0;

void* incrementer(void* arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&verrou);      // Verrouiller (bloque si nécessaire)
        compteur++;                        // Section critique garantie
        pthread_mutex_unlock(&verrou);    // Déverrouiller
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;

    // Initialisation (déjà faite avec PTHREAD_MUTEX_INITIALIZER)
    // Ou: pthread_mutex_init(&verrou, NULL);

    pthread_create(&t1, NULL, incrementer, NULL);
    pthread_create(&t2, NULL, incrementer, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("Compteur = %d (maintenant toujours 2000000) ✓\n", compteur);

    // Destruction
    pthread_mutex_destroy(&verrou);
    return 0;
}

Compilez et testez :

gcc -o test test.c -lpthread -Wall
./test

1. Atomicité garantie : l’opération est indivisible, aucune fenêtre de race possible
2. Efficacité : le noyau endort les threads bloqués au lieu de faire du busy-waiting (consommation CPU)
3. Ordre juste : si plusieurs threads attendent le même mutex, le noyau les réveille dans un ordre équitable

Bonnes pratiques avec les mutex

// Bien: section critique courte
void* tache(void* arg) {
    pthread_mutex_lock(&verrou);
    x++;
    pthread_mutex_unlock(&verrou);
}

// Mauvais: section critique longue, verrouille trop longtemps, tous le monde risque d'attendre 5 second
void* tache(void* arg) {
    pthread_mutex_lock(&verrou);
    sleep(5);   // Les autres threads attendent aussi 5 secondes !
    x++;
    pthread_mutex_unlock(&verrou);
}

//  Danger: oubli de déverrouillage (fuite de ressource) et dead lock au prochain appel
void* tache(void* arg) {
    pthread_mutex_lock(&verrou);
    if (x > 0)
        return;  // Oublie de déverrouiller, deadlock pour tous les autres threads
    x++;
    pthread_mutex_unlock(&verrou);
}

// Meilleur: structure cohérente avec cleanup
void* tache(void* arg) {
    pthread_mutex_lock(&verrou);
    // Utiliser des variables locales, pas de return prématurée
    int resultat = faire_travail_critique();
    pthread_mutex_unlock(&verrou);
    return NULL;
}

Spinlock

L’utilisation de mutex est la méthode la plus standard. Mais dans certaines applications critiques d’un point de vue performance, ces derniers peuvent introduire une latence non négligeable due aux changements de contexte et à la mise en veille des threads. C’est à dire que le thread n’est pas éxécuté (pas de quantum cpu) donc pas de ressources consommés. Il existe alors une autre possibilité : les spinlocks.

Contrairement aux mutex, un spinlock ne met pas le thread en attente passive lorsqu’il ne peut pas acquérir le verrou. Le thread entre à la place dans une boucle active (busy waiting) et vérifie en continu si le verrou devient disponible (pour faire simple c’est “équivalent” à while (mutex_trylock(&m) != 0) {}, mais repose sur des opérations plu optimisée). Cette approche permet d’éviter les coûts liés au changement de contexte et peut être plus efficace lorsque la section critique est très courte et que le temps d’attente est faible. Tient c’est notre cas ici ! En revanche, les spinlocks consomment du temps CPU pendant la phase d’attente et sont donc inadaptés aux sections critiques longues ou aux systèmes fortement chargés (coeur à 100%).

Dans le cadre de ce cours, on considérera les spinlocks comme un cas particulier de mutex, orienté performance.

RW lock

Les mutex peuvent être trop restrictifs pour certains cas d’usage. Dans le cas d’un cache de données, les opérations de lecture sont très fréquentes (environ 90 % des accès) et peuvent s’exécuter en parallèle sans danger, tandis que les écritures, beaucoup plus rares (environ 10 %), nécessitent une exclusivité stricte. Avec un mutex classique, même les lectures se bloquent mutuellement, ce qui empêche un parallélisme pourtant sûr et dégrade les performances.

Pour répondre à ce problème, on utilise des verrous lecteur-écrivain (read-write locks). Ils permettent plusieurs lecteurs simultanés tant qu’aucun écrivain n’est actif, tout en garantissant qu’un seul écrivain peut accéder à la ressource à la fois, bloquant alors lecteurs et autres écrivains. Des mécanismes internes assurent ainsi que toutes les lectures et écritures sont correctement synchronisées et cohérentes.

Dans le cadre de ce cours, on considérera les rw-locks comme un cas particulier de mutex, également orienté performance. Cést par contre bon a savoir ;)

Deadlock (interblocage)

Un deadlock survient quand deux ou plusieurs threads attendent mutuellement une ressource que l’autre détient, créant une situation d’impasse irrésoluble.

// Deadlock : T1 attend verrou B, T2 attend verrou A
pthread_mutex_t verrou_a, verrou_b;

void* t1_func(void* arg) {
    pthread_mutex_lock(&verrou_a);
    pthread_mutex_lock(&verrou_b);  // Attendre verrou_b
    // ...
    pthread_mutex_unlock(&verrou_b);
    pthread_mutex_unlock(&verrou_a);
}

void* t2_func(void* arg) {
    pthread_mutex_lock(&verrou_b);  // Obtient verrou_b d'abord
    pthread_mutex_lock(&verrou_a);  // Attend verrou_a (détenu par T1)
    // Jamais atteint: T1 attend verrou_b que T2 détient
    pthread_mutex_unlock(&verrou_a);
    pthread_mutex_unlock(&verrou_b);
}

// Solution : toujours acquérir les verrous dans le même ordre
void* t2_func_correct(void* arg) {
    pthread_mutex_lock(&verrou_a);  // Même ordre que t1_func
    pthread_mutex_lock(&verrou_b);
    // ...
    pthread_mutex_unlock(&verrou_b);
    pthread_mutex_unlock(&verrou_a);
}

Sémaphores

Un sémaphore est un compteur entier non-négatif, synchronisé par le noyau, qui contrôle l’accès à une ressource partagée pour un nombre arbitraire de threads. À la différence du mutex (binaire : verrouillé/déverrouillé), un sémaphore peut autoriser plusieurs accès simultanés si sa valeur est supérieure à 1.

• sem_wait() : décrémente le compteur. Si la valeur est 0, le thread se bloque jusqu’a avoir un jeton de disponible.
• sem_post() : incrémente le compteur et réveille un thread bloqué (si il y en a un).

Sémaphore binaire

Un sémaphore binaire est un mécanisme de synchronisation dont la valeur ne peut prendre que deux états (0 ou 1). Il est utilisé pour contrôler l’accès à une ressource partagée en autorisant ou bloquant l’exécution d’un thread selon la disponibilité de cette ressource. Historiquement, le sémaphore binaire a été l’un des premiers outils pour résoudre les problèmes de concurrence et peut, en pratique, jouer un rôle similaire à celui d’un verrou d’exclusion mutuelle. Conceptuelement c’est identique a un mutex, c’est donc un point d’entré intéréssant pour leurs introductions.

Cependant, dans la plupart des cas modernes, il est recommandé d’utiliser un mutex plutôt qu’un sémaphore binaire du point de vue des performances et de la sémantique. Les mutex sont conçus spécifiquement pour l’exclusion mutuelle : ils offrent des garanties plus fortes (propriété du verrou, détection d’erreurs, priorité d’ordonnancement) et s’intègrent mieux aux optimisations du système d’exploitation, ce qui les rend généralement plus efficaces et plus sûrs pour protéger des sections critiques.

Exemple d’utilisation :

#include <semaphore.h>
#include <pthread.h>
#include <stdio.h>

sem_t verrou;
int compteur = 0;

void* incrementer(void* arg) {
    for (int i = 0; i < 1000000; i++) {
        sem_wait(&verrou);    // Décrémente, bloque si valeur = 0 "meme" comportement a pthread_mutex_lock
        compteur++;
        sem_post(&verrou);    // Incrémente, réveille un thread bloqué  "meme" comportement a pthread_mutex_unlock
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;

    sem_init(&verrou, 0, 1);  // Initialiser avec valeur 1
    // (ici le 0 = partagé entre threads du même processus)

    pthread_create(&t1, NULL, incrementer, NULL);
    pthread_create(&t2, NULL, incrementer, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    printf("Compteur = %d ✓\n", compteur);

    sem_destroy(&verrou);
    return 0;
}

Sémaphore comptant

Un sémaphore comptant est un mécanisme de synchronisation dont la valeur est un entier supérieur ou égal à zéro, représentant le nombre de ressources identiques disponibles. Contrairement au sémaphore binaire ou au mutex, il permet à plusieurs threads d’entrer simultanément dans une section critique, tant que le compteur reste strictement positif. Chaque thread doit acquérir un « jeton » avant d’accéder à la ressource, et potentielement le rendre une fois son travail terminé.

Ce type de sémaphore est particulièrement adapté pour gérer des pools de ressources (connexions réseau, buffers, threads travailleurs, accès limités à un périphérique, etc.). Un appel à sem_wait() décrémente le compteur et bloque le thread si aucune ressource n’est disponible, tandis que sem_post() incrémente le compteur et réveille un thread en attente. Le sémaphore comptant garantit ainsi que le nombre maximal d’accès concurrents est respecté, tout en évitant la sur-synchronisation qu’imposerait un mutex exclusif.

• Vous pouvez initialiser le sémaphore avec le nombre de ressources initialement disponibles à l’aide de sem_init.
• Chaque thread peut ensuite consommer autant de jetons qu’il le souhaite en appelant sem_wait, tant que ceux-ci sont disponibles ; dans le cas contraire, le thread est mis en attente jusqu’à ce qu’un jeton soit libéré.
• Réciproquement, un thread peut générer autant de jetons qu’il le souhaite via sem_post, afin de signaler la libération ou la création de nouvelles ressources.
• Il n’existe pas de restriction stricte sur la quantité maximale du compteur du sémaphore (en dehors des limites imposées par l’implémentation), ce qui en fait un outil flexible pour modéliser et réguler l’accès à un ensemble de ressources partagées.

La suite au TP, voir MPMC !

Compilation et débogage

Compilez vos programmes Pthreads avec le flag -lpthread :

gcc -o prog prog.c -lpthread -Wall
./prog

Pour déboguer les race conditions (difficiles à reproduire en environnement normal), utilisez ThreadSanitizer de GCC/Clang :

gcc -o prog prog.c -lpthread -fsanitize=thread -g
./prog

ThreadSanitizer détectera les accès concurrents non-protégés et affichera des rapports détaillés.