Les threads POSIX

Frank Singhoff

I. Présentation

II. Threads et processus : calcul de plus courts chemins

III. Exercices de synchronisation

III.1 Le p'tit train train

III.2 Beau comme un camion

III.3 Le roi du pétrole

III.4 Les variables conditionnelles

IV. Correction

V. Correction "type" du CC2 de TRV 2003

I. Présentation

L'objectif de ce TP est la découverte de l'interface de programmation offerte par POSIX.4 ; et plus particulièrement les threads et les outils de synchronisation associés.

II. Threads et processus : calcul de plus courts chemins

Pour illustrer l'utilisation des threads, nous allons paralléliser un algorithme de calcul de plus courts chemins d'un graphe. L'algorithme en question (algorithme de Bellman et Ford) calcule tous les plus courts chemins pour tous les sommets d'un graphe donné.

Le code séquentiel de cet algorithme, appliqué au graphe ci-dessus, est donné dans le fichier ford.c. La matrice à droite de la figure est la matrice d'adjacence du graphe pour lequel, l'absence d'arc entre deux sommets est matérialisée par le signe + infini. L'algorithme fonctionne de la façon suivante :

1. Il effectue un calcul itératif sur la matrice de la figure ci-dessus (cf. boucle avec la variable m du programme ford.c).
2. Pour chaque itération du point précédent, la fonction calcul_une_ligne() est invoquée NB_SOMMETS fois.

Au final, les calculs effectués par cet algorithme sont équivalents à des multiplications de matrices.

Question 1 : threads vs processus

Dans un premier temps, on exécute l'algorithme à l'aide de plusieurs processus. Un processus effectue la boucle for de plus haut niveau. Puis, NB_SOMMETS processus effectuent les calculs sur les lignes de la matrice d'adjacence : chaque processus est chargé d'effectuer les calculs d'une ligne donnée.

• Récupérez le programme suivant.
• Compilez et exécutez le.
• Que constatez vous ? pourquoi ?

Question 2 : synchronisation avec pthread_join

• Substituez les processus par des threads POSIX.
• Compilez ce nouveau programme ; pour utiliser les extensions temps réel du standard POSIX.4, vous utiliserez la ligne de commande suivante :

• Testez le nouveau programme.
• A votre avis, doit on accéder aux matrices temp, Resultat et graphe en exclusion mutuelle ? pourquoi ?

III. Exercices de synchronisation

III.1 Le p'tit train train : exclusion mutuelle

Une ligne de chemin de fer relie quatre villes (les villes A, B, C et D). Cette ligne est utilisée par des trains partant de la ville A pour la ville C ainsi que par des trains partant de la ville D pour la ville A. On vous demande de gérer le partage de cette ligne de chemin de fer sachant que :

• Plusieurs trains peuvent partir simultanément de A.
• Plusieurs trains peuvent partir simultanément de D.
• A un instant donné, chaque segment de la ligne de chemin de fer (segments AB, BC et DB) ne peut être utilisé que par un train au plus.

On souhaite mettre en place un moniteur (acquisition et libération des ressources) sur les segments de chemin de fer.

Complétez ce programme afin que les règles ci-dessus soient respectées. Dans ce programme chaque train est modélisé par un thread.

III.2 Beau comme un camion : compteur de ressource ou sémaphores privés ?

1. Donnez un programme comportant un moniteur ( une fonction d'acquisition et une fonction de libération du pont) qui simule les règles de partage du pont ci-dessus. Votre programme modélisera les camions et voitures sous la forme de threads. Pour implanter les fonctions d'allocation et de libération, vous utiliserez la méthode du compteur de ressources :
   • Un sémaphore à compteur est associé à la ressource.
   • Le sémaphore à compteur est initialisé au nombre total de ressource (cette technique n'est applicable que lorsque les ressources sont toutes identiques).
   • L'allocation de la resource consiste alors à un ou des accès au sémaphore à compteur.
   
   
   
   
2. Quand un véhicule quitte le pont, on souhaite donner la priorité aux camions : lorsqu'une voiture et un camion sont bloqués en attente d'obtenir l'accès au pont, le camion doit être réveillé en premier, sous réserve, bien sûr, que la capacité maximale du pont soit respectée. Avec cette nouvelle contrainte, il n'est plus possible d'utiliser la méthode basée sur le sémaphore à compteur. Donnez une deuxième version du moniteur qui prenne en compte la priorité des camion. Cette nouvelle version sera basée sur le paradigme du sémaphore privé.

III.3 Le roi du pétrole

On vous demande d'écrire un programme qui convertit des nombres en base 10 vers la base 2. Pour ce faire, on vous demande d'utiliser un pipe-line de threads.

Votre programme doit être constitué de 8 threads :

• Le premier thread lit depuis le clavier le nombre à convertir, puis, transfère cette infomation vers le thread suivant.
• Les 7 autres threads effectuent les opérations suivantes :

1. Affichage de 0 ou 1 selon que le nombre reçu par le thread soit divisible ou non par deux.
2. Transfert du nombre divisé par 2 au thread suivant (sauf si le nombre divisé est égal à zéro).

• Le dernier thread du pipe-line doit afficher une erreur si le nombre à convertir dépasse la capacité du pipe-line.

Remarque : tel que le pipe-line est décrit ici, le résultat de la conversion doit normalement afficher le nombre en base 2 à l'envers.

III.4 Les variables conditionnelles

On reprend l'exercice II concernant le calcul de plus courts chemins.

Modifiez le programme obtenu dans la question 2 de l'exercice II de sorte que le thread principal soit synchronisé avec les threads qui exécutent calcul_une_ligne() grâce à une variable conditionnelle.