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 communication/synchronisation associés.

• Exercice I. Calcul des plus courts chemins dans un graphe

• Exercice II. Le paradigme lecteurs/rédacteurs

• Exercice III. E/S asynchrones, timer et signaux temps réel

Exercice I : Calcul des plus courts chemins dans un graphe

Pour illustrer l'utilisation des threads, nous allons paralléliser un algorithme de calcul des 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 du graphe.

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.

Compilez le programme précédent et exécutez le.

Question 1 : threads versus 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.

• Ecrivez le programme ford-fork qui encapsule la fonction calcul_une_ligne.c.
• 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 :

  gcc -D_REENTRANT pgm.c -o pgm -lpthread -lrt

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

Question 3 : utilisation d'une variable conditionnelle

Modifiez le programme précédent de sorte que le thread principal soit synchronisé avec les threads qui exécutent calcul_une_ligne() grâce à une variable conditionnelle.

Exercice II : Le paradigme lecteurs/rédacteurs

L'objectif de cet exercice est d'implanter le paradigme de coopération lecteurs/rédacteurs. Ce dernier permet l'accès à une ressource partagée entre plusieurs tâches/threads dans les conditions suivantes :

1. A un instant donné, un seul rédacteur (thread qui modifie la ressource) peut accèder à la ressource.
2. A un instant donné, plusieurs lecteurs (threads qui consultent la donnée) peuvent accèder à la ressource.
3. Lorsqu'un lecteur consulte la ressource, les rédacteurs ne peuvent la modifier et réciproquement. Une famine sur les rédacteurs est acceptée.

On vous demande de :

• Récupérez le programme lr.c. La ressource partagée est modélisée dans ce programme par la variable donnee_partagee. Vous aurez besoin d'un sémaphore à compteur pour protéger cette ressource et d'un mutex pour protéger la variable nb_lecteurs. Le sémaphore à compteur doit être initialisé à 1.
• Complétez et testez le programme. Les zones à compléter sont signalées par des étoiles.

Exercice III : E/S asynchrones, timer et signaux temps réel

En guise de conclusion pour ce TP, on allons voir qu'une certaine forme de parallélisme est possible sans les threads, et ce grâce aux timers et aux E/S asynchrones de POSIX.4. Le programme text.c en est un exemple.

Ce programme lit et affiche à l'écran un texte périodiquement (extrait de l'avare de Molière). Les lectures sont réalisées de façon asynchrones. Affichages et lectures s'effectuent grâce à un timer qui délivre un signal UNIX temps réel toutes les 2 secondes. Pour chaque occurrence de signal, on teste la terminaison de la lecture du texte, on affiche le texte et on lance la lecture suivante : cette méthode permet de recouvrir le temps de lecture du fichier : en effet, le processus n'est pas bloqué durant la phase de lecture et peut donc effectuer un traitement quelconque et ce jusqu'à l'occurrence du signal suivant où là, la lecture a toute les chances d'être terminée.

On vous demande de :

• Récuperez les fichiers text.c et avare.txt.
• Complétez la fonction main et la fonction handler afin de mettre en place un timer dont la période sera de 2 secondes et qui générera des signaux SIGRTMIN. Vous aurez besoin des fonctions sigaction, timer_create et timer_settime.
• Complétez la fonction demande_lecture_asynchrone et handler afin de lancer et tester la terminaison des lectures asynchrones. Les lectures ne devront pas générer de signaux. Vous aurez besoin des fonctions aio_read, aio_error et aio_return.

  NB: les zones à compléter sont signalées par des étoiles.

• Compilez et testez votre programme.