Département INFormatique 
 CSC4508/M2 : Concepts des systèmes d'exploitation et mise en œuvre sous Unix


   Évaluation



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

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

(Corrigés)

Modalités

Durée : 3 heures

Tous documents autorisés.

Les questions 1, 2 et 3 sont indépendantes les unes des autres. Aussi, n'hésitez pas à lire tout le sujet avant de commencer pour déterminer l'ordre dans lequel vous souhaitez traiter les questions.

Le barème est donné à titre indicatif des poids entre les différentes questions.

La « livraison » de votre travail en fin de TP noté se fera par remontée sous Moodle (rubrique « TP noté de 3 heures ») du fichier d'extension tgz constitué de la manière suivante :
cd votreRepertoireDeTravailPourCSC4508M2
tar cvfz ${USER}.tgz ${USER}_TPNote2014
NB: Si vous êtes plus à l'aise en écrivant vos réponses sur une copie plutôt qu'en les tapant sur ordinateur, vous pouvez rendre également une copie papier à l'enseignant qui vous surveille. En fin d'épreuve, même si vous ne rendez pas de copie, passez voir l'enseignant qui vous surveille pour lui signaler explicitement que vous ne rendez pas de copie.

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)

On considère le programme Q1/my_strtok.c qui s'appuie sur une implémentation de la fonction strtok_r pour décomposer des chaînes de caractères séparées par le caractère ':'. Les paramètres passés au programme sont distribués à plusieurs threads et chaque thread décompose sa chaîne de caractère en tokens. Ainsi, lorsque l'on invoque le programme avec les paramètres "ab:c:d" et "e:f", un thread décompose la chaîne "ab:c:d" en 3 jetons ("ab", "c" et "d") pendant qu'un autre décompose la chaîne "e:f" en "e" et "f" :

$ ./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.

---beginCorr

Le code de la fonction my_strtok_r n'est pas thread-safe. Lorsque plusieurs threads appellent my_strtok_r, la variable statique cur_pos est partagée: les threads modifient donc la variable de manière concurrente, ce qui entraîne des résultats incorrects, voire des accès en dehors des tableaux passés en paramètres.

---endCorr

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.

---beginCorr

Utiliser un mutex dans my_strtok_r ne sert à rien puisque cela ne résout pas le problème de réentrance de la fonction. Il faut déclarer la variable cur_pos en tant que variable TLS (Thread Local Storage), soit en utilisant la mot-clé __thread (voir corrige1.c), soit en utilisant une clé de type pthread_key_t (voir corrige2.c)

---endCorr

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.

---beginCorr

Corrigé avec __thread: my_strtok.corrige_v1.c
Corrigé avec une clé: my_strtok.corrige_v2.c

---endCorr

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

On considère le programme Q2/mystere.c
Compilez ce programme. Puis, tapez la commande : ./mystere mystere.c mystere2.c
Le programme plante.
Corrigez mystere.c pour que ./mystere ne plante plus.
Puis, expliquez dans le commentaire en tête du fichier mystere.c ce que fait ce programme ./mystere.
---beginCorr

Corrigé : mystere.corrige.c
Barême : 1,5 point pour la correction du code et 0,5 point pour l'explication du rôle de l'exécutable

---endCorr

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.

procédure codeStark()

// à compléter, si besoin, avec du code d'initialisation et de synchronisation

prier( );

// à compléter, si besoin, avec du code de synchronisation

Fin Procédure

À l'aide de sémaphores (dont vous indiquerez les valeurs initiales), d'éventuelles variables additionnelles (dont vous indiquerez les valeurs initiales), et d'opérations P() et V(), complétez l'algorithme de codeStark().

---beginCorr

Corrigé : stark.corrige.c

---endCorr

Question 3.2 (2 points)

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

---beginCorr

La solution proposée risque de mener à une famine : une fois qu'un Stark est entré, les Lannisters risquent d'attendre indéfiniment si des Starks arrivent continuellement.

---endCorr

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

Cet exercice s'intéresse à l'implantation, en environnement multithreadé, d'une liste chaînée destinée à stocker des entiers de manière ordonnée.

Le fichier d'interface Q4/Q4.1/LinkedList.h définit deux structures de données :
  • 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.
Ce fichier d'interface contient également les déclarations et descriptions doxygen des différentes opérations sur une liste chaînée.

Pour simplifier les algorithmes de notre implantation, une liste chaînée contient systématiquement au moins 2 maillons : le premier stocke la valeur entière INT_MIN (la valeur minimum des entiers), alors que le dernier stocke la valeur entière INT_MAX (la valeur maximum des entiers). Ainsi, une liste chaînée vide contient toujours 2 maillons (l'un contenant INT_MIN et l'autre INT_MAX).

La figure suivante représente une liste chaînée contenant les valeurs 0 et 3 :

Example of a linked list

Nous vous invitons à étudier le code des fonctions addLL et removeLL dans Q4/Q4.1/LinkedList.c pour bien comprendre le fonctionnement de cette implantation.

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)".

Toutefois, l'introduction de multithreading peut apporter des dysfonctionnements. Dans Q4/reponses4.txt (ou sur votre copie), montrer que :
  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.
---beginCorr
Barême : 1 point pour chaque démonstration correcte.
  1. Pour que l'ajout de 1 ou 2 soit perdu, il faut que thread1 décide que l'élement e0 (contenant la valeur 0) sera l'élément auquel il devra rattacher e1 (l'élément dans lequel thread1 stockera 1) et que, simultanément, thread2 décide que ce sera aussi e0 auquel il rattachera e2 (l'élément dans lequel thread2 stockera 2). thread1 et thread2 remplissent e1 et e2. Puis, chacun exécute la ligne e->next = newE. Si thread1 (respectivement thread2) exécute cette instruction avant thread2 (respectivement thread1), le pointeur vers e1 (respectivement e2) est perdu.
  2. Supposons que thread7 entre dans la boucle while de removeLL et que thread7 progresse jusqu'à ce que e soit égal à e5, l'élément contenant la valeur 5. 7 est supérieur à e->next-->val qui vaut 6. Donc, thread7 entre dans le corps du while. Mais, avant d'avoir exécuté l'instruction e = e->next, thread7 est interrompu par thread5 qui prend la main et se déroule entièrement. Donc, thread5 supprime e5, ce qui signifie que thread5 exécute l'instruction eToRemove = NULL et free(eToRemove) avec eToRemove correspondant à e5. Quand thread7 reprend la main, il exécute l'instruction e = e->next dans le corps du while. Il accède à e5 (qui a été libéré par thread5). Comme e5->next vaut NULL, thread7 se retrouve avec la valeur NULL dans la variable e.
---endCorr
 Pour vérifier l'un de ces dysfonctionnements, complétez Q4/Q4.1/multithreadTestLinkedList.c pour que :
  • 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().
Tapez make, puis ./multithreadTestLinkedList. Sur la machine du rédacteur de cet énoncé, nous obtenons une Erreur de segmentation (NB : du fait que vous n'avez aucun contrôle sur l'ordonnancement des threads sur votre système d'exploitation, il se peut aussi que votre test renvoie un résultat OK). L'analyse sous debugger (non demandée dans le cadre de ce TP noté) montre que la variable locale e de removeLL() se retrouve avec la valeur NULL dans le test de la boucle while : l'instruction e->next->val cause donc une erreur de segmentation.
---beginCorr
Corrigé : multithreadTestLinkedList.corrige.c
Barême :
  • 0,5 point pour la barrière
  • 0,5 point pour le fork des threads
  • 0,5 point pour le join des threads au niveau du main
  • 0,5 point pour le test du retour d'erreur
---endCorr

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.
---beginCorr

Vu qu'un seul thread peut accéder à la liste chaînée, il n'y a aucun moyen de paralléliser des traitements (par exemple, avoir plusieurs exécution de la fonction addLL() en parallèle).

Barême : 1 point.

---endCorr

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)".

---beginCorr
Corrigé : LinkedList.Q4.2.corrige.h et LinkedList.Q4.2.corrige.c
Barême : 1 point pour l'utilisation correcte du mutex aux bons endroits. Malus de 0,25 point si oubli du pthread_destroy().
---endCorr

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).
---beginCorr

Supposons que les threads qui exécutent removeLL() se contentent de prendre le mutex de l'élément qui précède l'élément à supprimer. Supposons qu'une liste chaînée contient les valeurs 4, 5, 6 et 7 (en plus des valeurs INT_MIN et INT_MAX) et qu'un thread thread5 exécute removeLL(liste, 5) tandis qu'un thread thread6 exécute simultanément removeLL(liste,6). thread5 (respectivement thread6) prend le mutex de e4 (respectivement e5), l'élément contenant la valeur 4 (respectivement 5). thread5 supprime e5 (il ne tient pas compte du fait que thread6 a pris un mutex sur e5) et fait pointer e4 vers e6. En parallèle, thread6 supprime e6 et fait pointer e5 vers e7. Au final, la liste chaînée contient e4 qui pointe vers e6 qui est un élément libéré. La liste chaînée est donc cassée.

Ce phénomène est impossible si thread5 prend le mutex de e4 et e5, tandis que thread6 essaye de prendre le mutex de e5 et e6.

NB : pour permettre le parallélisme, d'autres méthodes sont possibles. Se reporter au livre "The Art of Multiprocessor Programming" de  Maurice Herlihy et Nir Shavit, ainsi que leurs transparents de leur cours "Multiprocessor Synchronization" disponibles en http://cs.brown.edu/courses/cs176/lectures.shtml pour avoir plus d'informations.

Barême : 1 point

---endCorr

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)".

---beginCorr
Corrigé : LinkedList.Q4.3.corrige.h et LinkedList.Q4.3.corrige.c
Barême : 1 point pour l'implantation
---endCorr



Page mise à jour le 08 mai 2014