Threads

Qu'est ce que c'est ?

Jusqu'à présent, le programme était séquentiel (bon avec raylib c'était faux mais vous ne le saviez pas !).

Avec des threads, on est plusieurs à calculer. Chaque personne est un thread, par exemple, l'un est le thread principal et un thread secondaire que l'on a créé :

Le tas est partagé par tous les threads. Mais chaque thread possède sa propre pile d'appel, et bien sûr son propre program counter.

Motivation

Pourquoi utiliser plusieurs threads ?

  • Pour accélérer un calcul sur des architectures multi-coeurs
  • Pour lancer un calcul compliqué alors que l'interface graphique fonctionne encore
  • En JAVA, un thread ramasse-miettes, qui nettoie la mémoire (En Python, c'est en discussion https://peps.python.org/pep-0556/)

Librairie POSIX

Depuis C11, la gestion des threads est possible avec la librairie standard. Avant C11, on utilisait toujours des librairies qui dépendait des plates-formes. Là, on va faire comme dans le temps... on va utiliser la librairie de la norme POSIX qui s'appelle pthread. En effet :

  1. au moins on est sûr que ça même avec des anciennes versions de C sous Unix.
  2. La librairie standard n'est pas franchement différente.
  3. pthread est au programme de l'agrégation d'informatique.
#include <pthread.h>

Pour compiler il faut dire au compilateur d'utiliser la librairie pthread :

gcc -lpthread programme.c

Autrement dit, on effectue une liaison statique avec la librarie pthread.

Principe

But

Disons que l'on a une fonction

/**
@brief faire la plonge
**/
void faireLaVaisselle() {
    ...
}

que l'on aimerait déléguer.

Création d'une variante avec pointeurs

/**
@brief faire la plonge
**/
void* faireLaVaissellePourThread() {
    faireLaVaisselle();
    return NULL;
}

En fait, la communication avec l'extérieur (valeur de retour, et arguments) sont des pointeurs sur des données dans le tas.

Création du thread

Pour cela, on écrit :

pthread_t mon_thread;
int ok = pthread_create(&mon_thread, NULL, faireLaVaissellePourThread, NULL);
  • La fonction pthread_create place l'identifiant du thread créé dans mon_thread. C'est pourquoi on passe l'adresse de mon_thread.
  • Le deuxième paramètre est subtil et dans ce cours, on laisse à NULL.
  • Le troisième paramètre est la fonction f que le thread doit exécuter.
  • Le dernier paramètre sont un pointeur sur les paramètres de la fonction f.

Si ok vaut 0, tout s'est bien passé, on a réussi à créer un thread qui fait la vaisselle. Sinon, c'est qu'il n'y a pas assez de ressources, ou autre (voir doc pour la liste de tous les problèmes possibles).

Pendant que notre thread fait la vaisselle, nous, thread principal, on peut faire autre chose, comme passer la serpière.

  • Est-ce que chaque thread a sa pile d'appel ? Oui, encore heureux !

Attendre un thread

int ok = pthread_join(mon_thread, NULL);

ok vaut 0 si tout va bien. Mais autre chose en cas d'erreur :

  • pas de thread qui s'appelle mon_thread (dans le contenu de mon_thread ne désigne pas un thread)
  • le mon_thread a déjà été attendu
  • il y a deadlocks (i.e. les threads sont bloqués... on verra ça plus tard)

Création d'un thread avec un paramètre

Voici une fonction :

/**
@brief ajoute nbCrepes crêpes sur l'assiette.
@param nbCrepes
@param isRhum
*/
void preparerCrepes(int nbCrepes) {
    ...
}

On aimerait maintenant déléguer la tâche

    preparerCrepes(10);

à un autre thread.

Passage des paramètres

Heureusement, la bibliothèque pthread est générique. La fonction de création de threads ne dépend pas du type des paramètres. D'où l'utilisation de void* (pointeur sur n'importe quoi).

On crée une fonction pour la lecture du paramètre :

void* preparerCrepesPourThread(void* p) {
    preparerCrepes(*(int*) p);
    return NULL;
}

Puis :

pthread_t mon_thread;
int *p = malloc(sizeof(int));
if(p == NULL) exit(EXIT_FAILURE);
*p = 10;
int ok = pthread_create(&mon_thread, NULL, (void*) preparerCrepesPourThread, p);
  • Que pensez-vous de la fonction suivante :
void creerThreadCrepes() {
    pthread_t mon_thread;
    int *p = malloc(sizeof(int));
    if(p == NULL) exit(EXIT_FAILURE);
    *p = 10;
    int ok = pthread_create(&mon_thread, NULL, (void*) preparerCrepesPourThread, p);
}

Pourquoi pas... mais le thread courant perd le contrôle sur le thread créé.

  • Que pensez-vous de la fonction suivante :
void creerThreadCrepes(pthread_t* p_mon_thread) {
    int *p = malloc(sizeof(int));
    if(p == NULL) exit(EXIT_FAILURE);
    *p = 10;
    int ok = pthread_create(p_mon_thread, NULL, (void*) preparerCrepesPourThread, p);
}

Ca va (sauf si il y a des choses que je n'ai pas vu !).

  • Que pensez-vous de la fonction suivante :
void creerThreadCrepes(pthread_t* p_mon_thread) {
    int i = 10;
    int ok = pthread_create(p_mon_thread, NULL, (void*) preparerCrepesPourThread, &i);
}
Ce va pas car on donne une adresse de la pile du thread courant comme argument. C'est dangereux car la fonction `jetefaistonthread` et on perd les données, on lit dans une zone non allouée...
  • Que pensez-vous de ce code là ?
for (size_t i = 0; i < NUM_FRIENDS; i++)
    pthread_create(&friends[i], NULL, meetup, &i);
for (size_t j = 0; j < NUM_FRIENDS; j++)
    pthread_join(friends[j], NULL);

Il y a un problème. Non, pas de soucis sur le fait que la valeur soit sur la pile du thread appelant. Le problème est que la valeur est modifiée pour la boucle, donc tous les threads finissent par avoir la valeur NUM_FRIENDS comme paramètre au bout d'un moment.

Création d'un thread avec plusieurs paramètres

Ajoutons du rhum dans l'histoire. Voici une fonction qui prend deux paramètres :

/**
@brief ajoute nbCrepes crêpes sur l'assiette.
On utilise la pâte avec du rhum ssi isRhum est vrai.

@param nbCrepes
@param isRhum
*/
void preparerCrepes(int nbCrepes, bool isRhum) {
    ...
}

On aimerait maintenant déléguer la tâche

    preparerCrepes(10, true);

à un autre thread.

Passage des paramètres

  • Comment pour passer plusieurs arguments à une tâche à sous-traiter à un thread alors que pthread_create ne prend qu'un seul argument pour ces arguments justement ?

C'est un cas typique où on utilise une une struct pour représenter les paramètres. Démonstration !

Premièrement on définit le struct pour grouper les arguments.

/**
* @brief the struct that groups the parameters of preparerCrepes together
*/
struct mon_thread_args
{
   int nbCrepes;
   bool isRhum;
};

Ensuite, on écrit la fonction qui s'occupe de rediriger vers notre fonction existante :

void *preparerCrepesPourThread(void *pointeurArguments)
{
    struct mon_thread_args *p = pointeurArguments;
    preparerCrepes(p->nbCrepes, p->isRhum);
}

Puis on délègue la préparation des crêpes en créant un thread :

pthread_t mon_thread;
struct mon_thread_args *p = malloc(sizeof(*p));
if(p == NULL)
    exit(EXIT_FAILURE);
p->nbCrepes = 12230;
p->isRhum = true;
pthread_create(&mon_thread, NULL, preparerCrepesPourThread, p);

Application : accélérer l'affichage de l'ensemble de Mandelbrot

Problème de l'affichage de l'ensemble de Mandelbrot

On présente ici le problème d'afficher une comme celle-là.

  • Est-ce que vous savez ce que représente cette image ?

Il s'agit de la fractale de Mandelbrot.

La couleur d'un pixel est donnée par :

/**
 * \fn Color computeColor(complex z)
 * \param z a complex
 * \return the color that should be displayed at z
 */
Color computeColor(complex z)
{
    complex u = 0;

    for (int i = 0; i < NBINTER; i++)
    {
        u = u*u + z;
        if (cabs(u) > 2)
            return ColorFromHSV(i * 255 / NBINTER, 1.0, 1.0);
    }
    return BLACK;
}

Un programme mono-thread est lent ; le déplacement et le zoom dans la fractale râme. Pour cela, on se propose deux solutions.

Découpe du problème : fork and join

Voici la première solution. Au lieu de dessiner l'image en entier, on découpe l'image en zone et chaque thread va calculer sa zone.

  • On démarre les calculs des 4 zones
  • Puis on attend que les calculs soient finis

C'est le principe du fork and join.

  • Est-ce que vous voyez des qualités à cette approche ?

Simple à mettre en oeuvre. On ne partage pas de données. Pas besoin de mutex. Pas d'interblocages. Chaque thread travaille sur sa zone.

  • Est-ce que vous voyez un défaut à cette approche ?

Il se peut que la charge de travail ne soit pas bien réparti. Certains threads travaillent longtemps alors que d'autres peuvent partir en vacances très tôt !

File de tâches

On considère un bassin de threads. Chaque thread vient se servir d'une tâche à effectuer dans une file et s'arrête quand la file est vide.

  • Est-ce que vous voyez des qualités à cette approche ?

Jamais un thread ne s'ennuie. On ne part en vacances que s'il y a plus rien à faire.

  • Est-ce que vous voyez un défaut à cette approche ?

Malheureusement, la file est partagée. Il peut y avoir des problèmes de concurrences. Il faut utiliser un mutex, ce que nous allons voir dans la partie suivante.

Canaux

Il existe des architectures de threads qui ressemblent aux pipes. On ne va pas aborder ça ici.

Concurrence

Deux personnes ensemble ne savent pas compter

  • Qu'écrit ce programme ?
#include <stdio.h>
#include <pthread.h>

int x = 0;

void* f(void*) {
    for(int i = 0; i<50000; i++)
        x++;   
}

int main()
{
    pthread_t t1, t2;
    pthread_create(&t1, NULL, f, NULL);
    pthread_create(&t2, NULL, f, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("%d",x);
    return 0;
}

Il écrit assez souvent 100000 mais pas tout le temps, des fois c'est un autre nombre !

  • Est-ce que une valeur inférieure à la valeur attendue ?

Oui, en fait, par exemple t1 lit 10, fait son calcul 11, t2 lit.... 10, t2 fait son calcul 11, t1 écrit 11, t2 aussi...

Solution : les mutex

Un mutex (pour Mutual exclusion, Exclusion mutuelle) est une sorte de loquet/verrou. On déclare un mutex comme ça :

pthread_mutex_t mutex;
pthread_mutex_init(&mutex, NULL);

On donne l'adresse du mutex pour que pthread_mutex_init puisse y inscrire l'ID. Le paramètre NULL c'est pour des choses plus compliquées.

On verouille ou déverouille comme ça :

pthread_mutex_lock(&mutex);
...
pthread_mutex_unlock(&mutex);

Le morceau de programme entre le verrouillage du mutex et son déverouillage s'appelle la section critique.


  • En image pthread_mutex_lock(&m42);, c'est une porte labélisé m42, ouverte par défaut, suivi d'une dalle/bouton qui ferme toutes les portes de type m42.

  • En image, pthread_mutex_unlock(&m42);, est une dalle qui ouvre les portes de type m42.

A la fin, on détruit le mutex :

pthread_mutex_destroy(&mutex);

Exemple

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


pthread_mutex_t mutex;
int x = 0;

void* f(void*) {
    for(int i = 0; i<50000; i++) {
        pthread_mutex_lock(&mutex);
        x++;
        pthread_mutex_unlock(&mutex);
    }
           
}



int main()
{
    pthread_t t1, t2;
    pthread_mutex_init(&mutex, NULL);
    pthread_create(&t1, NULL, f, NULL);
    pthread_create(&t2, NULL, f, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    pthread_mutex_destroy(&mutex);
    printf("%d",x);
    return 0;
}

Deadlocks

Des fois, avec des mutex, on peut arriver à des situations bloquantes. Comme :

Thread 1
lock(mutex)
lock(mutex)
...

ou

Thread 1Thread 2
lock(mutex1)lock(mutex2)
lock(mutex2)lock(mutex1)
......

Exercices

  • Multiplication de matrices
  • Tri fusion et autres
  • FFT

Références

Programmer avec Rust. Jim Blandy et Jason Orendorff. (même si on fait du C et pas du Rust, le principe des threads est bien expliqué dans ce livre, avec l'exemple de la fractale de Mandelbrot et les différentes méthodes)