Exercices sur les structures de données

Exercice 1

On désire réaliser une petite librairie implémentant une file pour des entiers. La taille de la file sera dynamique. Afin de garantir un comportement cohérent et déterministe dans le cas d’une exécution multi-threadée, la file devra être thread-safe. Vous utiliserez les primitives d’exclusion mutuelle appropriées pour cela. L’interface des fonctions à implémenter se présente comme suit :

Décider ce que contiendra la structure queue_t définissant un objet de type file.


Remarque: Penser à insérer des assertions dans le code aux endroits nécessaires.


Exercice 2

On désire modéliser, à l’aide de threads, un “workflow” d’opérations réalisées en cascade sous forme “d’étages”, un petit peu comme ce qui serait réalisé sur une chaîne de montage. Les étages à implémenter sont les suivants:

L’exécution des 5 étages représente un cycle d’exécution. Le programme prendra en argument le nombre de cycle à exécuter. Commencer par réaliser une version séquentielle du programme. Ensuite, implémenter une version multi-threadée dont le but est de diminuer le temps d’exécution du programme.

Le programme multi-threadé prendra un argument supplémentaire: le nombre de threads à utiliser. Pour simplifier, on part du principe que la taille du vecteur de chaque étage est divisible par le nombre de threads. Vous êtes libres d’utiliser les primitives de synchronisation ou d’exclusion mutuelle de votre choix.

Attention à joindre tous les threads créés et détruire toute(s) barrière(s) avant la terminaison du programme. Enfin, afficher le temps obtenu après exécution du programme.


Questions 1

Exécuter le programme avec un nombre différent de threads.

  1. Quel est le gain obtenu pour votre version multi-threadée par rapport à la version séquentielle?
  2. Est-ce que le temps obtenu varie avec le nombre de threads?

Mesures de temps

Les mesures de temps peuvent être effectuées avec la fonction clock_gettime() de la librairie time.h comme montré ci-dessous:

struct timespec start, finish;
clock_gettime(CLOCK_MONOTONIC, &start);

// code à mesurer

clock_gettime(CLOCK_MONOTONIC, &finish);
double seconds_elapsed = finish.tv_sec-start.tv_sec;
seconds_elapsed += (finish.tv_nsec-start.tv_nsec)/1.0e9;

Le code ci-dessus requiert de lier (link) votre exécutable à la librairie rt. Pour ce faire, passer -lrt en dernier argument à gcc au moment de l’édition des liens.


  1. Pour générer les valeurs aléatoires utilisez le générateur réentrant rand_r().↩︎