TÉLÉCOM SudParis 2^ème année

TP Noté CSC4508/M2 du 20/05/14

Modalités

cd votreRepertoireDeTravailPourCSC4508M2
tar cvfz ${USER}.tgz ${USER}_TPNote2014

Préparation

	    cd votreRepertoireDeTravailPourCSC4508M2
	    wget http://www-inf.it-sudparis.eu/COURS/CSC4508/Current/Documents/ExoCoursSys/TPNote2014/WWW/tPNote2014.tgz
	    tar xvfz tPNote2014.tgz
	    mv TPNote2014 ${USER}_TPNote2014
	    cd ${USER}_TPNote2014
	  

Question 1 : Questions de cours (4 points)

$ ./my_strtok ab:c:d e:f
[0] 'ab'
[0] 'c'
[0] 'd'
[1] 'e'
[1] 'f'

Question 1.1 (2 points)

Le programme semble fonctionner lorsque l'on décompose une chaîne de caractère, mais se mélange les pinceaux lorsqu'il faut en traiter plusieurs.

Expliquez dans le fichier Q1/reponses.txt pourquoi le programme ne donne pas le résultat attendu lorsqu'il faut traiter plusieurs chaînes de caractères.

Question 1.2 (1 point)

Proposez (sans l'implémenter) dans le fichier Q1/reponses.txt une solution permettant de corriger la fonction my_strtok_r. Dans cette solution, seule la fonction my_strtok_r doit être modifiée.

Question 1.3 (1 point)

Complétez dans le répertoire Q1/Q1.3 le fichier my_strtok.c afin d'implémenter la solution que vous proposez.

Question 2 : Question de cours (suite) (2 points)

Question 3 : "Jeu de trônes" (6 points)

Dans le royaume de Westeros, les relations entre la famille Stark et la famille Lannister sont très tendues depuis quelques temps. Les Stark reprochent aux Lannister d'avoir tranché la tête de l'un des leurs. Les Lannisters quant à eux en veulent aux Starks d'avoir lancé des rumeurs de relations incestieuses entre Lannisters. Ces relations tendues ayant déjà causé la mort de plusieurs membres des deux familles, le Septon (prêtre) responsable d'un septuaire (lieu de prière) fréquenté par les deux familles a du prendre des mesures drastiques pour empêcher de futurs bains de sang : le septuaire ne peut être fréquenté que par une famille à la fois.

Si un Stark est occupé à prier, il peut être rejoint par d'autres Stark, mais les Lannisters souhaitant se recueillir doivent attendre que tous les Starks soient partis. La même règle s'applique quand les Lannisters occupent le lieu de prière : ils peuvent être rejoint par d'autres Lannisters, mais les Starks doivent attendre leur tour.

L'objectif de cet exercice est de simuler la circulation des membres des deux familles dans le septuaire. Pour cela, chaque Stark ou Lannister de l'histoire est représenté par un thread.

Lorsqu'un thread (Stark ou Lannister) entre dans le lieu de pière, il appelle la fonction prier. Tant qu'un thread est en train de prier, les threads du même type peuvent appeler la fonction prier. Les threads du type opposé doivent attendre que le lieu de prière soit libre avant d'appeler la fonction prier.

Pour chacune des questions ci-dessous :

• Répondez dans le fichier Q3/reponses3.txt ou bien sur votre copie (dans ce dernier cas, indiquez dans le fichier Q3/reponses3.txt « Réponse sur copie »).
• Le langage algorithmique utilisé n'a pas besoin de respecter strictement la syntaxe apprise en première année. L'essentiel est qu'il soit lisible par le correcteur et sans ambiguïté.
• Les questions 3.1 et 3.2 sont indépendantes.

Question 3.1 (4 points)

Chaque Stark est modélisé par un thread exécutant l'algorithme codeStark(). Chaque Lannister est modélisé par un thread exécutant un algorithme codeLannister() similaire.

Question 3.2 (2 points)

La solution que vous proposez induit-elle un risque de "famine" ? Justifiez votre réponse.

Question 4 : Liste chaînée (8 points)

• une structure Element correspondant à un maillon de la liste chaînée. Ce maillon contient l'entier stocké à cet endroit de la liste chaînée et un pointeur vers le maillon suivant de la liste chaînée (NULL si ce maillon est le dernier de la liste) ;
• une structure LinkedList contenant un pointeur vers le premier maillon de la liste chaînée.

Pour chacune des questions ci-dessous :

• répondez dans le fichier Q4/reponses4.txt ou bien sur votre copie (dans ce dernier cas, indiquez dans le fichier ; Q4/reponses4.txt « Réponse sur copie ») pour les questions portant sur la compréhension des problèmes de synchronisation (NB : ces questions comptent pour la moitié des points du barême).
• les questions 4.1, 4.2 et 4.3 sont indépendantes.

Question 4.1 (4 points)

Le code semble fonctionner parfaitement. En effet, en allant dans le répertoire Q4.1, en tapant make, puis ./monothreadTestLinkedList (qui est un test d'intégration de la liste), nous obtenons, à raison, le message "Test OK (la liste finale est vide)".

1. si la liste chaînée contient les valeurs 0 et 3 (en plus des valeurs INT_MIN et INT_MAX) et que si un thread thread1 exécute addLL(liste, 1) tandis qu'un thread thread2 exécute simultanément addLL(liste,2), l'ajout de 1 ou 2 peut être perdu ;
2. si la liste chaînée contient les valeurs 4, 5, 6 et 7 (en plus des valeurs INT_MIN et INT_MAX) et que si un thread thread5 exécute removeLL(liste, 5) tandis qu'un thread thread7 exécute simultanément removeLL(liste,7), pour thread7, la variable locale e de removeLL peut se retrouver avec la valeur NULL dans le test de la boucle while.
   

• votre fonction main() initialise une barrière pthread (cf. man pthread_barrier_init) ;
• votre fonction main() crée NBTHREAD threads (NBTHREAD étant une constante déjà définie dans Q4/Q4.1/multithreadTestLinkedList.c) qui exécutent la fonction addRemove() décrite ci-dessous ;
• votre fonction main() attend ensuite que les NBTHREADS aient terminé leur exécution ;
• votre fonction main() libère ensuite les différentes ressources ;
• chaque thread exécute la fonction addRemove() qui :
• commence par attendre sur la barrière pthread (cf. man pthread_barrier_wait),
• fait NBVAL appels à addLL() identiques à ceux que fait la fonction main() dans monothreadTestLinkedList.c , chaque appel à addLL() étant suivi par un appel à sched_yield(),
• et enfin effectue NBVAL appels à removeLL() identiques à ceux que fait la fonction main() dans monothreadTestLinkedList.c , chaque appel à removeLL() étant suivi par un appel à sched_yield().

Question 4.2 (2 points)

Pour éviter les problèmes identifiés à la question Q4.1, nous allons considérer tout accès à la liste chaînée comme une section critique (à l'aide d'un mutex garantissant que seul un thread peut accéder à la liste chaînée à un instant donné).
Dans Q4/reponses4.txt (ou sur votre copie), expliquez les inconvénients de cette méthode.

Dans Q4.2/LinkedList.h, ajoutez un champ de type pthread_mutex_t au niveau de la structure LinkedList.
Ensuite, modifiez Q4.2/LinkedList.c pour utiliser ce mutex de la manière qui vous semble adéquate dans les différentes fonctions de ce module.
Tapez make, puis ./multithreadTestLinkedList (ou bien ./monothreadTestLinkedList si vous n'avez pas terminé l'implantation de la question 4.1). Vous devez obtenir, à raison, le message "Test OK (la liste finale est vide)".

Question 4.3 (2 points)

NB : cette question étant difficile, abordez-la seulement quand vous avez terminé les autres questions.

Pour pallier l'inconvénient identifié à la question 4.2, nous vous proposons d'avoir un mutex au niveau de *chaque* élément de la liste chaînée.

Dans removeLL(), un thread progresse en prenant le mutex sur l'élément ei sur lequel il se trouve et son successeur ei+1. Lorsqu'il "avance" (e prend la valeur de ei+1), il prend le mutex sur ei+2 et relâche le mutex sur ei. Il progresse ainsi jusqu'à ce que ei+1 corresponde à l'élément à supprimer.

Dans addLL(), un thread progresse de la même manière que pour removeLL(). Il progresse ainsi jusqu'à ce que ei et ei+1 correspondent aux éléments entre lesquels le thread va insérer le nouvel élément.

Dans Q4/reponses4.txt (ou sur votre copie), expliquez pourquoi un thread qui exécute removeLL() ne peut pas se contenter de prendre le mutex de l'élément qui précède l'élément à supprimer (donc, sans prendre le mutex sur l'élément à supprimer).

Dans Q4.3/LinkedList.h, ajoutez un champ de type pthread_mutex_t au niveau de la structure Element.
Ensuite, modifiez Q4.3/LinkedList.c pour utiliser ce mutex comme décrit précédemment.
Tapez make, puis ./multithreadTestLinkedList (ou bien ./monothreadTestLinkedList si vous n'avez pas terminé l'implantation de la question 4.1). Vous devez obtenir, à raison, le message "Test OK (la liste finale est vide)".