Les Moniteurs

Définition

Un moniteur est un outil évolué de synchronisation.

Introduits par Brinch & Hansen en 1972-73 et Hoare en 1974. Un moniteur =

des variables d'état ;
des procédures internes ;
des procédures externes (points d'entrée) ;
des conditions ;
des primitives de synchronisation.

Les variables d'état sont manipulables par les procédures externes seulement (encapsulation).

Un exemple simple de moniteur

Moniteur incr_decr
incr_decr : moniteur ; var i : entier ; procédure incrémente ; début i := i + 1 ; fin ; procédure décrémente ; début i := i - 1 ; fin ; début i := 0 ; fin fin incr_decr.

Chaque procédure du moniteur est exécutée en exclusion mutuelle.

l'accès au moniteur s'effectue en exclusion mutuelle. Sauf si un processus exécute la primitive attendre.

Les instructions spéciales des moniteurs

Les variables de type condition.

Les primitives vide, attendre et signaler.

Soit c une condition.

c.attendre : bloque le processus et le place en attente de c.
c.vide : vrai si aucun processus n'est en attente de c, faux sinon.
c.signaler : si non c.vide alors réveiller un processus en attente de c.

Rendez-vous entre N processus

Moniteur de Rendez-vous
rendez_vous : moniteur ; `.` var n : entier ; `.` tous_là : condition ; procédure arriver ; début n := n + 1 ; si n < N alors `.` tous_là.attendre ; tous_là.signaler ; fin ; début n := 0 ; fin fin rendez_vous.

À l'intérieur des moniteurs

Chaque moniteur possède une file d'attente globale.

Chaque variable condition référence une file d'attente.

c.attendre placer le processus dans la file d'attente associée à c.
c.signaler sortir le processus suivant de la file d'attente associée à c.
c.vide teste si la file d'attente associée à c est vide.

Problème : un seul processus actif à la fois au sein d'un moniteur, donc comment implémenter la primitive signaler ?

Note 1 : un moniteur est en général implémenté avec des ... sémaphores !

Note 2 : c'est tout à fait logique, un système est bâti par niveaux d'abstraction successifs, un niveau i étant implémenté par les primitives du niveau i-1.

Problème des producteurs-consommateurs

processus producteur	processus consommateur
... produire(message_produit) ; tampon.déposer(message_produit) ; ...	... tampon.retirer(message_à_consommer) ; consommer(message_à_consommer) ; ...

À quoi ressemble le moniteur tampon ?

Moniteur tampon

tampon : moniteur ;

. var n : 0..N ;
. non_plein, non_vide : condition ;

procédure déposer(m : message) ;
début
si n = N alors
. non_plein.attendre ;
n := n + 1 ;
entrer(m) ;
non_vide.signaler ;
fin ;

procédure retirer( var m : message) ;
début
si n = 0 alors
. non_vide.attendre ;
sortir(m) ;
n := n - 1 ;
non_plein.signaler ;
fin ;

. type message : ... ;
. var file : tableau[0..N-1] de message ;
. tête, queue : 0..N-1 ;

procédure entrer(m : message) ;
début
file[queue] := m ;
queue := (queue + 1) mod N ;
fin ;

procédure sortir( var m : message) ;
début
m := file[tête] ;
tête := (tête + 1) mod N ;
fin ;

début
n := 0 ;
tête := 0 ;
queue := 0 ;
fin

fin tampon.

Moniteur tampon
tampon : moniteur ; `.` var n : 0..N ; `.` non_plein, non_vide : condition ; procédure déposer(m : message) ; début si n = N alors `.` non_plein.attendre ; n := n + 1 ; entrer(m) ; non_vide.signaler ; fin ; procédure retirer( var m : message) ; début si n = 0 alors `.` non_vide.attendre ; sortir(m) ; n := n - 1 ; non_plein.signaler ; fin ; `.` type message : ... ; `.` var file : tableau[0..N-1] de message ; `.` tête, queue : 0..N-1 ; procédure entrer(m : message) ; début file[queue] := m ; queue := (queue + 1) mod N ; fin ; procédure sortir( var m : message) ; début m := file[tête] ; tête := (tête + 1) mod N ; fin ; début n := 0 ; tête := 0 ; queue := 0 ; fin fin tampon.

Problème des lecteurs-rédacteurs

Soit un fichier (SGBD, ...) manipulé par deux sortes de processus différents :

les lecteurs qui consultent le fichier sans en modifier le contenu ;
les rédacteurs qui peuvent en modifier le contenu.

Soient nlect et nred le nombre de lecteurs et rédacteurs accédant au fichier à un instant donné.

Il faut respecter les contraintes d'intégrité (maintien de la cohérence) :

nred = 0 et nlect 0 ;
nred = 1 et nlect = 0 ;

Moniteur lecteur_rédacteur
lecteur_rédacteur : moniteur ; `.` var ecr : booléen ; `.` nl : entier ; `.` c_ecr, c_lect : condition ; procédure début_lire ; début nl := nl + 1; si ecr alors `.` c_lect.attendre ; `.` c_lect.signaler ; fin ; procédure fin_lire ; début nl := nl - 1; si nl = 0 alors `.` c_ecr.signaler ; fin ; procédure début_écrire ; début si ecr ou nl > 0 alors `.` c_ecr.attendre ; ecr := vrai ; fin ; procédure fin_écrire ; début ecr := faux ; si nl > 0 alors `.` c_lect.signaler ; sinon `.` c_ecr.signaler ; fin ; début ecr := faux ; nl := 0 ; fin fin lecteur_rédacteur.

Moniteur lecteur_rédacteur

lecteur_rédacteur : moniteur ;

. var ecr : booléen ;
. nl : entier ;
. c_ecr, c_lect : condition ;

procédure début_lire ;
début
nl := nl + 1;
si ecr alors
. c_lect.attendre ;
. c_lect.signaler ;
fin ;

procédure fin_lire ;
début
nl := nl - 1;
si nl = 0 alors
. c_ecr.signaler ;
fin ;

procédure début_écrire ;
début
si ecr ou nl > 0 alors
. c_ecr.attendre ;
ecr := vrai ;
fin ;

procédure fin_écrire ;
début
ecr := faux ;
si nl > 0 alors
. c_lect.signaler ;
sinon
. c_ecr.signaler ;
fin ;

début
ecr := faux ;
nl := 0 ;
fin

fin lecteur_rédacteur.

Critiques :

La priorité est donnée aux lecteurs.

Questions :

comment donner la priorité aux rédacteurs ?
comment équitablement gérer la priorité (mais est-ce souhaitable ?) ?

Retour au sommaire.