Systèmes d’exploitation & Programmation Concurrente II

Ce TP porte sur la synchronisation et la communication inter-processus dans les systèmes d’exploitation. Il propose plusieurs exercices pratiques permettant de comprendre et d’implémenter des mécanismes classiques de synchronisation tels que les sémaphores, les mutex, et les variables conditionnelles. Pour réaliser ce TP, il est nécessaire de disposer d’un environnement de programmation supportant le multithreading (par exemple en C avec pthreads) et de connaissances de base sur les concepts de processus, threads et synchronisation.

Objectifs

• Comprendre et appliquer la synchronisation entre processus à l’aide de sémaphores.
• Résoudre le problème des lecteurs-rédacteurs en gérant l’accès concurrent aux ressources partagées.
• Implémenter une solution multithreadée au problème du dîner des philosophes en utilisant mutex et variables conditionnelles.
• Concevoir un schéma de synchronisation respectant des contraintes d’accès concurrent à une ressource partagée (stade d’athlétisme).

Prérequis et préparation

• Connaissances sur les sémaphores, mutex et variables conditionnelles.
• Environnement de développement C avec support POSIX threads (pthreads).
• Compréhension des concepts de section critique, exclusion mutuelle, et synchronisation conditionnelle.
• Accès à un compilateur C et un terminal pour exécuter les programmes multithreadés.

Exercice 1 : Synchronisation selon un graphe de précédence (DAG)

On considère un graphe orienté acyclique (DAG) représentant l’ordre d’exécution de cinq processus P1 à P5. Chaque processus ne peut démarrer que lorsque tous ses prédécesseurs ont terminé.

L’objectif est d’implémenter cette synchronisation en utilisant un nombre minimal de sémaphores.

Procédure :

• Initialiser les sémaphores s1, s2, s3, s4 et s5 à zéro.
• Le processus P0 débute et libère les sémaphores s1 et s2 avec V(s1) et V(s2).
• Le processus P1 attend sur s1 (P(s1)) avant de s’exécuter.
• Le processus P2 attend sur s2 (P(s2)), puis à la fin de son exécution, il libère s3 et s4 (V(s3), V(s4)).
• Le processus P3 attend sur s3 (P(s3)), puis libère s5 (V(s5)) après exécution.
• Le processus P4 attend sur s4 (P(s4)), puis libère également s5 (V(s5)).
• Le processus P5 attend deux fois sur s5 (P(s5), P(s5)) avant de s’exécuter.

Cette organisation garantit que chaque processus démarre uniquement lorsque tous ses prédécesseurs ont terminé, en utilisant un nombre minimal de sémaphores.

Exercice 2 : Problème des Lecteurs-Rédacteurs

Ce problème classique gère l’accès concurrent à une ressource partagée par plusieurs lecteurs et rédacteurs. Les lecteurs peuvent accéder simultanément à la ressource, tandis que les rédacteurs doivent y accéder de façon exclusive.

1. Rôle des sémaphores mutex et wrt

• mutex : protège l’accès à la variable Nread (nombre de lecteurs actifs) pour assurer l’exclusion mutuelle lors de son incrémentation/décrémentation. Sa valeur initiale est 1.
• wrt : contrôle l’accès exclusif à la ressource partagée. Il est pris par le premier lecteur entrant ou par un rédacteur. Sa valeur initiale est 1.

2. Diagramme de Gantt

En utilisant la table des temps d’arrivée et de traitement estimé des lecteurs (R1, R2, R3) et rédacteurs (W1, W2, W3), il faut tracer un diagramme de Gantt indiquant :

• Les processus en attente (bloqués sur un sémaphore).
• Les processus actifs occupant la section critique (lecture ou écriture).

Le diagramme doit refléter la synchronisation imposée par les sémaphores mutex et wrt, en respectant les priorités et les temps d’exécution.

Exercice 3 : Problème du dîner des philosophes

Ce problème illustre la gestion des ressources partagées (fourchettes) entre plusieurs threads (philosophes) pour éviter les blocages (deadlocks) et assurer la synchronisation.

Procédure

• Définir 5 threads, chacun représentant un philosophe.
• Utiliser un tableau Fourchette[5] pour indiquer l’état de chaque fourchette (LIBRE=0, OCCUPE=1).
• Protéger l’accès aux fourchettes avec un mutex global.
• Utiliser une variable conditionnelle condManger pour gérer l’attente des philosophes.
• La fonction Demande_a_manger(i) bloque le philosophe i tant que les fourchettes adjacentes sont occupées, puis les marque comme occupées et affiche un message.
• La fonction Fini_de_Manger(i) libère les fourchettes et signale la variable conditionnelle pour réveiller d’autres philosophes.
• Chaque philosophe alterne entre penser, demander à manger, manger, puis libérer les fourchettes, répété 10 fois.

#include <stdio.h>
#include <pthread.h>

#define NbTh 5
#define LIBRE 0
#define OCCUPE 1

pthread_t tid[NbTh];
pthread_mutex_t mutex;
pthread_cond_t condManger;
int Fourchette[5];

void Demande_a_manger (int i){
  pthread_mutex_lock(&mutex);
  while((Fourchette[i]==OCCUPE)||(Fourchette[(i+1)%5] == OCCUPE)){
    pthread_cond_signal(&condManger);
    pthread_cond_wait(&condManger, &mutex);
  }
  Fourchette[i]=OCCUPE;
  Fourchette[(i+1)%5] = OCCUPE;
  printf("Le philosophe %d obtient les fourchettes F%d et F%d et mange \n", i, i, (i+1)%5);
  pthread_mutex_unlock(&mutex);
}

void Fini_de_Manger(int i){
  pthread_mutex_lock(&mutex);
  Fourchette[i]=LIBRE;
  Fourchette[(i+1)%5] = LIBRE;
  pthread_cond_signal(&condManger);
  printf("Le philosophe %d libere ses fourchettes F%d et F%d\n", i, i, (i+1)%5);
  pthread_mutex_unlock(&mutex);
}

void * fonc_philosophe(void * i){
  int j;
  srand(pthread_self());
  for (j=0; j<10; j++) {
    printf("Le philosophe %d pense ...\n", (int)i);
    usleep(rand()%200000);
    printf("Le philosophe %d veut manger \n", (int)i);
    Demande_a_manger((int)i);
    usleep(rand()%1000000);
    Fini_de_Manger((int)i);
  }
}

int main(){
  int num;
  pthread_mutex_init(&mutex,0);
  pthread_cond_init(&condManger,0);
  for(num=0;num<NbTh;num++) Fourchette[num]=LIBRE;
  for(num=0;num<NbTh;num++)
    pthread_create(tid+num,0,(void *(*)(void *))fonc_philosophe,(void*)num);
  for(num=0;num<NbTh;num++)
    pthread_join(tid[num],NULL);
  pthread_mutex_destroy(&mutex);
  pthread_cond_destroy(&condManger);
  exit(0);
}

Cette solution évite l’utilisation de sémaphores et repose uniquement sur mutex et variables conditionnelles pour gérer l’accès aux fourchettes.

Exercice 4 : Synchronisation d’accès au stade d’athlétisme

Trois clubs d’athlètes (A, B, C) s’entraînent dans un stade avec la contrainte suivante :

• À un instant donné, le stade peut recevoir un nombre quelconque d’athlètes, mais provenant d’au plus deux clubs différents.
• Si un athlète d’un troisième club souhaite entrer, il doit attendre que le stade soit vide d’au moins un des deux clubs présents.

Proposition de schéma de synchronisation

Utiliser les sémaphores suivants :

• mut1, mut2, mut3 : sémaphores pour exclusion mutuelle sur les compteurs d’athlètes de chaque club, initialisés à 1.
• club : sémaphore initialisé à 2, représentant la capacité d’accueil simultané de deux clubs maximum.

Variables globales :

• int NA=0, NB=0, NC=0 ; nombre d’athlètes présents de chaque club.

{
  P(mut1);
  if (NA == 0) P(club);
  NA++;
  V(mut1);
  Entrainement();
  P(mut1);
  NA--;
  if (NA == 0) V(club);
  V(mut1);
}

{
  P(mut2);
  if (NB == 0) P(club);
  NB++;
  V(mut2);
  Entrainement();
  P(mut2);
  NB--;
  if (NB == 0) V(club);
  V(mut2);
}

{
  P(mut3);
  if (NC == 0) P(club);
  NC++;
  V(mut3);
  Entrainement();
  P(mut3);
  NC--;
  if (NC == 0) V(club);
  V(mut3);
}

Ce schéma garantit que le stade ne reçoit jamais plus de deux clubs simultanément. Lorsqu’un club entre pour la première fois, il prend une unité du sémaphore club. Lorsqu’il n’y a plus d’athlètes de ce club, il libère cette unité. Ainsi, un troisième club ne peut entrer que si une place est libérée.

Résultats attendus

• Exercice 1 : Les processus s’exécutent dans l’ordre défini par le graphe, sans violation des précédences.
• Exercice 2 : Le diagramme de Gantt reflète la synchronisation correcte entre lecteurs et rédacteurs, avec exclusion mutuelle pour les rédacteurs et accès concurrent pour les lecteurs.
• Exercice 3 : Les philosophes alternent entre penser et manger sans blocage ni famine, chaque philosophe obtenant les deux fourchettes nécessaires avant de manger.
• Exercice 4 : Le stade accueille simultanément des athlètes de deux clubs maximum. Un athlète d’un troisième club attend que le stade soit libéré d’au moins un club avant d’entrer.

Pièges courants

• Exercice 1 : Oublier d’initialiser les sémaphores à zéro ou mal gérer les opérations P/V peut entraîner un blocage ou une exécution hors ordre.
• Exercice 2 : Mauvaise gestion des sémaphores mutex et wrt peut provoquer des conditions de course, famine ou interblocage.
• Exercice 3 : Ne pas utiliser correctement les variables conditionnelles peut causer des blocages ou des accès simultanés aux fourchettes.
• Exercice 4 : Ne pas protéger les compteurs NA, NB, NC avec les mutex respectifs peut entraîner des erreurs de comptage et violer la contrainte des deux clubs maximum.