Cours de systèmes
d’exploitation centralisés
Chapitre 5
Les Processus :
Outils de synchronisation
de haut niveau : Les moniteurs
Mr B. SOUICI – Mme L. BOUZAR
© 2018-2019
-1-
1. L’Exclusion Mutuelle
2. Synchronisation des processus avec sémaphores
3. Outils de synchronisation de haut niveau : Les moniteurs
-2-
Les moniteurs
1. INTRODUCTION
2. MONITEURS
2.1 Définition
2.2 Comment assurer l’exclusion mutuelle dans le moniteur ?
2.3 Structure syntaxique d'un moniteur
2.4 Implémentation des moniteurs par sémaphores
2.5 Exemples
2.5.1 Allocateur de ressources
2.5.2 Rendez-vous de n processus
2.5.3 Lecteurs-rédacteurs
2.5.4 Producteurs-consommateurs
-3-
1. INTRODUCTION
• Dans la technique de synchronisation avec sémaphores, un processus
exécute une opération P pour demander l’accès à la ressource, il exécute
une opération V pour la libérer et éventuellement réveiller un processus
en attente de cette ressource.
• L’action de V sur un sémaphore est mémorisée.
• Cette technique ne permet pas le contrôle dès la compilation: Les
variables partagées peuvent être utilisées, en dehors des sections
critiques, sans aucun contrôle.
• Les opérations P et V sont éparpillées dans le programmes ➔ Risque
d’erreur très important : On peut oublier, facilement, un P ou un V.
• D’autres outils de synchronisation existent et permettent d’écrire des
schémas de synchronisation plus clairs, plus structurés et contrôlables à
la compilation. On peut citer :
1) Les moniteurs (Hoare),
2) Les régions critiques conditionnelles (Brinsh Hansen et Hoare).- 4 -
2. MONITEURS
2.1 Définition
• Un moniteur BRINCH HANSEN[73] et HOARE[74] est une entité
syntaxique (module) qui regroupe :
✓ Les variables de synchronisation,
✓ Les ressources partagées,
✓ Les procédures qui manipulent les ressources partagées et les
variables de synchronisation.
• Par définition, les variables déclarées dans le moniteur ne sont
accessibles que par les procédures du moniteur.
• On distingue deux types de procédures du moniteur :
a) Internes : définies pour les besoins internes du moniteur et non
accessibles de l'extérieur.
BRINCH HANSEN[73]: Operating System Principles - Prentice-Hall, 1973.
HOARE[74]: “Monitors: An Operating System Structuring Concept” C.A.R. Hoare CACM,
Volume 17:10, pages 549–557, October 1974. -5-
b) Externes : accessibles de l'extérieur du moniteur, elles constituent
les points d'entrée du moniteur.
• Deux types de synchronisation(contrôle) sont définis dans un moniteur:
1. Exclusion mutuelle :
Réalisée, de manière implicite, entre les procédures du moniteurs ➔
Un seul processus à la fois peut exécuter les procédures du moniteur
jusqu'à ce qu'il sorte du moniteur ou jusqu'à son blocage.
2. Synchronisation :
Réalisée à l’aide de variables de synchronisation et des opérateurs
wait et signal:
✓ Les variables de synchronisation sont définies explicitement avec
l'attribut Condition : On les appelle variables condition.
✓ A chaque variable condition est associée une file d'attente de
processus.
✓ Sur les variables condition on peut appliquer Trois opérateurs :- 6 -
❖ Syntaxe générale
Variable [Link]érateur ou Opérateur(Variable condition).
a) Empty : Variable_Condition.empty
C'est une fonction booléenne qui renvoie :
✓ Vrai, si la file de la variable condition est vide(aucun processus
n’est bloqué derrière cette variable condition).
✓ Faux, si la file contient des processus.
b) Wait : Variable_Condition.Wait
Il permet d'exprimer des attentes sur condition en bloquant
systématiquement le processus qui l’exécute ➔
Le processus est inséré dans la file d'attente associée à la variable
condition concernée.
-7-
c) Signal : Variable_Condition.signal;
✓ Il permet de réveiller un processus bloqué dans la file d'attente
de la variable condition concernée.
✓ Si cette file d'attente est vide, le signal n'est pas mémorisé
et son action sera sans effet (pas de mémorisation du
signal).
• Sémantique de l’opérateur Signal
L’opérateur Signal tel qu‘il a été défini risque de provoquer une
violation de l’exclusion mutuelle dans le moniteur:
Deux processus peuvent se retrouver simultanément actifs à
l'intérieur du moniteur:
✓ Le processus qui a exécuté Signal est toujours dans le moniteur.
✓ Le processus réveillé par Signal risque de continuer son exécution
dans le moniteur.
-8-
2.2 Comment assurer l’exclusion mutuelle dans le moniteur ?
• Pour assurer l’exclusion mutuelle entre les procédures du moniteur, la
solution adoptée par HOARE consiste à donner la priorité au
processus réveillé ➔
Le processus exécutant Signal est bloqué jusqu'à ce que le processus
réveillé :
➢ Quitte le moniteur ou
➢ Se bloque à nouveau dans le moniteur ➔
➢ Les processus bloqués suite à une instruction Signal sont plus
prioritaires que les processus en attente(bloqués) sur un point
d’entrée. ➔
➢ Avant d’introduire un nouveau processus bloqué sur un
point d’entrée, vérifier s’il n y a pas de processus bloqués
suite à une instruction Signal.
-9-
1. Files d’attente d’un moniteur :
➢ Une file par moniteur pour assurer l’exclusion mutuelle :
le moniteur est une ressource critique,
➢ N files pour les processus en attente: une file pour chaque variable
condition,
➢ Une file pour les processus bloqués à la suite de l’exécution de
Signal.
Remarque : Si aucune variable condition n’a été déclarée ➔
- Zéro file (n=0) pour les processus en attente et
- Zéro file pour les processus bloqués à la suite d’un signal
(il n y aura aucun signal).
- 10 -
2. Représentation schématique des files d’attente du moniteur
- 11 -
2.3 Structure syntaxique d'un moniteur (1)
Nom : Moniteur;
✓ Déclaration des variables partagées;
✓ Déclaration des variables Condition;
✓ Déclaration des procédures externes:
Procédure Nom Entry(paramètres éventuels);
✓ Déclaration des procédures internes:
Procédure Nom(paramètres éventuels);
Début
✓ Initialisation des variables;
Fin du moniteur.
❖ Appel d’une procédure du moniteur (ou point d’entrée du moniteur)
Nom_du_moniteur.Nom _procédure_externe(paramètres);
- 12 -
2.3 Structure syntaxique d'un moniteur (2)
Nom : Moniteur;
✓ Déclaration des variables partagées;
✓ Déclaration des variables Condition;
✓ Déclaration des procédures externes;
Externe Nom1, Nom2, …, Nomn;
Procédure Nomi (paramètres éventuels);
✓ Déclaration des procédures internes;
Procédure Nom(paramètres éventuels);
Début
✓ Initialisation des variables;
Fin du moniteur.
Appel d’une procédure du moniteur (ou point d’entrée du moniteur).
Nom_du_moniteur.Nom _procédure_externe(paramètres);
- 13 -
2.4 Implémentation des moniteurs par sémaphores
• Signal peut apparaître n'importe où dans une procédure du moniteur.
• Le processus exécutant Signal doit se bloquer temporairement au profit
du processus qu'il a réveillé.
1) Exclusion mutuelle implicite
✓ Un seul sémaphore d‘exclusion mutuelle commun à toutes les procédures
externes suffit:
Sémaphore Mutex_nom_du_moniteur init 1;
✓ Un sémaphore Urgent derrière lequel seront bloqués les processus
exécutant une opération Signal.
Sémaphore Urgent init 0;
✓ Un compteur Urgent_count : permet de compter le nombre de processus
bloqués dans la file du sémaphore Urgent.
Entier Urgent_count init 0;
- 14 -
Traduction :
Toute procédure externe aura donc la forme suivante:
- 15 -
Procedure nom_proc(paramètres) Procedure nom_proc(paramètres)
Début Begin
Entrée de la procédure; P(Mutex_nom du moniteur);
Corps de la procédure; Corps de la procédure;
Begin
If (Urgent_count > 0) then
/* Réveiller un processus
bloqué à la suite de l’exécution
de Signal et quitter sans
Sortie de la procédure; libérer la SC */
V(Urgent);
Else
V(Mutex_nom_du_moniteur);
End;
Fin; End; - 16 -
2) Attentes
1. Attente sur une variable condition : [Link]
Associer à chaque variable condition :
• Un sémaphore de synchronisation cond_sem initialisé à 0;
Sémaphore cond_sem init 0;
• Un compteur de processus bloqués dans la file cond_count
initialisé à 0.
Entier cond_count init (0);
2. Attente temporaire des processus exécutant [Link] :
Le processus exécutant [Link] est bloqué jusqu’à ce que le
processus libéré quitte le moniteur ou se bloque à nouveau.
On utilise le sémaphore Urgent et le compteur Urgent_count définis
précédemment .
- 17 -
[Link] [Link];
Begin Begin
Cond_count := Cond_count + 1; If(Cond_count > 0) then
If (Urgent_count > 0) then Begin /* il y a des processus en
/* Réveiller un processus attente */
bloqué à la suite de Urgent_count := Urgent_count + 1;
l’exécution de Signal et
V(Cond_sem);
quitter sans libérer
la Section Critique */ /* le processus qui a exécuté signal
se met en attente(se bloque) */
V(Urgent);
P(Urgent);
Else V(Mutex_nom du moniteur);
Urgent_count := Urgent_count - 1;
P(Cond_sem);
End;
Cond_count := Cond_count - 1;
End;
End;
- 18 -
❖ Remarques :
L'interblocage entre processus exécutant des moniteurs différents est
possible:
• Une procédure d'un moniteur MA peut appeler une procédure d'un
autre moniteur MB pour le même processus : ➔
les 2 moniteurs restent verrouillés pendant cette exécution.
• Le moniteur MA comporte les procédures P1, P2,... , Pn.
• Le moniteur MB comporte les procédures L1, L2,... , Lm.
• Les appels croisés tels que:
[Link] appelle [Link] et
[Link] appelle [Link] ➔ Interblocage
Chaque moniteur ayant besoin des services de l'autre restera verrouillé
pendant toute l’exécution de ces appels croisés.
- 19 -
2.5 Exemples
2.5.1 Allocateur de ressources
a) Allocation d'une ressource critique (ex : une imprimante)
Processus i
Début
[Link];
Utiliser la ressource;
[Link]érer;
Fin du processus i;
- 20 -
Ressource : moniteur;
occupée : booléen; /* faux : ressource libre;
vrai : ressource occupée. */
Roccupée : condition; /* variable condition */
Externe Allouer, Libérer; /* procédures externes */
Procedure Allouer; Procedure Libérer;
Début Début
Si occupée alors Roccupé[Link]; occupée := Faux;
occupée := Vrai; Roccupé[Link];
Fin Allouer; Fin Libérer;
/* Initialisation */
Début
occupée := Faux;
Fin Ressource. - 21 -
b) Nombre de ressources est égal à n (ex : n imprimantes)
Processus i
Début
[Link];
Utiliser la ressource;
[Link]érer;
Fin du processus i;
- 22 -
Ressource : moniteur;
nlibre : entier; /* nlibre : nombre de ressources libres;
attendre : condition; /* variable condition */
Externe Allouer, Libérer; /* procédures externes */
Procedure Allouer; Procedure Libérer;
Début Début
nlibre := nlibre -1; nlibre := nlibre +1;
Si nlibre<0 alors [Link]; [Link];
Fin Allouer; Fin Libérer;
Procedure Allouer;
Début
Si nlibre=0 alors [Link];
nlibre := nlibre -1;
Fin Allouer;
/* Initialisation */
Début nlibre:= n;
Fin Ressource. - 23 -
Ressource : moniteur;
nlibre : entier; /* nlibre : nombre de ressources libres;
attendre : condition; /* variable condition */
Externe Allouer, Libérer; /* procédures externes */
Procedure Allouer; Procedure Libérer;
Début Début
nlibre := nlibre -1; nlibre := nlibre +1;
Si nlibre<0 alors [Link]; [Link];
Fin Allouer; Fin Libérer;
Procedure Allouer;
Début
Si nlibre=0 alors [Link];
nlibre := nlibre -1;
Fin Allouer;
/* Initialisation */
Début nlibre:= n;
Fin Ressource. - 24 -
2.5.2 Rendez-vous de N processus
Processus i
…
[Link]; /* point de rendez-vous */
…
Fin processus i
- 25 -
Rendez-vous : moniteur;
entier cpt ; /* nbre de processus arrivés au point de
rendez-vous*/
Rdv : condition; /* variable condition */
externe Arriver;
Procedure Arriver;
Début
cpt := (cpt+1) mod N;
Si cpt 0 alors [Link];
[Link]; /* réveil en cascade */
Fin Arriver;
Début
cpt := 0;
Fin Rendez-vous.
- 26 -
2.5.3 Problème des Lecteurs-Rédacteurs
Processusi
/* Lecture du fichier f */
Lecteur_Rédacteur.Demande_lecture
< Lire>
Lecteur_Rédacteur.fin_lecture
/* Ecriture du fichier f */
Lecteur_Rédacteur.Demande_ecriture
< Ecrire>
Lecteur_Rédacteur.fin_ecriture
- 27 -
a1) Ordre d’accès au fichier f quelconque
Lect_Rédacteur : moniteur;
ecrit : booléen ; nl : entier; clect, cecr: condition;
externe Demande_Lecture, Fin_Lecture,Demande_ecriture, Fin_écriture;
Procédure Demande_Lecture Procédure Demande_ecriture
Début Début
Si ecrit alors [Link]; Si ecrit ou (nl>0) alors [Link];
nl := nl + 1; ecrit := vrai ;
[Link]; /* réveil en cascade*/ Fin;
Sinon nl:=nl+1; Finsi
Fin;
Procédure Fin_lecture Procédure Fin_ecriture
Début Début
nl:= nl-1; ecrit:=faux;
Si nl=0 alors [Link]; Si [Link] alors
Fin; [Link];
Sinon
[Link] ;
Fin;
Début ecrit := faux ; nl := 0;
Fin lecteur_rédacteur. - 28 -
a2) Ordre d’accès au fichier f quelconque
Lecteur_Rédacteur : moniteur ;
ecrit : booléen ; nl : entier ; cf, cecr : condition ;
Externe Demande_lecture , Fin_lecture, Demande_ecriture, Fin_ecriture;
Procédure Demande_lecture Procédure Demande_ecriture
Début Début
Si ecrit alors [Link]; Si ecrit ou (nl > 0) alors [Link];
nl := nl + 1; Si ecrit ou (nl > 0) alors
[Link]; /* réveil en cascade début [Link]; [Link]; fin;
de processus lect ou red */ Finsi;
Sinon nl:=nl+1; Finsi ecrit := vrai ;
Fin; Fin;
Procédure Fin_lecture Procédure Fin_ecriture
Début Début
nl := nl-1; ecrit := faux;
Si nl = 0 alors Si non([Link]) Si non([Link]) Alors
Alors [Link]; [Link];
Sinon [Link]; Sinon
finsi [Link] ;
Fin; Fin;
Début ecrit := faux ; nl := 0 ;
Fin lecteur_rédacteur. - 29 -
b1) Ordre d’accès au fichier f selon FIFO
Lecteur_Rédacteur : moniteur;
ecrit : booléen ; nl : entier; cecr, Fifo : condition;
Externe Demande_lecture , Fin_lecture, Demande_ecriture, Fin_ecriture;
Procédure Demande_lecture Procédure Demande_ecriture
Début Début
Si(non([Link]) ou ecrit) alors Si ecrit ou (nl > 0 ) alors [Link];
[Link]; Ecrit := vrai; /* écriture ou
nl := nl + 1; attente d’écriture*/
[Link]; /* réveil en cascade*/ Si nl > 0 alors [Link];
Fin; Sinon
Ecrit := vrai; /* écriture*/
Finsi;
Fin;
Procédure Fin_lecture Procédure Fin_ecriture
Début Début
nl := nl-1; ecrit := faux;
Si nl = 0 alors Si non([Link]) [Link] ;
Alors [Link]; Fin;
Sinon [Link];
Finsi;
Fin;
Début ecrit := faux ; nl := 0 ;
Fin lecteur_rédacteur. - 30 -
b2) Ordre d’accès au fichier f selon FIFO
Lecteur_Rédacteur : moniteur;
ecrit : booléen ; nl: entier ; cecr,Fifo : condition ;
Externe Demande_lecture , Fin_lecture, Demande_ecriture, Fin_ecriture;
Procédure Demande_lecture Procédure Demande_ecriture
Début Début
Si(non([Link]) ou Si(non([Link]) ou (nl>0) ou
non([Link]) ou ecrit) alors non([Link]) ou ecrit)) alors
[Link]; [Link];
nl := nl + 1; Si nl>0 alors [Link];
[Link]; /* réveil en cascade*/ Finsi;
Fin; ecrit := vrai ; /* ecrire */
Fin;
Procédure Fin_lecture Procédure Fin_ecriture
Début Début
nl := nl-1; ecrit := faux;
Si nl = 0 alors [Link];
Si non([Link]) [Link]; Fin;
Sinon [Link];
Fin;
Début ecrit := faux ; nl := 0;
Fin lecteur_rédacteur. - 31 -
2.5.4 Modèle des producteurs-consommateurs
Programmes des producteurs et des consommateurs
Producteur Consommateur
Mp : message; Mc : message;
Début Début
Répéter Répéter
Produire(Mp); Prod_Cons.demande_retrait(Mc);
Prod_Cons.demande_dépot(Mp); Consommer(Mc);
Jusqu’à faux; Jusqu’à faux;
Fin; Fin;
- 32 -
Prod_Cons: moniteur ;
Plein entier; in, out : entier; Tampon : tableau[0..n-1] de message;
Nvide,Nplein : condition;
Externe demande_dépot, demande_retrait;
Procédure demande_dépot(Mp) Procédure demande_retrait(Mc)
Début Début
Si plein = n alors [Link]; Si plein = 0 alors [Link];
;
Déposer(Mp); Retirer(Mc);
Plein := plein + 1: Plein := plein - 1;
[Link]; /* signaler depôt*/ [Link]; /* signaler retrait*/
Fin; Fin;
Procédure déposer(Mp) Procédure Retier(Mc)
Début Début
Tampon[in] := Mp; Mc := Tampon[out];
In := (in +1) mod n; out := (out+1) mod n;
Fin; Fin;
Début
Plein := 0; in := 0; out := 0; Procédures
Fin Pro_Cons. internes
- 33 -
