it-swarm-eu.dev

Zustandsautomaten gegen Threads

Alan Cox einmal sagte "Ein Computer ist eine Zustandsmaschine. Threads sind für Leute, die keine Zustandsmaschinen programmieren können".
Da es keine Option für mich ist, Alan direkt zu fragen, möchte ich hier eher fragen: Wie erreicht man Multithreading-Funktionen in Hochsprachen wie Java mit nur einem Thread und einer Zustandsmaschine? Was ist zum Beispiel, wenn zwei Aktivitäten ausgeführt werden müssen (Berechnungen durchführen und E/A ausführen) und eine Aktivität blockiert werden kann?
Ist die Verwendung der Option "Nur Zustandsmaschine" eine Alternative zum Multithreading in Hochsprachen?

24
Victor Sorokin

Ein Thread verschachtelt nur Operationen, sodass sich Teile des Prozesses zeitlich zu überlappen scheinen. Eine Single-Core-Maschine mit mehreren Threads springt lediglich herum: Sie führt kleine Codebits von einem Thread aus und wechselt dann zu einem anderen Thread. Ein einfacher Scheduler entscheidet, welcher Thread die höchste Priorität hat und tatsächlich im Kern ausgeführt wird.

Auf einem Single-Core-Computer passiert nichts tatsächlich "zur gleichen Zeit". Es ist alles nur verschachtelte Ausführung.

Es gibt viele, viele Möglichkeiten, eine Verschachtelung zu erreichen. Viele.

Angenommen, Sie haben einen einfachen Prozess mit zwei Threads, der eine einfache Sperre verwendet, damit beide Threads in eine gemeinsame Variable schreiben können. Sie haben sechs Codeblöcke.

  • T1-vor Sperre
  • T1-mit Schloss
  • T1-Nachsperre
  • T2-vor-Sperre
  • T2-mit Schloss
  • T2-Nachsperre

[Dies kann in einer Schleife sein oder mehr Sperren haben oder was auch immer. Alles was es macht ist länger zu werden, nicht komplexer.]

Die Schritte von T1 müssen in der richtigen Reihenfolge ausgeführt werden (T1-vor, T1-mit, T1-nachher) und die Schritte von T2 müssen in der richtigen Reihenfolge ausgeführt werden (T2-vor, T2-mit, T2-nachher).

Abgesehen von der Einschränkung "In-Order" können diese auf beliebige Weise verschachtelt werden. Wie auch immer. Sie können wie oben aufgeführt ausgeführt werden. Eine andere gültige Reihenfolge ist (T1-vor, T2-vor, T2-Sperre, T1-Sperre, T2-nach, T1-nach). Es gibt viele gültige Bestellungen.

Warten.

Dies ist nur eine Zustandsmaschine mit sechs Zuständen.

Es ist eine nicht deterministische endliche Zustandsautomatik. Die Reihenfolge der T1-xxx-Zustände mit den T2-xxx-Zuständen ist unbestimmt und spielt keine Rolle. Es gibt also Orte, an denen der "nächste Zustand" ein Münzwurf ist.

Wenn der FSM beispielsweise startet, sind T1-vor oder T2-vor beide legitime erste Zustände. Wirf eine Münze.

Nehmen wir an, es kam T1-vor. TU das. Wenn das erledigt ist, haben Sie die Wahl zwischen T1-with und T2-before. Wirf eine Münze.

Bei jedem Schritt im FSM gibt es zwei Auswahlmöglichkeiten (zwei Threads - zwei Auswahlmöglichkeiten), und ein Münzwurf kann bestimmen, welcher bestimmte Status eingehalten wird.

25
S.Lott

Das Schreiben von Blockierungsfunktionen ist für Personen gedacht, die keine Zustandsautomaten erstellen können;)

Threads sind nützlich, wenn Sie das Blockieren nicht umgehen können. Keine grundlegende Computeraktivität blockiert wirklich, es ist nur so, dass viele von ihnen auf diese Weise implementiert werden, um die Verwendung zu vereinfachen. Anstatt ein Zeichen zurückzugeben oder "Lesen fehlgeschlagen", blockiert eine Lesefunktion, bis der gesamte Puffer gelesen ist. Anstatt in einer Warteschlange nach Rückmeldungen zu suchen und zurückzukehren, wenn keine gefunden wird, wartet eine Verbindungsfunktion auf die Antwort.

Sie können keine Blockierungsfunktionen in einer Zustandsmaschine verwenden (mindestens eine, die nicht "einfrieren" darf).

Und ja, die Verwendung einer Zustandsmaschine ist eine praktikable Alternative. In Echtzeitsystemen ist dies die einzige Option, da das System ein Framework für die Maschine bereitstellt. Die Verwendung von Threads und Blockierungsfunktionen ist nur "der einfache Ausweg", da normalerweise ein Aufruf einer Blockierungsfunktion etwa 3-4 Zustände in der Zustandsmaschine ersetzt.

9
SF.

Wie erreicht man Multithreading-Funktionen in Hochsprachen wie Java mit nur einem Thread und einer Zustandsmaschine? Was ist zum Beispiel, wenn zwei Aktivitäten ausgeführt werden müssen (Berechnungen durchführen und E/A ausführen) und eine Aktivität blockiert werden kann?

Was Sie beschreiben, heißt kooperatives Multitasking, wobei Aufgaben der CPU zugewiesen werden und diese nach einer selbst festgelegten Zeit oder Aktivität freiwillig abgeben sollen. Eine Aufgabe, die nicht zusammenarbeitet, indem sie weiterhin die CPU nutzt oder das gesamte Werk blockiert und keinen Hardware-Watchdog-Timer hat. Der Code, der die Aufgaben überwacht, kann nichts dagegen tun.

Was Sie in modernen Systemen sehen, heißt präemptives Multitasking. Hier müssen Aufgaben die CPU nicht freigeben, da der Supervisor dies für sie tut, wenn ein durch Hardware generierter Interrupt eintrifft. Die Interrupt-Serviceroutine im Supervisor speichert den Status der CPU und stellt ihn wieder her, wenn die Task das nächste Mal eine Zeitscheibe verdient. Anschließend wird der Status der Task wiederhergestellt, die als Nächstes ausgeführt werden soll, und springt zurück, als wäre nichts passiert . Diese Aktion wird als Kontextwechsel bezeichnet und kann teuer sein.

Ist die Verwendung der Option "Nur Zustandsmaschine" eine Alternative zum Multithreading in Hochsprachen?

Lebensfähig? Sicher. Gesund? Manchmal. Ob Sie Threads oder irgendeine Form von selbst gebrautem kooperativem Multitasking (z. B. Zustandsautomaten) verwenden, hängt von den Kompromissen ab, die Sie eingehen möchten.

Threads vereinfachen das Aufgabendesign bis zu dem Punkt, an dem Sie jedes Programm als ein eigenes Programm behandeln können, das zufällig den Datenraum mit anderen teilt. Dies gibt Ihnen die Freiheit, sich auf den jeweiligen Job zu konzentrieren, und nicht auf das gesamte Management und die Verwaltung, die erforderlich sind, damit er jeweils wiederholt ausgeführt wird. Da jedoch keine gute Tat ungestraft bleibt, zahlen Sie für all diese Bequemlichkeit bei Kontextwechseln. Wenn viele Threads die CPU nach minimaler Arbeit (freiwillig oder durch Blockieren wie E/A) belasten, kann dies viel Prozessorzeit beim Kontextwechsel in Anspruch nehmen. Dies gilt insbesondere dann, wenn Ihre Blockierungsvorgänge selten sehr lange blockieren.

In einigen Situationen ist der kooperative Weg sinnvoller. Ich musste einmal eine Userland-Software für eine Hardware schreiben, die viele Datenkanäle über eine speicherabgebildete Schnittstelle übertrug, die abgefragt werden musste. Jeder Kanal war ein Objekt, das so erstellt wurde, dass ich ihn entweder als Thread ausführen oder wiederholt einen einzelnen Abfragezyklus ausführen konnte.

Die Leistung der Multithread-Version war aus genau dem oben genannten Grund überhaupt nicht gut: Jeder Thread erledigte nur minimale Arbeit und lieferte dann die CPU, sodass die anderen Kanäle etwas Zeit haben konnten, was viele Kontextwechsel verursachte. Das Freilassen der Threads bis zur Freigabe half beim Durchsatz, führte jedoch dazu, dass einige Kanäle nicht gewartet wurden, bevor die Hardware einen Pufferüberlauf erlebte, da sie nicht früh genug eine Zeitscheibe erhielten.

Die Single-Threaded-Version, die sogar Iterationen jedes Kanals durchführte, lief wie ein verbrühter Affe, und die Belastung des Systems fiel wie ein Stein. Die Strafe, die ich für die zusätzliche Leistung bezahlte, bestand darin, die Aufgaben selbst zu jonglieren. In diesem Fall war der Code dafür so einfach, dass die Kosten für die Entwicklung und Wartung die Leistungsverbesserung wert waren. Ich denke, das ist wirklich das Endergebnis. Wären meine Threads herumgesessen und auf die Rückkehr eines Systemaufrufs gewartet, hätte sich die Übung wahrscheinlich nicht gelohnt.

Das bringt mich zu Cox 'Kommentar: Threads sind nicht ausschließlich für Leute gedacht, die können Zustandsmaschinen schreiben. Einige Leute sind dazu durchaus in der Lage, entscheiden sich jedoch für die Verwendung einer Zustandsmaschine (d. H. Eines Threads), um die Arbeit früher oder mit geringerer Komplexität zu erledigen.

9
Blrfl

was ist, wenn zwei Aktivitäten ausgeführt werden müssen (Berechnungen durchführen und E/A ausführen) und eine Aktivität blockiert werden kann?

Nun, ich kann mir ehrlich gesagt nicht vorstellen, wie ich mit blockierenden E/A ohne Threads umgehen soll. Es heißt Blockieren , nur weil Code, der es aufruft, wait muss.

Laut meiner Lektüre der Original-E-Mail von Cox (unten) weist er darauf hin, dass das Threading nicht gut skaliert werden kann. Ich meine, was ist, wenn es 100 E/A-Anforderungen gibt? 1000? 10000? Cox weist darauf hin, dass eine große Anzahl von Threads zu schwerwiegenden Problemen führen kann:

Von: Alan Cox ([email protected])
Datum: Fr 21. Januar 2000 - 13:33:52 EST

das IBM-Papier), dass Sie immer gegen den Scheduler stoßen werden, wenn Ihre Anwendung von einer großen Anzahl von Threads abhängt? Viele Leute werfen viele Fäden auf ein Problem und es kann wirklich schlechtes Design sein.

Das ist die geringste Sorge. 1000 Threads sind 8 MB Kernel-Stacks und genug Aufgabenwechsel, um sicherzugehen, dass Sie den größten Teil Ihres Caches ausschalten können. Ein Computer ist eine Zustandsmaschine. Threads sind für Leute, die Zustandsautomaten nicht programmieren können.

Es gibt viele Fälle, in denen Linux der Situation definitiv nicht hilft, insbesondere bei asynchronen Block-E/A.

Alan

quelle: Betreff: Interessante Analyse des Linux-Kernel-Threading durch IBM (Linux-Kernel-Mailinglisten-Archive)

2
gnat
  • Theoretisch stimmt das. Im wirklichen Leben sind Threads nur eine effiziente Abstraktion, die zum Programmieren einer solchen Zustandsmaschine verwendet wird. Sie sind so effizient, dass sie auch zum Programmieren von Zustandsdiagrammen und Petri-Netzen verwendet werden können (d. H. Parallele Verhaltensweisen, bei denen Zustandsmaschinen grundsätzlich sequentiell sind).

  • Das Problem bei Zustandsautomaten ist die kombinatorische Explosion. Die Anzahl der Zustände eines Computers mit 4G RAM beträgt 2 ^ (2 ^ 32) Zustände (ohne 2T-Festplattenlaufwerk).

  • Für einen Mann, dessen einziges Werkzeug ein Hammer ist, sieht jedes Problem wie ein Nagel aus.

1
mouviciel

Threads sind in zwei Fällen die einzige Option:

  • mehrere Kerne ohne Speichertrennung verwenden.
  • mit externem Code fertig zu werden, der blockiert.

Der zweite Grund ist, warum die meisten Leute denken, dass Threads für IO oder Netzwerkprogrammierung) unvermeidbar sind, aber dies liegt normalerweise daran, dass sie nicht wissen, dass ihr Betriebssystem über eine erweiterte API verfügt (oder nicht) will damit kämpfen).

Aus Gründen der Benutzerfreundlichkeit und Lesbarkeit gibt es immer Ereignisschleifen (wie libev oder EventMachine ), die das Programmieren einer Zustandsmaschine fast so einfach machen wie das Ausführen mit Threads, aber das Geben genug Kontrolle, um Synchronisierungsprobleme zu vergessen.

1
mbq

Ich denke nicht, dass es so ist - sicher, Zustandsmaschinen sind ein sehr "elegantes" Computerkonzept, aber wie Sie sagen, sie sind ziemlich kompliziert. Und komplizierte Dinge sind schwer richtig zu machen. Und Dinge, die nicht richtig sind, sind einfach kaputt. Wenn Sie also kein Genie von Alan Cox 'mutmaßlicher Statur sind, bleiben Sie bei Dingen, von denen Sie wissen, dass sie funktionieren - überlassen Sie die „clevere Codierung“ Lernprojekten.

Sie können erkennen, wann jemand den vergeblichen Versuch unternommen hat, einen zu tun, da Sie (vorausgesetzt, es funktioniert gut) bei der Wartung feststellen, dass die Aufgabe so gut wie unmöglich ist. Das ursprüngliche "Genie" wird Sie mit dem Klumpen kaum verständlichen Codes zurückgelassen haben (da diese Art von Entwicklern nicht dazu neigt, zu viele Kommentare zu hinterlassen, geschweige denn technische Dokumentation).

In einigen Fällen ist eine Zustandsmaschine die bessere Wahl - ich denke jetzt an eingebettete Dinge, bei denen einige Zustandsmaschinenmuster verwendet und wiederholt und formalisierter verwendet werden (dh ordnungsgemäßes Engineering :)).

Es kann auch schwierig sein, das Threading richtig zu machen, aber es gibt Muster, die Ihnen dabei helfen - hauptsächlich, indem Sie weniger Daten zwischen den Threads austauschen müssen.

Der letzte Punkt dabei ist, dass moderne Computer ohnehin auf vielen Kernen laufen, sodass eine Zustandsmaschine die verfügbaren Ressourcen nicht wirklich gut ausnutzt. Threading kann hier einen besseren Job machen.

0
gbjbaanb

Eine gute Möglichkeit, die Interaktion von Zustandsautomaten und Multithreading zu untersuchen, besteht darin, sich die GUI-Ereignishandler anzusehen. Viele GUI-Anwendungen/Frameworks verwenden einen einzelnen GUI-Thread, der die möglichen Eingabequellen abfragt und für jede empfangene Eingabe eine Funktion aufruft. Im Wesentlichen könnte dies als großer Schalter geschrieben werden:

while (true) {
    switch (event) {
        case ButtonPressed:
        ...
        case MachineIsBurning:
        ....
    }
}

Jetzt wird ziemlich schnell klar, dass der Grad der Steuerung auf hoher Ebene in diesem Konstrukt nicht hoch sein kann: Der Handler für ButtonPressed muss ohne Benutzerinteraktion beendet werden und zur Hauptschleife zurückkehren, da sonst keine weiteren Benutzerereignisse auftreten verarbeitet werden kann. Wenn ein zu speichernder Status vorhanden ist, muss dieser Status in globalen oder statischen Variablen gespeichert werden, jedoch nicht auf dem Stapel. Das heißt, der normale Kontrollfluss in einer imperativen Sprache ist begrenzt. Sie sind im Wesentlichen auf eine Zustandsmaschine beschränkt.

Dies kann ziemlich chaotisch werden, wenn Sie verschachtelte Unterprogramme haben, die beispielsweise eine Rekursionsstufe speichern müssen. Oder Sie sind gerade dabei, eine Datei zu lesen, aber die Datei ist derzeit nicht verfügbar. Oder sind nur in einer langen Berechnung. In all diesen Fällen wird es wünschenswert, den Status der aktuellen Ausführung zu speichern und zur Hauptschleife zurückzukehren, und dies ist Multithreading. Nicht mehr, nicht weniger.

Das Ganze wurde mit der Einführung des präventiven Multithreading etwas komplizierter (d. H. Das Betriebssystem entscheidet, wann Threads die Kontrolle übernehmen sollen), und deshalb ist die Verbindung heute nicht sofort klar.

Um die letzte Frage zu beantworten: Ja, die Zustandsmaschine ist eine Alternative. Die meisten GUIs funktionieren auf diese Weise mit dem GUI-Thread. Schieben Sie die Zustandsmaschine nur nicht zu weit, sie kann sehr schnell nicht mehr gewartet werden.

0
thiton

Die Frage, ob die Verwendung einer Zustandsmaschine in einer Hochsprache möglich ist, entspricht der Frage, ob das Schreiben in Assembler eine Alternative zur Verwendung einer Hochsprache ist. Beide haben ihren Platz in der richtigen Situation.

Die Abstraktion der Verwendung von Threading erleichtert die Implementierung komplexerer paralleler Systeme, aber letztendlich haben alle parallele Systeme dieselben Probleme zu lösen. Klassische Probleme wie Deadlock/Livelock und Prioritätsumkehrung sind bei Systemen auf Zustandsmaschinenbasis genauso möglich wie bei Shared Memory Parallel , - NUMA oder sogar CSP-basiert System, wenn es komplex genug ist.

0
Mark Booth

Gutes Beispiel für eine ordnungsgemäße Verwendung der Zustandsmaschine anstelle von Threads: nginx vs Apache2. Im Allgemeinen können Sie davon ausgehen, dass nginx alle Verbindungen in einem Thread verarbeitet. Apache2 erstellt einen Thread pro Verbindung.

Aber für mich ist die Verwendung von Zustandsautomaten gegen Threads mit perfekt handgefertigtem asm gegen Java ziemlich ähnlich: Sie können unglaubliche Ergebnisse erzielen, aber es erfordert viel Programmieraufwand, viel Disziplin, das Projekt komplexer und nur dann wertvoll, wenn es von verwendet wird viele andere Programmierer. Wenn Sie also derjenige sind, der einen schnellen Webserver erstellen möchte, verwenden Sie Statusmaschinen und asynchrone E/A. Wenn Sie das Projekt schreiben (nicht die Bibliothek, die überall verwendet werden soll), verwenden Sie Threads.

0
ZeusTheTrueGod