Automatisiertes Programmverwaltungsmodell

1. Einleitung

In [1] wurde eine Antwort auf die Frage gegeben, was als automatisches Programmieren (AP) zu betrachten ist, das Modell einer Finite-State-Maschine (SC) wurde jedoch nicht im Detail als Steuerungsmodell für automatische Programme beschrieben. Es ist klar, dass ein reiner abstrakter Automat für diese Rolle nicht geeignet ist, weil begrenzt durch die Anzahl der Kanäle. Das Strukturmodell des Automaten sowie die ihm entsprechende Theorie der Strukturautomaten lassen jedoch noch keine Antwort auf die Wahl des Automatenmodells zu.

Das Problem beginnt mit der Tatsache, dass es unter den vielen Arbeiten zur Theorie der endlichen Automaten (TCA) nur wenige gibt, die das Modell eines strukturellen endlichen Automaten (SCA) definieren. Man kann zwar verstehen, dass ein struktureller Automat ein [strukturelles] Diagramm elementarer Automaten (Funktionselemente) ist, das ein Modell eines abstrakten Automaten [2] implementiert. Man erinnere sich, dass gemäß der Theorie alles damit beginnt, ein Gerätemodell in Form eines abstrakten Automaten zu erstellen, und dann besteht die Aufgabe darin, eine digitale Schaltung zu synthetisieren, die es implementiert [3].

Das Programmieren sieht auf den ersten Blick wie eine Synthese digitaler Schaltkreise aus. Aber nur am Anfang. Erstens beginnt hier und da alles mit einem Algorithmus. Zweitens haben die strukturellen Probleme der Organisation und Implementierung digitaler Schaltungen und der Programmierung viel gemeinsam, insbesondere im Zusammenhang mit der parallelen Programmierung. Aber wir werden das Thema Parallelität separat diskutieren. In der Zwischenzeit besteht unsere Aufgabe darin, das Modell einer Finite-State-Maschine auszuwählen und / oder zu modifizieren, was für Programmierer, die mit verschiedenen Softwaretools verwöhnt sind, verständlich, praktisch und angenehm wäre.

Die Frage ist natürlich sofort logisch - warum ein weiteres und eher ungewöhnliches „automatisches Toolkit“? Wir werden versuchen, diese Frage zu beantworten, indem wir ein Modell der [verschachtelten] automatischen Steuerung definieren und dabei auch die Vorteile im Vergleich zum üblichen Programmiermodell berücksichtigen.

2. Definition des Steuerungsmodells von Automatikprogrammen

Im Verlauf der Evolution hat die Programmierpraxis bestimmte Anforderungen an das Programmverwaltungsmodell gestellt. Es muss anerkannt werden, dass das Modell einer klassischen Finite-State-Maschine ihnen eher wenig entspricht. Und wenn die Aufgabe darin besteht, Automaten in der Programmierung zu verwenden, muss diese angepasst werden. Es ist wünschenswert, dies im Rahmen der Automatentheorie zu tun. Die Hauptansprüche an den bestehenden AP reduzieren sich auf die Tatsache, dass diese Bedingung verletzt wird.

Definition 1. Wir bezeichnen die disjunktive Normalform endlicher Automaten (DNFA) als vollständig definierte endliche Automaten, deren Übergänge durch elementare Konjunktionen logischer Variablen gekennzeichnet sind.

Das DNA-Modell basiert auf formalen Modellen vollständig (vollständig) definierter Automaten mit einem abstrakten Zustand [4] und logischen Automaten [5].

Definition 2. Wir nennen die disjunktive Form eines endlichen Automaten (DFA) einen Automaten in Form eines DFA, der nur resultierende Übergänge enthält .

Die mit Ausgangssignalen gekennzeichneten Übergänge und Übergänge mit einem Strich anstelle der Ausgangssignale, die den aktuellen Zustand des Automaten ändern, werden als effektive Übergänge klassifiziert. Übergänge, die nicht in der Beschreibung des disjunktiven Automaten enthalten sind, stellen eine Hinzufügung des DKA (DDA) zu dem vollständig definierten DFA-Automaten dar. Eine solche Addition ist ein Automat, der aus isolierten Zuständen mit Übergängen in Form von Schleifen und mit Strichen anstelle der Ausgangssignale besteht.

3. Das Speichermodell für das Berechnungsmodell AP

Das Vorhandensein vieler Ein- und Ausgänge des DFA legt die Parallelität der damit verbundenen Software-Operatoren / Funktionen fest. Für die korrekte Implementierung ist ein Speichermodell vom Typ CREW (Concurrent Read Exclusive - Write) erforderlich [6]. Innerhalb seines Rahmens ist das Lesen aktueller Datenwerte seitens der Menge aller Funktionen (Prädikate und Aktionen) erlaubt, und nur eine von ihnen darf allgemeine Daten für parallel ausführbare Aktionen ändern.

Das automatische Steuerungsmodell beschränkt im Gegensatz zum Multi-Thread-Rechenmodell die Ausführung der Operatoren / Funktionen des automatischen Programms eindeutig auf die Grenzen eines diskreten Zeitzyklus. In einer solchen Situation können Änderungen des Speichers durch Aktionen, die im aktuellen Taktzyklus ausgeführt werden, in den "Schattenspeicher" geschrieben werden , so dass er nach Abschluss und vor dem Start des nächsten diskreten Taktzyklus seine neuen Werte annimmt.

Die Interaktion von Automatenprogrammierern mit dem Speicher wird als Schattenspeichermodell bezeichnet . Dieses Modell ist ein wesentlicher Bestandteil des allgemeinen Modells der automatischen Programmierung. Es stellt die Richtigkeit des Parallelbetriebs der AP-Bediener sicher und vereinfacht die Programmierung von Parallelprozessen.

Im Rahmen des Speichermodells werden komplexe und wenig zuverlässige Mechanismen zur Multithread-Synchronisation der Prozesse eigentlich nicht benötigt (Details siehe [7]). Aufgrund der Äquivalenz von Automaten und Algorithmenschemata (GAW) [8] schränkt das automatische Programmiermodell die Anwendung jedoch nicht ein.

4. Verschachtelte und Trägheitsmodelle von Automaten

Die Aufgabe, ein Modell des logischen Elements der Verzögerung zu erstellen, das weiter als Beispiel gewählt wurde, demonstriert einerseits die Probleme des klassischen Automatenmodells und spiegelt andererseits die Eigenschaften des DFA-Modells wider, das algorithmische Probleme mit visuelleren und bequemeren Mitteln löst. Das eingeführte Modell verschachtelter Automaten erzeugt eine Unterklasse von Automatenmodellen, im Folgenden als Inertialautomaten bezeichnet , und eine entsprechende Unterklasse von Inertialalgorithmen .

Es sei also die Aufgabe, ein diskretes Modell eines Verzögerungslogikelements zu erstellen, das die Übertragung eines binären Eingangssignals implementiert. Darüber hinaus fallen die Zeiten ihrer Verzögerungen t01 bzw. t10 zum Einheits- und Nullzustand im allgemeinen Fall nicht zusammen.

Das einfachste Modell einer einzelnen Verzögerung in Form eines mehligen Automaten ist in Abb. 1 dargestellt. 1 (siehe zum Vergleich das Verzögerungsmodell in [2]). Seine Verzögerungen werden durch einen einzelnen diskreten Taktzyklus bestimmt. Komplexere Modelle von Transportverzögerungen (Einzelheiten zu den Verzögerungsarten siehe [9]) in Form eines Miley-Automaten bzw. eines kombinierten Miley-Moore-Modells sind in Abb. 1 dargestellt. 2a und fig. 2b.


Abb. 1. Einheitsverzögerungsmodell in Form eines Meilenautomaten


Abb. 2. Das Transportverspätungsmodell von Miles (a) und Miles-Moore (b)

Das Eingangssignal x3 (wir erinnern uns, dass es im automatischen Programm dem Prädikat [1] entspricht) nimmt einen wahren Wert an, wenn der Wert des Taktzählers gleich dem Wert der Variablen t gleich der Verzögerung t01 oder t10 ist. Der Wert der Variablen t wird den Signalen y3 und y4 zugeordnet (im Programm die gleichnamigen Aktionsfunktionen wie die Ausgangssignale). Die Signale y1, y2 setzen den Wert der Variablen, die die Modellausgabe darstellt. Das Signal y5 erhöht den Taktzähler, der durch das Signal y6 zurückgesetzt wird.

Bemerkung 2. Die internen Zustände des Modells in Abb. In 1 ist es zweckmäßig, einen Ausgabezustand eines Elements zuzuordnen. Dadurch können wir nicht nur die Operatoren y1 und y2, sondern auch die Ausgabevariable selbst ausschließen.

Die Implementierung der Einbettung von Automaten ähnlich wie beim Aufrufen von Unterprogrammen bildet die Technologie der modularen Automatisierungsprogrammierung. Gleichzeitig ist dies auf Software-Ebene im Gegensatz zu ähnlichen Versuchen auf Hardware-Ebene (siehe [10] zum Vergleich) viel einfacher. Dazu müssen Sie den Programmaufruf des verschachtelten Automaten einfügen, und dann organisiert der Kern der Implementierung von Automaten wie ein normaler Prozessor die Rückkehr der Steuerung zur aktuellen Ebene der Verschachtelung.

Definition 3. Verschachtelte Automaten werden Automaten mit einem Endzustand genannt, dessen Übergang den Vorgang der Rückkehr zur vorherigen Ebene (Rang) der Verschachtelung startet.

Die korrekte Implementierung der Verschachtelung von Automaten schränkt die Prozedur für deren Erstellung ein. Erstens kann ein verschachtelter Automat nur untergeordnet sein. Darüber hinaus kann ein Top-Level-Automat mit Ausnahme von Rang Null auch ein verschachtelter Automat sein. Zweitens kann bei jedem Übergang nur ein verschachtelter Automat erstellt werden. Der Mechanismus verschachtelter Automaten schafft auch die Grundlage für die Implementierung rekursiver Algorithmen, die auf automatischer Steuerung basieren.


Abb. 3. Verzögerungsmodell in Form verschachtelter Automaten

Fig. 3 zeigt das Verzögerungsmodell, wobei Fig. 3a das Modell der oberen Ebene darstellt, und Fig. 3b und Fig. 3b das Verzögerungsmodell. 3c - Varianten verschachtelter Automaten für Transport- und Trägheitsverzögerungen (Einzelheiten zu Verzögerungsarten siehe [8]). Gleichzeitig sind dies Beispiele für zwei Arten von verschachtelten Automaten - gewöhnliche und Trägheit . Der Typ eines verschachtelten Automaten wird durch den Namen seiner Endzustände definiert: Ein Zustand mit dem Namen "00" bestimmt den üblichen Austritt aus dem verschachtelten Automaten, und ein Zustand mit dem Namen "XX" ändert den aktuellen Zustand des Automaten der obersten Ebene nicht.

Eine wichtige Erklärung für das Verständnis des Trägheitsverzögerungsalgorithmus. Der Wert des Prädikats x1 hängt dafür (siehe Fig. 3c) von dem Übergang ab, auf dem der eingebettete Automat erzeugt wird. Mit anderen Worten, das Prädikat im Zustand "0" steuert die Beibehaltung von "Null" am Eingang und im Zustand "1" im Gegensatz zu "Einheiten". Wenn der Wert am Eingang Null ist, müssen Sie den wahren Wert zurückgeben. Wenn ferner die Stabilität des Eingangs verletzt wird (der Wert x1 ist falsch) und die Verzögerungszeit nicht abgelaufen ist (der Wert x3 ist falsch), wird der Austritt aus der eingebetteten Maschine durch den Trägheitszustand realisiert (siehe Fig. 3c).

Definition 4. Automaten, einschließlich des Aufrufs verschachtelter Automaten mit einem endgültigen Trägheitszustand, werden als Trägheitsautomaten bezeichnet .

In dem Modell in Fig. 3a erzeugt die Aktion z1 (das Symbol z ist für die Namen von Aktionen ausgewählt, die einen Aufruf eines verschachtelten Automaten enthalten) einen verschachtelten Automaten, wenn ein Verzögerungswert definiert ist. Als Teil dieser Aktion wird der spezifizierte Verzögerungstyp bestimmt, in Übereinstimmung mit dem eine der verschachtelten Automaten erzeugt wird, wie in Fig. 3b oder Fig. 4 gezeigt. 3c.

Auf der obersten Ebene der Hierarchie stimmt die Ansicht des Automaten in Fig. 3a in der Struktur vollständig mit dem Modell in Fig. 1 überein und unterscheidet sich nur durch das Vorhandensein von Aktionen auf den Übergängen. Verzögerungen mit verschachtelten Automaten haben eine einfachere Form als das einstufige Modell in Abb. 2. Ein verschachtelter Automat kann auch als eine Art "Bibliotheksautomat" betrachtet werden, der von jedem anderen Automaten aufgerufen werden kann.

3. Programmierung der Objektautomaten

Das automatische Steuerungsmodell verfügt neben der grafischen Form auch über eine einfache tabellarische Form - eine Übergangstabelle (TP), die in C ++ effektiv interpretiert werden kann. Innerhalb seines Rahmens kann ein separates Automatenprogramm (oder ein Teil davon) und dementsprechend dessen Definition in Form einer Programmschaltung S durch eine Klasse dargestellt werden. In diesem Fall entsprechen die Speichermodelle den Eigenschaften der Klasse, die Menge der Operationen den Methoden der Klasse und die automatische Steuerung in Form eines TP beschreibt das Verhalten der Klasse. Die Einführung der Kontrolle in die Klasse ermöglicht es uns, über aktive Objekte, oft auch Agenten genannt, usw. zu sprechen.

Viele Objekte mit Verhalten in Form einer Automatensteuerung formalisieren das Konzept eines Objektautomaten-Parallelprogramms . In diesem Fall kann das Modell eines beliebigen parallelen Programms durch ein Programmdiagramm dargestellt werden, in dem die Steuerung C in Form eines Automatennetzwerks dargestellt wird, wobei Komponentenautomaten das Verhalten aktiver Objekte beschreiben, der Speicher M durch eine Kombination von Eigenschaften von Objekten dargestellt wird und viele Operatoren A durch eine Kombination von Methoden von Programmobjekten dargestellt werden.

In der VKPA-Umgebung wird die Rolle der automatisierten Programmiersprache der C ++ - Sprache zugewiesen. In „automatischem C ++“ sind Objekte mit Aktivität / Verhalten ausgestattet und können Parallelität beschreiben und implementieren, sowohl auf der Ebene der Methoden einzelner Objekte als auch auf der Ebene der Beschreibung der Parallelität vieler Objekte.

Bestehende Objektimplementierungen von AP sind ziemlich kompliziert. In VKPa basiert die Objektimplementierung auf der Interpretation von Automaten und der dedizierten Steuerung des Programms. Im Gegensatz zur direkten Implementierung von Automaten, wie sie beispielsweise in der SWITH-Technologie verwendet werden, entfällt hierdurch die Konvertierung eines Automatenmodells in ein Flussdiagrammmodell. Der in VKPa verwendete Interpretationsalgorithmus ähnelt der Methode zur Interpretation von Entscheidungstabellen von E. Hamby [12].

Sofern nicht anders angegeben, werden wir das Konzept eines Automatenprogramms weiter mit dem Konzept eines Automatenobjekts (AO) im Sinne von OOP verknüpfen, wobei wir jedoch das oben eingeführte Konzept eines Objektautomaten-Parallelprogramms berücksichtigen. Aus diesem Grund werden die Operatoren und der Speicher des AP durch die Methoden und Eigenschaften der aktiven Objekte bestimmt. Automatenobjekte unterscheiden sich von gewöhnlichen Objekten durch das Vorhandensein von Verhalten, das durch das Zustandsmaschinenmodell bestimmt wird.

4. Schlussfolgerungen

Das Erstellen eines Modells verschachtelter Automaten ist ein Schritt in Richtung eines qualitativen Wandels in der Programmiertechnologie. Das beschriebene Inertialmodell des Automaten ähnelt dem Konzept historischer Zustände in der UML. Das übliche Einbetten von Automaten hat eine analoge Programmierung, das "Inertial Embedding" hat es nicht, weil In einem Programm können Sie nicht zu einem Befehl zurückkehren, der einem Unterprogrammaufruf vorausgeht. Und dies sind Elemente eines qualitativen Unterschieds zwischen automatischer Programmierung und gewöhnlicher Programmierung.

Natürlich können Sie den Schattenspeicher in die gewöhnliche Programmierung einführen und die Parallelität von Funktionen bezeichnen. Aber im Rahmen des Automatenmodells hat all dies eine organische Form, sowohl in Bezug auf die Beschreibung als auch in Bezug auf die Leistung. Alles wird durch die natürliche Parallelität des Modells bestimmt. Das Blockdiagrammmodell verfügt nicht über solche Funktionen.

Aktive Objekte erweitern auch die Programmiermöglichkeiten. Der „Objekt-Wrapper“ wirkt sich jedoch qualitativ auf die automatische Programmierung aus und vereinfacht die Prozeduren zum Aufrufen und Implementieren verschachtelter Automaten. Die Verwendung von [lokalen] Klasseneigenschaften ermöglicht es Ihnen, nicht nur Einbettungsalgorithmen, sondern auch beliebige rekursive Algorithmen zu implementieren.