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 22/06/04
(2è session)

(Corrigés)

Modalités

Durée : 1 heure 30

Tous documents autorisés

Les 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 à frederique.silber-chaussumier@int-evry.fr (sujet «CS21:TPNoteSession2») avec en pièce jointe le fichier d'extension tgz constitué de la manière suivante :
cd votreRepertoireDeTravailPourCS21
tar cvfz $USER.tgz TPNote2004Session2

Préparation

cd votreRepertoireDeTravailPourCS21
cp ~silber/CS21/tPNote2004Session2.tgz .
tar xvfz tPNote2004Session2.tgz
cd TPNote2004Session2

Question 1 : O_SYNC (4 points)

man 2 open décrit le rôle de l'option O_SYNC dans l'appel système open.
Q1.1 : Pourquoi n'utilise-t-on pas cette option en général ?
---beginCorr
Avec cette option, chaque écriture sur le fichier donne lieu à une écriture immédiate sur disque : on ne profite pas des regroupements possibles d'écriture sur disque. Les performances sont donc mauvaises
---endCorr
 Q1.2 : Donner un exemple d'application où cette option est requise.
---beginCorr
Toute application utilisant une base de données où le programme indique à la base de données que les données doivent être commitées sur disque : ces données doivent donc être effectivement présentes sur disque (principe de Durabilité des bases de données) même si la machine plante quelques instants après (et donc ses caches disque sont perdus). Les écritures sur disque doivent donc être synchrones avec les appels système write.
NB : des mécanismes spécifiques (journalisation) sont mis en oeuvre dans les bases de données pour que cet aspect synchrone ne pénalise pas trop les performances de la base de données.
---endCorr
 NB : Vous pouvez répondre 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").

Question 2 : Concurrence d'accès (8 points)

Le module suivant est utilisé pour gérer une liste chaînée de données.

#include <stdlib.h>

/* Structure utilisee pour stocker les differents elements de la liste */
typedef struct element_t{
   /* Donnees stockees dans cet element de la liste chainee */
    char data[256];
   /* Pointeur vers l'element suivant de la liste chainee (NULL si pas */
   /* d'element suivant)                                               */
    struct element_t *next;
} element_t;

/* Pointeur sur le premier element de la liste chainee */
static element_t *first=NULL;

/* Ajoute l'element unElement en tete de liste chainee */
void addFirst(element_t *unElement){
   /* Comme unElement va etre insere en tete de liste,          */
   /* son successeur sera le premier element actuel de la liste */
   unElement->next = first;
   /* La nouvelle tete de liste est unElement */
   first = unElement;
}

Dans un programme mono-thread, ce module donne entière satisfaction.
En revanche, dans le cas d'un programme contenant deux threads (qui appellent à certains moments la fonction addFirst), chacun ayant une politique d'ordonnancement FIFO, l'un ayant une priorité statique égale à 1, l'autre ayant une priorité statique égale à 2, on constate qu'addFirst perd des éléments.
Q2.1 : Pourquoi ?
---beginCorr
Soit thread1 (respectivement thread2) le thread de priorité 1 (respectivement 2).
  • Supposons que thread1 appelle addFirst avec l'élément element1 en paramètre : thread1 exécute la première instruction d'addFirst. Il fait donc element1->next = first;
  • Supposons maintenant que thread2 se réveille juste à ce moment-là (par exemple, l'entrée-sortie qu'il avait en cours s'est terminée). Comme thread2 a une priorité statique supérieure à celle de thread1, thread2 prend la main. S'il appelle addFirst avec l'élément element2, il déroule tout le code d'addFirst. Il effectue donc : element2->next=first et first=element2
  • Quand thread2 relâche la main (par exemple, pour faire une autre entrée-sortie), thread1 reprend la main et termine son exécution d'addFirst. Il fait donc first=element1.
On constate qu'element2 est perdu.
---endCorr
 Q2.2 : Aurait-on ce bug si les deux threads avaient la même priorité statique (comprise entre 1 et 99) ? Justifier votre réponse.
---beginCorr
Non. En effet, même si thread2 se réveille, il ne prend pas la main dans la mesure où il n'a pas une priorité supérieure à celle de thread1 : thread1 ne peut plus être interrompu pendant son exécution d'addFirst (en effet, la politique d'ordonnancement de ces deux threads est FIFO : thread1 ne relâchera la main que volontairement).
---endCorr
 Q2.3 : Proposer, dans ses grandes lignes, une solution pour le bug d'addFirst quand les deux threads ont une priorité statique différente.
---beginCorr
Il suffit de rajouter un sémaphore pour garantir l'exclusion mutuelle dans la manipulation de la liste chaînée :

/* on suppose que mutex est un semaphore initialise à 1 */

/* Ajoute l'element unElement en tete de liste chainee */
void addFirst(element_t *unElement){
   /* Entree en section critique */
   P(mutex);
   /* Comme unElement va etre insere en tete de liste,          */
   /* son successeur sera le premier element actuel de la liste */
    unElement->next = first;
   /* La nouvelle tete de liste est unElement */
   first = unElement;
   /* Sortie de section critique */
   V(mutex);
}
---endCorr
 NB : Vous pouvez répondre sur votre copie ou bien dans le fichier Q2/reponse.txt  (dans ce dernier cas, indiquez sur votre copie "Réponse dans Q2/reponse.txt").

Question 3 : Tube versus mémoire partagée (8 points)

On souhaite comparer les performances des communications à travers un tube et celles à travers une zone de mémoire partagée synchronisée selon un paradigme producteur/consommateur.
Pour ce faire, on se propose de coder le programme Q3/tube.c (respectivement Q3/memoirePartagee.c) selon l'algorithme suivant
  • Création d'un tube (respectivement d'un tampon et des entités liées au paradigme producteur/consommateur)
  • Création d'un enfant
  • Déclaration d'une variable s de type structure_t
  • Initialisation de tous les octets de s à '\0'
  • répéter NBECHANGES fois
    • Envoyer s à l'enfant via le tube (respectivement la zone de mémoire partagée)
  • Fin Répéter
  • Attendre décès de l'enfant
Dans ce programme, le fils effectue l'algorithme suivant :
  • Définir une variable s de type structure_t
  • répéter NBECHANGES fois
    • Lire la valeur de s envoyée par le père via le tube (respectivement la zone de mémoire partagée)
  • Fin Répéter

Question 3.1 : Codage de Q3/tube.c

Le programme Q3/memoirePartagee.c est déjà fourni.
Compléter les lignes /*** A completer ***/ de Q3/tube.c pour qu'il fonctionne conformément à l'algorithme ci-dessus.
NB : même si vous n'arrivez pas à répondre à cette question, vous pouvez quand même travailler sur la question Q4.2.
---beginCorr
tube.corrige.c
---endCorr

Question 3.2 : Analyse

Dans le fichier Q3/commentaire.txt :
  • Q3.2.1. Indiquer le résultat de la commande /usr/bin/time appliqué à Q3/memoirePartagee et Q3/tube (ou Q3/tubeSiQ31KO si vous n'avez pas pu répondre à la question Q3.1)
    ---beginCorr
    Résultat dépendant de la machine. A titre indicatif, sur craie (machine à 1 Ghz) sous Linux RedHat 7.2, on a les résultats suivants :
    $ /usr/bin/time tube
    0.72user 2.29system 0:03.31elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (101major+38minor)pagefaults 0swaps
    $ /usr/bin/time pc
    1.89user 2.31system 0:04.62elapsed 90%CPU (0avgtext+0avgdata 0maxresident)k
    0inputs+0outputs (101major+35minor)pagefaults 0swaps
    ---endCorr
  • Q3.2.2. Les résultats obtenus militent en faveur de l'utilisation systématique des tubes. En remarquant que le nombre d'octets contenus dans un tube n'est pas aisément paramétrables (recompilation du noyau requise), citer une situation où on préférera utililiser de la mémoire partagée plutôt que des tubes (même si les performances sont moins bonnes).
    ---beginCorr
    On préfère utiliser de la mémoire partagée quand:
    • On a besoin de garanties sur le nombre d'octets stockables dans le "tampon" utilisé pour les communications entre le père et l'enfant. Avec de la mémoire partagée, on est en mesure de spécifier avec précision le nombre de cases dans le tampon et le nombre d'octets dans chaque case. Avec les tubes, ce n'est pas possible.
    • Un processus externe a besoin de lire le contenu du "tampon" (par exemple, pour voir les données en attente). Avec un tube, on ne sait pas faire.
      ---endCorr
  • Q3.2.3. La différence de temps d'exécution peut surprendre. Expliquer pourquoi : on ne demande pas d'expliquer la différence de temps d'exécution en elle-même (il faudrait analyser le code du noyau Linux pour comprendre la gestion des tubes et de la mémoire partagée), mais on demande d'expliquer en quoi la différence de temps d'exécution est surprenante.
    NB : cette question est plus difficile que les autres. Il est donc recommandé de ne l'aborder que quand vous avez traité les autres questions.
    ---beginCorr
    L'utilisation de la mémoire partagée est nettement moins performante que l'utilisation du tube. Vu que la différence se fait surtout au niveau du temps user (1.89-0.72=1.27 seconde), il semble qu'une grande partie du temps soit perdue dans les opérations de recopie entre la mémoire du processus et la mémoire partagée, ce qui est surprenant puisque, quand on utilise des tubes, on fait aussi des opérations de recopie mémoire.
    ---endCorr

Page mise à jour le 15 mai 2006