TP5 - Synchronisation de threads

Le but de ce TP est d'utiliser différentes méthodes pour synchroniser plusieurs threads.

Exercice 0 - Instructions

Il y a un fichier à rendre pour chaque exercice.

Exercice 1 : 4 points
Exercice 2 : 3 points
Exercice 3 : 3 points
Exercice bonus : jusqu'à 3 points bonus

Exercice 1

Nom du fichier : votrelogin_cars_mutex1.c

On reste sur le même thème que le TP précédent.

On va modifier le TP précédent pour corriger les bugs visuels qu'on pouvait rencontrer.

On ne connaissait pas les mutex la semaine dernière, on a donc fait un truc un tantinet bancal pour éviter d'avoir plein de bugs visuels : on a ajouté de l'aléatoire dans la vitesse de nos voitures, avec un usleep(50000 + rand() % 1000).

Reprendre la version minimale de la correction du TP précédent.
Supprimer juste la partie aléatoire du usleep. Garder la partie fixe.
Compiler et exécuter le programme. Lancer notamment plusieurs voitures à la fois, en tapant par exemple jkjkjk puis la touche Entrée.
Constater qu'il y a des bugs visuels : des caractères qui s'affichent au mauvais endroit ou qui ne sont pas effacés. Ne pas hésiter à m'appeler s'il n'y a pas de bug.

L'affichage de plusieurs threads s'entremêle. Si on a deux threads qui exécutent ces codes en parallèle :

move_cursor(2, 4);
fprintf(stdout, ">");

et

move_cursor(4, 16);
fprintf(stdout, "<");

Les fonctions s'exécuteront simultanéments, résultant en un affichage qui pourrait correspondre à ce code, par exemple :

move_cursor(2, 4);
move_cursor(4, 16);
fprintf(stdout, "<");
fprintf(stdout, ">");

Et ça ne va pas du tout faire ce qu'on veut.

Le problème est donc de l'ordre de l'accès concurrentiel à une ressource partagée : stdout.

Pour résoudre ce problème, on va devoir protéger les accès à stdout derrière un mutex.

Créer et initialiser un mutex partagé. Faire un init dans game_init, un lock avant chaque affichage, et un unlock après chaque affichage.

Vous allez devoir utiliser les fonctions suivantes, qui existent déjà dans la librairie pthread.h:

// Le deuxième argument est facultatif
pthread_mutex_init(pthread_mutex_t *mutex, pthread_mutexatttr_t *optional_attribute);
pthread_mutex_lock(pthread_mutex_t *mutex);
pthread_mutex_unlock(pthread_mutex_t *mutex);

De cette manière, l'affichage de plusieurs threads ne pourra plus s'emmêler.

Exercice 2

votrelogin_cars_mutex2.c

On reste toujours sur le même thème.

Mais cette fois-ci, il y a des travaux sur l'autoroute.

Une des deux voies est partiellement bouchée, et les voitures sont obligées de passer une à une sur la voie restante !

Dans un premier temps, compilez et exécutez le programme ci-dessous. C'est la correction étendue du TP précédent, mais avec une deviation sur une des deux voies.

Essayez de lancer plusieurs voitures sur les deux routes en même temps et observez le problème 📝

Code

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

void clear_screen() { fprintf(stdout, "\e[1;1H\e[2J"); }

void refresh() { fflush(stdout); }

void move_cursor(unsigned int y, unsigned int x) {
  fprintf(stdout, "\e[%d;%dH", y, x);
}

void print_n(char *s, unsigned int repeat) {
  while (repeat > 0) {
    fprintf(stdout, "%s", s);
    repeat--;
  }
}

// Amélioration Couleur
const unsigned int COLOR_RESET = 0, COLOR_RED = 1, COLOR_GREEN = 2,
                   COLOR_YELLOW = 3, COLOR_BLUE = 4, COLOR_PURPLE = 5,
                   COLOR_LIGHTBLUE = 6;

void color(int color) {
  if (color == COLOR_RESET) {
    fprintf(stdout, "\e[0m");
  } else {
    fprintf(stdout, "\e[3%cm", color + '0');
  }
}

unsigned int ROAD_SIZE, BLOCK_SIZE, LEFT_LIMIT, RIGHT_LIMIT;

// Amélioration Input
struct termios OLD_TERMINAL_PARAMS;

void game_init() {
  BLOCK_SIZE = ROAD_SIZE / 10 + 2;
  LEFT_LIMIT = ROAD_SIZE / 2 - BLOCK_SIZE;
  RIGHT_LIMIT = ROAD_SIZE / 2 + BLOCK_SIZE;

  srand(time(NULL));

  clear_screen();

  // Première partie de la ligne 1
  move_cursor(1, 1);
  print_n("-", LEFT_LIMIT);

  // Deuxième partie de la ligne 1
  move_cursor(1, RIGHT_LIMIT);
  print_n("-", LEFT_LIMIT + 1);

  // Première partie de la ligne 2
  move_cursor(3, 1);
  print_n("- ", LEFT_LIMIT / 2 - 1);

  // Deuxième partie de la ligne 2
  move_cursor(3, LEFT_LIMIT + 2);
  print_n("-", BLOCK_SIZE * 2 - 3);

  // Troisième partie de la ligne 2
  move_cursor(3, RIGHT_LIMIT + 2);
  print_n("- ", LEFT_LIMIT / 2);

  // Ligne 3
  move_cursor(5, 1);
  print_n("-", ROAD_SIZE);

  move_cursor(1, LEFT_LIMIT);
  fprintf(stdout, "\\");

  move_cursor(1, RIGHT_LIMIT);
  fprintf(stdout, "/");

  move_cursor(2, LEFT_LIMIT + 1);
  fprintf(stdout, "\\");

  move_cursor(2, RIGHT_LIMIT - 1);
  fprintf(stdout, "/");

  // Amélioration Messages
  move_cursor(7, 1);
  fprintf(stdout, "Press j to spawn a car riding to the east");
  move_cursor(8, 1);
  fprintf(stdout, "Press k to spawn a car riding to the west");
  move_cursor(9, 1);
  fprintf(stdout, "Press q to quit");

  move_cursor(1, ROAD_SIZE + 1);

  // Amélioration Input
  struct termios new_terminal_params;
  // Store old params
  tcgetattr(STDIN_FILENO, &OLD_TERMINAL_PARAMS);
  // Copy params
  new_terminal_params = OLD_TERMINAL_PARAMS;
  // Change params
  // Remove ICANON flag (wait for enter) and ECHO flag (print stdin)
  new_terminal_params.c_lflag &= ~(ICANON | ECHO);
  // Apply params
  tcsetattr(STDIN_FILENO, TCSANOW, &new_terminal_params);

  refresh();
}

void game_close() {
  clear_screen();

  // Amélioration Input
  // Restore old params
  tcsetattr(STDIN_FILENO, TCSANOW, &OLD_TERMINAL_PARAMS);

  refresh();
}

// Amélioration Compteur
// Extra: une couleur différente à chaque fois que le compteur change
unsigned int CAR_COUNTER = 0;
void *counter_thread(void *param) {
  int counter_color = 0;
  int last_count = CAR_COUNTER;
  while (1) {
    if (CAR_COUNTER != last_count) {
      counter_color = (counter_color + 1) % 6;
      last_count = CAR_COUNTER;
      move_cursor(3, ROAD_SIZE + 2);
      color(counter_color);
      fprintf(stdout, "%d", CAR_COUNTER);
    }
    sleep(1);
  }
  return NULL;
}

void *car_thread(void *param) {
  int car = *((int *)param);

  unsigned int car_color = rand() % 6;

  unsigned int increment, x, y, base_sleep = 80000;
  char logo;

  if (car == 0) {
    increment = -1;
    x = ROAD_SIZE + 1;
    y = 2;
    logo = '<';
  } else {
    increment = 1;
    x = 0;
    y = 4;
    logo = '>';
  }

  // Amélioration Compteur
  CAR_COUNTER++;

  for (int i = 1; i < ROAD_SIZE; i++) {
    // We check if we can move
    // TODO
    // We reset old position
    move_cursor(y, x);
    fputc(' ', stdout);
    // We move to new position
    if (car == 0) {
      if (x == RIGHT_LIMIT || x == RIGHT_LIMIT + 1) {
        y++;
        base_sleep = 110000;
      } else if (x == LEFT_LIMIT || x == LEFT_LIMIT + 1) {
        y--;
        base_sleep = 110000;
      } else {
        base_sleep = 80000;
      }
    }
    x += increment;
    move_cursor(y, x);
    // Amélioration Couleur
    color(car_color);
    fputc(logo, stdout);
    move_cursor(1, ROAD_SIZE + 1);
    refresh();
    // We release the lock if we're out of the critical part of the road
    // TODO
    usleep(base_sleep + rand() % 10000);
  }

  move_cursor(y, x);
  fputc(' ', stdout);
  move_cursor(1, ROAD_SIZE + 1);
  refresh();

  return NULL;
}

// Amélioration Messages
void *error_thread(void *param) {
  color(0);
  move_cursor(11, 1);
  fprintf(stdout, "Unrecognised input.");
  refresh();

  sleep(2);

  color(0);
  move_cursor(11, 1);
  fprintf(stdout, "                   ");
  refresh();
  return NULL;
}

int main(int argc, char **argv) {

  {
    char buf[10];
    printf("Quel taille doit faire la route ? (défaut 40, min 20) → ");
    fgets(buf, 10, stdin);
    int size = atoi(buf);
    if (size < 20) {
      ROAD_SIZE = 40;
    } else {
      ROAD_SIZE = size;
    }
  }

  game_init();

  pthread_t last, unused_thread_id;

  // Amélioration Compteur
  pthread_create(&unused_thread_id, NULL, counter_thread, NULL);

  char input;

  int car_arg;

  do {
    input = fgetc(stdin);
    switch (input) {
    case 'j':
    case 'k':
      if (input == 'j') {
        car_arg = 1;
      } else {
        car_arg = 0;
      }

      pthread_create(&last, NULL, car_thread, &car_arg);

      color(0);
      move_cursor(11, 1);
      fprintf(stdout, "                   ");
      refresh();
      break;
    case 'q':
      // Amélioration Messages
      color(0);
      move_cursor(11, 1);
      fprintf(stdout, "Quitting.          ");
      refresh();
      break;
    default:
      // Amélioration Messages
      pthread_create(&unused_thread_id, NULL, error_thread, NULL);
    }
  } while (input != 'q');

  pthread_join(last, NULL);

  game_close();
}

Le code introduit cette nouvelle fonctionnalité, mais aucune synchronisation n'est mise en place. Les voitures peuvent donc rouler les unes sur les autres, ce qui est impossible dans la vraie vie.

Le tronçon de route unique est une ressource limitée.

Le but de cet exercice est d'améliorer le code, pour empêcher les voitures de se rouler dessus.

Le code à ajouter se fait au niveau des TODO écrits dans le code (plus l'initialisation).

On va utiliser un mutex partagé entre tous les threads, comme dans l'exercice 1.

Indice 1

Vous allez devoir utiliser les fonctions suivantes, qui existent déjà dans la librairie pthread.h:

// Le deuxième argument est facultatif
pthread_mutex_init(pthread_mutex_t *mutex, pthread_mutexatttr_t *optional_attribute);
pthread_mutex_lock(pthread_mutex_t *mutex);
pthread_mutex_unlock(pthread_mutex_t *mutex);

Indice 2

L'initialisation doit se faire une fois au début du programme.

Indice 3

On doit bloquer le mutex avant de passer sur le tronçon de route. Pour savoir quand c'est le moment de bloquer ou débloquer, on s'aidera des constantes LEFT_LIMIT et RIGHT_LIMIT.

Indice 4

On doit débloquer le mutex quand on a fini de passer sur le tronçon de route. Pour savoir quand c'est le moment de bloquer ou débloquer, on s'aidera des constantes LEFT_LIMIT et RIGHT_LIMIT.

On ne cherchera pas à faire en sorte que les voitures attendent à la queue-leu-leu. Ce n'est pas grave qu'elles attendent toutes au même endroit

Exercice 3

On va partir du code de l'exercice 2, mais écrire dans un nouveau fichier, à rendre séparément :

votrelogin_cars_sem.c

Afin de permettre à plusieurs voitures d’être sur la voie rétrécie simultanément, on va utiliser deux sémaphores, un par voie. Chacun de ces sémaphores peut être vu comme un feu de circulation.

Pour simplifier la synchronisation de ces feux, celle-ci sera effectuée par un thread à part qui s'occupera de bloquer un des sémaphores de voie, puis l’autre à intervalle régulier.

On aura besoin des fonctions suivantes, vues en cours :

#include <semaphore.h>
sem_init(sem_t *sem, int pshared, int value);
sem_wait(sem_t *sem);
sem_post(sem_t *sem);

Voilà un exemple simple d'utilisation d'un sémaphore :

sem_t s;
// Initialisé à 1, un sémaphore se comporte comme un mutex : il ne permet qu'un
// accès concurrent à la ressource partagée.
// Initialisé à 2, un sémaphore permet 2 accès concurrents à la ressource partagée.
sem_init(&s, 0, 1);
// L'équivalent de lock : enlève 1 au sémaphore, et bloque si on tombe à zéro
sem_wait(&s);
// L'équivalent de unlock : rajoute 1 au sémaphore
sem_post(&s);

Il est suggéré de faire une fonction switchLanes qui se charge de bloquer le sémaphore de la voie qui est libre puis de libérer le sémaphore de celle qui bloquée. Cette fonction sera appelée à intervalle régulier dans un thread autonome.

Exercice 4 - Bonus

On partira du code de l'exercice 3.

Réfléchir à comment faire pour éviter que les voitures ne stationnent toutes sur la même case.

On indiquera en commentaire à la fin du fichier quelle est la proposition de solution.

Toute tentative d'implémentation est également bienvenue !