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

Institut National des Télécommunications
Télécom INT 2è année

TP Noté CS21 du 20/06/05

(Corrigés)

Modalités

Durée : 3 heures

Les trois questions sont indépendantes les unes des autres.

Le barême est donné à titre indicatif des poids entre les différentes questions. Seront notés :
  • La clarté du code,
  • Le fait que le code compile (sans warning),
  • Le fait que le code répond correctement à la question posée,
  • Le fait que le retour de chaque appel système, s'il y en a un, est testé et géré (traitement d'erreur),
  • Le fait que les ressources système réservées pendant l'exécution du programme sont libérées à la fin de l'exécution.
La «livraison» de votre travail en fin de TP noté se fera par remise de votre copie à l'enseignant et par envoi d'un mail à Michel.Simatic@int-evry.fr (sujet «CS21:TP noté») avec en pièce jointe le fichier d'extension tgz constitué de la manière suivante :
cd votreRepertoireDeTravailPourCS21
tar cvfz $USER.tgz TPNote2005

Préparation

cd votreRepertoireDeTravailPourCS21
cp ~simatic/CS21/tPNote2005.tgz .
tar xvfz tPNote2005.tgz
cd TPNote2005

Question 1 : Relecture de code (4,5 points)

Pour chacun des six extraits de code suivants, déterminez s'il contient des anomalies (erreur de programmation, erreur d'utilisation ou bien code non optimal).
Pour chaque anomalie trouvée, donnez sa localisation et une explication sur votre copie ou bien dans le fichier Q1/reponse.txt (dans ce dernier cas, indiquez sur votre copie "Réponse dans Q1/reponse.txt" ).
/*************/
/* Extrait 1 */
/*************/
Ligne  1: int i;
Ligne  2: pid_t pid;
Ligne  3: /* Creation de NBENFANTS enfants */
Ligne  4: for (i=0 ; i<NBENFANTS ; i++){
Ligne  5:   pid = fork();
Ligne  6:   switch(pid){
Ligne  7:     case -1:
Ligne  8:       perror("fork");
Ligne 10:       exit(EXIT_FAILURE);
Ligne 11:     case 0:
Ligne 12:       i = NBENFANTS;
Ligne 13:       break;
Ligne 14:     default:
Ligne 15:       break;
Ligne 16:   }
Ligne 17: }  







/*************/
/* Extrait 2 */
/*************/
Ligne  1: typedef struct {
Ligne  2:   short nbTorchons;
Ligne  3:   int   nbAssiettes;
Ligne  4:   short nbServiettes;
Ligne  5:   int   nbCuillières;
Ligne  6: } materielCuisine;

/*************/
/* Extrait 3 */
/*************/
Ligne  1: int fd;
Ligne  2: int rc;
Ligne  3: int donnee;
Ligne  4: fd = open("unFichier.dat", O_RDONLY|O_SYNC);
Ligne  5: if (fd == NULL){
Ligne  6:   perror("fopen");
Ligne  7:   exit(EXIT_FAILURE);
Ligne  8: }
Ligne  9: rc = read(fd, &donnee, sizeof(donnee));
Ligne 10: if (rc < 0){
Ligne 11:   perror("read");
Ligne 12:   exit(EXIT_FAILURE);
Ligne 13: }

/*************/
/* Extrait 4 */
/*************/
Ligne  1: void attenteRequete(void *arg);
Ligne  2: int i;
Ligne  3: for (i=0 ; i<NBTHREADS ; i++) {
Ligne  4:   int retcode;
Ligne  5:   pthread_t thread;
Ligne  6:   retcode = pthread_create(&thread, NULL, attenteRequete, (void *)i);
Ligne  7:   if (retcode != 0) {
Ligne  8:     perror("pthread_create");
Ligne  9:     exit(EXIT_FAILURE);
Ligne 10:   }
Ligne 11:   pthread_detach(thread);
Ligne 12: }

/*************/
/* Extrait 5 */
/*************/
Ligne  1: void attenteNaissance(void) {
Ligne  2:   assert(pthread_mutex_lock(&mutexNaissance) >= 0);
Ligne  3:   while (bebeEstNe == FAUX) {
Ligne  4:     assert(pthread_mutex_unlock(&mutexNaissance) >= 0);
Ligne  5:     assert(pthread_cond_wait(&conditionNaissance, &mutexNaissance) >= 0);
Ligne  6:     assert(pthread_mutex_lock(&mutexNaissance) >= 0);
Ligne  7:   }
Ligne  8:   assert(pthread_mutex_lock(&mutexNaissance) >= 0);
Ligne 10: }

/*************/
/* Extrait 6 */
/*************/
Ligne  1: FILE *f;
Ligne  2: char ligne[TAILLEMAX];
Ligne  3: f = popen("programmeExterne", "r");
Ligne  4: if (f == NULL) {
Ligne  5:   perror("popen");
Ligne  6:   exit(EXIT_FAILURE;
Ligne  7: }
Ligne  8: while (feof(f) == 0) {
Ligne  9:   fflush(f);
Ligne 10:   if (fgets(ligne, sizeof(ligne), f) != NULL) {
Ligne 11:     traitement(ligne);
Ligne 12:   }
Ligne 13: }
---beginCorr
Barême : 0,6 point par erreur majeure (c'est une erreur qui ne peut être détectée à la compilation) trouvée (x 8 erreurs), plus précisément 0,2 point pour la localisation et 0,4 point pour la justification.
+ 0,2 point par erreur mineure (c'est une erreur qui peut être détectée à la compilation) (x 3 erreurs)
+ 0,5 point pour ceux qui n'ont pas écrit que l'extrait 1 ne forkait pas NBENFANTS enfants.
avec écrêtage à 4,5 points.
Extrait 1
Il n'y a aucune erreur dans cet extrait qui permet au parent de forker NBENFANTS enfants.
L'absence de définition pour NBENFANTS ne peut être considérée comme une erreur, puisqu'on peut légitimement supposer que cet extrait est précédé du #define qui va bien.
Noter que l'instruction de la ligne 12 (i = NBENFANTS;) permet à l'enfant de sortir de la boucle sans forker lui-même des enfants. Cette instruction modifie un indice de boucle dans une boucle, ce qui est déconseillé en général, mais qui n'est pas remplacable par un break dans le cas présent puisqu'on est dans un switch.
Extrait 2
La définition de la structure n'est pas optimale (elle occupe 16 octets à cause des octets de padding). Pour éviter le padding et donc n'occuper que 12 octets, on peut, par exemple, déclarer :
typedef struct {
  short nbTorchons;
  short nbServiettes;
  int   nbAssiettes;
  int   nbCuillières;
} materielCuisine;
Par ailleurs, ligne 5, erreur mineure : le nom du champ nbCuillières contient un caractère accentué, ce qui posera des problèmes à la compilation.
Extrait 3
Ligne 4, on précise l'option O_SYNC alors que le fichier est O_RDONLY, i.e. on ne fait jamais d'écritures avec ce fichier. Cette instruction O_SYNC est inutile (NB : la moitié des points a été attribuée à ceux qui ont dit que O_SYNC posait problème car ralentissait les écritures).
Ligne 5, il faut fd < 0 au lieu de fd == NULL, sinon on ne risque pas de détecter des retours avec erreur pour open.
Ligne 9, le test d'erreur est incorrect. Il faut mettre : if (rc != sizeof(donnee)).
Extrait 4
Ligne 1, erreur mineure : la fonction devrait retourner un void *.
NB : la définition de attenteRequete pourrait être meilleure pour signaler qu'on lui passera un int en paramêtre (avec un cast en ligne 6 pour le passage en param&eacirc;tre de la fonction). Cela n'a pas été fait pour ne pas embrouiller les étudiants.
Ligne 6, la ligne est correcte, même si on passe i en paramêtre au lieu de &i. Cela nous garantit que le thread travaillera avec une valeur qui lui est propre (sinon il partagera la valeur avec celui qui l'a créé).
Ligne 11, manque le test de retour de pthread_detach
Extrait 5
Les lignes 4 et 6 posent problème. En effet, d'une part, elles sont inutiles vu que le pthread_cond_wait de la ligne 5 fait leur travail. D'autre part, la ligne 4 est dangereuse puisqu'elle ne fait pas le unlock de manière atomique avec le wait. De ce fait, il se peut très bien que le thread déverrouille le mutex en ligne 4, qu'un autre thread prenne la main pour mettre bebeEstNe à VRAI et donc faire un pthread_cond_signal avant que le thread qui a déverrouillé le mutex ne se bloque sur le pthread_cond_wait de la ligne 5 sans prendre en compte le signal. Par ailleurs, le lock de la ligne 6 risque de bloquer le thread puisque le mutex est déjà pris par le pthread_cond_wait.
Ligne 8, il faudrait faire un pthread_mutex_unlock sinon on va bloquer toute l'application.
Lignes 2, 4, 6 et 8 : le test du assert est faux. Les fonctions dans ces assert ne se sont déroulées correctement que quand elles renvoient 0 (NB : ces 4 erreurs ne comptent que comme une erreur majeure).

Extrait 6
popen ouvre un flux en lecture. L'instruction fflush de la ligne 9 est donc superflu.
---endCorr

Question 2 : En voiture (8 points)

Un constructeur automobile vous demande d'écrire un simulateur de sa prochaine usine de construction de voitures. Les composants de cette usine (simplifiée dans la mesure où on n'en simule que la partie "montage des roues") sont :
  • Un  "robot transporteur", simulé à l'aide d'un thread, chargé d'apporter une voiture sur le lieu de montage, d'attendre le montage de ses roues, puis de la retirer avant d'appporter un nouveau véhicule, selon l'algorithme suivant :
robotTransporteur() {
   Faire pour toujours
      apporterVoitureSurLieuMontage();
      signalerVoitureSurLieuMontage();
      attendreMontageRoues();
      retirerVoitureDeLieuMontage();
   Fait;
}
  • Quatre "robots monteur de roues", simulés à l'aide d'un thread par robot, pouvant travailler en parallèle. Chacun de ces robots prend une roue dans un distributeur de roues (partagé entre ces quatre robots), attend qu'un véhicule soit prêt au montage, monte la roue à l'endroit qui lui est assigné (par exemple, avant-gauche), selon l'algorithme suivant :
robotMonteurRoues(Localisation localisationSurVoiture) {
   Faire pour toujours
      Roue roue;
      roue = prendreRoueDansDistributeur();
      attendreVoitureSurLieuMontage(localisationSurVoiture);
      monterRoue(roue, localisationSurVoiture);
      signalerMontageDUneRoueTermine();
   Fait;
}
  • Un "robot chargeur", simulé à l'aide d'un thread, responsable de mettre des roues dans le distributeur selon l'algorithme suivant :
robotChargeur() {
   Faire pour toujours
      mettreRoueDansDistributeur(nouvelleRoue());
   Fait;
}
  • Un "distributeur", simulé à l'aide d'un tableau tabRoue de MAXROUES éléments de type Roue. Le chargement de roues se fait dans l'ordre des cases tabRoue[0], tabRoue[1]... tabRoue[MAXROUES-1], tabRoue[0]... La prise de roue est également réalisée dans l'ordre tabRoue[0], tabRoue[1]... tabRoue[MAXROUES-1], tabRoue[0]...
    Noter que mettreRoueDansDistributeur() attend si aucune case de tabRoue n'est libre et prendreRoueDansDistributeur() attend si aucune case de tabRoue ne contient de roue.
NB : pour la question 2.1 (respectivement 2.2), vous pouvez répondre sur votre copie ou bien dans le fichier Q2/reponse21.txt (respectivement Q2/reponse22.txt). Dans ce dernier cas, indiquez sur votre copie "Réponse dans Q2/reponse21.txt" (respectivement "Réponse dans Q2/reponse22.txt" )

Question 2.1 : Identification des paradigmes (3 points)

Indiquez les différents types de problème de synchronisation auquel vous allez être confrontés pour implémenter ce simulateur (exclusion mutuelle, cohorte, producteur/consommateur...) en précisant, pour chaque problème, ses acteurs (par exemple, si vous trouvez qu'il y a un paradigme de lecteurs/rédacteur dans lequel intervient le "robot chargeur", vous devez préciser si le "robot chargeur" est lecteur ou rédacteur).
---beginCorr
Barême : 1 point par paradigme (x 3 paradigmes) répartis en 0,5 point pour le paradigme et 0,5 pour la justification. NB : donner 0,5 points pour les étudiants qui ont parlé de cohorte entre le "robot transporteur" et les "robots monteur".

Quand il a fini d'apporter une voiture sur le lieu de montage, le "robot transporteur" doit envoyer un signal à chacun des "robots monteur de roue". Noter que ce signal est spécifique à chaque "robot monteur" car chacun de ces robots est sp&eactue;cialisé (on ne peut pas se permettre d'avoir une cohorte de 4 "robots monteur" car on a le risque que ce soit 4 fois le même "robot monteur" qui monte une roue sur la même voiture).
Quand le montage des roues est terminé, i faut que le dernier "robot monteur" qui a fini de monter sa roue envoie un signal au "robot transporteur" pour qu'il retire la voiture du lieu de montage.
La gestion du "distributeur" est un problème de producteur/consommateur avec un producteur (le "robot chargeur") et 4 consommateurs (les "robots monteurs").
---endCorr

Question 2.2 : Conception à l'aide de sémaphores (5 points)

À l'aide de sémaphores (munis de leurs opérations P() et V()) et de variables que vous déclarerez de manière globale (i.e. ils seront accessibles à partir de n'importe quelle procédure/fonction de votre programme) et initialiserez, écrivez les algorithmes suivants :
  • Procédure attendreMontageRoues()
  • Procédure attendreVoitureSurLieuMontage(Localisation localisationSurVoiture)
  • Procédure mettreRoueDansDistributeur(Roue uneRoue)
  • Fonction prendreRoueDansDistributeur() qui renvoie une entité de type Roue
  • Procédure signalerMontageDUneRoueTermine()
  • Procédure signalerVoitureSurLieuMontage()
---beginCorr
Barême : 0,7 point par algorithme correct (x 6 algo) et 0,1 point par initialisation correcte (x 9 initialisations avec un maximum de 0,8 points).
InitialisationSémaphore(attenteMontageRoues,0);
/* On suppose que Localisation est un type enumere avec les valeurs */
/* AvGa (i.e. Avant-Gauche), AvDr, ArGa et ArDr                     */

/* On initialise attenteVoitureSurLieuMontage qui est un tableau de */
/* 4 semaphores                                                     */
InitialisationSémaphore(attenteVoitureSurLieuMontage[AvGa],0);
InitialisationSémaphore(attenteVoitureSurLieuMontage[AvDr],0);
InitialisationSémaphore(attenteVoitureSurLieuMontage[ArGa],0);
InitialisationSémaphore(attenteVoitureSurLieuMontage[ArDr],0);

InitialisationSémaphore(placeDispo,MAXROUES);
InitialisationSémaphore(rouePrête,0);
InitialisationSémaphore(mutex,0);
InitialisationSémaphore(mutexC,0);
iDépot = 0;
iExtrait = 0;

attendreMontageRoues(){
  P(attenteMontageRoues);
}

attendreVoitureSurLieuMontage(Localisation localisationSurVoiture){
  P(attenteVoitureSurLieuMontage[localisationSurVoiture]);
}

mettreRoueDansDistributeur(Roue uneRoue){
  P(placeDispo);
  tabRoue[iDépot] = uneRoue;
  iDépot = (iDépot + 1) modulo MAXROUES;
  V(rouePrête);
}

Roue prendreRoueDansDistributeur() {
  Roue roue;
  P(rouePrete);
  P(mutexC);
  roue = tabRoue[iExtrait];
  iExtrait = (iExtrait + 1) modulo MAXROUES;
  V(mutexC);
  V(placeDispo);
  return roue;
}

signalerMontageDUneRoueTermine() {
  P(mutex);
  roueMontées = roueMontées + 1;
  si roueMontées = 4 alors
    V(attenteMontageRoues);
    rouesMontées = 0;
  finsi
  V(mutex);
}

signalerVoitureSurLieuMontage() {
  /* On signale aux *4* "robots monteur de roue" que la voiture */
  /* est disponible                                             */
  /* NB : faire directement                                     */
  /*        V(attenteVoitureSurLieuMontage);                    */
  /*        V(attenteVoitureSurLieuMontage);                    */
  /*        V(attenteVoitureSurLieuMontage);                    */
  /*        V(attenteVoitureSurLieuMontage);                    */
  /*      n'est pas bon, car il se pourrait que le thread       */
  /*      associe a une roue profite de ces 4 V pour essayer de */
  /*      monter 4 roue au meme endroit d'une voiture !         */
  V(attenteVoitureSurLieuMontage[AvGa]);
  V(attenteVoitureSurLieuMontage[AvDr]);
  V(attenteVoitureSurLieuMontage[ArGa]);
  V(attenteVoitureSurLieuMontage[ArDr]);
}

NB : La variante suivante permet de se passer de mutex et de roueMontées. 
attendreMontageRoues(){
  P(attenteMontageRoues);
  P(attenteMontageRoues);
  P(attenteMontageRoues);
  P(attenteMontageRoues);
}

signalerMontageDUneRoueTermine() {
  V(attenteMontageRoues);
}
---endCorr

Question 3 : Toujours plus de "M. et Mme" (7,5 points)

Pour cette question, vous avez à votre disposition :
  • Un serveur de "M. et Mme" constitué d'un processus distributeur et de 26 processus enfants, chacun de ces derniers étant chargé des "M. et Mme" commençant par une certaine lettre de l'alphabet :
    • Chaque enfant cherche, dans le fichier, la première et la dernière ligne commençant par sa lettre.
    • Sur réception d'une requête, le distributeur fait suivre la requête à l'enfant correspondant à la 1-ère lettre du "M. et Mme" :
      • L'enfant ne cherche que dans les lignes qui le concernent ;
      • Il répond au client  ;
      • Il attend une requête du processus distributeur.
    (Certains reconnaîtront à raison le serveur développé à la question 6 de l'exercice 1 des exercices Client/Serveur).
  • Un client capable d'interroger ce serveur.
L'objectif de cette question est de développer une application ajout qui permette d'ajouter dynamiquement des "M. et Mme" au fichier mEtMme.txt en respectant les spécifications suivantes :
  • ajout ne peut ajouter que quand il est sûr qu'aucun enfant du serveur n'est en train de répondre à une requête de "M. et Mme".
  • ajout doit insérer le "M. et Mme" fourni en paramètre au bon endroit dans le fichier (qui est classé alphabétiquement).
  • Quand ajout souhaite insérer un "M. et Mme", il n'y a aucun risque qu'il attende indéfiniment que des enfants du serveur traitent des requêtes de "M. et Mme".
Ceci va entraîner des modifications dans le fichier ajout.c, mais aussi dans le fichier serveur.c. En effet, les processus enfants sont impactés dans la mesure où :
  • Quand ajout insère un nouveau "M. et Mme", les enfants attendent qu'ajout ait fini avant de recommencer à traiter des requêtes de "M. et Mme".
  • Après une insertion d'ajout, avant de recommencer à traiter des requêtes de "M. et Mme", les enfants commencent par réinitialiser la position de la première et de la dernière ligne commençant par la lettre dont ils sont responsables.
Travail demandé :
  1. Indiquez le principe de votre solution sur votre copie ou bien dans le fichier principe.txt (dans ce dernier cas, précisez sur votre copie "Réponse dans Q3/principe.txt).
  2. Modifiez les fichiers ajout.c et serveur.c pour obtenir l'ajout dynamique de "M. et Mme".
NB : Pour cette question, il y a 3 problèmes à résoudre (classés par ordre de difficulté croissante) :
  1. la synchronisation entre ajout et les enfants du serveur,
  2. la mise-à-jour de mEtMme.txt par ajout,
  3. la réinitialisation des enfants
Il est recommandé de les traiter dans cet ordre et de vérifier qu'un problème est traité avant de passer à la résolution du problème suivant (pour information, les 3 problèmes seront notés indépendamment les uns des autres).
---beginCorr
Barême :
  • Principes (3,5 points) :
    • 2 points pour lecteur/rédacteur avec famine (seulement 1,5 point si sans famine et 1 point si paradigme proposé=exclusion mutuelle)
    • 1 point pour principe mise-à-jour fichier
    • 0,5 point pour le principe de réinitialisation des enfants
  • 3 points pour la mise en oeuvre du lecteur/rédacteur :
    • 1 pour la crétion/initialisation des sémaphores)
    • 1 point pour la mise en place de la mémoire partagée
    • 1 point pour la mise en place des différents P() et V()
  • 1 point pour la mise-à-jour du fichier
  • 1 point (de bonus) pour la réinitialisation des enfants après un ajout
  • 0,5 points (de bonus) pour la propreté (commentaires, indentation...)
  • 0,5 points (de bonus) pour le traitement des erreurs

Principe de solution
Synchronisation entre ajout et les enfants du serveur

C'est un problème de lecteur/rédacteur (avec évitement de famine), les lecteurs étant les enfants, le rédacteur étant ajout.

Mise-à-jour de mEtMme.txt par ajout

L'algorithme est le suivant : 
ajoutDansFic(char *mEtMme){
  int offsetMEtMme = calculOffsetOuPlacerMEtMme(mEtMme);
  decalerDansFicLesOctetsAPartirOffset(offsetMEtMme, strlen(mEtMme));
  sePositionnerEn(offsetMEtMme);
  ecrireDansFichier(mEtMme);
}

decalerDansFicLesOctetsAPartirOffset(int offsetMEtMme, int decalage){
  int positionPremierOctetADecaler = offsetDernierOctetFichier();
        /* on peut l'obtenir en regardant, par exemple, le resultat */
        /* de lseek(fd, 0, SEEK_END)                                */
  int tailleADecaler;
  #define TAILLEMAXBUFFER 4096
  char buffer[TAILLEMAXBUFFER];
  TANTQUE positionPremierOctetADecaler > offsetMEtMme FAIRE
    tailleADecaler = minimum(positionPremierOctetADecaler-offsetMEtMme, TAILLEMAXBLOC);
    positionPremierOctetADecaler -= tailleADecaler;
    sePositionnerEn(positionPremierOctetADecaler);
    lire(fd, buffer, tailleADecaler);
    sePositionnerEn(positionPremierOctetADecaler+decalage);
    ecrire(fd, buffer, tailleADecaler);
  FINTANTQUE
}
On peut envisager des variantes vu que le fichier mEtMme.txt n'est pas grand :
  • On lit chaque ligne du fichier dans une ligne d'un tableau de caractères. Puis, on fait l'insertion dans ce tableau avant d'écrire ce tableau mis-à-jour dans le fichier.
  • On stocke les lignes qui doivent être décalées dans un fichier temporaire. On écrit le nouveau mEtMme dans mEtMme.txt, puis on recopie le fichier temporaire dans mEtMme.txt.
Réinitialisation des enfants

Pour l'aspect réinitialisation :
  • On a besoin d'une variable partagée (appelée numVersionFichier) entre ajout et les enfants. Cette variable est créée par le main du serveur et initialisée à 1.
  • Chaque enfant a une variable (locale) dernierNumVersionFichierLu initialisée à 0.
  • Quand ajout s'exécute, il incrémente numVersionFichier de 1 (en veillant qu'il ne prenne jamais la valeur 0).
  • Quand un enfant s'apprête à lire mEtMme.txt suite à une requête, une fois qu'il a acquis le sémaphore signifiant qu'il va pouvoir lire, il déroule l'algorithme suivant :
Si dernierNumVersionFichierLu != numVersionFichier Alors
   faireLaRéinitialisation();
   dernierNumVersionFichierLu = numVersionFichier;
FinSi
Codage
ajout-serveur.corrige.h
ajout.corrige.c
serveur.corrige.c
---endCorr

Page mise à jour le 15 mai 2006