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é CSC4508/M2 du 25/05/07

Corrigés

Modalités

Durée : 3 heures

Tous documents autorisés.

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 remise de votre copie à l'enseignant et 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 TPNote2007

Préparation

cd votreRepertoireDeTravailPourCSC4508M2
cp ~simatic/Cours/CSC4508/tPNote2007.tgz .
tar xvfz tPNote2007.tgz
cd TPNote2007

Question 1 : Files d'attente de sémaphore et priorité de processus (4 points)

Pour chacune des questions ci-dessous, répondez sur votre copie ou bien dans le fichier Q1/reponse1.txt (dans ce dernier cas, indiquez sur votre copie « Réponse dans Q1/reponse1.txt » ).

Chaque objet système sémaphore comprend une file d'attente des processus qui ont fait une opération P() et attendent qu'un autre processus fasse une opération V().
À l'aide de deux expériences, cet exercice cherche à prouver que cette file d'attente ne prend en compte ni les priorités statiques, ni les priorités dynamiques des processus qui sont en attente sur ce sémaphore. Dit autrement, en cas d'opération V(), ce n'est pas le processus en attente le plus prioritaire (statiquement ou dynamiquement) qui est réveillé en premier.

Question 1.1 : Expérience avec des processus à priorités statiques différentes (2 points)

On décide de s'appuyer sur le code du fichier  Q1/testSemaphoreEtPrioriteStatique.c listé ci-dessous :

/*************************************/
/* testSemaphoreEtPrioriteStatique.c */
/*************************************/

#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <sched.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <sys/ipc.h>
#include <sys/sem.h>

#define FATAL(msg) {\
  char m[128];       \
  sprintf(m, "%s in %s:%d:%s", msg, __FILE__, __LINE__, __func__); \
  perror(m); \
  abort(); \
}

/**********************************************************************/
/* Code de P et V                                                     */
/**********************************************************************/
void P(int semId){
  struct sembuf op;
  op.sem_num =  0;
  op.sem_op  = -1;
  op.sem_flg =  0;
  if (semop(semId, &op, 1) == -1){
    FATAL("semop");
  }
}

void V(int semId){
  struct sembuf op = {0, 1, 0};
  if (semop(semId, &op, 1) == -1){
    FATAL("semop");
  }
}

/**********************************************************************/
/* Code execute par les processus enfant                              */
/**********************************************************************/
void codeEnfant(int numEnfant, int semId)
{
  struct sched_param sp;

  /* Section de Code 1 (SC1) */
  sp.sched_priority = numEnfant;
  if (sched_setscheduler(0,SCHED_FIFO,&sp) < 0) {
    FATAL("sched_setscheduler");
  }

  /* Section de Code 2 (SC2) */
  sleep(numEnfant);

  /* Section de Code 3 (SC3) */
  P(semId);

  /* Section de Code 4 (SC4) */
  printf("Enfant %d s'est reveille !\n", numEnfant);

  exit(EXIT_SUCCESS);
}

/**********************************************************************/
/* Programme principal                                                */
/**********************************************************************/
int main(int argc, char* argv[])
{
  int status;
  key_t cle;
  int i;
  int semId;

 
  /* Section de Code 5 (SC5) */
  cle = ftok("./testSemaphoreEtPrioriteStatique.c", '0');
  if (cle < 0) {
    FATAL("ftok");
  }
  semId = semget(cle, 1, IPC_CREAT|0666);
  if (semId < 0) {
    FATAL("semget");
  }
  if (semctl(semId, 0, SETVAL, 0) < 0) {
    FATAL("semctl");
  }

  /* Section de Code 6 (SC6) */
  for (i=1 ; i<4 ; i++){
    switch (fork()) {
    case -1:
      FATAL("fork");
      break;
    case 0:
      codeEnfant(i, semId);
      break;
    default:
      break;
    }
  }

  /* Section de Code 7 (SC7) */
  sleep(4);

  /* Section de Code 8 (SC8) */
  for (i=1 ; i<4 ; i++){
    V(semId);
    if (wait(&status) < 0){
      FATAL("wait");
    }
  }

  /* Section de Code 9 (SC9) */
  if (semctl(semId, 0, IPC_RMID, 0) < 0){
    FATAL("semctl");
  }

  return EXIT_SUCCESS;
}

Décrivez l'expérience réalisée avec ce code.

A l'exécution, on obtient l'affichage suivant :

Enfant 1 s'est reveille !
Enfant 2 s'est reveille !
Enfant 3 s'est reveille !

Qu'en concluez-vous ?

Question 1.2 : Expérience avec des processus à priorités dynamiques différentes (2 points)

Modifiez le fichier Q1/testSemaphoreEtPrioriteDynamique.c (qui, pour l'instant, est une copie conforme de Q1/testSemaphoreEtPrioriteStatique.c) pour adapter l'expérience de la question 1.1 au cas de processus avec des priorités dynamiques.

Compilez Q1/testSemaphoreEtPrioriteDynamique.c
Exécutez Q1/testSemaphoreEtPrioriteDynamique
Sur votre copie ou bien dans le fichier Q1/reponse1.txt, indiquez l'affichage obtenu et votre conclusion.

Question 2 : Des threads pour un moteur (4 points)

Pour chacune des questions ci-dessous, répondez sur votre copie ou bien dans le fichier Q2/reponse2.txt (dans ce dernier cas, indiquez sur votre copie « Réponse dans Q2/reponse2.txt »).

Le but du programme Q2/indexation.c est de créer un moteur d'indexation parcourant une arborescence de documents. Voici son listing :

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/types.h>
#include <dirent.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#define NBMAXDOCS 20
#define MAXDIRNAME 80

int nbDocIndexes = 0;
int nbThreads = 0;
char docname[MAXDIRNAME];
char dirname[MAXDIRNAME];

void *indexer_document(void *arg)
{
  char *docname = (char *)arg;
  printf("Debut indexer document =%s\n", docname);

  sleep(3);

  printf("Fin indexer document =%s\n", docname);
  nbDocIndexes ++;
  pthread_exit(NULL);
}


void indexer_repertoire(DIR *dir)
{

  struct dirent *entry;

  pthread_t thread;
  int rc, i = 0;

  do {
    entry = readdir(dir);
    if (entry == NULL)
      break;

    strcpy(docname, entry->d_name);

   
    nbThreads ++;
    rc = pthread_create(&thread, NULL, indexer_document, docname);

    if (rc){
      perror("pthread_create");
      exit(EXIT_FAILURE);
    }
    i++;
   
  } while (i < NBMAXDOCS);

  if (i == NBMAXDOCS){
      fprintf(stderr, "Indexation incomplete: le nombre de documents est superieur a NBMAXDOCS (%d)\n", NBMAXDOCS);
  }
}


int main(int argc, char **argv){
  DIR *directory;
  int i;
 
  if (argc < 2){
      fprintf(stderr, "Usage: %s listeRepertoires\n", argv[0]);
      exit(EXIT_FAILURE);
  }


  for (i = 1; i < argc; i++){
      assert(strlen(argv[i]) < MAXDIRNAME);
      strcpy(dirname, argv[i]);

      directory = opendir(dirname);
      if (directory == NULL){
        perror("opendir");
        exit(EXIT_FAILURE);
      }

      indexer_repertoire(directory);
      closedir(directory); 
    }

  printf("Le nombre de threads crees est = %d\n", nbThreads);

  printf("Le nombre de documents indexes est = %d\n", nbDocIndexes);

  exit(EXIT_SUCCESS);
}

Question 2.1 : Analyse du code (2 points)

  • Combien de threads sont créés?
  • Quel est le rôle de chaque thread?
  • Combien de threads font appel à la fonction readdir()?
  • Précisez pour chacune des variables globales si ces variables sont accédées par un ou plusieurs threads. Expliquez.

Question 2.2 : Débuggage du code

Ce code ne s'exécute pas correctement. Il contient 4 erreurs. Donnez chacune des erreurs et proposez un principe de correction (sur votre copie ou dans le fichier Q2/reponse2.txt ; NB : ne modifiez pas le fichier Q2/indexation.c : il ne sera pas corrigé !).

Question 3 : BoursINT (garanti sans ail, ni fines herbes ;-) ) (12 points)

Pour chacune des questions ci-dessous, répondez sur votre copie ou bien dans le fichier Q3/reponse3.txt (dans ce dernier cas, indiquez sur votre copie « Réponse dans Q3/reponse3.txt »).

BoursINT, le club Bourse de l'INT, a décidé d'automatiser sa surveillance des différentes salles de marché avec lesquelles il travaille. L'idée est d'avoir une application constituée de N+1 tâches et d'un tableau t de N doubles partagé entre les N+1 tâches :
  • N tâches (nommées Si [comme Surveillant] dans la suite) sont chargées de surveiller chacune une salle de marché (Paris, Londres, New York...). Chaque tâche Si calcule plus ou moins rapidement le résultat de la séance (sous la forme d'un nombre réel indiquant la tendance -en pourcentage de hausse ou de baisse- des valeurs dans cette salle). Une fois son calcul effectué, elle écrit ce résultat dans la iè case du tableau t.
  • Quand les N tâches de surveillance ont chacune écrit leur case de tableau, elles préviennent la N+1è tâche (nommée A [comme Afficheur] dans la suite) qu'elle doit s'exécuter pour afficher la moyenne des valeurs du tableau t. Les tâches Si se mettent alors en attente jusqu'à ce que la tâche A leur indique qu'elle a terminé son calcul de moyenne. Elles redémarrent alors leur surveillance.

Question 3.1 : Identification des paradigmes (1,5 point)

Indiquez les différents types de problème de synchronisation auxquels vous êtes confrontés pour implémenter cette application (exclusion mutuelle, cohorte, producteur/consommateur...) en précisant, pour chaque problème, ses acteurs.

Question 3.2 : Conception à l'aide de sémaphores (4 points)

Le club BoursINT a commencé à écrire les algorithmes :

Variables globales
==================
// Tableau permettant la communication entre les tâches
// Surveillant et la tâche Afficheur
t Tableau[1..N] de doubles
// Variables associées aux paradigmes de type Signal
Sémaphore topAfficheur initialisé à ? // A completer
Sémaphore topSurveillant initialisé à ? // A completer
// A completer (eventuellement)

Tache Surveillanti
==================
faire
  t[i]=surveiller(i)
  // A completer
tant que VRAI

Tache Afficheur
===============
faire
  P(topAfficheur)
  Ecrire "Moyenne = ", moyenne(t)
  pour i=1:Entier à N faire
    V(topSurveillant)
  fpour i
tant que VRAI

Compléter les déclarations de variables globales et le(s) algorithme(s) (en particulier, tous les commentaires « // A completer » doivent disparaître) pour répondre au problème posé.
NB :
  • Si jamais vous avez besoin d'autres sémaphores, essayez de vous limiter à un seul sémaphore supplémentaire.
  • Vous pouvez modifier l'algorithme de la tâche Afficheur si vous en éprouvez le besoin.
  • Sous sa forme actuelle, l'algorithme de la tâche Afficheur comprend une anomalie si la file d'attente associée aux sémaphores n'est pas FIFO. Ne vous préoccupez pas de cette anomalie dans cette question (elle sera traitée à la question 3.4)

Question 3.3 : Codage (5 points)

Dans le fichier Q3/boursINT.c, implémentez les algorithmes de la question 3.2, en prenant N égal à 9 et en utilisant des processus enfants.

Pour les tâches Si, la fonction surveiller est fournie dans le fichier (son résultat est à stocker dans la case concernée du tableau t).

Seront notés pour cette question :
  • Le fait que, à l'exécution, le code répond correctement au problème posé,
  • La clarté du code,
  • Le fait que le code compile (sans warning),
  • 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.

Question 3.4 : Correction de l'anomalie de la question 3.2 (1,5 points)

Les algorithmes conçus à la question 3.2 ne fonctionnent correctement que si on suppose que les sémaphores ont une liste d'attente associée de type FIFO.

Donnez un exemple de ce qui pourrait arriver avec l'algorithme de la question 3.2 si la liste d'attente n'était pas FIFO. Expliquez notamment le dysfonctionnement résultant.

En utilisant au plus 4 sémaphores, écrivez des algorithmes qui fonctionnent même si les listes d'attente associées au sémaphore ne sont pas FIFO.

Question (bonus) 3.5 : Reprise de la question 3.4 avec des objets de synchronisation threads (bonus de 2 points)

Reprendre le problème de la question 3.4, à l'aide d'objets de synchronisation thread (mutex avec les opérations pthread_mutex_lock et pthread_mutex_unlock et conditions avec les opérations pthread_cond_wait, pthread_cond_signal et éventuellement pthread_cond_broadcast).



Page mise à jour le 24 mai 2007