Communicating sequential processes - Définition

Détails sur les commandes

La commande parallèle

Elle permet la mise en concurrence de processus par la syntaxe suivante :

      [        proc1:: liste de commandes      ||        proc2:: liste de commandes      ||        ...      ]      

Une telle commande ne se termine que lorsque tous les processus qu'elle définit sont terminés, l'échec d'un seul entraînant l'échec de la commande parallèle. Précisons qu'une variable définie avant une commande parallèle est visible par les processus qu'elle contient. Ceci implique nécessairement que tous les processus définis devront avoir accès aux variables déclarées avant la commande parallèle. On assiste donc ici à un partage de ressources, dont les contraintes soulevées (accès exclusif, etc.) sont à la charge du programmeur.

On note aussi la possibilité de déclarer plusieurs processus pour une même liste de commandes, comme le montre l'exemple suivant :

      proc1 [i:1..10]:: liste de commandes      

Ici, dix processus ayant la même liste de commandes seront mis en concurrence.

La commande d'entrée/sortie

Les communications entre processus reposent sur cette commande. Pour expliciter son fonctionnement, partons du cas simple de deux processus producteur et consommateur, le premier voulant transmettre une variable x au second. Une telle communication s'effectuera alors au travers des commandes suivantes :

      consommateur!x       

permettra au processus producteur d'envoyer x au processus consommateur

      producteur?x       

permettra au processus consommateur de recevoir x depuis le processus producteur

Du point de vue de la syntaxe, on remarque que le ! indique une commande de sortie, tandis que le ? indique une commande d'entrée. Plus formellement, une commande d'entrée se présentera sous la forme :

      processus_source?variable_cible      

et une commande de sortie sous la forme :

      processus_cible!expression_source.      

De plus, pour que la communication soit possible entre deux commandes d'e/s, CSP impose que :

1. l'une soit une commande d'entrée, l'autre une commande de sortie ;
2. les deux processus se nomment mutuellement ;
3. les typages de la variable cible et de l'expression source soient identiques.

Dans ces conditions, la transmission peut avoir lieu, et le contenu de l'expression source est copié vers la variable cible. Si l'une de ces conditions n'est pas respectée, les processus sont mis en attente, entraînant par conséquent un interblocage. Si l'un des processus est mort, alors toute commande d'entrée/sortie impliquant ce processus doit échouer. Enfin, le premier processus demandant la communication doit être mis en attente jusqu'à ce que le second le rejoigne. On retrouve ici le principe du rendez-vous. Notons aussi le cas particulier d'une synchronisation simple, c'est-à-dire sans transmission de valeur, possible grâce à l'utilisation d'un signal pur. Exemple :

      [       producteur:: ... consommateur?p(); ...      ||       consommateur:: ... producteur!p(); ...      ]      

La commande alternative

Une commande alternative se présente sous la forme d'un ensemble de sélectives, chacune étant composée d'une garde ainsi que d'une liste de commandes. Une garde est quant à elle composée d'une partie expression booléenne et d'une partie commande d'entrée, l'une ou l'autre pouvant être omise. Syntaxiquement, une commande alternative se présente sous la forme suivante :

      [        garde1 → liste de commandes      []        garde2 → liste de commandes      []        ...      ]      

Où garde1 et garde2 sont de la forme :

      expression_booleenne ; commande_entrée      

Ce qui donne par exemple :

      [          i < 5 ; processus?p(x) → ...      []          console!write(msg) → ...      []          i > 5 → ...      ]      

Lors de l'exécution d'une commande alternative, chacune de ses gardes est testée, afin de déterminer sa valeur selon une logique trivaluée (c'est-à-dire qu'une garde peut être vraie, fausse, ou neutre) :

• Une expression booléenne peut évidemment prendre les valeurs vrai ou faux
• Une commande d' entrée prend la valeur :
  • vrai si la communication est possible immédiatement ;
  • neutre si le processus nommé par la commande n'est pas encore prêt ;
  • faux si le processus nommé par la commande est mort (i.e. a fini son exécution).
• Dans le cas d'une garde contenant à la fois une partie expression booléenne et une partie commande entrée, l'expression booléenne est d'abord évaluée. Si elle est à faux, la garde est évaluée à faux. Si elle est à vrai, la commande d'entrée est alors évaluée, et donne la valeur à la garde.

Ainsi, si une ou plusieurs commandes gardées sont vraies, un choix indéterministe (i.e. aléatoire) doit être effectué pour n'en sélectionner qu'une. Si aucune n'est vraie mais que certaines sont neutres, le processus se met en attente des commandes d'entrées correspondantes. Et si toutes les commandes gardées sont fausses, la commande alternative échoue.

Si une garde est sélectionnée, la liste de commande correspondante doit alors être exécutée.

Il est aussi important de noter que la contrainte d'ordre syntaxique limitant les commandes d'e/s dans les gardes aux simples commandes d'entrée, provient d'un choix fait par HOARE dans le but d'éviter les incohérences.

Pour illustrer ce propos, partons de l'exemple suivant (qui suppose possible l'utilisation de commande de sortie dans les gardes) :

      [       proc1::            [              proc2?p() → ...            []              proc2?q() → ...            ]      ||       proc2::            [              proc1!p() → ...            []              proc1!q() → ...            ]      ]      

Supposons que les deux processus soient chacun arrivés sur leur commande alternative. Les deux commandes vont donc être évaluées parallèlement :

• le premier processus va évaluer chacune des gardes de l'alternative, puis, les deux étant vraies, il va effectué un choix aléatoire entre l'une ou l'autre ;
• de même, le second processus va se retrouver à devoir faire un choix entre l'une ou l'autre des gardes de son alternative.

Si les deux alternatives sélectionnent la même communication, aucun problème n'est soulevé. Par contre, si chacune choisie une communication différente, on assiste à un cas d'incohérence entraînant nécessairement un interblocage.

Ainsi, la communication entre commandes d'entrée/sortie gardées posant des problèmes, HOARE a décidé de l'empêcher en autorisant uniquement les commandes d'entrée dans les gardes.

Précisons cependant que le compilateur proposé en fin de cet article autorise les commandes de sortie dans les gardes, mais ajoute en contrepartie la condition suivante :

• Pour qu'une communication soit établie entre deux processus, il faut qu'au moins une des deux commandes d'e/s soit hors-garde.

On évite alors bien le problème cité ci-dessus.

La commande répétitive

La commande répétitive est composée d'une unique commande alternative, dont l'échec entraîne la fin de la répétition. On peut donc considérer qu'une répétitive ne peut se terminer qu'avec succès. Syntaxiquement, elle se présente sous la forme d'une étoile suivie d'une alternative :

      *commande alternative      

Par exemple :

      i:= 0;      *[        i < 10 → i:= i + 1      ]      

Ici, la commande répétitive se terminera lorsque i aura atteint la valeur 10.