Modèle de gestion de programme automatisé

1. Introduction

Dans [1], une réponse a été donnée à la question de ce qui est considéré comme une programmation automatique (AP), mais le modèle d'une machine à états finis (SC) n'a pas été décrit en détail comme un modèle de contrôle des programmes automatiques. Il est clair qu’un automate abstrait pur ne convient pas à ce rôle, car limité par le nombre de canaux. Mais le modèle structurel de l'automate, ainsi que la théorie des automates structuraux qui lui correspondent, ne permettent pas encore de donner une réponse sur le choix du modèle de l'automate.

Le problème commence par le fait que parmi les nombreux travaux sur la théorie des automates finis (TCA), rares sont ceux qui donnent une définition du modèle d'un automate fini structurel (SCA). Certes, on peut comprendre qu'un automate structurel est un diagramme [structurel] d'automates élémentaires (éléments fonctionnels) qui implémente un modèle d'automate abstrait [2]. Rappelons que, conformément à la théorie, tout commence par la création d'un modèle d'appareil sous la forme d'un automate abstrait, puis la tâche est de synthétiser un circuit numérique qui le met en œuvre [3].

La programmation à première vue ressemble un peu à une synthèse de circuits numériques. Mais seulement au début. Tout d'abord, ça et là tout commence par un algorithme. Deuxièmement, les problèmes structurels d'organisation et de mise en œuvre des circuits et de la programmation numériques ont beaucoup en commun, en particulier dans le contexte de la programmation parallèle. Mais nous aborderons séparément le sujet du parallélisme. En attendant, notre tâche consiste à choisir et / ou modifier le modèle d'une machine à états finis, ce qui serait compréhensible, pratique et agréable pour les programmeurs gâtés par divers outils logiciels.

Certes, la question est immédiatement logique - pourquoi une «boîte à outils automatique» de plus et plutôt inhabituelle? Nous allons essayer de répondre à cette question en définissant un modèle de contrôle automatique [imbriqué], considérant également ses avantages par rapport au modèle de programmation habituel.

2. Définition du modèle de contrôle des programmes automatiques

En cours d'évolution, la pratique de la programmation a formé certaines exigences pour le modèle de gestion de programme. Il faut reconnaître que le modèle d'une machine à états finis classique leur correspond plutôt peu. Et si la tâche consiste à utiliser des automates dans la programmation, il doit être adapté. Il est souhaitable de le faire dans le cadre de la théorie des automates. Les principales prétentions au PA existant sont réduites au fait que cette condition est violée.

Définition 1. Nous appelons la forme normale disjonctive des automates finis (DNKA) des automates finis entièrement définis dont les transitions sont étiquetées par des conjonctions élémentaires de variables logiques.

Le modèle d'ADN est basé sur des modèles formels d' automates entièrement (entièrement) définis avec un état abstrait [4] et des automates logiques [5].

Définition 2. Nous appelons la forme disjonctive d'un automate fini (DFA) un automate sous la forme d'un DFA ne contenant que des transitions résultantes .

Les transitions marquées avec des signaux de sortie et les transitions avec un tiret à la place des signaux de sortie qui changent l'état actuel de l'automate sont classées comme transitions effectives. Les transitions qui ne sont pas incluses dans la description de l'automate disjonctif constituent un ajout du DKA (DDA) à l'automate DFA entièrement défini. Un tel ajout est un automate composé d'états isolés avec des transitions sous forme de boucles et des tirets à la place des signaux de sortie.

3. Le modèle de mémoire pour le modèle de calcul AP

La présence de nombreuses entrées et sorties du DFA définit le parallélisme des opérateurs / fonctions logicielles qui lui sont associés. Pour sa mise en œuvre correcte, un modèle de mémoire de type CREW (lecture simultanée exclusive - écriture) est requis [6]. Dans son cadre, la lecture des valeurs de données actuelles est autorisée de la part de l'ensemble de toutes les fonctions (prédicats et actions), et une seule d'entre elles est autorisée à modifier les données générales pour les actions exécutables parallèles.

Le modèle de contrôle automatique, contrairement au modèle informatique multithread, limite clairement l'exécution des opérateurs / fonctions du programme automatique aux limites d'un cycle temporel discret. Dans une telle situation, toute modification de la mémoire par des actions effectuées sur le cycle d'horloge en cours peut être écrite dans la «mémoire fantôme» , de sorte qu'après leur achèvement et avant le début du cycle d'horloge discret suivant, elle devienne ses nouvelles valeurs.

L'interaction des opérateurs de programme d'automate avec la mémoire sera appelée modèle de mémoire fantôme . Ce modèle est une partie essentielle du modèle général de programmation automatique. Il garantit l'exactitude du fonctionnement parallèle des opérateurs AP et simplifie la programmation des processus parallèles.

Dans le cadre du modèle de mémoire, des mécanismes complexes et peu fiables de synchronisation multithread des processus ne sont en fait pas nécessaires (pour plus de détails voir [7]). Mais si nécessaire, en raison de l'équivalence des automates et des schémas d'algorithmes (GAW) [8], le modèle de programmation automatique ne limite pas leur application.

4. Modèles imbriqués et inertiels d'automates

La tâche de créer un modèle de l'élément logique du retard, choisi plus loin à titre d'exemple, d'une part, démontre les problèmes du modèle classique de l'automate et, d'autre part, reflète les qualités du modèle DFA qui résout les problèmes algorithmiques avec des moyens plus visuels et pratiques. Le modèle introduit d'automates imbriqués génère une sous-classe de modèles d'automates, ci-après dénommés automates inertiels , et une sous-classe correspondante d' algorithmes inertiels .

Alors, que ce soit la tâche de créer un modèle discret d'un élément logique à retard qui implémente la transmission d'un signal d'entrée binaire. De plus, les instants de ses retards t01 et t10, respectivement, aux états unitaire et zéro dans le cas général ne coïncident pas.

Le modèle le plus simple d'un seul retard sous la forme d'un automate Mealy est illustré à la Fig. 1 (voir, pour comparaison, le modèle de retard dans [2]). Ses retards sont déterminés par un seul cycle d'horloge discret. Des modèles plus complexes de retards de transport (pour plus de détails sur les types de retards, voir [9]) sous la forme d'un automate Miley et d'un modèle Miley-Moore combiné sont présentés, respectivement, sur la Fig. 2a et fig. 2b.


Fig. 1. Modèle de retard d'unité sous la forme d'un automate Miles


Fig. 2. Le modèle de retard de transport de Miles (a) et Miles-Moore (b)

Le signal d'entrée x3 (on rappelle que dans le programme automatique il correspond au prédicat [1]) prend une valeur vraie si la valeur du compteur d'horloge est égale à la valeur de la variable t égale au retard t01 ou t10. La valeur de la variable t est affectée aux signaux y3 et y4 (dans le programme, les fonctions d'action du même nom que les signaux de sortie). Les signaux y1, y2 définissent la valeur de la variable représentant la sortie du modèle. Le signal y5 incrémente le compteur d'horloge, qui est réinitialisé par le signal y6.

Remarque 2. Les états internes du modèle de la Fig. 1, il est commode de l'associer à un état de sortie d'un élément. Cela nous permet d'exclure non seulement les opérateurs y1 et y2, mais également la variable de sortie elle-même.

L'implémentation de l'intégration d'automates similaires aux sous-routines d'appel forme la technologie de programmation modulaire d'automates. En même temps, au niveau logiciel, contrairement à des tentatives similaires au niveau matériel (voir [10] pour comparaison), c'est beaucoup plus simple. Pour ce faire, vous devez insérer l'appel de programme de l'automate imbriqué, puis le noyau de l'implémentation des automates, comme un processeur normal, organise le retour du contrôle au niveau d'imbrication actuel.

Définition 3. Les automates imbriqués seront appelés automates avec un état final, dont la transition démarre la procédure de retour au niveau précédent (rang) d'imbrication.

La mise en œuvre correcte de l'imbrication des automates impose des restrictions sur la procédure de leur création. Tout d'abord, un automate imbriqué ne peut être que subordonné. De plus, un automate de niveau supérieur, à l'exclusion du rang zéro, peut également être un automate imbriqué. Deuxièmement, à chaque transition, un seul automate imbriqué peut être créé. Le mécanisme des automates imbriqués crée également la base pour la mise en œuvre d'algorithmes récursifs basés sur le contrôle automatique.


Fig. 3. Modèle de retard sous forme d'automates imbriqués

La Fig. 3 montre le modèle de retard, où la Fig. 3a représente le modèle de niveau supérieur, et la Fig. 3b et la Fig. 3c - variantes d'automates imbriqués pour le transport et les retards inertiels (pour plus de détails sur les types de retards, voir [8]). En même temps, ce sont des exemples de deux types d'automates imbriqués - ordinaire et inertiel . Le type d'un automate imbriqué est défini par le nom de ses états finaux: un état avec le nom "00" détermine la sortie habituelle de l'automate imbriqué, et un état avec le nom "XX" ne change pas l'état actuel de l'automate de niveau supérieur.

Une explication importante pour comprendre l'algorithme de retard inertiel. Pour cela (voir Fig. 3c), la valeur du prédicat x1 dépend de la transition sur laquelle l'automate embarqué est créé. En d'autres termes, le prédicat dans l'état "0" contrôle la conservation de "zéro" à l'entrée, et dans l'état "1", au contraire, "unités". Si la valeur à l'entrée est zéro à la valeur zéro de la sortie, vous devez renvoyer la vraie valeur. De plus, si la stabilité de l'entrée est violée (la valeur x1 est fausse) et le temps de retard n'a pas expiré (la valeur x3 est fausse), alors la sortie de la machine embarquée est réalisée par l'état inertiel (voir Fig.3c).

Définition 4. Les automates, y compris l'appel des automates imbriqués qui ont un état inertiel final, seront appelés automates inertiels .

Dans le modèle de la figure 3a, l'action z1 (le symbole z est sélectionné pour les noms d'actions qui incluent un appel à un automate imbriqué) crée un automate imbriqué si une valeur de retard est définie. Dans le cadre de cette action, le type de retard spécifié est déterminé, selon lequel l'un des automates imbriqués est créé, illustré sur la Fig.3b ou la Fig. 3c.

Au niveau supérieur de la hiérarchie, la vue de l'automate sur la figure 3a coïncide complètement en structure avec le modèle de la figure 1, ne différant que par la présence d'actions sur les transitions. Les retards avec des automates imbriqués ont une forme plus simple que le modèle à un niveau de la figure 2. Un automate imbriqué peut également être considéré comme une sorte d '«automate de bibliothèque» qui peut être appelé à partir de n'importe quel autre automate.

3. Programmation d'un automate objet

Le modèle de contrôle automatique, en plus de la forme graphique, a également une forme tabulaire simple - une table de transition (TP), qui peut être efficacement interprétée en C ++. Dans son cadre, un programme automate séparé (ou une partie de celui-ci) et, par conséquent, sa définition sous la forme d'un circuit de programme S peuvent être représentés par une classe. Dans ce cas, les modèles de mémoire correspondront aux propriétés de la classe, l'ensemble des opérations correspondra aux méthodes de la classe, et le contrôle automatique sous forme de TP décrira le comportement de la classe. L'introduction du contrôle dans la classe nous permet de parler des objets actifs, aussi souvent appelés agents, etc.

De nombreux objets ayant un comportement sous forme de contrôle d'automate officialisent le concept d'un programme parallèle d'objet automate . Dans ce cas, le modèle de tout programme parallèle peut être représenté par un diagramme de programme dans lequel le contrôle C sera présenté sous la forme d'un réseau d'automates, où les automates de composants décrivent le comportement des objets actifs, la mémoire M est représentée par une combinaison de propriétés d'objets, et de nombreux opérateurs A sont représentés par une combinaison de méthodes d'objets de programme.

Dans l'environnement VKPA, le rôle du langage de programmation automatisé est attribué au langage C ++. En «C ++ automatique», les objets sont dotés d'activité / de comportement et ont les moyens de décrire et de mettre en œuvre le parallélisme, tant au niveau des méthodes des objets individuels qu'au niveau de la description du fonctionnement parallèle de nombreux objets.

Les implémentations d'objets existantes d'AP sont plutôt compliquées. Dans VKPa, son implémentation d'objet est basée sur l'interprétation d'automates et un contrôle dédié du programme. Contrairement à l'implémentation directe d'automates, utilisée par exemple dans la technologie SWITH, cela élimine la procédure de conversion d'un modèle d'automate en modèle d'organigramme. L'algorithme d'interprétation utilisé dans VKPa est similaire à la méthode d'interprétation des tables de décision par E. Hamby [12].

Sauf indication contraire, nous associerons en outre le concept de programme d'automate au concept d' objet automate (AO) au sens de POO, mais en tenant compte du concept de programme parallèle d'automate objet introduit ci-dessus. Pour cette raison, les opérateurs et la mémoire de l'AP seront déterminés par les méthodes et les propriétés des objets actifs. Les objets automates se distinguent des objets ordinaires par la présence d'un comportement déterminé par le modèle de machine à états.

4. Conclusions

La création d'un modèle d'automates imbriqués est une étape vers un changement qualitatif dans la technologie de programmation. Le modèle inertiel décrit de l'automate est similaire au concept d'états historiques en UML. L'incorporation habituelle des automates a un analogue en programmation, l '"incorporation inertielle" ne l'a pas, car Dans un programme, vous ne pouvez pas revenir à une commande précédant un appel de sous-routine. Et ce sont des éléments d'une différence qualitative entre la programmation automatique et la programmation ordinaire.

Vous pouvez, bien sûr, introduire la mémoire fantôme dans la programmation ordinaire et dénoter le parallélisme des fonctions. Mais dans le cadre du modèle automate, tout cela a une forme organique, à la fois en termes de description et en termes de performances. Tout est déterminé par le parallélisme naturel du modèle. Le modèle de diagramme n'a pas de telles capacités.

Les objets actifs étendent également les capacités de programmation. Mais le «wrapper d'objet», pour sa part, affecte qualitativement la programmation automatique, simplifiant les procédures d'invocation et d'implémentation d'automates imbriqués. Ainsi, l'utilisation des propriétés de classe [locales] vous permet d'implémenter non seulement l'incorporation, mais aussi des algorithmes récursifs.