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 17/06/16

(Corrigés)

Modalités

Durée : 1 heure 30

Tous documents autorisés.

Le sujet est délibérément trop long pour que toutes les questions puissent être traitées en 1h30. Le barême prévu tient compte de cela: le TP est noté sur 30. Vous pouvez donc choisir de vous concentrer sur certaines questions sans chercher à traiter l'ensemble du sujet.
Les questions 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 1 heure 30 ») du fichier d'extension tgz constitué de la manière suivante :
cd votreRepertoireDeTravailPourCSC4508M2
tar cvfz ${USER}.tgz ${USER}_TPNote2016Session2

Préparation

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

Question 1 : smart pointers (10 points)

Les smart pointers sont des pointeurs conçus pour faciliter la gestion mémoire en C++. Le concept est assez similaire à la gestion mémoire faite par Java: à chaque copie d'un pointeur, on incrémente un compteur de références. Le compteur est décrémenté lorsqu'une copie est détruite. Si le compteur tombe à zéro (et donc, qu'il ne reste aucune copie du pointeur), la zone pointée par le pointeur peut être libérée.

Le fichier Q1/smart_pointers.c implémente un système de smart pointers simple. Ce système est utilisé par le programme Q1/test_smart_pointers.c.

Question 1.1

Dans le fichier Q1/Q1.1/smart_pointers.c, implémentez la fonction smart_pointer_free.

---beginCorr

Corrigé : smart_pointers.corrige.Q1.1.c.

---endCorr

Question 1.2

Répondez à cette question dans le fichier Q1/reponses1.txt.

Afin de vérifier l'implémentation des smart pointers et leur utilisation, quel outil peut on utiliser pour analyser les accès mémoire ? Donnez la ligne de commande permettant d'analyser les accès mémoire du programme test_smart_pointers.

---beginCorr

On peut utiliser valgrind, par exemple, avec la commande: valgrind ./test_smart_pointers

---endCorr

Question 1.3

Répondez à cette question dans le fichier Q1/reponses1.txt.

L'implémentation actuelle des smart pointers n'est pas thread-safe. Quel problème peut survenir avec une application multi-threadée utilisant ces smart pointers.

---beginCorr

Les accès concurrents au champs nb_ptr risquent de provoquer des races condition. Par exemple, on risque de désallouer plusieurs fois le buffer, ou de le désallouer alors qu'un thread utilise encore le pointeur.

---endCorr

Question 1.4

Dans le fichier Q1/Q1.4/smart_pointers.c, corrigez l'implémentation des smart pointers afin de la rendre thread-safe.

---beginCorr

Corrigé : smart_pointers.corrige.Q1.4.c et smart_pointers.corrige.Q1.4.h.

---endCorr

Question 2 : Capitaine de soirée (10 points)

Le capitaine de soirée est la personne qui, dans un groupe se déplaçant en automobile pour se rendre à une fête, promet de rester sobre et de conduire au retour.

Le but de cet exercice est de simuler l'organisation d'un covoiturage et la désignation d'un capitaine de soirée.

On considère que chaque participant est modélisé par un thread exécutant l'algorithme suivant:

attendre_que_la_voiture_soit_remplie();
désigner_un_capitaine_de_soirée();
aller_à_la_fête();
si(je_suis_capitaine_de_soirée) alors
faire_la_fête_sobrement();
sinon
faire_la_fête();
finsi
attendre_que_la_voiture_soit_remplie();
rentrer_se_coucher();

Pour chacune des questions ci-dessous :

  • Répondez dans le fichier Q2/reponse2.txt.
  • 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 2.1 et 2.2 sont indépendantes.

Question 2.1

On souhaite dans un premier temps implémenter la fonction "attendre_que_la_voiture_soit_remplie()" à partir d'un ou plusieurs sémaphores. Cette fonction attend que 5 threads soient montés dans la voiture. Cette barrière est un point de synchronisation qui garantit que N tâches sont arrivées à un point spécifique. Lorsqu'un thread atteint la barrière, il attend jusqu'à ce que le nombre de threads requis soit atteint.

À l'aide de sémaphores (dont vous indiquerez les valeurs initiales), d'éventuelles variables additionnelles (dont vous indiquerez si elles sont partagées entre les threads ou si elle sont locales, ainsi que leurs valeurs initiales), et d'opérations P() et V(), écrivez l'algorithme de attendre_que_la_voiture_soit_remplie().

---beginCorr
Variables utilisées :
int nb_threads : initialisé à zero
semaphore mutex: initialisé à 1
semaphore attente : initialisé à 0

procedure barriere ( )
P(mutex)
nb_threads++;
si( nb_threads == 5) alors
Pour i de 1 à 5 faire
V(attente);
Fin Pour

nb_threads = 0;

V(mutex);
sinon
V(mutex);
P(attente);
Fin Si
Fin Procedure
---endCorr

Question 2.2

On souhaite maintenant implémenter la fonction désigner_un_capitaine_de_soirée(). Cette fonction, appelée par les 5 passagers d'une voiture désigne l'un des passager pour qu'il soit le capitaine de soirée. Chaque processus passager possède une variable locale booléenne je_suis_capitaine_de_soirée qui doit être positionnée à vrai ou faux de manière à ce qu'en sortant de la fonction, un et seul un des 5 threads soit capitaine de soirée. Le choix du thread désigné capitaine est libre.

À l'aide de sémaphores (dont vous indiquerez les valeurs initiales), d'éventuelles variables additionnelles (dont vous indiquerez si elles sont partagées entre les threads ou si elle sont locales, ainsi que leurs valeurs initiales), et d'opérations P() et V(), écrivez l'algorithme de désigner_un_capitaine_de_soirée().

---beginCorr
Variables utilisées :
int nb_threads : initialisé à zero (variable partagée)
bool je_suis_capitaine_de_soirée : initialisé à false (variable locale)
semaphore mutex: initialisé à 1
semaphore attente : initialisé à 0

procedure désigner_un_capitaine_de_soirée()
P(mutex)
nb_threads++;
si( nb_threads == 5) alors
// On choisit le dernier arrivé (il n'avait qu'à être à l'heure !)
je_suis_capitaine_de_soirée = true;
sinon
je_suis_capitaine_de_soirée = false;
Fin Si
V(mutex);
Fin Procedure ---endCorr

Question 3 : My Find (10 points)

Le but de cet exercice est de développer une application capable d'examiner les fichiers d'une arborescence. Pour cela, nous vous fournissons le squelette de programme Q3/my_find.c. Ce programme utilise popen("ls <dirname>", "r") pour obtenir la liste des entrées d'un répertoire. Le but de cet exercice est d'étendre ce programme afin de traiter chacunes de ces entrées.

Question 3.1

Expliquez (dans le fichier Q3/reponses3.txt) le fonctionnement de la commande popen("ls <dirname>", "r").

---beginCorr

popen("ls <dirname>", "r") crée un processus fils (avec fork), exécute la commande ls <dirname> et redirige la sortie (cf l'argument "r") de la commande dans un flux. Le processus père peut donc accèder au résultat de la commande en faisant des fread/fscanf.

---endCorr

Question 3.2

Complétez, dans Q3/Q3.2/my_find.c, le programme afin d'afficher, pour chaque entrée un message du type "new entry: fichier1.txt". Voici un exemple d'exécution attendue :

$ ./my_find .
new entry: 'Makefile'
new entry: 'Makefile~'
new entry: 'my_find'
new entry: 'my_find.c'
new entry: 'my_find.c~'
 ---beginCorr

Corrigé : my_find.corrige.Q3.2.c.

---endCorr

Question 3.3

Complétez votre programme (dans Q3/Q3.3/my_find.c) afin d'afficher un message différent pour les repertoires. Par exemple:

$ ./my_find .
New file: ./Makefile
New file: ./Makefile~
New file: ./my_find
New file: ./my_find.c
New file: ./my_find.c~
New directory: ./Q3.2
New directory: ./Q3.3
New directory: ./Q3.4
---beginCorr

Corrigé : my_find.corrige.Q3.3.c.

---endCorr

Question 3.4

On souhaite maintenant parcourir récursivement les sous-répertoires. Complétez votre programme (dans Q3/Q3.4/my_find.c) afin qu'il crée, pour chaque répertoire, un nouveau processus exécutant la commande ./my_find <sous-répertoire>. Voici un exemple d'exécution attendue:

$ ./my_find .
Entering .
New file: ./Makefile
New file: ./Makefile~
New file: ./my_find
New file: ./my_find.c
New file: ./my_find.c~
New file: ./my_find_sujet.c
New directory: ./Q3.2
Entering ./Q3.2
New file: ./Q3.2/Makefile
New file: ./Q3.2/my_find.c
Leaving ./Q3.2
New directory: ./Q3.3
Entering ./Q3.3
New file: ./Q3.3/my_find.c
Leaving ./Q3.3
New directory: ./Q3.4
New file: ./Q3.4/my_find.c
Leaving ./Q3.4
Leaving .
---beginCorr

Corrigé : my_find.corrige.Q3.4.c.

---endCorr



Page mise à jour le 13 juin 2016