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 22/06/11

(2ème session)

(Corrigés)

Modalités

Durée : 1 heure 30

Tous documents autorisés.

Les questions 1, 2 et 3 sont indépendantes. 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 TPNote2011Session2

Préparation

cd votreRepertoireDeTravailPourCSC4509M2
cp ~simatic/Cours/CSC4508/tPNote2011Session2.tgz .
tar xvfz tPNote2011Session2.tgz
cd TPNote2011Session2

Question 1 : De l'alignement des structures (6 points)

On considère le programme C suivant :
#include <stdlib.h>

typedef struct {
short aShort;
int anInt;
short aShort2;
} __attribute__((packed,aligned(8))) MaStruct;

int main() {
MaStruct maStruct = {0,0,0};
maStruct.anInt = 1;
return EXIT_SUCCESS;
}

Pour chacune des questions ci-dessous, répondez dans le fichier Q1/reponse1.txt ou bien sur votre copie (dans ce dernier cas, indiquez dans le fichier Q1/reponse1.txt « Réponse sur copie »).
  1. Expliquez le rôle de l'attribut packed dans __attribute__((packed,aligned(8))).
  2. Expliquez le rôle de l'attribut aligned(8) dans __attribute__((packed,aligned(8))).
  3. Sur un processeur Intel, ce programme s'exécute parfaitement. En revanche, sur un processeur ARM d'ancienne génération, ce programme plante au niveau de l'instruction maStruct.anInt = 1; en faisant une « Erreur d'accès mémoire ». Expliquez pourquoi.
  4. Quels changements proposez-vous dans ce programme pour que l'instruction maStruct.anInt = 1; s'exécute correctement sur processeur ARM ancienne génération ?
---beginCorr
Barème : 1,5 point par réponse apportée
  1. L'attribut packed permet d'indiquer au compilateur que cette structure doit être compactée. De ce fait, même si l'entier n'est pas correctement aligné dans la structure, le compilateur ne doit pas générer ni 2 octets de stuffing après aShort, ni 2 autres après aShort2 (ce que le compilateur ferait automatiquement s'il n'y avait pas cet attribut packed).
  2. L'attribut aligned(8) permet d'indiquer au compilateur que toute variable ayant pour type cette structure doit être alignée sur une frontière de 8 octets, i.e. son adresse doit être un multiple de 8 octets.
  3. A cause de ces 2 attributs, anInt est à cheval sur une frontière de 4 octets (2 octets avant cette frontière et 2 octets après). De ce fait, l'accès à anInt nécessite un traitement spécial que sait faire le processeur Intel, mais que ne sait pas faire le processeur ARM.
    NB :
    1. S'il n'y avait pas eu l'attribut aligned(8), le compilateur aurait quand même cherché à aligner la structure sur une frontière de 4 octets. Donc anInt aurait été totu de même sur une frontière de 4 octets (cf. Exercice 3 des exercices autour de la Mémoire).
    2. Les processeurs Intel qui implémentent le jeu d'instructions MMX sont également confrontés à ce problème d'accès mémoire sur une frontière d'octets (cf. Exercice 8 des exercices autour de la Mémoire).
  4. Il suffit de placer anInt en premier ou en dernier dans la structure MaStruct. Ainsi, anInt se retrouve sur une frontière de 4 octets : le processeur ARM peut y accéder sans problème.
---endCorr

Question 2 : Le retour de La Trace du Hourra (4 points)

Dans l'une des questions du TP noté de 2011 (session 1), nous avons étudié l'algorithme de synchronisation des trains fonctionnant sur la montagne russe La Trace du Hourra du Parc Astérix.

Rappels (que vous pouvez ne pas lire si vous vous souvenez du TP noté de 2011 [session 1])

La figure 1 modélise cette montagne russe. Elle est constituée de 4 zones:
  • zoneE est la zone d'Embarquement où les passagers montent et descendent d'un train. zoneE peut contenir au maximum 2 trains.
  • zoneA est la zone d'Attente juste avant de pouvoir entrer dans zoneE. Elle ne peut contenir qu'un train.
  • zoneH est la zone où un train monte avant de se lancer dans sa descente infernale (c'est donc la zone des Hurlements où les gens crient « Help, je veux descendre ! Non, pas comme çaaaaaaaa... »). Elle ne peut contenir qu'un train.
  • zoneG est la zone de Garage du train. Les trains y sont parqués avant d'être injectés dans le circuit zoneE-zoneH-zoneA. NB : dans cet exercice, on suppose qu'une fois qu'un train est sorti de zoneG, il n'y retourne plus jamais.
Schéma de la montagne russe "La Trace du Hourra"
Figure 1 : Modélisation de la montagne russe « La Trace du Hourra »

Quand cette attraction fonctionne :
  • Un train ne peut quitter zoneG que s'il y a de la place dans zoneE.
  • Un train ne peut quitter zoneE que si zoneH est vide.
  • Un train ne peut quitter zoneH que si zoneA est vide.
  • Un train ne peut quitter zoneA que s'il y a de la place dans zoneE.

La question 2 proprement dite

Une personne, que nous dénommerons Candide par la suite, a proposé l'algorithme ci-dessous pour chaque train de cette attraction. Noter que l'algorithme du corrigé du TP noté de 2011 (session 1) et l'algorithme de Candide ne diffèrent que par la valeur d'initalisation du sémaphore zoneE.


Semaphore zoneE initialisé à 1; // Dans le corrigé du TP noté
                                // de 2011 (session 1), le
                                // le sémaphore zoneE était
                                // initialisé à 2 et non à 1.
Semaphore zoneA initialisé à 1;
Semaphore zoneH initialisé à 1;

Procédure codeTrain()
afficher("Je suis dans zoneG");dormirUnPeu();
P(zoneE);
Tant que VRAI faire
afficher("Je suis dans la zone zoneE");dormirUnPeu();
P(zoneH)
V(zoneE);
afficher("Je suis dans la zone zoneH");dormirUnPeu();
P(zoneA);
V(zoneH);
afficher("Je suis dans la zone zoneA");dormirUnPeu();
P(zoneE);
V(zoneA);
Fin Tant que
Fin Procédure
  1. Expliquez pourquoi, quand le sémaphore zoneE est initialisé à 1 (au lieu de 2), la zone zoneE ne peut contenir qu'un seul train à la fois.
  2. Quand le sémaphore zoneE est initialisé à 1 (au lieu de 2), si 3 trains sont injectés dans la montagne russe, ces trois trains n'arrivent pas à circuler. Expliquer pourquoi.
---beginCorr
Barème : 2 points par réponse apportée
  1. Le sémaphore zoneE est initialisé à 1. Donc quand un train rentre dans la zone zoneE, il fait passer ce sémaphore à 0. De ce fait, vu que quand un autre train cherche à rentrer dans la zone zoneE, il commence par faire P(zoneE), il reste bloqué sur ce P(zoneE) tant que l'autre train n'a pas quitté la zone zoneE (et donc fait V(zoneE)). En conséquence, on ne put avoir qu'un seul train dans la zone zoneE.
  2. Supposons qu'il y ait 3 trains dans le circuit et qu'ils sont tous sortis de la zone zoneG. Comme il ne peut y avoir qu'un train par zone, chacun occupe forcément l'une des 3 zones zoneE, zoneH et zoneA. Or, pour pouvoir quitter sa zone, chaque train T doit franchir le P(semaphoreDeLaZoneSuivante). Comme la zone est occupée par un autre train (qui ne fera V(semaphoreDeSaZone) qu'apres avoir franchi le P(semaphoreDeLaZoneSuivante)), le train T ne peut pas quitter sa zone. Aucun train n'arrive donc à circuler.
---endCorr

Question 3 : Simulation de La Trace du Hourra (10 points)

Candide, la personne évoquée à la question 2, a développé un programme correspondant à son algorithme (cf. question 2). Dans ce programme, Candide crée NB_TRAINS threads qui exécutent le code de codeTrain() ; le Tant que VRAI faire de l'algorithme est remplacé par un for (nbTours=0 ; nbTours<NB_TOURS ; nbTours++) pour que chaque thread s'arrête après avoir fait NB_TOURS tours de montagne russe.

Avant de rentrer dans le vif du sujet, exécutez ce programme : cd Q3-1 ; make ; ./simulationTraceDuHourra
L'affichage permet d'observer la synchronisation des différents trains.

Les trois sous-questions suivantes peuvent être traitées les unes indépendamment des autres.

Question 3-1 : Plusieurs trains dans la zone zoneE (4,5 points)

Comme tous ses sémaphores étaient initialisés à 1, Candide les a implémentés avec des pthread_mutex.
Dans cette question, on souhaite pouvoir avoir deux trains en même temps dans la zone zoneE et donc, comme on l'a vu à la question Q2, 3 trains qui circulent en parallèle sur la montagne russe.
Dans simulationTraceDuHourra.c, mettez la valeur de NB_TRAINS à 3 et remplacez le pthread_mutex zoneE par un sémaphore de type sem_t initialisé à (NB_TRAINS - 1).
---beginCorr
Barème :
  • Il y a 1 sem_init, 1 sem_destroy, 2 sem_post et 2 sem_wait : si chaque appel est bien fait, on compte 0,5 points par appel (soit un total de 3 points).
  • Dans le error_at_line qui suit chacune de ces instructions, on doit mettre errno en 2ème paramètre à la place de rc. On compte 0,25 point par errno à la place de rc (soit un total de 1,5 points)
  • Pénalité si code compile avec des warnings : -0,5 point
Voir fichier simulationTraceDuHourra.Q3-1.corrige.c
---endCorr

Question 3-2 : Synchronisation du main avec les threads (3 points)

Dans le code actuel, le main dort après avoir créé les threads. Ainsi, Candide est sûr que tous les threads sont terminés quand le main se réveille et termine son exécution.
Dans simulationTraceDuHourra.c, remplacez sleep(20) par une attente explicite de la fin de l'exécution des différents threads.
---beginCorr
Barème :
  • Dans les pthreads_create, il faut remplacer les &thread par &thread[i] : 1 point
  • Boucle avec pthread_join : 1 point
  • 2ème paramètre correct dans le pthread_join : 0,5 point
  • Test d'erreur après pthread_join : 0,5 point
  • Pénalité si code compile avec des warnings : -0,5 point
Voir fichier simulationTraceDuHourra.Q3-2.corrige.c
Dans les pthreads_create, il faut remplacer les &thread par &thread[i].
Après la boucle de démarrage des threads, il faut faire une boucle avec pthread_join()
---endCorr

Question 3-3 : Où les threads deviennent des enfants (2,5 points)

Dans le code actuel, utilisez des enfants à la place des threads.
---beginCorr
Barème :
  • fork() correctement codé : 0,5 points
  • Passage du paramètre numTrain à la procédure déroulant le code du train correct : 0,5 points
  • wait() correctement codé : 0,5 points
  • Création et initialisation des 3 sémaphores : 0,3 points (0,1 point par sémaphore)
  • Destruction des 3 sémaphores : 0,3 points (0,1 point par sémaphore)
  • Appel à P() et V() : 0,4 points (0,05 point pour chacun des 8 appels)
  • Pénalité si code compile avec des warnings : -0,5 point
Voir fichier simulationTraceDuHourra.Q3-3.corrige.c
---endCorr


Page mise à jour le 20 juin 2011