Processus et concurrence

Le langage de programmation Mesa fournit un support de langage pour l'exécution simultanée de plusieurs processus. Cela permet aux programmes étant intrinsèquement parallèles par nature d'être clairement exprimés. Le langage de programmation fournit également des fonctionnalités pour synchroniser ces processus au moyen d'une entrée dans des moniteurs et d'une attente sur des variables de condition.

La section suivante traite de la bifurcation et de la jonction de processus simultanés. Les sections suivantes traitent des moniteurs, de la manière dont leurs verrous sont spécifiés et de la manière dont ils sont entrés et sortis. Les variables de condition sont abordées, ainsi que leurs opérations associées.

Exécution simultanée, FORK et JOIN.

Les instructions FORK et JOIN permettent l'exécution parallèle de deux procédures. Leur utilisation nécessite également le nouveau type de données PROCESS. Étant donné que les fonctions de traitement Mesa offrent une flexibilité considérable, il est plus facile de les comprendre en examinant d'abord un exemple simple.

Un exemple de processus

Prenons l'exemple d'une application avec une routine frontale permettant la composition et l'édition interactives des lignes d'entrée :

L'appel :

collectera une ligne de saisie utilisateur jusqu'à un CR et la placera dans une chaîne de caractères nommée buffer. Bien sûr, l'appelant ne peut rien faire d'autre pendant la saisie de la ligne. S'il y a autre chose à faire, cela peut être fait en même temps que la saisie en faisant un fork vers ReadLine au lieu de l'appeler :

Cela permet aux instructions étiquetées calcul simultané de se dérouler en parallèle avec la saisie de l'utilisateur (clairement, le calcul simultané ne doit pas référencer le tampon de chaîne de caractères). La construction FORK génère un nouveau processus dont le type de résultat correspond à celui de ReadLine. (ReadLine est appelé la «procédure racine» du nouveau processus.)

Plus tard, les résultats sont récupérés par l'instruction JOIN, supprimant également le processus généré. Évidemment, cela ne doit pas se produire tant que les deux processus ne sont pas prêts (c'est-à-dire qu'ils n'ont pas atteint respectivement le JOIN et le RETURN) ; ce rendez-vous est synchronisé automatiquement par la fonction de processus.

Notez que les types des paramètres et des résultats de ReadLine sont toujours vérifiés au moment de la compilation, qu'il soit appelé ou qu'il soit forké.

La différence majeure entre l'appel d'une procédure et son fork réside dans la gestion des signaux.

Constructions du langage de processus

La déclaration d'un PROCESS est similaire à la déclaration d'une PROCEDURE, sauf que seul l'enregistrement de retour est spécifié. La syntaxe est formellement spécifiée comme suit :

Supposons que f soit une procédure et p un processus. Pour forker f et affecter le processus résultant à p, la ReturnClause de f et celle de p doivent être compatibles.

La syntaxe des instructions FORK et JOIN est simple :

Le ForkCall renvoie toujours une valeur (de type PROCESS) et donc un FORK ne peut pas être utilisé seul comme instruction. Contrairement à un appel de procédure, renvoyant un RECORD, la valeur du FORK ne peut pas être supprimée en écrivant un extracteur vide. L'action spécifiée par le FORK consiste à générer un processus parallèle à celui en cours et à le lancer en exécutant la procédure nommée.

Le JoinCall apparaît comme une instruction ou une expression, selon que le processus en cours de jointure possède ou non une ReturnsClause vide. Sa signification est la suivante : lorsque la procédure dupliquée a exécuté un RETURN, la JOIN est exécutée (dans l'un ou l'autre ordre) :

• Le processus de retour est supprimé
• Le processus de jointure reçoit les résultats et continue l'exécution.

Une phrase d'attrapage peut être attachée à un FORK ou à un JOIN en la spécifiant dans l'appel. Notez cependant qu'une telle phrase d'attrapage ne capte pas les signaux générés pendant l'exécution de la procédure.

Il existe plusieurs autres similitudes importantes avec les appels de procédure normaux méritant d'être notées :

• Les types de tous les paramètres et résultats sont vérifiés au moment de la compilation.
• Il n'existe aucune règle intrinsèque interdisant la coexistence simultanée de plusieurs activations (appels et/ou forks) de la même procédure. Bien sûr, il est toujours possible d'écrire des procédures fonctionnant de manière incorrecte si elles sont utilisées de cette manière, mais le mécanisme lui-même n'interdit pas une telle utilisation.

Un modèle d'utilisation attendu du mécanisme ci-dessus consiste à placer une paire FORK/JOIN correspondante au début et à la fin d'une unité textuelle unique (par exemple, une procédure, une instruction composée,...) de sorte que le calcul au sein de l'unité textuelle se produise en parallèle avec celui du processus généré. Ce style est encouragé, mais n'est pas obligatoire ; en fait, les FORK et JOIN correspondants n'ont même pas besoin d'être effectués par le même processus. Il faut bien sûr veiller à ce que chaque processus généré ne soit joint qu'une seule fois, car le résultat de la jonction d'un processus déjà supprimé n'est pas défini. Notez que le processus généré commence et termine toujours sa vie dans la même unité textuelle (par exemple, la procédure cible du FORK).

Bien que de nombreux processus aient tendance à suivre le paradigme FORK/JOIN, il y en aura d'autres dont le rôle sera mieux défini comme la fourniture continue de services plutôt que comme un calcul unique de résultats. Un tel processus «détaché» n'est jamais joint. Si sa durée de vie est limitée, sa suppression est une affaire privée, car elle n'implique ni synchronisation ni livraison de résultats. Aucune fonctionnalité de langage de programmation n'est requise pour cette opération.

Moniteurs

En général, lorsque deux ou plusieurs processus coopèrent, ils doivent interagir de manière plus complexe que simplement se diviser et se joindre. Un mécanisme plus général est nécessaire pour permettre une interaction ordonnée et synchronisée entre les processus. Le mécanisme de synchronisation interprocessus fourni dans Mesa est une variante des moniteurs adaptée des travaux de Hoare, Brinch Hansen et Dijkstra. L'idée sous-jacente est que l'interaction entre les processus se réduit toujours à un accès soigneusement synchronisé aux données partagées et qu'un véhicule approprié pour cette interaction est celui unifiant :

• La synchronisation
• Les données partagées
• Et le corps du code effectuant les accès.

La fonction de surveillance Mesa permet une grande souplesse d'utilisation. Avant d'entrer dans les détails, examinons d'abord une description légèrement simplifiée du mécanisme et un exemple simple. Le reste de cette section traite des bases des moniteurs ; WAIT et NOTIFY sont décrits plus loin.

Aperçu général des moniteurs

Un moniteur est une instance de module. Il possède donc ses propres données dans son cadre global et ses propres procédures pour accéder à ces données. Certaines de ces procédures sont publiques, ce qui permet d'effectuer des appels au moniteur depuis l'extérieur. Évidemment, des conflits peuvent survenir si deux processus s'exécutent simultanément sur le même moniteur. Pour éviter cela, un verrou de moniteur est utilisé pour l'exclusion mutuelle (c'est-à-dire pour garantir qu'un seul processus peut être dans chaque moniteur à tout moment). Un appel à un moniteur (à une procédure d'entrée) acquiert implicitement son verrou (en attente si nécessaire) et le retour du moniteur le libère. Le verrou du moniteur sert à garantir l'intégrité des données globales, étant exprimée comme l'invariant du moniteur -- c'est-à-dire une assertion définissant ce qui constitue un "bon état" des données pour ce moniteur particulier. Il incombe à chaque procédure d'entrée de restaurer l'invariant du moniteur avant de revenir, au bénéfice du prochain processus entrant dans le moniteur.

Les choses se compliquent un peu si un processus entre dans le moniteur et découvre que les données du moniteur, bien que dans un bon état, indiquent néanmoins que ce processus ne peut pas continuer jusqu'à ce qu'un autre processus entre dans le moniteur et améliore la situation. L'opération WAIT permet au premier processus de libérer le verrou du moniteur et d'attendre la condition souhaitée. L'opération WAIT est exécutée sur une variable de condition, étant associée par accord à la condition réelle requise. Lorsqu'un autre processus rend cette condition vraie, il exécute une NOTIFY sur la variable de condition, et le processus d'attente reprend là où il s'est arrêté (après avoir réacquis le verrou, bien sûr).

Par exemple, considérons un allocateur d'entreposage de blocs fixes fournissant deux procédures d'entrée : Allocate et Free. Un appelant d'Allocate peut trouver l'entreposage libre épuisé et être obligé d'attendre qu'un appelant de Free renvoie un bloc d'entreposage.

Notez qu'il est clairement indésirable que deux processus désynchronisés s'exécutent simultanément dans le StorageAllocator. L'utilisation de procédures d'entrée pour Allocate et Free assure une exclusion mutuelle. Le verrou du moniteur est libéré pendant l'attente dans Allocate afin de permettre l'appel de Free (cela permet également à d'autres processus d'appeler également Allocate, ce qui conduit à plusieurs processus en attente dans la file d'attente pour StorageAvailable).

Verrouillage du moniteur

La composante le plus simple d'un moniteur est son verrou. Un verrou de moniteur est un type prédéfini, pouvant être considéré comme un petit enregistrement :

Le verrou du moniteur est privé ; ses champs ne sont jamais explicitement consultés par le programmeur Mesa. Au lieu de cela, il est utilisé implicitement pour synchroniser l'entrée dans le code du moniteur, autorisant ainsi l'accès aux données du moniteur (et dans certains cas, à d'autres ressources, telles que les périphériques d'entrées/sorties,...). La section suivante décrit plusieurs types de moniteurs pouvant être construits à partir de ce mécanisme de base. Dans tous ces cas, l'idée est la même : lors de l'entrée dans un moniteur, il est nécessaire d'acquérir le verrou du moniteur en :

• Attendre : Dans la file d'attente jusqu'à ce que : locked = FALSE,
• Définir : locked ← TRUE.

Déclaration des modules de surveillance, procédures ENTRY et INTERNAL

En plus d'une collection de données et d'un verrou associé, un moniteur contient un ensemble de procédures effectuant des opérations sur les données. Les modules de surveillance sont déclarés de la même manière que les modules de programme ou de définition ; par exemple :

Les procédures d'un module de surveillance sont de trois types :

• Procédures d'entrée
• Procédures internes
• Procédures externes

Chaque moniteur possède une ou plusieurs procédures d'entrée ; celles-ci acquièrent le verrou du moniteur lorsqu'elles sont appelées et sont déclarées comme suit :

Les procédures d'entrée comprennent généralement l'ensemble des procédures publiques visibles par les clients du module de surveillance. (Il existe certaines situations dans lesquelles ce n'est pas le cas ; voir les procédures externes, ci-dessous). Les règles par défaut habituelles de Mesa pour les procédures PUBLIC et PRIVATE s'appliquent.

De nombreux moniteurs auront également des procédures internes : des routines communes partagées entre les différentes procédures d'entrée. Celles-ci s'exécutent avec le verrou du moniteur maintenu et peuvent ainsi accéder librement aux données du moniteur (y compris les variables de condition) si nécessaire. Les procédures internes doivent être privées, car les appels directs à celles-ci depuis l'extérieur du moniteur contourneraient l'acquisition du verrou (pour les moniteurs implémentés sous forme de modules multiples, ce n'est pas tout à fait correct). Les procédures internes ne peuvent être appelées qu'à partir d'une procédure d'entrée ou d'une autre procédure interne. Elles sont déclarées comme suit :

Les attributs ENTRY ou INTERNAL ne peuvent être spécifiés sur une procédure que dans un module de surveillance. Certains modules de surveillance peuvent souhaiter disposer de procédures externes. Celles-ci sont déclarées comme des procédures normales non liées au moniteur :

Ces procédures sont logiquement en dehors du moniteur, mais sont déclarées dans le même module pour des raisons de paquet logique. Par exemple, une procédure externe publique peut effectuer un traitement préliminaire, puis effectuer des appels répétés au moniteur proprement dit (via une procédure d'entrée privée) avant de retourner à son client. Étant en dehors du moniteur, une procédure externe ne doit référencer aucune donnée du moniteur (y compris les variables de condition), ni appeler aucune procédure interne. Le compilateur vérifie les appels aux procédures internes et l'utilisation des opérations de variables de condition (WAIT, NOTIFY,...) dans les procédures externes, mais ne vérifie pas les accès aux données du moniteur.

Un point important : En fait, les variables globales en lecture seulement et immuables sont accessibles par des procédures externes : il s'agit de données de surveillance modifiables étant strictement interdites.

D'une manière générale, une chaîne d'appels de procédure impliquant un module de surveillance a la forme générale suivante :

• Procédure Client -- en dehors du module
          ↓
• Procédures externes -- à l'intérieur du module mais en dehors du moniteur
          ↓
• Procédures d'entrée -- à l'intérieur du moniteur
          ↓
• Procédures Internes -- à l'intérieur du moniteur

Tout écart par rapport à ce modèle est susceptible d'être une erreur. Une technique utile pour éviter les bogues et augmenter la lisibilité d'un module de surveillance consiste à structurer le texte source dans l'ordre correspondant :

Interfaces vers les moniteurs

Dans Mesa, les attributs ENTRY et INTERNAL sont associés au corps d'une procédure, et non à son type. Ils ne peuvent donc pas être spécifiés dans un module DEFINITIONS. En général, les procédures internes ne sont pas exportées de toute façon, bien qu'elles puissent l'être pour un moniteur multi-module. En fait, le compilateur émet un avertissement lorsque la combinaison PUBLIC INTERNAL se produit.

Du côté client d'une interface, un moniteur apparaît comme un module de programme normal, c'est pourquoi les mots-clefs MONITOR et ENTRY n'apparaissent pas. Par exemple, un moniteur M avec des procédures d'entrée P et Q peut apparaître comme suit :