===============================================
INFO 1 - Systèmes d’Exploitations - TP5 - Mutex
===============================================


Avant-propos sur les sémaphores binaires
----------------------------------------

Un *mutex* est un objet d’exclusion mutuelle, et est très pratique pour protéger
des données partagées de modifications concurrentes, et pour implémenter des
sections critiques.

Un mutex peut être dans deux états : déverrouillé ou vérouillé (appartenance à
un thread). Il ne peut être pris que par un seul thread à la fois. Un thread qui
tente de verrouiller un mutex déjà verrouillé est suspendu jusqu’à ce que le
mutex soit déverrouillé.

* Initialisation :
  ```c
  int pthread_mutex_init(pthread_mutex_t *mutex,
                         const pthread_mutexattr_t *mutexattr);
  ```
  Initialise le mutex pointé par `mutex` selon les attributs de mutex spécifiés
  par `mutexattr`, si ce dernier vaut `NULL`, les paramètres par défaut sont
  utilisés (mutex de type rapide). On peut également initialiser un mutex rapide
  de manière statique : `pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;`.
  Voir la page de manuel pour les autres types de mutex.
* Verrouillage :
  ```c
  int pthread_mutex_lock(pthread_mutex_t *mutex);
  ```
* Déverrouillage :
  ```c
  int pthread_mutex_unlock(pthread_mutex_t *mutex);
  ```
* Destruction d’un mutex non verrouillé :
  ```c
  int pthread_mutex_destroy(pthread_mutex_t *mutex);
  ```

Exemple : une variable globale partagée `x` peut être protégée par un mutex :
```c
int x;
pthread_mutex_t mut = PTHREAD_MUTEX_INITIALIZER;
…
pthread_mutex_lock(&mut);
++x;
pthread_mutex_unlock(&mut);
```
On pourra réfléchir à la meilleur manière de régler le problème des philosophes,
sans inter-blocage ni famine, ou encore le problème du producteur et du
consommateur.


Exercices
---------

Crédits : Pierre Rousselin.

1. Télécharger et lire le programme `https://lipn.univ-paris13.fr/~dufour/se/rsrc/belmondo.c`
   (avec `wget` ou `curl`, pour changer).
   * L’exécuter plusieurs fois, et constater.
   * Modifier le programme de façon à ce que toutes les lignes du texte initial
     soient lues et que les acteurs ne parlent pas en même temps (peu importe si
     un des acteurs enchaîne deux lignes avant que l’autre n’ait fini de traiter
     la sienne, ou si des lignes ne sont pas dans le bon ordre (on rectifiera au
     montage), l’essentiel est qu’elles y soient toutes).

2. Télécharger le programme `https://lipn.univ-paris13.fr/~dufour/se/rsrc/space_invaders.c`.
   Il effectue les choses suivantes `num_iter` fois :
   - d’abord, la prochaine image à afficher est calculée. Ici, simplement,
     toutes les lignes sont décalées et un pixel (représenté par `*`) est ajouté
     sur la première ligne.
   - Ensuite, le terminal est effacé et l’image (les pixels de l’écran) est
     affichée.
   Après avoir lu, compilé et exécuter le programme,
   * rendre ce programme concurrent : un thread devrait être dédié au calcul du
     prochain écran (_prochaine frame_) pendant qu’un autre affiche la _frame_
     courante.
     Pour ce faire, deux écrans seront nécessaires, un pour la _frame_ en train
     d’être affichée, l’autre pour celle qui se fait calculer. Pour éviter les
     copies intempestives, travailler avec deux pointeurs globaux :
     ```c
     int (*ecran_a_afficher)[HAUTEUR][LARGEUR];
     int (*ecran_a_modifier)[HAUTEUR][LARGEUR];
     ```
   * Il faudra bien sûr faire bien attention aux problèmes de synchronisation.
     Lancer le programme avec double-buffer avec la commande `time` devrait
     montrer qu’il prend (environ) deux fois moins de temps que la version
     non-double-bufferisée.

3. Dans ce problème, il y a des danseurs, dont `NB_MENEURS` meneurs et
   `NB_SUIVEURS` suiveurs. Un meneur ne peut danser qu’avec un suiveur et
   réciproquement (c’est une danse de salon, par exemple du *rock’n roll*, ou de
   la salsa).
   Dans une boucle infinie :
   - Chaque danseur met un certain temps à se préparer.
   - Ensuite, il essaie de choisir un partenaire (un suiveur, s’il est meneur et
     réciproquement) :
     - si aucun partenaire n’est disponible, il ne pourra en choisir un : il
       attend d’être choisi en s’adossant tristement au mur ;
     - sinon, il choisit (c’est-à-dire ici réveille : on laisse faire le
       système) un partenaire de l’autre catégorie et l’invite à danser, après
       lui avoir demandé son nom (ici son numéro) et donné le sien.
   - Lorsqu’ils ont choisi ou ont été choisis les danseurs dansent avec
     leur partenaire.
  * Télécharger et lire le programme
    `https://lipn.univ-paris13.fr/~dufour/se/rsrc/danseurs_non_sync.c`
  * Le compiler et l’exécuter. Noter un certain nombre d’incohérences.
  * Le but est d’arriver à la situation décrite ci-dessus : un danseur
    choisit ou est choisi (réveille ou est réveillé) par un danseur de l’autre
    catégorie et danse avec lui.

  C’est loin d’être facile, alors voici quelques pistes :
  - les nombres des meneurs et des suiveurs en attente devraient être
    enregistrés, par exemple dans des variables globales ;
  - à tout instant, il ne peut y avoir qu’un et un seul danseur qui
    essaie d’en choisir (réveiller) un autre et manipule l’une ou l’autre des
    deux variables évoquées ci-dessus ;
  - on peut utiliser un sémaphore `file_suiveur` pour
    les suiveurs qui attendent d’être choisis (réveillés) par un meneur
    et un sémaphore `file_meneur` pour les meneurs qui attendent
    d’être choisis (réveillés) par un suiveur ;
  - il faut également faire attention à ce que les partenaires se
    transmettent correctement leurs noms (numéros).