M4104C-TP-Boost-Exercice1

Groupe de threads et functor

Dans cet exercice, le vector de pointeurs de threads n’est nécessaire que pour permettre au main-thread d’attendre qu’ils soient tous terminés avant de passer à la suite.

Il devient complètement inutile dès lors que les threads créés appartiennent au même groupe. Le main-thread peut alors se contenter d’attendre la fin de tous les threads du groupe.

La plupart des constructeurs de threads ont un paramètre de type Callable, c’est-à-dire pouvant être appelé au moyen de l’opérateur-fonction (). On peut donc utiliser un functor comme paramètre.

Travail à effectuer

Créer le projet GrpThreadsEtFctor. Vous pouvez vous servir de QT comme d’un éditeur de texte intelligent et réaliser les compilations et éditions de liens dans un terminal gnome ou faire tout avec QT. Cependant sachez que QT traite déjà ses propres threads qui seront en concurrence avec les vôtres.
Sachez également que lorsque vous importerez, dans QT, des fichiers dont les noms contiennent des majuscules, QT transformera ces majuscules en minuscules.

Télécharger le fichier Concurrence.cpp qui est le corrigé de l’exercice précédent. Le renommer en GrpThreadsEtFctor.cpp.

Modifier les propriétés du projet (ajout de la ligne
LIBS = /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.62.0 /usr/lib/x86_64-linux-gnu/libboost_system.so.1.62.0
dans le fichier .pro du projet).

Remplacer les fonctions Incr() et Decr() par les functors correspondants.

Supprimer tout ce qui concerne la classe vector, créer un groupe de threads et y ajouter dynamiquement tous les threads.

Compiler et tester.

M4104C-TP-Boost-Exercice2

Dans ce qui suit, il s’agit d’établir un point de synchronisation entre N threads, simulant des activités que nous appellerons des passants.

L’activité de chaque passant (thread) est composée de trois parties :

  1. le traitement T1() à exécuter avant d’atteindre le point de synchronisation,

  2. l’arrivée au point de synchronisation, et l’attente que les N thread aient atteint ce point,

  3. le traitement T2() à exécuter après avoir quitté le point de synchronisation.

Les traitements T1() et T2() seront simplement simulés par des attentes (appels de sleep()).

Travail à effectuer

Créer le projet RDV_NThreadsBoost.

Télécharger les fichiers SleepChronogram.h et SleepChronogram.cpp.

Version a

Dans l’espace de noms anonyme du fichier RDV_NThreadsBoost.cpp, écrire la fonction RendezVous(), de profil

void RendezVous ();

qui est appelée par chaque thread lorsqu’il arrive au point de rendez-vous.

Cette fonction doit utiliser :

  • un compteur de threads encore attendus (variable globale initialisée au nombre total de threads et décrémentée chaque fois qu’un thread arrive au RDV),

  • une variable-condition qui bloque les threads tant que le compteur n’est pas nul et qui libère ensuite tous les threads bloqués (broadcast).

Dans l’espace de noms anonyme du fichier RDV_NThreadsBoost.cpp, écrire la classe (ou la struct) CPassant, qui contient :

  • un identifiant (entier naturel) qui s’incrémente automatiquement à chaque création d’un CPassant (utiliser une variable statique),

  • les caractéristiques de fonctionnement d’un thread : le temps qu’il met à arriver au point de rendez-vous, et le temps qu’il met à se terminer après être reparti du point de rendez-vous.

  • l’operator() qui représente le comportement de chaque passant.

    Le corps de cette fonction est composé de trois parties :

    1. l’arrivée au point de rendez-vous (sleep()),

    2. le blocage au point de rendez-vous (RendezVous()),

    3. le départ du point de rendez-vous(sleep()).

Ajouter un vector de CPassants.

Dans la fonction main(), lire au clavier le nombre de threads à lancer puis, pour chacun, les délais d’arrivée et de départ (on entrera ces données dans un fichier texte qui sera redirigé sur l’entrée standard du programme).

Ces délais sont placés dans une instance de CPassant, qui est ensuite rangée dans le vector.

Affichage : afin de suivre le chronogramme du déroulement des opérations, nous vous proposons ici d’utiliser une visualisation plus agréable que de faire afficher des tops d’horloge : à chaque seconde, chaque thread affiche son état (une lettre par exemple) sur une ligne qui lui est propre : le thread 1 progresse sur la ligne 1, le thread 2 progresse sur la ligne 2, etc.

Il n’affiche rien lorsqu’il est bloqué (sur un sémaphore, dans une variable condition, etc.)

En utilisant le fichier de données
StdIn
suivant qui contient :

3
3 5
4 6
5 2

redirigé sur l’entrée standard de l’exécutable RDV_NThreadsBoost qui est mis à votre
disposition et que vous devez
télécharger
(mais cela ne fonctionne pas), vous obtiendrez les chronogrammes suivants (à deux instants différents) :

AAA
AAAA
AAAA

Trois passants (threads) ont été lancés en même temps.

Le symbole 'A' est affiché à chaque seconde pendant que le thread Arrive vers le point de rendez-vous.

On voit que le thread 1 est bloqué alors que les deux autres ont continué à progresser pendant 1 seconde.

AAADDDDD
AAAADDDDD
AAAAADDX

On voit sur ce chronogramme que les trois threads sont repartis lorsque le troisième est arrivé au rendez-vous (au bout de 5 secondes).

Chacun a alors repris son exécution normale (Départ).

Le troisième s’est terminé au bout de 2 secondes (X), les autres continuent depuis 4 secondes.

Pour obtenir ces affichages, vous devez utiliser la NTCTS clrscr, la classe gotoxy et la fonction SleepChronogram(), toutes trois décrites dans le fichier SleepChronogram.h.

Version b

Modifier la fonction RendezVous() pour effectuer un réveil en cascade.

Version c

La bibliothèque Boost offre la fonction barrier qui permet de réaliser très simplement un rendez-vous de N threads !

La mettre en oeuvre.

M4104C-TP-Boost-Exercice3

Il s’agit de simuler par des threads des activités parallèles, que nous appellerons des baigneurs.

L’activité de chaque baigneur (thread) est constituée de différentes phases :

  1. le traitement initial effectué avant l’arrivée à la piscine, qui sera symbolisé par la lettre A (Arriver),

  2. le déshabillage, qui sera symbolisé par la lettre D,

  3. la baignade, qui sera symbolisé par la lettre B,

  4. le rhabillage, qui sera symbolisé par la lettre R,

  5. le traitement final effectué après le départ de la piscine, qui sera symbolisé par la lettre Q, (Quitter).

Chacun de ces cinq traitements sera simulé par un appel à la fonction sleep(), d’une durée différente pour chaque baigneur.

Ressources critiques : certaines phases de ces activités mettent en jeu des ressources critiques, pour lesquelles les threads entrent en compétitions :

  • la piscine dispose d’un certain nombre NbPaniers de paniers dans lesquels les baigneurs laissent leurs habits pendant le temps de la baignade,

  • chaque baigneur se déshabille et se rhabille dans une cabine individuelle.

    La piscine dispose d’un nombre NbCabines de cabines.

Les phases de déshabillage et de rhabillage ne peuvent commencer que si certaines conditions sont réalisées :

  • chaque baigneur doit disposer d’un panier et d’une cabine pour commencer à se déshabiller,

  • chaque baigneur ne doit disposer que d’une cabine pour commencer à se rhabiller.

Ces deux conditions sont donc éventuellement bloquantes.

Les fins des phases de déshabillage et de rhabillage ne sont pas bloquantes mais correspondent à la libération de ressources critiques :

  • chaque baigneur rend sa cabine quand il a fini de se déshabiller,

  • chaque baigneur rend sa cabine et son panier quand il a fini de se rhabiller.

Ces ressources critiques seront gérées au moyen de variable(s)-condition.

Travail à effectuer

Créer le projet PiscineThreadsBoost.

Télécharger les fichiers /tpAA-COO/usingthreads/usingthreads/RDV_NThreadsBoost/SleepChronogram.cpp”>SleepChronogram.cpp.

Dans l’espace de noms anonyme du fichier PiscineThreads.cpp, écrire les quatre fonctions de synchronisation DebutDeshabiller(), FinDeshabiller(), DebutRhabiller(), FinRhabiller(), de profils :

void DebutDeshabiller (void);
void FinDeshabiller   (void);
void DebutRhabiller   (void);
void FinRhabiller     (void);

Ces fonctions doivent utiliser :

  • deux compteurs NbPaniers et NbCabines, variables globales initialisées en début de programme et indiquant à l’instant t le nombre de ressources correspondantes encore disponibles,

  • une variable-condition qui bloque le thread si la ou les ressources dont il a besoin ne sont pas disponibles, et qui réveille les threads bloqués s’il rend une ou plusieurs ressources.

Dans l’espace de noms anonyme, écrire la classe (ou la struct) CBaigneur qui contient :

  • un identifiant (entier naturel) qui s’incrémente automatiquement à chaque création d’un CBaigneur (utiliser une variable statique),

  • les caractéristiques de fonctionnement d’un thread : le temps qu’il met à arriver à la piscine, le temps du déshabillage, le temps de la baignade, le temps du rhabillage, le temps qu’il met à se terminer après être reparti de la piscine,

  • l’operator() qui représente le comportement de chaque baigneur.

    Le corps de cette fonction est composé de cinq parties :

    1. l’arrivée à la piscine (sleep()),

    2. le déshabillage

      DebutDeshabiller()

      sleep()

      FinDeshabiller()

    3. la baignade (sleep()),

    4. le rhabillage,

      DebutRhabiller()

      sleep()

      FinRhabiller()

    5. le départ de la piscine (sleep()),

Ajouter un vector de CBaigneurs.

Dans la fonction main(), lire au clavier :

  • le nombre NbPaniers de paniers disponibles,

  • le nombre NbCabines de cabines disponibles (NbCabines < NbPaniers),

  • le nombre de baigneurs (threads) à lancer,

  • pour chaque baigneur, les 5 délais de son activité (on entrera ces données dans un fichier texte qui sera redirigé sur l’entrée standard du programme).

    Ces délais sont placés dans une instance de CBaigneur, qui est ensuite rangée dans le vector.

Comme dans l’exercice “Rendez-vous entre N threads“, l’affichage pourra être réalisé de façon agréable au moyen des outils mis à votre disposition dans les fichiers SleepChronogram.h et SleepChronogram.cpp.

Vous pouvez de nouveau /tpAA-COO/usingthreads/usingthreads/PiscineThreadsBoost/PiscineThreadsBoost.a”>-->télécharger et tester l’exécutable PiscineThreadsBoost qui est mis à votre disposition (mais qui ne se télécharge pas.

M4104C-TP-Boost-Exercice4

L’intérêt du parallélisme est double :

  • profiter de la puissance de traitement des machines multi-processeurs,

  • confier à chaque thread une activité spécifique beaucoup plus facile à concevoir et maintenir qu’au sein d’un gros programme.

Rappel : le nombre de combinaisons de N objets (N > 0) pris p à p (p <= N), noté C (N, p), est défini par :

C (N, p) = N si p = 1
C (N, p) = 1 si p = N

C (N, p) = C (N-1, p-1) + C (N-1, p) dans les autres cas

Il peut être calculé récursivement par :

unsigned CNp (unsigned N, unsigned p)
{
    return (N == p) ? 1 : (p == 1) ? N : CNp (N-1, p-1) + CNp (N-1, p);

} // CNp() 

// programme appelant :
...
Result = CNp (NbTot, Nb);
...

Il vous est demandé de remplacer chaque appel de la fonction récursive CNp() par la création d’un thread qui calcule la valeur correspondante.

A son tour, chaque thread lance 2 threads dont il attend le résultat (ou aucun) avant de se terminer lui-même.

Le main_thread lance un thread avec les valeurs initiales N et p et attend sa fin.

Travail à effectuer

Créer le projet CNpThreadsBoostV1.

Dans l’espace de noms anonyme du fichier CNpThreadsBoostV1.cpp, écrire la fonction thread CNp() qui effectue le calcul C(N, p), selon cette méthode.

N et p lui sont passés en paramètre(s).

En principe, elle devrait renvoyer le résultat, mais une fonction-thread ne renvoie pas de résultat (void).

Il ne reste plus qu’à en faire une procédure (utiliser un paramètre-résultat supplémentaire !).

Attention et rappel : les paramètres d’une fonction-thread sont toujours passés par valeur …

Pour créer un thread on utilisera la fonction bind(), de la bibliothèque functional,
qui renvoie un callable, qui lie son premier paramètre (une fonction), avec tous les autres paramètres de
bind() qui sont, dans l’ordre, les paramètres de la fonction premier paramètre de bind.

Exemple :

void f (int P1, char P2, int * P3);
int Val;
bind (f, 12, 'c', & Val) // est un callable

Ecrire la fonction main() qui amorce le calcul réparti, en utilisant les valeurs N et p passées en arguments de la commande (à vérifier), et qui affiche le résultat.

M4104C-TP-Boost-Exercice5

Remarque préliminaire : cet exercice ne peut être effectué qu’après l’exercice Application répartie entre threads – Partie I.

La solution de l’exercice ci-dessus présente deux inconvénients majeurs liés :

  1. l’arborescence des appels de CNp() présente de très nombreux noeuds identiques, comme le montre l’exemple C(5,3) ci-dessous :




    Figure 1

  2. puisque chaque noeud correspond à la création d’un thread, et puisque leur nombre est limité, il est probable que le nombre maximal soit très vite atteint.

L’exercice proposé ici consiste à ne lancer un thread que si la combinaison correspondante n’a pas été déja calculée, ou si elle n’est pas en cours de calcul.

Cette technique est connue en informatique sous le nom de .

Pour cela, on utilise une matrice à deux dimensions, Combin qui mémorise les valeurs de C(i, j) avec 1 <= i <= N, et 1 <= j <= p.

Celle-ci est supposée déclarée au début de l’espace de noms, à des dimensions suffisantes.

Conventionnellement, on utilisera les valeurs suivantes :

Combin [i][j] = -1        : C(i, j) non calculée
Combin [i][j] =  0        : C(i, j) en cours de calcul
Combin [i][j] =  x > 0    : C(i, j) déjà calculée

Pour simplifier le traitement, Combin[i][j] correspond à C(i, j).

Pour cela, une ligne correspondant à i = 0 et une colonne correspondant à j = 0 ont été ajoutées au tableau.

Avant le début du calcul, la matrice Combin doit être initialisée.

Pour N = 5 et p = 3 par exemple, elle prend les valeurs suivantes :


Vous remarquez que certaines valeurs initiales découlent immédiatement de la définition et n’ont pas besoin d’être calculées pour être connues : les C(i, i) et C(N, 1).

Elles ont donc été directement placées dans la matrice.

La figure suivante représente le contenu de la matrice Combin après la fin du calcul de C(5, 3).


Travail à effectuer

Créer le projet CNpThreadsBoostV2.

Télécharger le fichier

M4104C-TP-Boost-Exercice6

Exercice donné en test le 06/04/2007

Dans le cours magistral, une implémentation de Boîte Aux Lettres (BAL) a été donnée en utilisant un mutex et une variable condition.

Il a été montré que cette version est fausse ou lourde en présence de plusieurs producteurs et/ou consommateurs.

Une solution consiste à avoir deux files d’attente (= deux variables condition) : l’une pour les consommateurs, l’autre pour les producteurs, et à réveiller sélectivement le thread adéquat.

Travail à effectuer

Créez le projet BALMultiThreadsBoost.

Pour la fin de l’exercice, vous aurez besoin de la fonction Rand().

Modifiez le fichier .pro du projet en conséquence.

Implémentez sur le principe indiqué plus haut la classe C_BALGen d’une boîte aux lettres générique (le “type” de la lettre), ayant pour interface un constructeur, un destructeur, et les deux primitives :

        void Deposer (const T & Val);
        T Retirer (void);

Testez en créant plusieurs producteurs et plusieurs consommateurs qui appellent les fonctions Deposer() et Retirer() avec des périodicités choisies ou aléatoires.

Les affichages doivent faire apparaître quel est le thread qui effectue l’action et quel est le contenu déposé ou retiré de la boîte.

Après quelques essais, vous constaterez sans doute quelques anomalies d’affichage.

Avant de lire la remarque ci-dessous, essayez de les expliquer et reportez-vous à la première partie de l’exécution commentée (plus bas).

Remarque

Les éditions ayant parfois tendance à s’inverser (malgré une exclusion mutuelle), il est intéressant d’ajouter aux opérations un estampillage : le “temps-systeme” doit être récupéré au moment où les opérations de retrait et de dépôt sont effectuées.

Pour cela, vous pouvez récupérer le temps système au moment où les opérations sont effectuées : la fonction de Boost <-- get_system_time() renvoie le temps système de type <-- system_time affichable par l’opérateur d’injection.

Il suffit d’ajouter (provisoirement) un paramètre de ce type aux fonctions Deposer() et Retirer(), et de faire afficher les temps correspondants par chaque producteur/consommateur.

Les affichages 2 et 3 présentés à la suite du paragraphe “Exécution” illustrent ce qu’on appelle la technique d’estampillage.

Exécution

La première ligne correspond à une suite de “mots” lus successivement au clavier.

Le reste du déroulement de programme peut se traduire par la trace suivante :

a z e r t y u i
Prod. 2 a déposé : z Cons. 1 a retiré : z Prod. 1 a déposé : a Cons. 2 a retiré : a
Prod. 2 a déposé : r Cons. 3 a retiré : r Prod. 1 a déposé : e
Cons. 3 a retiré : e Cons. 2 a retiré : t
Prod. 2 a déposé : t Cons. 1 a retiré : y Prod. 1 a déposé : y Cons. 2 a retiré : u
Prod. 2 a déposé : u Prod. 1 a déposé : i
Cons. 3 a retiré : i

Une première anomalie apparaît (cadre rouge) : il semble que deux consommateurs puissent prélever successivement, alors qu’aucun nouveau producteur n’ait produit !

Elle est cependant facile à expliquer : on peut vérifier que les deux consommateurs ne consomment pas la même information.

C’est donc qu’un producteur s’est intercalé entre les deux, mais ce sont les accès en exclusion mutuelle à l’écran qui a inversé les événements.

Une deuxième anomalie apparaît (cadre noir) : les lettres 'a' et 'z', semblent prélevées en ordre inverse de leur apparition dans le flux d’entrée !

Cela se reproduit aussi pour les lettres 'r' et 'e'

En fait, le 'a' a obligatoirement été lu avant le 'z' (cin est un conteneur à accès séquentiel).

Mais le premier thread producteur qui a lu 'a' n’a pas eu le temps de le déposer : le second threadproducteur a lu à son tour 'z' et l’a déposé le premier.

Le premier thread consommateur a donc lu 'z' dans la BAL, etc.

Après ajout de l’estampillage

a z e r t y u i
2008-Nov-19 12:12:51.187172 : Prod. 2 a déposé : z
2008-Nov-19 12:12:51.187547 : Cons. 1 a retiré : z
2008-Nov-19 12:12:52.187153 : Prod. 1 a déposé : a
2008-Nov-19 12:12:52.187329 : Cons. 2 a retiré : a
2008-Nov-19 12:12:55.187577 : Prod. 2 a déposé : r
2008-Nov-19 12:12:55.187752 : Cons. 3 a retiré : r
2008-Nov-19 12:12:57.187359 : Prod. 1 a déposé : e
2008-Nov-19 12:12:59.187873 : Cons. 3 a retiré : e
2008-Nov-19 12:13:03.187792 : Cons. 2 a retiré : t
2008-Nov-19 12:13:03.187782 : Prod. 2 a déposé : t
2008-Nov-19 12:13:04.187567 : Cons. 1 a retiré : y
2008-Nov-19 12:13:04.187556 : Prod. 1 a déposé : y
2008-Nov-19 12:13:08.188564 : Cons. 2 a retiré : u
2008-Nov-19 12:13:08.188553 : Prod. 2 a déposé : u
2008-Nov-19 12:13:11.187859 : Prod. 1 a déposé : i
2008-Nov-19 12:13:11.187991 : Cons. 3 a retiré : i

Remarque : en fait, c’est le premier affichage plus haut qui a été obtenu en supprimant l’estampillage !!!

En effet, rien ne prouve que les messages apparaîtraient dans le même ordre lors d’une seconde exécution !

Après remise en ordre chronologique des messages, les deux dernières anomalies disparaissent et li ne reste que l’inversion des deux premiers caractères, qui ne dépendent pas de la boîte aux lettres mais de l’accès à l’écran.

a z e r t y u i
2008-Nov-19 12:12:51.187172 : Prod. 2 a déposé : z
2008-Nov-19 12:12:51.187547 : Cons. 1 a retiré : z
2008-Nov-19 12:12:52.187153 : Prod. 1 a déposé : a
2008-Nov-19 12:12:52.187329 : Cons. 2 a retiré : a
2008-Nov-19 12:12:55.187577 : Prod. 2 a déposé : r
2008-Nov-19 12:12:55.187752 : Cons. 3 a retiré : r
2008-Nov-19 12:12:57.187359 : Prod. 1 a déposé : e
2008-Nov-19 12:12:59.187873 : Cons. 3 a retiré : e

2008-Nov-19 12:13:03.187782 : Prod. 2 a déposé : t
2008-Nov-19 12:13:03.187792 : Cons. 2 a retiré : t
2008-Nov-19 12:13:04.187556 : Prod. 1 a déposé : y
2008-Nov-19 12:13:04.187567 : Cons. 1 a retiré : y
2008-Nov-19 12:13:08.188553 : Prod. 2 a déposé : u
2008-Nov-19 12:13:08.188564 : Cons. 2 a retiré : u

2008-Nov-19 12:13:11.187859 : Prod. 1 a déposé : i
2008-Nov-19 12:13:11.187991 : Cons. 3 a retiré : i

M4104C-TP-Boost-Exercice7

Exercice donné en test le 06/04/2007

Remarque préliminaire :

cet exercice utilise les résultats de l’exercice BAL multi-producteurs/multi-consommateurs.

Il ne peut donc être effectué qu’après ce dernier.

Il est assez facile d’écrire un itérateur sur un conteneur “linéaire” comme un vector ou une liste chaînée par exemple.

Il suffit en effet de mémoriser dans cet itérateur un pointeur sur l’élément courant.

Le passage à l’élément suivant est obtenu en incrémentant ce pointeur d’une unité pour un vector, ou en appelant la fonction GetSuivant() de l’élément courant de la liste.

C’est beaucoup plus délicat de proposer un itérateur sur un arbre.

En effet, il ne suffit pas de garder un pointeur sur un nœud de l’arbre pour pouvoir passer au suivant : il faut aussi garder tout le chemin parcouru depuis la racine, afin de pouvoir éventuellement remonter dans l’arbre pour en explorer une nouvelle branche, ou de revenir au cœur des appels récursifs pour continuer le parcours, ce qui est totalement impossible.

Les threads offrent une alternative très élégante à ce problème.

Le principe

Un thread parcourt récursivement tous les nœuds de l’arbre (parcours infixé par exemple).

Le traitement du nœud courant consiste à déposer un pointeur sur ce nœud dans une BAL qui, par définition, est bloquante tant que l’information n’a pas été retirée par un consommateur.

Lorsque l’arbre est entièrement parcouru, le thread dépose un pointeur nul dans la BAL.

Un second thread retire successivement de la BAL chaque nœud, qu’il traite, jusqu’à trouver un pointeur de nœud invalide.

L’existant

Pour simplifier, nous travaillerons sur un arbre de recherche d’entiers, déclaré ainsi :

    class CNode;
    typedef CNode * PNode_t;

    class CNode
    {
        int     m_Val;
        PNode_t m_fg;
        PNode_t m_fd;

      public :
        PNode_t GetGauche (void)       const { return m_fg; }
        PNode_t GetDroit  (void)       const { return m_fd; }
        void    SetGauche (PNode_t fg)       { m_fg = fg;   }
        void    SetDroit  (PNode_t fd)       { m_fd = fd;   }

        CNode (int Val, PNode_t fg = 0, PNode_t fd = 0)
            : m_Val (Val), m_fg (fg), m_fd (fd) {}

        int GetVal (void) const { return m_Val; }

    }; // CNode

La classe CSearchTree encapsule la structure arborescente :

    class CSearchTree
    {
        PNode_t m_Racine;

        PNode_t AddNode (int Val, PNode_t Racine);

      public :
        CSearchTree (void) : m_Racine (0) {}
        void AddNode (int Val);

    }; // CSearchTree

La fonction publique non récursive AddNode() appelle la fonction privée récursive AddNode() qui ajoute dans l’arbre la valeur passée en paramètre.

De plus, nous disposons de la classe générique C_BALGen suivante :

    template <typename T>
    class C_BALGen
    {
        // ...
      public :
         C_BALGen (void);
        ~C_BALGen (void);

        void Deposer (const T & Val);
        T    Retirer (void);

    }; // C_BALGen

Classe CIterTree

L’interface (partie visible) de la classe CIterTree est la suivante :

    class CIterTree
    {
        // ...

      public :
        CIterTree (CSearchTree & Arbre);

        PNode_t GetNext (void);

    }; // CIterTree

Un itérateur CIterTree comporte aussi (données membres):

  • une BAL qui servira à communiquer les pointeurs des différents noeuds rencontrés,

  • une association à l’arbre qu’il doit parcourir (reçu à la construction).

L’utilisateur n’a plus qu’à appeler la fonction GetNext() pour obtenir un pointeur vers le nœud courant (avec passage au nœud suivant).

La fonction GetNext() renvoie un pointeur nul lorsque tout l’arbre a été exploré.

Voici un exemple d’utilisation par un thread utilisateur :

void ThreadUser (void)
{
    // ...
    CSearchTree Arbre;

    // Remplissage de l'arbre

    CIterTree Iter (Arbre);

    for (PNode_t Ptr; (Ptr = Iter.GetNext()); )
    {
        cout << "Valeur lue : " << Ptr->GetVal() << '\n';
        this_thread::sleep (seconds (1));
    }
    // ...

} // ThreadUser()

La classe CIterTree a deux fonctions membres privées :

void Parcours (PNode_t Racine);
void Parcours ();

La première, récursive, parcourt dans l’ordre infixé l’arbre à partir du nœud qui lui est passé en paramètre.

Rappel d’un parcours d’arbre :

void Parcours (PNode_t Node)
{
    if (!Node) return;

    // Traitement préfixé de *Node

    Parcours (Node->GetGauche());

    // Traitement infixé de *Node

    Parcours (Node->GetDroit());

    // Traitement postfixé de *Node

} // Parcours()

La seconde, non récursive, sert à amorcer la récursivité sur la totalité de l’arbre associé à l’itérateur.

Le constructeur de CIterTree lance un thread ParcoursThr() (fonction membre statique de la classe) dont le paramètre est un pointeur vers l’itérateur d’arbre qui est en train de le lancer.

Ce thread parcourt l’arbre associé à l’itérateur qui l’a lancé à travers la fonction Parcours()) qui dépose successivement dans la BAL de l’itérateur tous les nœuds rencontrés, puis un pointeur nul.

Le ThreadUser récupère les nœuds dans la BAL de l’itérateur à travers la fonction GetNext().

Travail à effectuer

Créer le projet IterArbreThreadsBoost.

Dans l’espace de noms anonyme du fichier IterArbreThreadsBoost.cpp, recopier la classe CBALGen générique ci-dessous :

    template <class CLettre>
    class CBALGen
    {
        condition_variable  m_CondVarProd;
        condition_variable  m_CondVarConsomm;
        mutex               m_MtxCondVar;
        CLettre             m_Lettre;
        bool                m_IsVide;

      public :
        CBALGen () : m_IsVide (true) {}

        void Deposer (const CLettre & MaLettre)
        {
            {
                unique_lock <mutex> Lock (m_MtxCondVar);
                if (!m_IsVide) m_CondVarProd.wait (Lock);

                m_Lettre = MaLettre;
                m_IsVide = false;
            }
            m_CondVarConsomm.notify_one();

        } // Deposer()

        CLettre Retirer ()
        {
            CLettre MaLettre;
            {
                unique_lock <mutex> Lock (m_MtxCondVar);
                if (m_IsVide) m_CondVarConsomm.wait (Lock);

                MaLettre = m_Lettre;
                m_IsVide = true;
           }
           m_CondVarProd.notify_one();

           return MaLettre;

        } // Retirer()

    }; // CBALGen

Recopier et compléter si nécessaire les classes CNode et CSearchTree décrites ci-dessus (en particulier, indiquer si nécessaire les friends à y ajouter).

Écrire la classe CIterTree (déclarations/définitions dans la déclaration de la classe).

Test de la classe CIterTree

Pour tester la classe CIterTree, nous vous proposons la séquence suivante :

  • dans l’espace de noms anonyme du fichier IterArbreThreadsBoost.cpp, déclarer un arbre de recherche d’entiers Arbre,

  • dans l’espace de noms anonyme du fichier IterArbreThreadsBoost.cpp, écrire la classe functor CLecteur ayant pour seule donnée-membre son ID (numéro d’ordre donné à la construction permettant d’identifier le thread correspondant),

  • ajouter à la classe CLecteur l’operator() qui :

    1. affiche le message :

      Debut du lecteur xxx
      

      xxx désigne l’ID du thread

    2. déclare un itérateur sur l’arbre Arbre déclaré précédemment,

    3. parcourt tout l’arbre en affichant à chaque noeud le message suivant :

      Valeur lue par lecteur xxx : yyy
      

      xxx désigne l’ID du thread et yyy la valeur associée au noeud courant.

      Le lecteur dort 1 seconde entre chaque affichage;

    4. affiche le message suivant après la fin du parcours et avant la fin du thread :

      Fin du lecteur xxx
      

    Dans la fonction main() :

      ajouter successivement 10 valeurs entières quelconques à l’Arbre précédemment déclaré,

    • créer un groupe de threads,

    • lancer plusieurs CLecteurs décalés dans le temps.

Vous constaterez (en principe !) que chaque lecteur accède indépendamment à tous les éléments de l’arbre.

Autre test possible


Un problème classique consiste à comparer les contenus de deux arbres binaires AVL n’ayant pas la même structure.

Il est alors nécessaire de les parcourir en parallèle (au moyen de deux itérateurs) et de comparer les valeurs obtenues.

S’il vous reste du temps, construisez deux arbres AVL de structures différentes mais de contenus identiques, et conparez-les.

M4104C-TP-Boost-Exercice8

Bibliothèque C et threads

Comme nous l’avons vu dans des exercices précédents, les variables locales aux threads sont stockées dans des piles séparées.

On considère donc qu’il n’y a aucun risque de concurrence entre variables locales de threads différents.

C’est ce que nous allons voir !

Dans la première partie, nous allons montrer que certaines fonctions standard du C créent à l’insu de l’utilisateur des variables globales.

Ces fonctions peuvent être appelées “simultanément” par plusieurs threads, l’accès concurrent à cette variable globale sans aucune protection peut provoquer des erreurs.

Dans la deuxième et la troisième partie, nous allons montrer que l’implémentation de certaines parties de la bibliothèque standard du C++ dans la glibc est “plus ou moins” sécurisé dans un contexte de multi-threading.

Travail demandé

Créez le projet CCppAndThreads.

Modifier le .pro du projet pour pouvoir utiliser les boost_thread et libUtil.

Partie A

Dans cet exercice, plusieurs threads créent une copie locale d’une NTCTS commune.

Chacun décompose ensuite sa donnée locale en tokens au moyen de la fonction C standard strtok().

Cet exercice doit faire apparaître une interférence entre les traitements des NTCTSs, qui sont pourtant des variables locales aux threads.

Dans l’espace de noms anonyme du fichier CCppAndThreads_a.cpp, déclarer le mutex io_Mtx destiné à effectuer les affichages en exclusion mutuelle.

Ajouter à l’espace de noms anonyme la définition de la fonction-thread Thread() de profil :

void Thread (const string * Param);

qui :

  • crée localement une NTCTS contenant la copie du contenu de Param,

  • affiche en exclusion mutuelle la NTCTS créée.

Dans la fonction main() (le main-thread) :

  1. fabriquer une longue chaîne (string), par exemple en concaténant 200 000 fois le même mot (terminé par un espace),

  2. récupérer le nombre de threads à lancer, passé en argument de la commande,

  3. lancer les threads en leur passant en paramètre la chaîne obtenue par concaténation.

Au début de l’espace de noms anonyme, ajouter la ligne :

typedef vector <char *> CVpChar;    // vector de NTCTS

Dans la fonction Thread(), déclarer un tableau de NTCTS de type CVpChar, puis décomposer la NTCTS locale en mots grâce à la fonction strtok(), en prenant l’espace comme séparateur.

A chaque itération de cette décomposition :

  • appeler la fonction strtok()

  • ajouter l’adresse du nouveau token dans le tableau,

En fin de Thread(), afficher en exclusion mutuelle le nombre de mots trouvés (en principe 200 000 !!!)

Compilez.

Ouvrez un terminal et testez, d’abord avec un seul thread pour vérifier le bon fonctionnement de votre fonction et connaître le nombre de mots, puis avec deux ou trois threads (ça devrait suffire).

En principe, vous devriez constater quelques petits défauts … Pour quelle raison, à votre avis ?

Remarque :

Il est très surprenant que ces threads interfèrent alors qu’ils n’ont, en principe, aucune donnée commune, une fois la NTCTS recopiée localement.

Comme ce n’est pas cette copie qui provoque l’erreur, il faut aller chercher beaucoup plus profondément, dans l’implémentation même de la fonction strtok().

Lors de son premier appel, le premier paramètre lui indique l’adresse mémoire à partir de laquelle doit être effectué le découpage de la chaîne.

Dans les appels suivants, c’est un pointeur nul qui lui est passé.

Cela signifie que le découpage doit continuer à partir de la position courante dans la chaîne.

La fonction conserve donc entre chaque appel la position courante dans la chaîne traîtée, jusqu’à une prochaine réinitialisation.

On peut imaginer que la fonction a la structure suivante :

char *strtok (char *s, const char * delim)
{
    static char * Debut;
    if (s) Debut = s;
	
    char * Result = Debut;

    char * Ptr = Debut;
    // balayage de la NTCTS au moyen du pointeur Ptr jusqu'à ce qu'un
    //     délimiteur soit atteint
    *Ptr = '\0';
	
    // suite du balayage de la NTCTS au moyen du pointeur Ptr
    //     jusqu'à ce que tous les délimiteurs consécutifs aient été 
    //     sautés.
    // Ptr pointe alors sur le début du prochain token
	
    Debut = Ptr; // ou analogue !
    return Result;

} // strtok()

Cette fonction garde donc dans une variable globale, statique et unique une valeur qui mémorise l’avancement dans une NTCTS donnée.

Son utilisation dans un contexte multi-threading a donc toutes les “chances” de provoquer un accès concurrent à cette donnée involontairement partagée.

Plusieurs autres fonctions C effectuent un traitement analogue, et doivent donc être utilisées avec infiniment de précaution.

Il s’agit en particulier de :

rand()
strtok()
asctime()
ctime()
gmtime()
localtime()

Il existe des bibliothèques C écrites spécialement pour être utilisées dans un tel contexte.

Le man de la fonction strtok() indique d’ailleurs ce risque d’erreur dans un contexte de multi-threading et conseille l’utilisation de la fonction strtok_r().

Suite

Modifier l’exercice en remplaçant la fonction strtok() par strtok_r() (le suffixe _r signifie “réentrant” et est utilisé dans la bibliothèque GLibC pour toutes les fonctions dont le code est susceptible d’être parcouru par plusieurs exécutions simultanées – c’est le cas du multi-threading).

#include <string.h>

char * strtok_r (char * str, const char * delim, char **saveptr);

saveptr est un paramètre résultat de type char *, à utiliser ainsi :

char * Ptr;
... strtok_r (..., ..., & Ptr);

Constatez-vous une amélioration ?

Partie B

Classe string C++ et threads

Il y a deux façons de considérer qu’une bibliothèque est thread-safe :

  • la bibliothèque garantit que les actions en parallèle sur deux objets distincts de la même classe n’interagissent pas.

    C’est ce qu’indique par exemple la documentation de l’implémentation SGI :

    Client must lock shared mutable containers

    The SGI implementation of STL is thread-safe only in the sense that simultaneous accesses to distinct containers are safe, and simultaneous read accesses to to shared containers are safe. If multiple threads access a single container, and at least one thread may potentially write, then the user is responsible for ensuring mutual exclusion between the threads during the container accesses.

  • la bibliothèque garantit que les actions en parallèle sur le même objet sont cohérentes : les opérations d’écriture se font en exclusion mutuelle entre elles et en exclusion mutuelle avec les opérations de lecture.

Nous allons tout d’abord tenter de vérifier la première définition.

Dans le fichier CCppAndThreads_b.cpp, définir une string globale initialisée par 10000 '.'.

Dans la fonction Thread() ayant pour paramètre un int représentant un caractère :

  1. recopier la chaîne globale dans une variable locale.

    Inutile de faire cette opération en exclusion mutuelle (pourquoi ?)

  2. dans une boucle, remplacer chaque caractère de la chaîne locale par le caractère reçu en paramètre (temporiser chaque opération comme précédemment).

  3. en fin de boucle, vérifier si la chaîne locale ainsi créée est “cohérente” (c-à-d. si tous les caractères qu’elle contient sont identiques).

    Afficher (en exclusion mutuelle !) l’identifiant du thread (this_thread::get_id()) et le résultat de cette vérification : Chaine coherente ou Chaine non coherente

Compiler et, comme précédemment, tester d’abord avec un seul thread, puis avec plusieurs.

Que constatez-vous et qu’en concluez-vous?

Remarque :

Sans pouvoir l’affirmer (il faudrait aller voir le code source), il semble que la classe string de la bibliothèque C++ de la glibc 3.2 respecte la première définition du safethreading : les accès parallèles aux chaînes distinctes (qui partagent pourtant la même NTCTS au début) semblent ne pas perturber le fonctionnement normal (aucune anomalie relevée jusqu’à 100 threads, ce qui ne constitue aucunement une preuve !)

Partie C

Nous allons pour finir tenter de vérifier si la bibliothèque glibc vérifie la seconde définition de safethreading.

Recopier le fichier CCppAndThreads_b.cpp dans CCppAndThreads_c.cpp.

Remplacer la taille de la chaîne globale par 10 000 000.

Dans la fonction Thread(), remplir une chaîne locale par 10 000 000 fois le caractère passé en paramètre.

Affecter la chaîne locale à a chaîne globale.

Après la fin de tous les threads, afficher dans le main-thread si la chaîne globale est cohérente.

Compiler et, comme précédemment, tester d’abord avec un seul thread, puis avec plusieurs (avec un peu de chances, dix suffisent !).

Il arrive parfois que le programme plante par :

*** glibc detected *** double free or corruption (!prev): 0x0804d610 ***
Abort (core dumped)

ou par

Erreur de segmentation

Qu’en concluez-vous?

Remarque :

La glibc n’est pas safethreaded au second sens de ce terme.

C’est le cas de la majorité des implémentations courantes (SGI, HP, etc.) de la bibliothèque standard du C++, contrairement aux bibliothèques correspondantes de Java.