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


    Évaluation



TÉLÉCOM & Management SudParis
TÉLÉCOM SudParis 2ème année

TP Noté CSC4508/M2 du 21/06/10

(2è session)

(Corrigés)

Modalités

Durée : 1 heure 30

Tous documents autorisés.

Les questions 1 et 2 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 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 TPNote2010Session2

Préparation

cd votreRepertoireDeTravailPourCSC4509M2
cp ~simatic/Cours/CSC4508/tPNote2010Session2.tgz .
tar xvfz tPNote2010Session2.tgz
cd TPNote2010Session2

Question 1 : Parallélisation d'un algorithme (10 points)

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 ).



Dans cet exercice, on considère l'algorithme suivant dans lequel la fonction f et la fonction g sont appelées pour modifier des données (globales à l'ensemble de l'application) jusqu'à ce que la fonction calculCondition renvoie VRAI :
   Ligne 1. Répéter
   Ligne 2.    f(données);
   Ligne 3.    pour i de 0 à 9 faire
   Ligne 4.         g(données)
   Ligne 5.    fait
   Ligne 6. Jusqu'à ce que calculCondition(données)

Question 1.1 (3 points)

On souhaite que les lignes 1, 2 et 6 soient traitées par un thread Ta et que les lignes 3, 4, 5 soient traitées par un thread Tb.
Indiquez quel est le paradigme de synchronisation.
Ensuite, écrivez, à l'aide de sémaphores (pour lesquels vous indiquerez les valeurs initiales), les algorithmes de Ta et de Tb.
---beginCorr
Barème :
  • 1 point pour le type de paradigme de synchronisation
  • 0,5 points pour les 2 sémaphores (avec l'initialisation correcte)
  • 0,75 point pour chaque algorithme
Ce problème est un problème d'appel de procédure entre threads (processus).

Variables globales
==================
Sémaphore appel initialisé à 0
Sémaphore retour initialisé à 0

Algorithme du thread Ta
=======================
Répéter
   f(données);
   V(appel)
   P(retour)
Jusqu'à ce que calculCondition(données)

Algorithme du thread Tb
=======================
P(appel)
pour i de 0 à 9 faire
   g(données)
fait
V(retour)
---endCorr

Question 1.2 (3 points)

On souhaite que les lignes 1, 2, 3, 5, 6 soient traitées par un thread Tc, tandis que la ligne 4 est traitée par plusieurs threads parmi les threads Td0, Td1...Td9.
Écrivez, à l'aide de sémaphores (pour lesquels vous indiquerez les valeurs initiales), les algorithmes de Tc et de Tdj (0 <= j <= 9) en veillant à ce que les threads Td0, Td1...Td9 s'exécutent en parallèle.
---beginCorr
Barème :
  • 0,5 points pour les 2 sémaphores (avec l'initialisation correcte)
  • 1,25 point pour chaque algorithme
    NB : pour l'algorithme de Tc, s'il ne permet pas une exécution parallèle de Td0, Td1...Td9, on met seulement 0,5 point.
Ce problème est toujours un problème d'appel de procédure entre threads (processus).

Variables globales
==================
Sémaphore appel initialisé à 0
Sémaphore retour initialisé à 0

Algorithme du thread Tc
=======================
Répéter
    f(données);
   pour i de 0 à 9 faire
      V(appel)
   fait
   pour i de 0 à 9 faire
      // NB : si on mettait le P(retour) dans la boucle ci-dessus, on n'aurait aucun
      // parallelisme entre les differents threads
Tdi
      P(retour)
   fait
Jusqu'à ce que calculCondition(données)

Algorithme du thread Tdi
========================
P(appel)
g(données)
V(retour)
---endCorr

Question 1.3 (4 points)

L'algorithme utilisé jusqu'à présent devient :
   Ligne 1. Répéter
   Ligne 2.    f(données);
   Ligne 3.    pour i de 0 à 9 faire
   Ligne 4.         g(données,i)     /* Notez l'ajout de ",i" : l'exécution de la fonction g dépend désormais de la valeur de i. */
   Ligne 5.    fait
   Ligne 6. Jusqu'à ce que condition(données)

On souhaite que les lignes 1, 2, 3, 5, 6 soient traitées par un thread Te et que la ligne 4 soit traitée par le i-ème thread parmi les threads Tf0, Tf1...Tf9.
Écrivez, à l'aide de sémaphores (pour lesquels vous indiquerez les valeurs initiales), l'algorithme de Te et de Tfj (0 <= j <= 9).

NB :
  1. g(données,i) (i allant de 0 à 9) doit absolument être traité par le thread Tfi
  2. On rappelle que si 2 threads T1 et T2 exécutent l'algorithme suivant :
       tant que VRAI
         P(sem)
         traitement()
      fin tant que
    et qu'ils sont tous les deux bloqués à un instant donné sur l'instruction P(sem), alors si un thread T0 fait deux fois V(sem), on peut avoir l'une des exécutions suivantes :
    • T1, puis T2
    • T2, puis T1
    • T1, puis T1
    • T2, puis T2
    • T1 en parallèle de T2 (cas d'un processeur double-cœur, par exemple)
---beginCorr
Barème :
  • 0,25 points pour le sémaphore retour (avec l'initialisation correcte)
  • 0,75 points pour le tableau de sémaphores appel (avec l'initialisation correcte)
  • 1,5 point pour chaque algorithme
Ce problème est toujours un problème d'appel de procédure entre threads (processus).

Variables globales
=============
Tableau de sémaphores appel[10], chaque sémaphore étant initialisé à 0
Sémaphore retour initialisé à 0

Algorithme du thread Te
=================
Répéter
    f(données);
   pour i de 0 à 9 faire
      V(appel[i])
   fait
   pour i de 0 à 9 faire
      P(retour)
   fait
Jusqu'à ce que calculCondition(données)

Algorithme du thread Tfj
==================
P(appel[j])
g(données,j)
V(retour)
---endCorr

Question 2 : Implémentation de l'outil de synchronisation Loquet (10 points)

L'objectif de cette question est d'implémenter l'outil de synchronisation Loquet dont la conception a été étudiée dans l'une des questions du TP noté de 2010 (session 1).

Complétez le type loquet_t dans le fichier loquet.h. de manière à y intégrer toutes les variables liées au Loquet (voir ci-dessous les rappels concernant le Loquet).

En utilisant des mutex et/ou des sémaphores POSIX, complétez le code des fonctions nouveauLoquet(), attenteLoquet(), decrementLoquet() et destructionLoquet() dans le fichier loquet.c (le rôle de chacune de ces fonctions et de ses paramètres est décrit dans le fichier loquet.c).

Vérifiez que votre code est correct en générant l'application testLoquet (à l'aide de la commande make), puis en exécutant cette application. Vous devez obtenir l'affichage suivant :
nouveauLoquet() appele avec valeur 3 en parametre
threadDecrementLoquet demarre !
On demarre des threads threadAttenteLoquet alors que le loquet n'est pas passant
threadAttenteLoquet 0 appelle attenteLoquet()
threadAttenteLoquet 1 appelle attenteLoquet()
threadAttenteLoquet 2 appelle attenteLoquet()
threadAttenteLoquet 3 appelle attenteLoquet()
threadAttenteLoquet 4 appelle attenteLoquet()
threadDecrementLoquet a appele decrementLoquet() (rc = 0, encore 2 appels)
threadDecrementLoquet a appele decrementLoquet() (rc = 0, encore 1 appels)
threadDecrementLoquet a appele decrementLoquet() (rc = 0, encore 0 appels)
threadDecrementLoquet termine !
threadAttenteLoquet 0 est sorti de attenteLoquet() (rc = 0)
threadAttenteLoquet 1 est sorti de attenteLoquet() (rc = 0)
threadAttenteLoquet 2 est sorti de attenteLoquet() (rc = 0)
threadAttenteLoquet 3 est sorti de attenteLoquet() (rc = 0)
threadAttenteLoquet 4 est sorti de attenteLoquet() (rc = 0)
On demarre des threads threadAttenteLoquet alors que le loquet est passant
threadAttenteLoquet 0 appelle attenteLoquet()
threadAttenteLoquet 0 est sorti de attenteLoquet() (rc = 0)
threadAttenteLoquet 1 appelle attenteLoquet()
threadAttenteLoquet 1 est sorti de attenteLoquet() (rc = 0)
threadAttenteLoquet 2 appelle attenteLoquet()
threadAttenteLoquet 2 est sorti de attenteLoquet() (rc = 0)
threadAttenteLoquet 3 appelle attenteLoquet()
threadAttenteLoquet 3 est sorti de attenteLoquet() (rc = 0)
threadAttenteLoquet 4 appelle attenteLoquet()
threadAttenteLoquet 4 est sorti de attenteLoquet() (rc = 0)


Quelques rappels sur ce qui a été vu lors du TP noté de 2010 (session 1) sur l'outil de synchronisation Loquet.
  • Un Loquet est un outil de synchronisation permettant de retarder l'exécution de threads tant que le Loquet n'est pas dans son état terminal. Un Loquet agit comme une porte : tant qu'il n'est pas dans son état terminal, la porte est fermée et aucun thread ne peut passer. Dans son état terminal, la porte s'ouvre et tous les threads peuvent entrer. Quand un Loquet est dans son état terminal, il ne peut changer d'état et reste ouvert à jamais.
    Le Loquet permet donc qu'un ou plusieurs threads attendent qu'un ensemble d'événements se produisent. L'état du Loquet est formé d'un compteur initialisé (au moment de la création du Loquet avec la fonction nouveauLoquet()) avec un nombre positif qui représente le nombre d'événements à attendre. La fonction decrementLoquet() décrémente ce compteur pour indiquer qu'un événement est survenu. La fonction attenteLoquet() attend que le compteur passe à zéro, ce qui signifie que tous les événements se sont passés. Si le compteur est non nul lorsqu'elle est appelée, attenteLoquet() se bloque jusqu'à ce qu'il atteigne zéro. Si le compteur est nul, attenteLoquet() retourne immédiatement.
  • Le corrigé des algorithmes était le suivant :

    Variables liées à un loquet
    ===========================
    int compteur = 0
    int nbAttenteLoquetOuvert = 0
    Semaphore mutex initialisé à 1
    Sémaphore attenteLoquetOuvert initialisé à 0

    Algorithme de nouveauLoquet(int valeurCompteur)
    ===============================================
    compteur = valeurCompteur

    Algorithme de decrementLoquet()
    ===============================
    P(mutex)
    compteur -= 1
    Si compteur == 0 alors
      Répéter nbAttenteLoquetOuvert fois
          V(attenteLoquetOuvert)
      FinRépéter
    FinSi
    V(mutex)

    Algorithme de attenteLoquet()
    =============================
    P(mutex)
    Si compteur > 0 alors
       nbAttenteLoquetOuvert += 1
       V(mutex)
       P(attenteLoquetOuvert)
    Sinon
       V(mutex)
    FinSi
---beginCorr
Voir loquet.corrige.h et loquet.corrige.c
Barème :
  • 2 points pour la définition de la structure (0,4 point pour chacun des 5 éléments de la structure)
  • 2 point par fonction (si la gestion du retour du code d'erreur n'est pas bonne pour une fonction, on enlève 0,5 point de ces 2 points)
---endCorr



Page mise à jour le 21 juin 2010