Les moniteurs

Introduction

Bien que les sémaphores fournissent un mécanisme pratique et efficace pour la synchronisation de processus, leur utilisation incorrecte peut toutefois conduire à des erreurs de synchronisation difficiles à détecter, puisqu'elles ne surviennent que si des séquences d'exécution particulières ont lieu et que celles-ci ne produisent pas toujours.

Pour l'illustrer, revoyons la solution du problème de la section critique utilisant les sémaphores. Tous les processus partagent un même sémaphore mutex initialisé à 1. Chaque processus doit exécuter mutex.P() avant d'entrer en section critique et ensuite mutex.V(). Si cette séquence n'est pas observée, deux processus peuvent être simultanément dans leur section critique. Cette situation peut résulter d'une erreur de programmation ou d'un programmeur non coopératif :

Supposez qu'un processus échange l'ordre dans lequel les opérations P() et V() sont effectuées sur le sémaphore mutex, conduisant à l'exécution suivante :

mutexV() ;
Section Critique ;
mutex.P() ;

Dans cette situation, plusieurs processus peuvent exécuter leurs sections critiques simultanément, violant ainsi le besoin d'exclusion mutuelle. Cette erreur peut être découverte uniquement si plusieurs processus sont actifs simultanément dans leur section critique. Cette situation n'est pas toujours reproductible.

Supposez qu'un processus remplace mutex.V() par mutex.P(). C'est à dire il exécute :

mutex.P() ;
Section Critique ;
mutex.P() ;

Dans ce cas, un interblocage apparaîtra.

Supposez qu'un processus omette soit le mutex.P() soit le mutex.V() ou les deux à la fois. Dans ce cas, l'exclusion mutuelle sera violée ou un inteblocage apparaîtra.
Ces exemples illustrent que divers types d'erreurs peuvent être facilement générés lorsque les programmeurs utilisent les sémaphores de manière incorrecte pour résoudre le problème de la section critique.

Pour traiter de telles erreurs, les chercheurs ont développé des constructions langage de haut niveau. Dans cette section, nous décrivons une construction fondamentale de haut niveau : le type moniteur.

Définition:

Les moniteurs sont des structures qui regroupent des invariables partagées par plusieurs processus et les instructions qui les manipulent.

Dans certains langages tel que : Concurrent Pascal, le moniteur est défini comme un type, dans la partie déclaration du programme.

Les variables partagées sont donc encapsulées dans le moniteur. Ces données sont accédées par l'intermédiaire d'un ensemble de méthodes publiques qui opèrent sur ces données.

Un moniteur présente un ensemble d'opérations définies par le programmeur à qui l'on fournit l'exclusion mutuelle à l'intérieur du moniteur.

Propriétés de moniteurs

Une procédure définie à l'intérieur d'un moniteur ne peut accéder qu'aux variables qui sont déclarées localement à l'intérieur du moniteur et à tous les paramètres formels qui sont passés aux procédures.

La structure du moniteur ne permet qu'à un seul processus à la fois d'être actif à l'intérieur d'un moniteur. Par conséquent, le programmeur n'a pas besoin de coder explicitement la synchronisation ; elle est bâtie dans le type moniteur.

Sa structure = procédure sans paramètres

A l'intérieur du moniteur, nous distinguons les différentes parties suivantes.

Déclaration des variables partagée qui ne sont pas accessibles en dehors du moniteur

Des procédures et des fonctions internes au moniteur. Elles sont les seules à manipuler des variables partagées. Leurs paramètres constituent le lien avec le programme.

Un corps comportant l'initialisation des variables.

Exemple:

type nombre_de_clients = Moniteur
Entier N ;

void incrémenter ()
{
N = N+1 ;
}
{
N = 0 ;
}

Le processus compteur admet une section critique qui consiste à incrémenter.
Compteur1 et Compteur2 n'exécutent plus N= N+1; ils font appel à la procédure incrémenter du moniteur.

Format de l'appel:

nom_du_moniteur. nom_de_la_procedure.

Tant que < le magasin_est_ouvert > faire
        si < entrée > alors Nombre_de_clients.incrémenter

Les variables de type condition ont un rôle particulier dans les moniteurs par le biais des opérations spéciales qui sont invoquées sur elles (wait et signal). Un programmeur qui doit écrire son schéma de synchronisation sur mesure peut définir une ou plusieurs variables de type condition :

Condition x,y;
L'opération: x.wait signifie que le processus invoquant cette opération est suspendu jusqu'à ce qu'un autre processus invoque x.signal.

L'opération x.signal reprend l'exécution d'un processus. Si aucun processus n'est suspendu, alors l'opération signal n'a pas d'effet ; c'est à dire que l'état de x est maintenu comme si l'opération n'avait jamais été exécutée. Opposons cette opération à l'opération V sur les sémaphores qui en affecte toujours l'état.

Maintenant supposons que lorsque l'opération x.signal est invoquée par un processus P, il y a un processus suspendu Q associé à la condition x. Clairement s, si le processus Q suspendu est autorisé à reprendre son exécution, le processus signalant P doit attendre. Dans le cas contraire, P et Q seraient tous deux simultanément actifs à l'intérieur du moniteur. remarquez cependant que les deux processus peuvent conceptuellement poursuivre leur exécution. Il existe deux possibilités

signal-and-wait - soit P attend que Q quitte le moniteur, soit il attend une autre condition ;

signal-and-continue - soit Q attend que P quitte le moniteur, soit il attend une autre condition.

Il existe des arguments raisonnables pour choisir l'une ou l'autre des solutions. Puisque P s'exécute déjà dans le moniteur, signal-and-continue semble plus raisonnable. Cependant, si nous autorisons le processus P à continuer, alors la condition logique pour laquelle Q attendait peut ne plus être valable au moment où Q reprendra son exécution.

signal-and-wait était défendu par Hoare, principalement du fait que l'argument précédent en sa faveur se traduisait directement en règles de preuves simples et élégantes.

Avantages des moniteurs

Les sections critiques sont transformées en fonctions ou procédures d'un moniteur. Elles ne sont plus dispersées

La gestion de ces sections n'est plus à la charge de l'utilisateur. Elle est réalisée par l'implantation du moniteur. Elle garantit qu'au plus 1 processus à la fois peut accéder à cette structure.

Le moniteur tout entier est implanté comme une section critique.

Quand un processus désire exécuter une opération concernant une variable partagée, il appelle une procédure particulière d'un moniteur. Cette procédure sera exécutée seulement si le moniteur est disponible. Si au contraire le moniteur est occupé le BCP du processus est placé dans une file d'attente associée au moniteur.
Dès que ce dernier(le moniteur) est libéré, un processus est choisi de la file et la procédure invoquée et exécutée :

De cette façon, le problème de la section critique (Exclusion Mutuelle) est réglé. Mais, pour obtenir la puissance d'expression de sémaphores et résoudre les problèmes de synchronisation il a fallu définir et introduire un nouveau type: Condition.

Variables de type Condition

Les variables de type condition peuvent être déclarées, à l'intérieur du moniteur de la manière suivante :

Condition X ;
Cette variable = file de processus en attente.
Elle peut être manipulée à l'intérieur du moniteur (uniquement) par 2 opérations:
Wait X.Wait;
Signal X.Signal;

Lorsqu'un processus, ayant appelé une procédure d'un moniteur, exécute une instruction X.Wait, il est mis en attente dans la file X. De plus, l'accès au moniteur redevient possible pour un autre processus.

L'exécution de X.Signal par un processus déclenche le réveil d'un autre processus en attente dans la file X. Si cette file est vide, l'instruction n'a aucun effet.

L'implantation de l'opération signal doit régler deux problèmes
Choix du processus à réveiller
Choix de celui à être exécuté à l'intérieur du moniteur.

Si P est le processus ayant exécuté X.Signal
Si Q est le processus réveillé par cette opération

L'un de ces deux processus doit reprendre son exécution tandis que l'autre doit être mis en attente, pour qu'un seul processus soit actif à l'intérieur du moniteur.

Solution

Choix du processus à réveiller : utilisation des files FIFO

Choix entre P et Q: pas d'arguments décisifs en faveur d'une solution. la solution de Hoare: faire attendre P jusqu'à ce que Q quitte le moniteur ou mis en attente sur une autre condition.

En concurrent Pascal: le processus P quitte imédiatemment le moniteur

Exemple: Ressource unique

Il est possible de définir un moniteur pour gérer cette ressource. (Simulation d'un sémaphore)

type Allocateur = Moniteur
Var
Booléen Occupé ;
Condition Libre ;

void acquisition()
{
Si Occupé alors Libre.Wait ;
Occupé = Vrai ;
}


void Libération()
{
Occupé = Faux ;
Libre.Signal ;
}

{
Occupé = Faux ;
}

Cet exemple est important de point de vue théorique : Pour prouver que nous n'avons rien perdu en puissance.

Implantation des moniteurs (Utilisant les sémaphores)

Une implantation possible, qui assure l'usage du moniteur en exclusion mutuelle, consiste à associer à chaque moniteur, un sémaphore "Ex_Mut" initialisé à 1.
Comme c'est le cas d'une S.C., l'entrée dans le moniteur est précédée d'une opération Ex_Mut.P(); la sortie du moniteur est suivie de Ex_Mut.V().
La file d'attente pour l'entrée dans le moniteur est celle du sémaphore Ex_Mut. Cependant, lorsqu'on choisit de faire attendre un processus ayant exécuté une opération Signal sur une variable condition il faut définir une file d'attente supplémentaire à l'intérieur du moniteur.

La file d'attente d'un autre sémaphore ("URGENT") joue ce rôle. Chaque processus après Un Signal sera placé en attente sur la file de ce sémaphore. La longueur de cette file est repérée par une variable entière : Longueur. Le compilateur remplace chaque procédure du moniteur par :

Ex_Mut.P()
corps de la procédure
Si Longueur > 0 Alors {
URGENT.V();
Longueur --;
}

Sinon Ex_Mut.V();

De cette façon, lorsqu'un processus sort du moniteur, il réveille en priorité un processus de la file du sémaphore URGENT. Si cette file est vide, il réveille un des processus en attente à l'entrée sur la file du sémaphore Ex_Mut.

L'implantatiion des variables de type condition se fait de manière analogue à l'aide des sémaphores et des variables entières. Ces dernières représentent la longueur de la file d'attente du sémaphore.

Le compilateur remplace donc chaque procédure du moniteur par :

Ex_Mut.P()
corps de la procédure
Si Longueur > 0 Alors {
URGENT.V() ;
Longueur -- ;
}

Sinon Ex_Mut.V() ;

Ex_Mut est un sémaphore initialisé à 1.
URGENT est un sémaphore initialisé à 0.

Toute variable de type condition sera implanté en utilisant un sémaphore initialisé à 0. Ainsi, Si on considère par exemple la déclaration suivante:

Condition C ;

L'opération C.Signal sera remplacée par le compilateur par la séquence suivante :

Si ! (C.Vide()) Alors {
C.V() ;
URGENT.P() ;
}
Si la file de C n'est pas vide alors on en réveille un processus ; le processus appelant se bloque dans la file URGENT

L'opération C.Wait sera, quant à elle, remplacé par le compilateur par la séquence suivante :

Si !(URGENT.Vide()) URGENT.V() ;
Sinon Ex_Mut.V() ;
C.Wait ;

Cette opération permet de libérer le moniteur et bloquer le processus appelant.