Ce document, intitulé « TD4 : Synchronisation des processus avec des Sémaphores », est conçu pour les étudiants de première année d'ingénierie en Systèmes d'Exploitation Avancés.
Il propose une série d'exercices pratiques visant à approfondir la compréhension des mécanismes fondamentaux de synchronisation inter-processus à l'aide des sémaphores. Les problèmes classiques abordés incluent :
- Les barrières de synchronisation
- Le problème du dîner des philosophes
- Le problème du coiffeur endormi
- Le problème des lecteurs-rédacteurs
Exercice 1 : Barrières de Synchronisation
Les barrières de synchronisation sont des mécanismes qui forcent un groupe de processus ou de threads à attendre qu'un certain nombre d'entre eux atteignent un point précis de leur exécution avant de pouvoir continuer. Une fois ce point atteint par tous les participants requis, ils peuvent reprendre leur exécution.
Contexte Commun et Variables
Voici une implémentation simplifiée d'une barrière de synchronisation utilisant des sémaphores :
sémaphore mutex = 1; /* Sémaphore pour l'exclusion mutuelle lors de l'accès à NbArrivés */
sémaphore s = 0; /* Sémaphore pour bloquer les processus en attente */
int NbArrivés = 0; /* Nombre de processus arrivés au point de rendez-vous */
/* N est le nombre total de processus devant atteindre la barrière */Procédure de Rendez-vous (RDV)
Chaque processus qui doit se synchroniser appelle cette procédure :
Procédure RDV
Début
down(mutex); /* Accès exclusif à la variable NbArrivés */
NbArrivés = NbArrivés + 1;
Si (NbArrivés < N) Alors
/* Tous les processus ne sont pas encore arrivés */
up(mutex); /* Libère l'accès à NbArrivés */
down(s); /* Le processus se bloque en attendant les autres */
Sinon
/* Le dernier processus est arrivé */
up(mutex); /* Le dernier arrivé libère l'accès à NbArrivés */
Pour i = 1 à N-1 Faire
up(s); /* Réveille les N-1 processus qui sont bloqués sur le sémaphore 's' */
Finsi
FinDans cette implémentation, la fonction down() (aussi appelée P) décrémente la valeur du sémaphore et bloque le processus si la valeur devient négative. La fonction up() (aussi appelée V) incrémente la valeur du sémaphore et réveille un processus bloqué s'il y en a.
Exercice 2 : Le dîner des philosophes
Le problème du dîner des philosophes est un problème classique en informatique distribuée, illustrant les défis de la synchronisation et de la prévention des interblocages. N philosophes sont assis autour d'une table, avec une fourchette entre chaque paire. Chaque philosophe alterne entre penser et manger. Pour manger, un philosophe doit prendre les deux fourchettes adjacentes. L'objectif est d'éviter l'interblocage (situation où tous les philosophes prennent une fourchette et attendent l'autre indéfiniment) et la famine (un philosophe ne mange jamais).
Définitions et Variables Globales
#define N 5 /* Nombre de philosophes */
#define GAUCHE (i - 1 + N) % N /* Indice du voisin de gauche du philosophe i */
#define DROITE (i + 1) % N /* Indice du voisin de droite du philosophe i */
#define PENSE 0 /* État : Le philosophe est en train de penser */
#define FAIM 1 /* État : Le philosophe a faim et veut manger */
#define MANGE 2 /* État : Le philosophe est en train de manger */
typedef int sémaphore;
int état[N]; /* Tableau pour suivre l'état de chaque philosophe */
sémaphore mutex = 1; /* Sémaphore pour l'exclusion mutuelle lors de l'accès au tableau 'état' */
sémaphore s[N]; /* Un sémaphore par philosophe, initialisé à 0, pour le bloquer s'il ne peut pas manger */Note : Le calcul de GAUCHE a été ajusté à (i - 1 + N) % N pour gérer correctement l'indice du philosophe 0 sans résultat négatif.
Fonctions Principales
Procédure philosophe(int i)
philosophe(int i) { /* i : numéro du philosophe */
while(VRAI) {
penser();
prendre_fourchettes(i); /* Tente de prendre les deux fourchettes ou se bloque */
manger();
poser_fourchettes(i); /* Repose les deux fourchettes */
}
}Procédure prendre_fourchettes(int i)
prendre_fourchettes(int i) {
down(mutex); /* Entrée en section critique pour modifier l'état */
état[i] = FAIM;
test(i); /* Tente de prendre les fourchettes en vérifiant les voisins */
up(mutex); /* Quitte la section critique */
down(s[i]); /* Se bloque si les fourchettes n'ont pas pu être prises */
}Procédure poser_fourchettes(int i)
poser_fourchettes(int i) {
down(mutex); /* Entrée en section critique pour modifier l'état */
état[i] = PENSE; /* Le philosophe a fini de manger */
test(GAUCHE); /* Vérifie si le voisin de gauche peut maintenant manger */
test(DROITE); /* Vérifie si le voisin de droite peut maintenant manger */
up(mutex); /* Quitte la section critique */
}Procédure test(int i)
test(int i) {
if (état[i] == FAIM && état[GAUCHE] != MANGE && état[DROITE] != MANGE) {
état[i] = MANGE;
up(s[i]); /* Réveille le philosophe i s'il était bloqué */
}
}Cette solution utilise un sémaphore mutex pour protéger l'accès au tableau état, garantissant que les modifications de l'état des philosophes sont atomiques. Des sémaphores individuels s[N] sont utilisés pour bloquer et réveiller chaque philosophe selon la disponibilité des fourchettes.
Exercice 3 : Le problème du coiffeur endormi
Le problème du coiffeur endormi est un problème de synchronisation classique qui modélise l'interaction entre un coiffeur (un processus) et des clients (d'autres processus). Le coiffeur dort s'il n'y a pas de clients. Quand un client arrive, il réveille le coiffeur s'il dort. Si le coiffeur est occupé et toutes les chaises d'attente sont prises, le client quitte le salon. Sinon, le client prend une chaise d'attente.
Variables Globales et Sémaphores
#define N_CHAISES 5 /* Nombre de chaises d'attente dans le salon */
sémaphore Clients = 0; /* Bloque le coiffeur s'il n'y a pas de clients */
sémaphore Mutex = 1; /* Sémaphore pour l'exclusion mutuelle lors de l'accès à 'attente' */
sémaphore Coiffeurs = 0; /* Bloque un client si le coiffeur est occupé avec un autre client */
int attente = 0; /* Nombre de clients en attente */Logique du Coiffeur
void coiffeur() {
while(VRAI) {
down(Clients); /* Le coiffeur attend un client (se bloque si 'Clients' est à 0) */
down(Mutex); /* Accès à la section critique pour modifier 'attente' */
attente = attente - 1; /* Un client quitte la zone d'attente */
up(Coiffeurs); /* Informe le client que le coiffeur est prêt */
up(Mutex); /* Libère la section critique */
Couper_cheveux(); /* Le coiffeur coupe les cheveux */
}
}Logique du Client
void client() {
down(Mutex); /* Accès à la section critique pour vérifier les chaises */
if (attente < N_CHAISES) {
attente = attente + 1; /* Le client prend une chaise d'attente */
up(Clients); /* Informe le coiffeur de l'arrivée d'un client */
up(Mutex); /* Libère la section critique */
down(Coiffeurs); /* Le client attend que le coiffeur soit libre */
Obtenir_coupe(); /* Le client se fait couper les cheveux */
} else {
up(Mutex); /* Salon plein, le client quitte sans obtenir de coupe */
}
}Cette solution garantit que le coiffeur ne travaille que s'il y a des clients et que les clients n'attendent que s'il y a des chaises disponibles, évitant ainsi les interblocages et la famine.
Exercice 4 : Le problème des lecteurs-rédacteurs
Le problème des lecteurs-rédacteurs est un problème de synchronisation qui implique des processus (lecteurs et rédacteurs) accédant à une ressource partagée (par exemple, une base de données). Plusieurs lecteurs peuvent accéder à la ressource simultanément, mais un seul rédacteur à la fois peut y accéder. De plus, aucun lecteur ne doit accéder à la ressource pendant qu'un rédacteur est en train de l'utiliser, et inversement.
Variables Globales et Sémaphores
sémaphore mutex = 1; /* Contrôle l'accès à la variable partagée 'nb_lect' */
sémaphore db = 1; /* Contrôle l'accès exclusif à la base de données */
int nb_lect = 0; /* Compteur du nombre de lecteurs accédant actuellement à la base de données */Logique du Lecteur
void lecture() {
while (VRAI) { /* Boucle infinie */
down(mutex); /* Protéger l'accès à 'nb_lect' */
nb_lect++; /* Incrémente le nombre de lecteurs */
if (nb_lect == 1) {
down(db); /* Si c'est le premier lecteur, il bloque l'accès à la base de données pour les rédacteurs */
}
up(mutex); /* Libère l'accès exclusif à 'nb_lect' */
lire_la_BD(); /* Accès à la base de données (lecture) */
down(mutex);
nb_lect--; /* Décrémente le nombre de lecteurs */
if (nb_lect == 0) {
up(db); /* Si c'est le dernier lecteur, il libère l'accès à la base de données */
}
up(mutex);
utiliser_données(); /* Section restante : traitement des données lues */
}
}Logique du Rédacteur
void écriture() {
while (VRAI) { /* Boucle infinie */
créer_données(); /* Section restante : préparation des données à écrire */
down(db); /* Demande l'accès exclusif à la base de données */
ecrire_dans_la_BD(); /* Accès à la base de données (écriture) */
up(db); /* Libère l'accès exclusif à la base de données */
}
}Cette solution favorise les lecteurs, car un rédacteur ne peut accéder à la base de données que lorsqu'il n'y a plus aucun lecteur actif. Si des lecteurs continuent d'arriver, les rédacteurs peuvent être victimes de famine.
Foire Aux Questions (FAQ)
Qu'est-ce qu'un sémaphore et à quoi sert-il ?
Un sémaphore est une variable ou un type de données abstrait utilisé pour contrôler l'accès par plusieurs processus à une ressource commune dans un environnement multiprogrammé. Il sert principalement à garantir l'exclusion mutuelle et la synchronisation entre processus, empêchant les conditions de concurrence et les interblocages.
Quelle est la différence entre les opérations down() (P) et up() (V) ?
L'opération down() (ou P, pour "Proberen" - essayer en néerlandais) décrémente la valeur du sémaphore. Si la valeur devient négative, le processus appelant est bloqué jusqu'à ce qu'un autre processus effectue une opération up(). L'opération up() (ou V, pour "Verhogen" - augmenter) incrémente la valeur du sémaphore. Si des processus sont bloqués sur ce sémaphore, l'un d'eux est réveillé et peut reprendre son exécution.
Pourquoi la synchronisation des processus est-elle importante ?
La synchronisation des processus est cruciale pour assurer la cohérence des données et le bon fonctionnement des systèmes concurrents. Sans synchronisation, des problèmes comme les conditions de concurrence (où le résultat dépend de l'ordre d'exécution non déterministe), les interblocages (où des processus s'attendent mutuellement indéfiniment) et la famine (où un processus ne peut jamais accéder à une ressource) peuvent survenir, entraînant des comportements imprévisibles, des erreurs de données et une dégradation des performances du système.