Ce document de Travaux Dirigés (TD) est conçu pour les étudiants universitaires, notamment ceux suivant le cours de Systèmes d'Exploitation Avancés en première année d'ingénierie. Il vise à renforcer la compréhension des mécanismes de synchronisation et de gestion des processus.
Le contenu explore:
- La synchronisation à l'aide des sémaphores, avec un cas pratique sur les processus producteur-consommateur.
- L'implémentation de la synchronisation via les moniteurs, appliquée aux problématiques classiques telles que les lecteurs-rédacteurs et la gestion du trafic ferroviaire sur voie unique.
TD9 : Révision Systèmes d’Exploitation Avancés
Télécharger PDFCorrection TD9 : Révision Systèmes d’Exploitation Avancés
Télécharger PDFExercice 1 : Les Sémaphores
Les processus A, B, C sont trois processus indépendants qui s'exécutent à l'infini. Ils réalisent des calculs que l'on note respectivement CalA, CalB et CalC. Le processus A produit des messages dans un tampon (buffer) nommé Buff.
Les deux processus B et C doivent lire tous ces messages dans Buff. Les processus disposent en mémoire commune d'un tampon de N cases, de Buff[0] à Buff[N-1], chacune capable de contenir un message.
On dispose des procédures Ecrire(Buff[i], M), Lire(Buff[i], M) et Supprimer(Buff[i]) pour lire, écrire ou supprimer le message M dans la case Buff[i] du tampon.
Le comportement des processus est le suivant (dans une boucle infinie) :
- Le processus A effectue un calcul
CalA, puis écrit un message dans le tampon. - Les processus B et C lisent les messages écrits par A dans le
Buffet effectuent, respectivement le traitementCalBetCalCaprès chaque lecture. - Un message n'est supprimé du tampon que lorsqu'il est lu par B et par C (peu importe l'ordre de sa lecture).
- Les processus B et C sont indépendants, de sorte que chacun est susceptible de prendre temporairement de l'avance par rapport à l'autre.
Voici le pseudo-code des processus A, B et C qui assure le comportement décrit ci-dessus ainsi que la cohérence des données dans le tampon, à l'aide de sémaphores.
Initialisation des sémaphores :
Semaphore FullB = 0
Semaphore FullC = 0
Semaphore Empty = N
Semaphore Mutex = 1
Tableau Lu[N] = false (tableau de booléens indiquant si une case a été lue par l'un des deux consommateurs)
Pseudo-code du Processus A (Producteur)
While (true) {
Down (empty)
CalA
Down (mutex)
Ecrire (Buff[i], M)
Lu[i] = false
Up (mutex)
Up (fullB)
Up (fullC)
}
Pseudo-code des Processus B et C (Consommateurs)
(Le processus C est identique au processus B, attendant sur fullC et exécutant CalC)
Processus B
While (true) {
Down (fullB)
Lire (Buff[i], M)
CalB
Down (mutex)
If (Lu[i]) { // Si l'autre processus (C) a déjà lu ce message
Supprimer (Buff[i])
Up (empty)
} Else { // Sinon, marquer que ce processus (B) a lu le message
Lu[i] = true
}
Up (mutex)
}
Cette implémentation garantit qu'un message n'est libéré du tampon (et la case marquée comme vide) que lorsque les deux consommateurs B et C l'ont traité.
Exercice 2 : Les Moniteurs
1. Problème des Lecteurs-Rédacteurs
Le problème des lecteurs-rédacteurs concerne la synchronisation d'accès à une ressource partagée (par exemple, un fichier ou une base de données) par deux types de processus :
- Lecteurs : qui consultent la ressource sans en modifier le contenu. Plusieurs lecteurs peuvent accéder simultanément à la ressource.
- Rédacteurs : qui peuvent modifier le contenu de la ressource. Un seul rédacteur à la fois peut accéder à la ressource, et aucun lecteur ne doit y accéder pendant qu'un rédacteur est actif.
Soient nlect et nred le nombre de lecteurs et rédacteurs accédant au fichier à un instant donné.
Voici l'implémentation d'un moniteur pour gérer l'accès concurrentiel, tel que fourni dans l'exercice :
Moniteur lecteur_rédacteur
lecteur_rédacteur : moniteur ;
var
ecr : booléen ; // Vrai si un rédacteur est actif
nl : entier ; // Nombre de lecteurs actifs
c_ecr, c_lect : condition ; // Variables de condition pour les rédacteurs et les lecteurs
procédure début_lire ;
début
nl := nl + 1;
si ecr alors
c_lect.attendre ;
c_lect.signaler ; // ATTENTION : Ce signal est généralement incorrect ici, car un lecteur en attente ne devrait pas signaler un autre.
fin ;
procédure fin_lire ;
début
nl := nl - 1;
si nl = 0 alors // Si plus aucun lecteur n'est actif
c_ecr.signaler ; // Réveiller un rédacteur en attente
fin ;
procédure début_écrire ;
début
si ecr ou nl > 0 alors // Si un rédacteur est actif ou des lecteurs sont présents
c_ecr.attendre ;
ecr := vrai ; // Autoriser le rédacteur à procéder
fin ;
procédure fin_écrire ;
début
ecr := faux ; // Le rédacteur a terminé
si nl > 0 alors // S'il y a des lecteurs en attente
c_lect.signaler ; // Réveiller un lecteur (ou potentiellement tous selon l'implémentation de 'signal')
sinon // Sinon, s'il y a des rédacteurs en attente
c_ecr.signaler ; // Réveiller un rédacteur
fin ;
début // Initialisation du moniteur
ecr := faux ;
nl := 0 ;
fin
fin lecteur_rédacteur.
2. Problème des Trains sur Voie Unique
Ce problème simule la circulation de trains sur un tronçon de voie unique avec les règles suivantes :
- Le tronçon ne doit jamais être emprunté simultanément par deux trains allant en sens inverse.
- Le tronçon peut être emprunté par un ou plusieurs trains allant tous dans le même sens.
- Il n'y a pas de sens de parcours prioritaire.
Deux classes de processus sont introduites : les trains PONTOISE-ORLEANS et les trains ORLEANS-PONTOISE.
Tâche PONTOISE-ORLEANS :
Début
Parcours (PONTOISE, VERSAILLES) ;
Entrée_nord ;
Parcours (VERSAILLES, CHEVREUSE) ;
Sortie_sud ;
Parcours (CHEVREUSE, ORLEANS) ;
Fin
Tâche ORLEANS-PONTOISE :
Début
Parcours (ORLEANS, CHEVREUSE) ;
Entrée_sud ;
Parcours (CHEVREUSE, VERSAILLES) ;
Sortie_nord ;
Parcours (VERSAILLES, PONTOISE) ;
Fin
Voici le moniteur Troncon contenant les quatre points d'entrée (Entrée_nord, Sortie_sud, Entrée_sud, Sortie_nord) pour gérer la synchronisation des trains :
Type Troncon = moniteur {Variables locales}
Var NS, SN, AttNS, AttSN : entier ;
Accès_Nord, Accès_Sud : condition ;
{points d’entrée}
Procédure Entry Entrée_Nord ;
Début
Si (SN > 0) alors {blocage si trains dans l’autre sens}
AttNS = AttNS + 1 ;
Accès_Nord.Wait ;
finsi ;
NS = NS + 1 ; // Un train Nord-Sud entre
Si (AttNS > 0) alors {si des trains Nord-Sud sont en attente, réveil du prochain train}
AttNS = AttNS - 1 ;
Accès_Nord.Signal ;
finsi ;
Fin
Procédure Entry Sortie_Sud ;
Début
NS = NS - 1 ; // Un train Nord-Sud sort
Si (NS == 0) alors {dernier train Nord-Sud sorti}
Si (AttSN > 0) alors {si des trains Sud-Nord sont en attente, réveil du premier train}
AttSN = AttSN - 1 ;
Accès_Sud.Signal ;
finsi ;
finsi ;
Fin
Procédure Entry Entrée_Sud ;
Début
Si (NS > 0) alors {blocage si trains dans l’autre sens}
AttSN = AttSN + 1 ;
Accès_Sud.Wait ;
finsi ;
SN = SN + 1 ; // Un train Sud-Nord entre
Si (AttSN > 0) alors {si des trains Sud-Nord sont en attente, réveil du prochain train}
AttSN = AttSN - 1 ;
Accès_Sud.Signal ;
finsi ;
Fin
Procédure Entry Sortie_Nord ;
Début
SN = SN - 1 ; // Un train Sud-Nord sort
Si (SN == 0) alors {dernier train Sud-Nord sorti}
Si AttNS > 0 alors {si des trains Nord-Sud sont en attente, réveil du premier train}
AttNS = AttNS - 1 ;
Accès_Nord.Signal ;
finsi ;
finsi ;
Fin
Début {initialisations des variables locales}
NS = 0;
SN = 0 ;
AttNS = 0 ;
AttSN = 0 ;
Fin
Foire Aux Questions (FAQ)
Qu'est-ce qu'un sémaphore et comment aide-t-il à la synchronisation ?
Un sémaphore est un outil de synchronisation simple, utilisé en programmation concurrente pour contrôler l'accès à une ressource partagée ou pour signaler des événements entre processus. Il s'agit essentiellement d'un entier non négatif sur lequel on peut effectuer deux opérations atomiques : Down (ou P, ou wait), qui décrémente le sémaphore et bloque le processus si sa valeur est négative, et Up (ou V, ou signal), qui l'incrémente et réveille potentiellement un processus bloqué. Les sémaphores permettent d'assurer l'exclusion mutuelle (avec un sémaphore binaire) et la synchronisation de l'ordre d'exécution.
Quelle est la différence fondamentale entre un sémaphore et un moniteur ?
Les sémaphores et les moniteurs sont tous deux des mécanismes de synchronisation pour les processus concurrents, mais ils diffèrent dans leur abstraction et leur facilité d'utilisation. Un sémaphore est une primitive de bas niveau nécessitant une gestion explicite des opérations Down et Up par le programmeur, ce qui peut rendre le code sujet aux erreurs (oublis de Up, deadlocks). Un moniteur, en revanche, est une construction de plus haut niveau qui encapsule les données partagées et les procédures qui y accèdent, garantissant l'exclusion mutuelle automatiquement. Le moniteur gère l'accès de manière implicite et utilise des variables de condition pour la synchronisation, simplifiant ainsi le développement de code concurrent correct.
Quel est l'objectif principal du problème des Lecteurs-Rédacteurs ?
Le problème des Lecteurs-Rédacteurs vise à trouver une solution de synchronisation efficace et correcte pour l'accès concurrentiel à une ressource partagée. Il s'agit de permettre à plusieurs processus de lire la ressource simultanément (puisque la lecture ne modifie pas son état), tout en garantissant qu'un processus qui écrit a un accès exclusif à la ressource, c'est-à-dire qu'aucun autre lecteur ou rédacteur ne peut y accéder pendant qu'il écrit. L'objectif est de maximiser le parallélisme pour les lecteurs tout en maintenant l'intégrité des données lors des écritures.