Réseaux de Kahn

• Un processus peut ne pas avoir d’entrées, ou ne rien lire de ses entrées, il agit en ce cas en tant que source pure de données ;
• Un processus peut ne pas avoir de sorties, ou ne pas écrire sur ses sorties ;
• Tester si une entrée est vide peut être autorisé pour des raisons d’optimisation, à la condition expresse que ça ne modifie pas les sorties. Par exemple, un processus doit lire l’entrée 1, puis l’entrée 2, avant d’écrire sa sortie. S’il sait que la file 1 est vide mais que la 2 est prête, il peut gagner du temps en lisant d’abord la valeur de la file 2 avant d’être bloqué en lecture de la file 1. Cela peut permettre de gagner du temps notamment si le temps de lecture est long (allocation de ressources par exemple).

Modélisation en réseau de Petri du processus P de l’introduction

Prenons le réseau schématisé dans l’introduction. Supposons que le processus P est constitué de sorte qu’il lise d’abord sur l’entrée A (FIFO A), puis sur B, qu’il calcule quelque chose avec les deux données, puis l’écrit sur la sortie C, puis recommence. On peut modéliser ce comportement à l’aide du réseau de Petri présenté ci-contre. Le jeton situé dans la place PE resource force une exécution séquentielle du réseau de Kahn. Lorsque des données arrivent via les entrées A ou B, des jetons sont placés respectivement dans les places FIFO A et FIFO B. La transition Read A peut-être effectué lorsqu’il y a au moins un jeton dans FIFO A et un jeton dans PE resource. Le résultat de la transition rempli la place nécessaire à la transition Read B suivant le même principe. La dernière transition Compute/Write C correspond au calcul du processus P et à l’écriture sur sa sortie C. Le franchissement de cette dernière transition rempli à nouveau la place PE resource, permettant de franchir à nouveau la transition Read A dès qu’un jeton est disponible dans FIFO A.

Un automate fini représentant un processus

Un processus de Kahn peut être modélisé à l’aide d’un automate fini de deux états, dont le schéma est donné ci-contre :

• Active (en cours) : le processus calcule ou écrit sur une de ses sorties ;
• Wait (en attente) : le processus est bloqué en lecture sur une entrée.

En supposant que l’automate lise des données correspondant au comportement du processus, il pourrait donc lire trois types d’éléments Compute (calculer), Read (lire) et Write token (écrire). Une lecture le mène forcément dans l’état Wait, duquel il ne peut sortir qu’en lisant Get token, signifiant que le canal de communication contient au moins une valeur.

Une file est strictement bornée par ${\displaystyle b}$ s’il y a au plus ${\displaystyle b}$ éléments dans cette file pour toutes les exécutions possibles. Un réseau est strictement borné par ${\displaystyle b}$ si toutes les files sont strictement bornées par ${\displaystyle b}$.

Le nombre de données en attente dépend de l’ordre d’exécution des processus. Une source spontanée de données peut produire une quantité arbitraire de données dans une file si l’ordonnanceur n’exécute pas les processus pour en consommer.

Une application concrète ne peut pas avoir de files non bornées. Une implémentation doit donc calculer l’ordonnancement des processus afin d’établir une limite maximale de taille de file. Le problème de la capacité peut-être géré de différentes façons :

• Les limites de file peuvent être dérivées mathématiquement lors de la conception pour éviter les débordements de file. Cependant cette méthode n’est pas applicable pour tous les réseaux. Déterminer la valeur pour laquelle un réseau est strictement borné est indécidable. De plus, les capacités nécessaires peuvent dépendre du type de données à traiter.
• La capacité des files peut grandir lorsque c’est nécessaire (Parks 1995).
• Il est possible de rendre l’écriture bloquante lorsqu’une file est pleine. Cependant cette approche peut mener à des interblocages artificiels, à moins que le concepteur du réseau n'ait correctement calculé les limites sûres des files (Parks 1995). Une détection locale lors de l’exécution peut être nécessaire pour garantir des sorties correctes (Geilen et Basten 2003).

Un réseau fermé est un réseau dans lequel il n’y a pas d’entrée ou de sortie externes. Toutes les files sont connectées à deux processus. Les processus n’ayant pas d’entrée sont des producteurs, et ceux n’ayant pas de sortie, des consommateurs.

Un réseau ouvert est un réseau dans lequel tous les processus ont au moins une entrée et une sortie.

Les processus d’un réseau de Kahn sont déterministes. Pour la même séquence de données dans ses entrées, un processus produira la même séquence de sortie. Les processus peuvent être modélisés comme des programmes séquentiels qui lisent et écrivent dans des canaux dans n’importe quel ordre et pour n’importe quelle quantité de données, tant que la propriété de déterminisme est préservée. Le modèle des réseaux de Kahn est déterministe de sorte que les sorties du système sont déterminées par le comportement des processus, le schéma du réseau et les valeurs initiales. Ni le temps de calcul propre à chaque processus, ni la latence des files de communication n’interviennent dans la caractérisation de déterminisme.

Les réseaux de Kahn sont monotones, ils n’ont besoin que de données partielles depuis leurs entrées pour produire des données partielles en sortie. La monotonie permet le parallélisme, car les processus sont de simple fonctions des entrées vers les sorties.