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

(2è session)

(Corrigés)

Modalités

Durée : 1 heure 30

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 1 heure 30 ») du fichier d'extension tgz constitué de la manière suivante :
cd votreRepertoireDeTravailPourCSC4508M2
tar cvfz $USER.tgz TPNote2007Session2

Préparation

cd votreRepertoireDeTravailPourCSC4508M2
cp ~silber/Cours/CSC4508/tPNote2007Session2.tgz .
tar xvfz tPNote2007Session2.tgz
cd TPNote2007Session2

Question 1 : Verrou pour la banque (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 » ).

Pour l'exercice hors présentiel Entrées-Sorties #7 (Gestion d'une banque), on souhaite écrire une procédure qui se charge de mettre à jour le solde d'un compte.

Trois versions sont envisagées :
 








 void majCompteVersion1(int fd, int numCompte, typSolde nouveauSolde){
verrou.l_type = F_WRLCK;
verrou.l_whence = SEEK_SET;
verrou.l_start = numCompte*sizeof(typSolde);
verrou.l_len = sizeof(typSolde);
assert(fcntl(fd, F_SETLKW, &verrou) >= 0);

assert( lseek(fd, numCompte*sizeof(typSolde), SEEK_SET) >= 0);

assert(write(fd, &solde, sizeof(typSolde)) == sizeof(typSolde));

verrou.l_type = F_UNLCK;
assert(fcntl(fd, F_SETLK, &verrou) >= 0);
 }
 
void majCompteVersion2(int fd, int numCompte, typSolde nouveauSolde){
verrou.l_type = F_WRLCK;
verrou.l_whence = SEEK_SET;
verrou.l_start = 0;
verrou.l_len = 0; /* Ce 0 signifie "jusqu'a la fin du fichier" */
assert(fcntl(fd, F_SETLKW, &verrou) >= 0);

assert( lseek(fd, numCompte*sizeof(typSolde), SEEK_SET) >= 0);

assert(write(fd, &solde, sizeof(typSolde)) == sizeof(typSolde));

verrou.l_type = F_UNLCK;
assert(fcntl(fd, F_SETLK, &verrou) >= 0);
 }
 
void majCompteVersion3(int fd, int numCompte, typSolde nouveauSolde){
assert( lseek(fd, numCompte*sizeof(typSolde), SEEK_SET) >= 0);

verrou.l_type = F_WRLCK;
verrou.l_whence = SEEK_SET;
verrou.l_start = numCompte*sizeof(typSolde);
verrou.l_len = sizeof(typSolde);
assert(fcntl(fd, F_SETLKW, &verrou) >= 0);
);

assert(write(fd, &solde, sizeof(typSolde)) == sizeof(typSolde));

verrou.l_type = F_UNLCK;
assert(fcntl(fd, F_SETLK, &verrou) >= 0);
 }

Quelle version de procédure permet d'avoir le plus de mise-à-jour simultanées sur le fichier des comptes ? Justifier votre réponse.
Quelle version de procédure réduit le plus le nombre de mise-à-jour simultanées sur le fichier des comptes ? Justifier votre réponse.






---beginCorr
Barême : 2 points par réponse (avec la justification correcte).

C'est majCompte3 qui permet d'avoir le plus de mise-à-jour simultanées sur le fichier des comptes. En effet, elle permet de ne verrouiller que l'enregistrement concerné. En plus, elle ne le fait qu'au moment du write (alors que majCompte1 le fait aussi pendant son lseek !).
C'est majCompte2 qui réduit le plus le nombre de mise-à-jour simultanées sur le fichier des comptes. En effet, elle verrouille systématiquement l'ensemble du fichier pour faire une mise-à-jour : aucune concurrence n'est possible.
---endCorr

Question 2 : Lecteur/rédacteur et impression, le retour (7 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 »).

On considère l'exercice hors présentiel Communication inter-processus/Synchronisation entre processus #6 (Lecteur/rédacteur et impression). Pour cette application, le corrigé propose que :
  • le serveur d'impression et ses clients soient considérés comme des rédacteurs de la zone de mémoire partagée où sont stockés les noms de fichier à imprimer (puisqu'ils modifient le contenu de cette zone) ;
  • les différentes instances de l'application de consultation de la liste des fichiers à imprimer soient considérées comme des lecteurs de la zone de mémoire partagée où sont stockés les noms de fichier à imprimer (puisqu'elles ne font que lire le contenu de cette zone).
De ce fait, les algorihtmes suivants sont proposés :

Variables globales
==================
fichiersAImprimer Tableau[0..NBMAXNOMFIC - 1] de chaîne de caractères
iExtrait Entier = 0
iDepot Entier = 0
// Données liées à la synchronisation Producteurs/Consommateur
Sémaphore placeDispo initialisé à NBMAXNOMFIC
Sémaphore infoPrete initialisé à 0
Sémaphore mutexP initialisé à 1
// Données liées à la synchronisation Lecteurs/Rédacteurs
nbLec Entier = 0
Sémaphore mutexL initialisé à 1
Sémaphore fifo initialisé à 1
Sémaphore mutexG initialisé à 1

Tâche serveur
=============
  faire
    P(fifo);
    P(mutexG);
    V(fifo);

    P(infoPrete);
    impression(fichiersAImprimer[shm->iExtrait]);
    V(placeDispo);
    iExtrait = (iExtrait+1) % NBMAXNOMFIC;

    V(mutexG);
  tant que VRAI
 













Tâche client
============
  faire
    afficherALEcran("Nom du fichier a imprimer (taper '0' pour terminer) ? ");
    lireAuClavier(nomFic);
    si (nomFic est égal à la chaîne "0") alors
      arrêter la tâche
    finsi
    P(fifo);
    P(mutexG);
    V(fifo);

    P(placeDispo);
    P(mutexP);
    fichiersAImprimer[shm->iDepot] = nomFic;
    iDepot = (iDepot + 1) % NBMAXNOMFIC;
    V(mutexP);
    V(infoPrete);

    V(mutexG);
  tant que VRAI

Tâche consultant
================
  P(fifo);
  P(mutexL);
  nbLec += 1;
  if (nbLec == 1) {
    P(mutexG);
  }
  V(mutexL);
  V(fifo);
  affichageTravauxEnAttente();
  P(mutexL);
  nbLec -= 1;
  if (nbLec == 0) {
    V(mutexG);
  }
  V(mutexL);

Question 2.1 : Où on se rend compte que le corrigé n'est pas très astucieux (2 points)

Les algorithmes ci-dessus ne permettent pas au serveur de retirer un nom de fichier de fichiersAImprimer pendant que simultanément des clients ajoutent des noms de fichiers. Expliquez pourquoi.
---beginCorr
Barême : 2 points pour l'explication

Les clients et le serveur sont des rédacteurs dans le paradigme Lecteurs/Rédacteurs qu'on a mis en place. Or, il y a exclusion mutuelle entre les rédacteurs : ils ne peuvent pas s'exécuter en même temps.
---endCorr

Question 2.2 : Vers un corrigé plus astucieux (5 points)

Modifiez les algorithmes ci-dessus pour faire évoluer l'implémentation du lecteur/rédacteur de sorte que le serveur puisse s'exécuter en parallèle de clients quand il n'y a aucune application de consultation en train de s'exécuter.
---beginCorr
Barême :
  • 0,5 point pour la variable supplémentaire
  • 0,5 point pour le sémaphore supplémentaire
  • 1,5 pour l'algorithme correct au niveau du serveur
  • 1,5 pour l'algorithme correct au niveau du client
  • 1 point pour signaler que la tâche consultant est inchangée.
Les applications de consultation sont des lecteurs que nous appelerons "lecteurs du groupe de lecteurs 1" dans la suite.
Il faut mettre en place un mécanisme qui permette au serveur et aux clients de se comporter comme "lecteurs du groupe de lecteurs 2", les lecteurs d'un même groupe pouvant lire en même temps, mais un lecteur du groupe 1 ne pouvant pas lire en même temps qu'un lecteur du groupe 2. Seuls les algorithmes de la tâche serveur  et des tâches client changent (la tâche consultant est inchangée).

Variables globales
==================
fichiersAImprimer Tableau[0..NBMAXNOMFIC - 1] de chaîne de caractères
iExtrait Entier = 0
iDepot Entier = 0
// Données liées à la synchronisation Producteurs/Consommateur
Sémaphore placeDispo initialisé à NBMAXNOMFIC
Sémaphore infoPrete initialisé à 0
Sémaphore mutexP initialisé à 1
// Données liées à la synchronisation Lecteurs/Rédacteurs
nbLec Entier = 0
Sémaphore mutexL initialisé à 1
Sémaphore fifo initialisé à 1
Sémaphore mutexG initialisé à 1

nbLecGroupe2 Entier = 0
Sémaphore mutexLGroupe2 initialisé à 1

Tâche serveur
=============
  faire

    P(fifo);
    P(mutexLGroupe2);
    nbLecGroupe2 += 1;
    if (nbLecGroupe2 == 1) {
      P(mutexG);
    }
    V(mutexLGroupe2);
    V(fifo);

    P(infoPrete);
    impression(fichiersAImprimer[shm->iExtrait]);
    V(placeDispo);
    iExtrait = (iExtrait+1) % NBMAXNOMFIC;

    P(mutexLGroupe2);
    nbLecGroupe2 -= 1;
    if (nbLecGroupe2 == 0) {
      V(mutexG);
    }
    V(mutexLGroupe2);
  tant que VRAI
 
Tâche client
============
  faire
    afficherALEcran("Nom du fichier a imprimer (taper '0' pour terminer) ? ");
    lireAuClavier(nomFic);
    si (nomFic est égal à la chaîne "0") alors
      arrêter la tâche
    finsi
    P(fifo);
    P(mutexLGroupe2);
    nbLecGroupe2 += 1;
    if (nbLecGroupe2 == 1) {
      P(mutexG);
    }
    V(mutexLGroupe2);
    V(fifo);

    P(placeDispo);
    P(mutexP);
    fichiersAImprimer[shm->iDepot] = nomFic;
    iDepot = (iDepot + 1) % NBMAXNOMFIC;
    V(mutexP);
    V(infoPrete);

     P(mutexLGroupe2);
    nbLecGroupe2 -= 1;
    if (nbLecGroupe2 == 0) {
      V(mutexG);
    }
    V(mutexLGroupe2);
  tant que VRAI
---endCorr

Question 3 : Somme des n premiers entiers (9 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 »).

Le code du fichier sommeEntier.c calcule la somme des n premiers entiers, n étant fourni en argument du programme.


#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

typedef struct {
  int donnee;
  int resultat;
} typSomme;


void *calculSomme(void *arg)
{
  if (((typSomme *)arg)->donnee == 1){
    ((typSomme *)arg)->resultat = 1;
  }else{
    typSomme ts;
    pthread_t thread;
    int rc;

    ts.donnee = ((typSomme *)arg)->donnee - 1;
    rc = pthread_create(&thread, NULL, calculSomme, &ts);
    if (rc){
    perror("pthread_create");
    fprintf(stderr, "((typSomme *)arg)->donnee valait %d\n",
               ((typSomme *)arg)->donnee);
    exit(EXIT_FAILURE);
    }
    rc = pthread_join(thread, NULL);
    ((typSomme *)arg)->resultat = ((typSomme *)arg)->donnee + ts.resultat;   
  }

  pthread_exit(NULL);
}

int main(int argc, char **argv)
{
  int n;
  typSomme ts;
  pthread_t thread;
  int rc;
 
  if (argc < 2)
    {
      fprintf(stderr, "Usage: %s entierStrictementPositif\n", argv[0]);
      exit(EXIT_FAILURE);
    }
 
  n = atoi(argv[1]);
  if (n <= 0){
    fprintf(stderr, "Usage: %s entierStrictementPositif\n", argv[0]);
    exit(EXIT_FAILURE);
  }
 
  ts.donnee = n;
  rc = pthread_create(&thread, NULL, calculSomme, &ts);
  if (rc){
    perror("pthread_create");
    exit(EXIT_FAILURE);
  }
  rc = pthread_join(thread, NULL);

  printf("Somme des %d premiers entiers = %d\n", n, ts.resultat);
  return EXIT_SUCCESS;
}

Question 3.1 : Fonctionnement du programme (3 points)

Expliquez le fonctionnement de ce programme.
---beginCorr
Barême :
  • 1,5 points pour l'explication de la récursion
  • 1 point pour l'explication de la condition d'arrêt de la récursion
  • 0,5 point pour l'explication de l'endroit où est stocké le résultat de l'exécution d'une thread
On fait une récursion en lançant un thread à chaque étape de la récursion :
  • Le premier thread calcule (n) + (somme des n-1 premiers entiers calculée par le 2è thread et trouvée dans ts.resultat).
  • Le 2è thread calcule (n-1) + (somme des n-1 premiers entiers calculée par la 2è thread et trouvée dans ts.resultat)
  • ...
  • Le nè thread stocke 1 dans ts.resultat (et arrête la récursion).
---endCorr

Question 3.2 : Limite du programme (2 points)

Lorsqu'on exécute sommeEntier 2000 sur une machine de la salle B07-03, le programme affiche l'erreur suivante :

pthread_create: Cannot allocate memory
((typSomme *)arg)->donnee valait 1697

Expliquez ce message d'erreur.
Déduire de cet affichage le plus grand entier pour lequel sommeEntier fonctionne.
---beginCorr
Barême : 2 points pour l'explication (il faut au moins parler de pile de thread dans l'explication).

Chaque thread a besoin d'une pile pour fonctionner. Cette pile est allouée dans la zone mémoire du processus global où se font les allocations mémoire. Or, quand on a créé 2000 -1697 =  303 threads, le processus n'a plus de mémoire allouable pour qu'un nouveau thread dispose d'une pile.Donc, le programme s'arrête.
sommeEntier fonctionne correctement jusqu'à l'entier 303.
---endCorr

Question 3.3 : Repousser les limites (2 points)

On se propose de repousser les limites observées précédemment en utilisant les primitives pthread_attr_init() et pthread_attr_setstacksize() pour créer des threads avec une pile de 16 Ko (Cette valeur est la taille minimale de pile de thread sur un Linux en environnement PC).
  • Expliquez comment ces primitives et cette valeur de 16 Ko peuvent aider à repousser les limites.
  • Indiquez pourquoi on n'a pas de risque à créer des threads avec de si petites piles.
  • Modifiez le code du fichier sommeEntierQ3.3.c pour que :
    • il affiche (à l'aide de pthread_attr_setstacksize()) la quantité de pile utilisée par défaut pour la création d'un thread ;
    • il crée des threads avec une pile de 16 Ko
  • L'exécution sommeEntierQ3.3 16229 affiche le résultat "Somme des 16229 premiers entiers = 131698335", mais sommeEntierQ3.3 16230 donne un affichage semblable à ce qui suit :
Taille de la pile (par défaut) = 10485760
Taille de la pile (après setstacksize) = 16384
pthread_create: Resource temporarily unavailable
Erreur de segmentation

Commentez cet affichage (en expliquant notamment quel aurait dû être le plus grand entier pour lequel sommeEntier fonctionne, compte tenu de cette taille de pile de 16 Ko).
---beginCorr
Barême :
  • 0,5 point pour l'explication pour repousser les limites
  • 0,25 point pour l'indication de petite pile
  • 1 point pour le code
  • 0,25 point pour le commentaire
Les primitives pthread_attr_init() et pthread_attr_setstacksize() permettent d'avoir des threads qui ont besoin de moins de pile, donc qui nécessitent moins de mémoire dans le processus qui les crée. De ce fait, on devrait pouvoir créer plus de threads.
On n'a aucun risque à créer des threads avec une petite pile dans le cas de cette application, car la fonction utilise très peu de pile.
Le fichier sommeEntierQ3.3.corrige.c présente un corrigé.
On n'arrive pas à calculer la somme au delà de 16.229. Or, vu qu'on divise la pile de chaque thread par 10.485.760 / (16 * 1024) = 640, on devrait pouvoir allouer 640 fois plus de threads. Donc au lieu de s'arrêter à 303 comme précédemment, on devrait s'arrêter à 640*303 ~190.000. Or, on a une limite environ 15 fois inférieure. Il est probable qu'on atteint une limite système sur le nombre de threads simultanés au sein du processus (voire de l'ensemble du système (pour vérifier cela, il faudrait lancer plusieurs processus en parallèle)). Cela est d'ailleurs suggéré par le libellé du message d'erreur qui est différent de celui qu'on avait à la question 3.2.
---endCorr

Question 3.4 : Une autre manière de communiquer son résultat (2 points)

Dans le code utilisé actuellement, un thread communique son résultat au thread qui l'a créé en utilisant le champ resultat de la structure typSomme. Modifiez le fichier sommeEntierQ3.3.c pour que le thread communique son résultat via la fonction pthread_exit().
---beginCorr
Barême :
  • 1 point pour l'allocation/libération de la mémoire
  • 0,5 point sur l'utilisation du pthread_exit()
  • 0,5 point pour les tests d'erreur (notamment au niveau du malloc).
Le fichier sommeEntierQ3.4.corrige.c présente un corrigé.
---endCorr



Page mise à jour le 18 juin 2007