Wir müssen eine einfache Zustandsmaschine in C implementieren .
Ist eine Standard-switch-Anweisung der beste Weg?
Wir haben einen aktuellen Zustand (Zustand) und einen Auslöser für den Übergang.
switch(state)
{
case STATE_1:
state = DoState1(transition);
break;
case STATE_2:
state = DoState2(transition);
break;
}
...
DoState2(int transition)
{
// Do State Work
...
if(transition == FROM_STATE_2) {
// New state when doing STATE 2 -> STATE 2
}
if(transition == FROM_STATE_1) {
// New State when moving STATE 1 -> STATE 2
}
return new_state;
}
Gibt es einen besseren Weg für einfache Zustandsautomaten?
EDIT: Für C ++ denke ich, dass die Boost Statechart- Bibliothek der richtige Weg sein könnte. Bei C hilft es jedoch nicht . Konzentrieren wir uns auf den C-Anwendungsfall.
c
design-patterns
finite-automata
Benoit
quelle
quelle
Antworten:
Ich bevorzuge für die meisten Zustandsautomaten einen tabellengesteuerten Ansatz:
Dies kann natürlich erweitert werden, um mehrere Zustandsautomaten usw. zu unterstützen. Übergangsaktionen können ebenfalls berücksichtigt werden:
Der tabellengesteuerte Ansatz ist einfacher zu warten und zu erweitern und einfacher auf Zustandsdiagramme abzubilden.
quelle
Vielleicht haben Sie meine Antwort auf eine andere C-Frage gesehen, in der ich FSM erwähnt habe! So mache ich das:
Mit den folgenden Makros definiert
Dies kann an den speziellen Fall angepasst werden. Beispielsweise haben Sie möglicherweise eine Datei
FSMFILE
, mit der Sie Ihren FSM steuern möchten, sodass Sie die Aktion zum Lesen des nächsten Zeichens in das Makro selbst integrieren können:Jetzt haben Sie zwei Arten von Übergängen: Einer wechselt in einen Status und liest ein neues Zeichen, der andere wechselt in einen Status, ohne dass Eingaben erforderlich sind.
Sie können die Handhabung von EOF auch mit folgenden Funktionen automatisieren:
Das Gute an diesem Ansatz ist, dass Sie ein von Ihnen gezeichnetes Zustandsdiagramm direkt in Arbeitscode übersetzen können und umgekehrt einfach ein Zustandsdiagramm aus dem Code zeichnen können.
Bei anderen Techniken zur Implementierung von FSM wird die Struktur der Übergänge in Kontrollstrukturen (während, wenn, wechseln ...) vergraben und durch Variablenwerte gesteuert (typischerweise a
state
Variable) und es kann eine komplexe Aufgabe sein, das schöne Diagramm mit a in Beziehung zu setzen verschlungener Code.Ich habe diese Technik aus einem Artikel in der großen Zeitschrift "Computer Language" gelernt, der leider nicht mehr veröffentlicht wird.
quelle
Ich habe auch den Tabellenansatz verwendet. Es gibt jedoch Overhead. Warum eine zweite Liste von Zeigern speichern? Eine Funktion in C ohne () ist ein const-Zeiger. So können Sie tun:
Abhängig von Ihrem Angstfaktor (dh Sicherheit gegenüber Geschwindigkeit) möchten Sie möglicherweise nach gültigen Zeigern suchen. Bei Zustandsautomaten mit mehr als drei Zuständen sollte der obige Ansatz weniger Anweisungen enthalten als ein äquivalenter Switch- oder Tabellenansatz. Sie könnten sogar makroisieren:
Aus dem Beispiel des OP geht auch hervor, dass es eine Vereinfachung gibt, die beim Nachdenken über / Entwerfen einer Zustandsmaschine vorgenommen werden sollte. Ich denke nicht, dass der Übergangszustand für die Logik verwendet werden sollte. Jede Zustandsfunktion sollte in der Lage sein, ihre gegebene Rolle ohne explizite Kenntnis vergangener Zustände auszuführen. Grundsätzlich legen Sie fest, wie Sie von dem Zustand, in dem Sie sich befinden, in einen anderen Zustand übergehen.
Beginnen Sie schließlich nicht mit dem Entwurf einer Zustandsmaschine, die auf "funktionalen" Grenzen basiert, sondern verwenden Sie dafür Unterfunktionen. Teilen Sie die Zustände stattdessen danach auf, wann Sie warten müssen, bis etwas passiert, bevor Sie fortfahren können. Dies hilft dabei, die Häufigkeit zu minimieren, mit der Sie die Zustandsmaschine ausführen müssen, bevor Sie ein Ergebnis erhalten. Dies kann wichtig sein, wenn Sie E / A-Funktionen schreiben oder Handler unterbrechen.
Außerdem ein paar Vor- und Nachteile der klassischen switch-Anweisung:
Vorteile:
Nachteile:
Beachten Sie die beiden Attribute Pro und Contra. Ich denke, der Wechsel bietet die Möglichkeit, zu viel zwischen Staaten zu teilen, und die gegenseitige Abhängigkeit zwischen Staaten kann unüberschaubar werden. Für eine kleine Anzahl von Zuständen ist es jedoch möglicherweise am besten lesbar und wartbar.
quelle
Verwenden Sie für eine einfache Zustandsmaschine einfach eine switch-Anweisung und einen Aufzählungstyp für Ihren Zustand. Führen Sie Ihre Übergänge innerhalb der switch-Anweisung basierend auf Ihrer Eingabe durch. In einem realen Programm würden Sie offensichtlich das "if (Eingabe)" ändern, um nach Ihren Übergangspunkten zu suchen. Hoffe das hilft.
quelle
In Martin Fowlers UML Distilled erklärt er (kein Wortspiel beabsichtigt) in Kapitel 10 Zustandsmaschinendiagramme (Hervorhebung von mir):
Verwenden wir ein vereinfachtes Beispiel für den Status der Anzeige eines Mobiltelefons:
Verschachtelter Schalter
Fowler gab ein Beispiel für C # -Code, aber ich habe es an mein Beispiel angepasst.
Zustandsmuster
Hier ist eine Implementierung meines Beispiels mit dem GoF-Statusmuster:
Zustandstabellen
Hier ist eine Tabelle für mein Beispiel, die sich von Fowler inspirieren lässt:
Vergleich
Der verschachtelte Schalter hält die gesamte Logik an einem Ort, aber der Code kann bei vielen Zuständen und Übergängen schwer zu lesen sein. Es ist möglicherweise sicherer und einfacher zu validieren als die anderen Ansätze (kein Polymorphismus oder Dolmetschen).
Die Implementierung des Zustandsmusters verteilt die Logik möglicherweise auf mehrere separate Klassen, was das Verständnis als Ganzes zu einem Problem machen kann. Andererseits sind die kleinen Klassen separat leicht zu verstehen. Das Design ist besonders fragil, wenn Sie das Verhalten durch Hinzufügen oder Entfernen von Übergängen ändern, da es sich um Methoden in der Hierarchie handelt und möglicherweise viele Änderungen am Code vorgenommen werden. Wenn Sie nach dem Designprinzip kleiner Schnittstellen leben, werden Sie feststellen, dass dieses Muster nicht so gut funktioniert. Wenn die Zustandsmaschine jedoch stabil ist, sind solche Änderungen nicht erforderlich.
Der Ansatz für Statustabellen erfordert das Schreiben einer Art Interpreter für den Inhalt (dies ist möglicherweise einfacher, wenn Sie sich in der von Ihnen verwendeten Sprache widerspiegeln), was im Vorfeld eine Menge Arbeit bedeuten kann. Wie Fowler betont, können Sie das Verhalten Ihrer Software ändern, wenn Ihre Tabelle von Ihrem Code getrennt ist, ohne sie neu zu kompilieren. Dies hat jedoch einige Auswirkungen auf die Sicherheit. Die Software verhält sich basierend auf dem Inhalt einer externen Datei.
Bearbeiten (nicht wirklich für C-Sprache)
Es gibt auch einen fließenden Schnittstellenansatz (auch bekannt als interne domänenspezifische Sprache), der wahrscheinlich durch Sprachen mit erstklassigen Funktionen erleichtert wird . Die zustandslose Bibliothek existiert und dieser Blog zeigt ein einfaches Beispiel mit Code. Eine Java-Implementierung (vor Java8) wird diskutiert. Mir wurde auch ein Python-Beispiel auf GitHub gezeigt .
quelle
Es gibt auch das Logikgitter, das mit zunehmender Zustandsmaschine besser gewartet werden kann
quelle
In einfachen Fällen können Sie Ihre Switch-Style-Methode verwenden. Ich habe festgestellt, dass es in der Vergangenheit gut funktioniert, sich auch mit Übergängen zu befassen:
Ich weiß nichts über die Boost-Bibliothek, aber diese Art von Ansatz ist denkbar einfach, erfordert keine externen Abhängigkeiten und ist einfach zu implementieren.
quelle
switch () ist eine leistungsstarke und standardmäßige Methode zum Implementieren von Zustandsautomaten in C, kann jedoch die Wartbarkeit verringern, wenn Sie über eine große Anzahl von Zuständen verfügen. Eine andere übliche Methode besteht darin, Funktionszeiger zu verwenden, um den nächsten Zustand zu speichern. Dieses einfache Beispiel implementiert ein Set / Reset-Flip-Flop:
quelle
Ich fand eine wirklich raffinierte C-Implementierung von Moore FSM im edx.org-Kurs Embedded Systems - Shape the World UTAustinX - UT.6.02x, Kapitel 10, von Jonathan Valvano und Ramesh Yerraballi ....
quelle
Vielleicht möchten Sie einen Blick auf die libero FSM-Generator-Software werfen . Aus einer Zustandsbeschreibungssprache und / oder einem (Windows-) Zustandsdiagramm-Editor können Sie Code für C, C ++, Java und viele andere generieren ... sowie eine schöne Dokumentation und Diagramme. Quelle und Binärdateien von iMatix
quelle
Dieser Artikel ist gut für das Statusmuster (obwohl es C ++ ist, nicht speziell C).
Wenn Sie das Buch " Head First Design Patterns " in die Hand nehmen können , sind die Erklärung und das Beispiel sehr klar.
quelle
Eines meiner Lieblingsmuster ist das Zustandsmuster. Reagieren Sie auf dieselben Eingaben oder verhalten Sie sich anders.
Eines der Probleme bei der Verwendung von switch / case-Anweisungen für Zustandsautomaten besteht darin, dass das Erstellen / Verwalten von switch / case-Dateien schwieriger / unhandlicher wird, unorganisierten Spaghetti-Code fördert und zunehmend schwieriger zu ändern ist, ohne etwas zu beschädigen. Ich finde, dass die Verwendung von Entwurfsmustern mir hilft, meine Daten besser zu organisieren, was den ganzen Punkt der Abstraktion ausmacht. Anstatt Ihren Statuscode anhand des Status zu entwerfen, aus dem Sie gekommen sind, strukturieren Sie Ihren Code so, dass er den Status aufzeichnet, wenn Sie einen neuen Status eingeben. Auf diese Weise erhalten Sie effektiv eine Aufzeichnung Ihres vorherigen Zustands. Ich mag die Antwort von @ JoshPetit und habe seine Lösung einen Schritt weiter gebracht, direkt aus dem GoF-Buch:
stateCtxt.h:
stateCtxt.c:
statehandlers.h:
statehandlers.c:
Für die meisten Staatsmaschinen, insb. Bei endlichen Zustandsmaschinen weiß jeder Zustand, wie sein nächster Zustand aussehen soll und welche Kriterien für den Übergang in seinen nächsten Zustand gelten. Bei Designs mit losen Zuständen ist dies möglicherweise nicht der Fall, daher besteht die Möglichkeit, die API für Übergangszustände verfügbar zu machen. Wenn Sie mehr Abstraktion wünschen, kann jeder Statushandler in eine eigene Datei aufgeteilt werden, die den konkreten Statushandlern im GoF-Buch entspricht. Wenn Ihr Entwurf mit nur wenigen Status einfach ist, können sowohl stateCtxt.c als auch statehandlers.c der Einfachheit halber in einer einzigen Datei kombiniert werden.
quelle
Nach meiner Erfahrung ist die Verwendung der Anweisung 'switch' die Standardmethode, um mehrere mögliche Zustände zu behandeln. Obwohl ich überrascht bin, dass Sie einen Übergangswert an die Verarbeitung pro Status übergeben. Ich dachte, der springende Punkt einer Zustandsmaschine sei, dass jeder Zustand eine einzelne Aktion ausführt. Dann bestimmt die nächste Aktion / Eingabe, in welchen neuen Zustand übergegangen werden soll. Ich hätte also erwartet, dass jede Zustandsverarbeitungsfunktion sofort alles ausführt, was für den Eintritt in den Zustand festgelegt ist, und anschließend entscheidet, ob ein Übergang in einen anderen Zustand erforderlich ist.
quelle
Es gibt ein Buch mit dem Titel Practical Statecharts in C / C ++ . Es ist jedoch viel zu schwer für das, was wir brauchen.
quelle
Für Compiler, die dies unterstützen
__COUNTER__
, können Sie sie für einfache (aber große) Status-Mashines verwenden.Der Vorteil der Verwendung
__COUNTER__
anstelle von fest codierten Zahlen besteht darin, dass Sie Zustände in der Mitte anderer Zustände hinzufügen können, ohne jedes Mal alles neu zu nummerieren. Wenn der Compiler dies nicht unterstützt__COUNTER__
, kann er in begrenztem Umfang vorsichtshalber verwendet werden__LINE__
quelle
__COUNTER__
eine Neunummerierung überflüssig, da der Precompiler die Nummerierung während der Kompilierung vornimmt.Sie können das minimalistische UML-Zustandsmaschinen-Framework in c verwenden. https://github.com/kiishor/UML-State-Machine-in-C
Es unterstützt sowohl endliche als auch hierarchische Zustandsmaschinen. Es hat nur 3 APIs, 2 Strukturen und 1 Aufzählung.
Die Zustandsmaschine wird durch
state_machine_t
Struktur dargestellt. Es ist eine abstrakte Struktur, die geerbt werden kann, um eine Zustandsmaschine zu erstellen.Der Zustand wird durch einen Zeiger auf dargestellt
state_t
Struktur im Framework dargestellt.Wenn das Framework für die Finite-State-Maschine konfiguriert ist,
state_t
enthält es:Das Framework bietet eine API
dispatch_event
zum Versenden des Ereignisses an die Zustandsmaschine und zwei APIs für die Zustandsüberquerung.Weitere Informationen zum Implementieren einer hierarchischen Zustandsmaschine finden Sie im GitHub-Repository.
Codebeispiele
https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine/readme.md
https://github.com/kiishor/UML-State-Machine-in -C / blob / master / demo / simple_state_machine_enhanced / readme.md
quelle
Berücksichtigen Sie in C ++ das Statusmuster .
quelle
Ihre Frage ähnelt "Gibt es ein typisches Datenbankimplementierungsmuster"? Die Antwort hängt davon ab, was Sie erreichen möchten. Wenn Sie eine größere deterministische Zustandsmaschine implementieren möchten, können Sie ein Modell und einen Zustandsmaschinengenerator verwenden. Beispiele können unter www.StateSoft.org - SM Gallery eingesehen werden. Janusz Dobrowolski
quelle
Boost hat die Statechart-Bibliothek. http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html
Ich kann jedoch nicht mit der Verwendung sprechen. Ich habe es (noch) nicht benutzt
quelle