TD1

Exercice 1 : Sémaphores

On veut implémenter une structure classique de parallèlisme appelée producteur-consommateur. Le principe est le suivant. Un ou plusieurs threads remplissent une structure de données tandis que un ou plusieurs autres suppriment des éléments dedans. Il existe de nombreuses variantes, par exemple avec consommateur ne supprimant pas la ressource, avec priorité....

  1. Dans quelle(s) situation(s) ce patron de conception peut-il améliorer les performances ?
  2. À quelle(s) condition(s) un producteur peut-il ajouter une donnée dans la structure? à quelle(s) condition(s) un consommateur peut-il en retirer ?
  3. En ignorant tout problème de concurrence (i.e. pas de multithread), écrivez le pseudo-code du producteur et du consommateur.
  4. On considère maintenant le cas multi-thread. On suppose qu'ajouter/retirer une donnée est une opération atomique. Est-ce suffisant pour garantir le bon fonctionnement ?
  5. En utilisant deux sémaphores, rendez le code fiable pour un nombre quelconque de producteurs et consommateurs.
  6. (difficile) Comment devrait-on faire pour avoir des producteurs prioritaires, i.e. aucun consommateur ne peut entrer en section critique tant qu'au moins un producteur attend.

Exercice 2 (moniteurs)

Un moniteur est un objet qui permet a un ou plusieurs processus de se synchroniser. Un processus peut ainsi attendre un signal venant d'un autre processus avant de poursuivre son exécution. Un moniteur peut avoir un nombre arbitraire de méthodes et l'accès à ces méthodes se fait à travers une exclusion mutuelle.

Concrètement, un moniteur encapsule une condition (souvent appelée aussi queue) C sur laquelle il est possible de faire les opérations suivantes :

C.wait(): le processus appelant arrête son exécution et se place dans la queue C. Il est considéré comme hors de la section critique

C.signal() :

  • Si aucun processus n'est dans la queue C, alors le signal est perdu
  • Si au moins un processus est dans la queue C, alors le signal active le premier processus en queue. Le processus ayant exécuté signal sort de la section critique mais a priorité pour y retourner.

C.empty() : Prédicat pour tester si la queue est vide

Soit le moniteur suivant

moniteur RDV

entier Compteur

entier MAX = 10

condition Queue

//cette méthode aurait pu s'appeler toto ou titi

     //et on pourrait en rajouter d'autres

methode barriere()

...

fin methode

fin moniteur

Il permet de créer une barrière, c'est à dire un point de synchronisation pour un ensemble de processus (ici 10). Chaque processus appelle la méthode barrière qui effectue les opérations suivantes

  • Si nombre de processus en attente <MAX, alors le processus est mis en attente.
  • Si nombre de processus en attente =MAX, alors tous les processus sont réveillés

On suppose que la méthode barriere() a un mécanisme d'exclusion mutuelle.

  1. Complétez la méthode barriere()

Exercice 3

Implémentez un producteur consommateur avec un moniteur.

Exercice 4 (moniteurs et sémaphores)

Comment implémenter un moniteur en utilisant des sémaphore?