Laboratoire 12 - Outils de synchronisation

Page content

Remarque: n’oubliez pas, lors de l’utilisation d’appels systèmes, de traiter les cas d’erreur.

Dîner des philosophes

Le problème du Dîner des philosophes consiste en un nombre de n (habituellement égal à cinq) de philosophes assis autour d’une table ronde, sur laquelle sont installées n assiettes et n couverts. Chaque philosophe dispose d’un couvert de chaque côté de son assiette.

Les philosophes, ont trois états penser, manger, attendre de manger. Les philosophes commencent tous dans l’état penser. Lorsque l’un d’eux se décide à faire une pause pour manger, il cherche à prendre les deux couverts qui se trouvent de chaque côté de son assiette. Si un de ses voisins mange déjà, il devra attendre pour manger jusqu’à que les deux couverts soient disponibles.

Le programme prend fin dès qu’un nombre de cycles penser-manger fournis en argument aura été réalisé par chaque philosophe.

  • Vous devrez compléter le squelette du programme diner_phi ci-dessous de manière à éviter les problèmes liés à la concurrence. Chaque philosophe (cinq dans notre cas) est représenté par un thread distinct. Le temps passé dans l’état manger et penser est compris entre 1 et 5 secondes obtenu de manière semi-aléatoire avec la fonction rand. Lorsqu’un philosophe veut manger il doit vérifier si les couverts à sa droite et à sa gauche sont disponibles si c’est le cas il peut manger.
    • N’oubliez pas de passer l’option -pthread à gcc lors de la compilation du programme.
    • Les fonctions suivantes pourraient vous servir: pthread_create, pthread_join, pthread_mutex_init, pthread_mutex_destroy, pthread_mutex_lock, pthread_mutex_trylock, pthread_mutex_unlock
  1. Développez une première version de diner_phi sans utiliser de mutex. Dans cette version, un seul philosophe peut manger à la fois. Si un philosophe est déjà en train de manger, tout autre philosophe qui est prêt doit attendre de 1 à 5 secondes avant de retenter.
  2. À partir de votre programme diner_phi développé à l’étape précédente améliorez la synchronisation en utilisant un mutex. Dans cette version, il n’y a toujours qu’un seul philosophe qui peut manger à la fois.
  3. Finalement, développez un version de diner_phi où plus d’un philosophe peut manger à la fois.
    • Nous vous recommandons d’utiliser un mutex par couvert.
    • Attention à l’ordre d’acquisition et de libération des couverts!
  4. Avec l’utilitaire time(1) comparez le temps d’exécution du squelette fourni et de vos 3 versions du programme. Que constatez vous? Quelles versions du programme évitent réellement les problèmes de concurrence?
    • Afin d’éviter les différences dues au temps d’attente aléatoire, mettez en commentaire la première ligne de la fonction attendre et décommentez la ligne int sleep_time = 1;.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

#define NOMBRE_DE_PHILOSOPHE 5
#define NOMBRE_DE_REPAS 2

void attendre() {
  int sleep_time = (rand() % 5) + 1;
  // int sleep_time = 1;
  sleep(sleep_time);
}

// Tableau qui contient le nombre de repas mangés par chaque philosophe.
// Tableau qui contient le nombre de repas mangés par chaque philosophe.
int nombre_repas[NOMBRE_DE_PHILOSOPHE];

// Ajoutez la structure nécessaire pour gérer la concurrence.

// Fonction pour faire penser le philosophe pendant un temps aléatoire (entre 1 et 5s)
void pense(int id_philosophe){
  printf("Le philosophe %d pense.\n", id_philosophe);
  attendre();
}

// Fonction pour faire manger le philosophe pendant un temps aléatoire (entre 1 et 5s)
void mange(int id_philosophe){
  printf("Le philosophe %d mange.\n", id_philosophe);
  nombre_repas[id_philosophe]++;
  attendre();
}

void prendre_couverts(int id_philosophe){
  //À completer
}

void poser_couverts(int id_philosophe){
  //À completer
}

void *philosophe(void *arg){
    int id_philosophe = *(int *)arg;
    while(nombre_repas[id_philosophe] < NOMBRE_DE_REPAS)
    {
        pense(id_philosophe);
        prendre_couverts(id_philosophe);
        mange(id_philosophe);
        poser_couverts(id_philosophe);
    }

    printf("Le philosophe %d sort de table.\n", id_philosophe);
}

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

  // À compléter: Initialisation des éléments utilisés pour la synchronisation

  pthread_t phi_thread[NOMBRE_DE_PHILOSOPHE];
  int tab[NOMBRE_DE_PHILOSOPHE];

  int i;
  // Création de l'ensemble des threads (1 thread par philosophe), qui exécuteront la fonction philosophe
  for (i=0; i < NOMBRE_DE_PHILOSOPHE; i++){
    tab[i]=i;
    pthread_create( phi_thread + i, NULL , philosophe, &tab[i]) ;
  }

  // Attendre que l'ensemble des threads soit terminé.
  for (i=0; i < NOMBRE_DE_PHILOSOPHE; i++){
    pthread_join( phi_thread[i], NULL ) ;
  }

  // À compléter: Nettoyage des éléments utilisés pour la synchronisation


  return 0;
}