Ersatz für Warteschlangen in RTOS

12

Für die Kommunikation zwischen Tasks oder für den Datenaustausch zwischen zwei RTOS-Tasks verwenden wir Warteschlangen. Das Problem mit Warteschlangen ist jedoch, dass sie langsam sind. Sie kopieren Daten in den Puffer, dann in die Verarbeitung von Mutex und dann in die Datenübertragung. Es ist irritierend langsam, wenn Sie große Datenmengen übertragen müssen. Ein weiteres Problem besteht darin, dass mehrere Tasks auf dieselbe Warteschlange zugreifen. Das Bild sieht dann folgendermaßen aus: - Warten Sie, bis Sie auf The Queue, dann auf Queue Internal Mutex Handling und dann auf Data Transfer zugreifen können.

Dies erhöht den Systemaufwand. Was könnte der effiziente Ersatz für Warteschlangen sein?

(Ich denke, diese Frage ist unabhängig von dem von uns verwendeten RTOS. Die meisten RTOS behandeln Warteschlangen nur auf diese Weise.)

Swanand
quelle
Was verstehen Sie unter einer Warteschlange, auf die mehrere Tasks zugreifen? Meinen Sie damit das Posten in der Warteschlange oder das Lesen aus der Warteschlange? Mehrere Aufgaben sollten mit minimalem Aufwand in eine Warteschlange gestellt werden können. Das RTOS sollte das Mutexing so handhaben, dass ein Post eine atomare Operation ist. Für 99% der Aufgaben sollte eine Schleife vorhanden sein, die an einer Warteschlange hängt und die Nachricht verarbeitet. Eine Warteschlange sollte (normalerweise) nur von einer Task gelesen werden. Sie müssen sich wahrscheinlich Ihr Design und die Verwendung von Warteschlangen ansehen, anstatt sie zu ersetzen.
Erik
@ Erik: Entschuldigung! Ich benutze den von Ihnen erwähnten Mechanismus .... Ich wollte noch etwas sagen und habe etwas anderes geschrieben .... das werde ich bearbeiten !! Vielen Dank für den Hinweis auf den Fehler! Ich warte auf den Warteschlangenzugriff in meinem Code!
Swanand

Antworten:

7

Warteschlangen funktionieren auf diese Weise, da dies ein threadsicheres Transaktionsmodell für die Kommunikation zwischen Tasks ist. Sie riskieren Datenkorruption und / oder Eigentumsprobleme in einem weniger strengen Schema.

Kopieren Sie die Daten in einen Puffer im Speicher und übergeben Sie dann einen Zeiger mit den Warteschlangenelementen oder versuchen Sie, alle Daten in den Warteschlangenelementen selbst zu übergeben? Wenn Sie keine Zeiger übergeben, wird die Leistung gesteigert, anstatt ein Byte nach dem anderen durch die Warteschlangenelemente zu übergeben.

AngryEE
quelle
2
Ich wollte dasselbe sagen. Wenn Sie nur Zeiger auf die Daten in Warteschlangen übergeben, können Sie die Geschwindigkeit erhöhen, stellen Sie jedoch sicher, dass Sie nicht mit zwei Threads enden, die versuchen, die Daten zu verwenden und zu ändern.
Kortuk
Wie @Kortuk sagte, muss ich sicherstellen, dass Sie nicht mit zwei Threads enden, die versuchen, die Daten zu verwenden und zu ändern. :(
Swanand
Es gibt also keinen Ersatz für Warteschlangen ... Anstelle der Datenwarteschlange muss die Zeigerwarteschlange verwendet werden!
Swanand
1
@Swanand Wenn Sie Ihre Anwendung so planen, dass Warteschlangen nur unidirektional sind (dh Sie haben in zwei Aufgaben nie dieselbe Warteschlange gelesen) und die am Zeiger gespeicherten Daten sofort verarbeiten und anschließend freigeben, sollten Sie keine Probleme mit der Freigabe der Daten haben. Der Overhead wird erhöht, da Sie möglicherweise mehrere Warteschlangen erstellen müssen, um Daten zuverlässig hin und her zu übertragen. Dies ist jedoch der Preis für die Ausführung von Geschäften in einer Multitasking-Umgebung.
AngryEE
7

Eine einfache Möglichkeit besteht darin, einen Zeiger auf die Daten in der Warteschlange zu platzieren und die Daten mithilfe des Zeigers zu verbrauchen.

Beachten Sie, dass Sie Sicherheit gegen Leistung eintauschen, da Sie Folgendes sicherstellen müssen:

  1. Der Puffer bleibt solange gültig, bis der Verbraucher die Daten verbraucht hat
  2. Jemand gibt die Zuordnung des Puffers auf

Wenn Sie keinen dynamisch zugewiesenen Speicher verwenden, müssen Sie die Zuordnung nicht aufheben. Sie müssen jedoch sicherstellen, dass der Speicherbereich nicht wiederverwendet wird, bevor die Daten verbraucht wurden.

Trygve Laugstøl
quelle
6

Sperrfreie Warteschlangen können für den Einzelfall Produzent / Einzelverbraucher implementiert werden, und häufig können Sie Ihre Software so entwickeln, dass die Anzahl der Warteschlangen für mehrere Produzenten oder für mehrere Verbraucher minimiert wird.

Eine Warteschlange ohne Sperre kann folgendermaßen aufgebaut werden: Ordnen Sie ein Array der zu übermittelnden Elemente sowie zwei Ganzzahlen zu, und nennen Sie sie Head und Tail. Head ist ein Index im Array, in dem das nächste Element hinzugefügt wird. "Tail" ist ein Index im Array, in dem das nächste Element zum Entfernen verfügbar ist. Die Producer-Task liest H und T, um festzustellen, ob Platz zum Hinzufügen eines Elements vorhanden ist. Schreibt das Element in den H-Index und aktualisiert dann H. Die Consumer-Tasks lesen H und T, um festzustellen, ob Daten verfügbar sind, lesen Daten aus dem Index T und aktualisieren dann T. Grundsätzlich handelt es sich um einen Ringpuffer, auf den von zwei Tasks zugegriffen wird Die Reihenfolge der Operationen (Einfügen, dann Aktualisieren von H; Entfernen, dann Aktualisieren von T) stellt sicher, dass keine Datenbeschädigung auftritt.

Wenn Sie eine Situation mit mehreren Produzenten und einem einzelnen Konsumenten oder einem einzelnen Produzenten und mehreren Konsumenten haben, haben Sie effektiv irgendeine Ressourcenbeschränkung, und es gibt nichts anderes, als die Synchronisation zu verwenden, da es wahrscheinlicher ist, dass der Leistungsbegrenzer dies tut sei der einzige Produzent / Konsument als ein OS-Overhead mit dem Sperrmechanismus.

Wenn Sie jedoch mehrere Produzenten UND Konsumenten haben, lohnt es sich, Zeit (im Design-Bereich) zu investieren, um zu prüfen, ob Sie keinen besser koordinierten Kommunikationsmechanismus erhalten können. In einem solchen Fall macht die Serialisierung aller Daten über eine einzelne Warteschlange die Effizienz der Warteschlange definitiv zur zentralen Determinante der Leistung.

JustJeff
quelle
1
Ich wollte +1 dazu geben, aber Sie sind falsch: Warteschlangen ohne Sperre können für mehrere Leser und Verfasser implementiert werden, sie sind nur komplizierter. (Sehen Sie sich Michael + Scotts Artikel über Warteschlangen ohne Sperre an. google.com/search?q=michael%20scott%20queue )
Jason S,
1
@Jason S - Fordert das Scott-Papier ausdrücklich eine erneute Eingabe für die sperrenfreien Einfüge- und Entnahmevorgänge an? Wenn ja, wenn Sie das extrahieren und veröffentlichen können, dann tun Sie dies bitte, es wäre für viele von unschätzbarem Wert. Der Leser sollte beachten, dass das zitierte Papier spezielle Maschinenanweisungen verwendet, während meine Position im obigen Beitrag keine solchen Anweisungen voraussetzte.
JustJeff
1
Ja, die Kosten für die Algorithmen ohne Sperre hängen normalerweise von CAS oder ähnlichen Anweisungen ab. Aber wie kommt hier die Wiedereintritt ins Spiel? Dies ist sinnvoll für Mutexe + Sperrstrukturen, jedoch nicht für Datenstrukturoperationen.
Jason S
2

Ein effizienter Betrieb in einer sperrenfreien Single-Consumer-Warteschlange mit mehreren Herstellern ist möglich, wenn die Warteschlange selbst Elemente enthält, die klein genug sind, um mit einem Load-Store-Exclusive-, Compare-Exchange- oder ähnlichen Grundelement zu arbeiten, und a verwendet werden kann reservierter Wert oder reservierte Werte für leere Warteschlangensteckplätze. Beim Schreiben in die Warteschlange führt der Schreiber einen Vergleichsaustausch durch, um zu versuchen, seine Daten im nächsten leeren Slot zu speichern. Wenn dies fehlschlägt, versucht der Writer den folgenden Slot. Obwohl die Warteschlange einen Zeiger auf den nächsten leeren Steckplatz verwaltet, lautet der Zeigerwert "advisory". Beachten Sie, dass, wenn ein System Compare-Exchange anstelle von Load-Store-Exclusive verwendet, möglicherweise eine 'Familie' mit verschiedenen 'Leerslot'-Werten erforderlich ist. Andernfalls, wenn der Schreiber zwischenzeitlich einen leeren Warteschlangenplatz findet und versucht, darauf zu schreiben, Ein anderer Schreiber schreibt den Slot und der Leser liest ihn. Der erste Schreiber würde seine Daten unwissentlich an einer Stelle ablegen, an der der Leser sie nicht sehen würde. Dieses Problem tritt bei Systemen nicht auf, die load-store-exclusive verwenden, da store-exclusive erkennt, dass die Daten geschrieben wurden, obwohl sie auf den alten Wert zurückgeschrieben wurden.

Superkatze
quelle
1

Sie können effizienter auf Warteschlangen zugreifen, indem Sie über die Warteschlange schreiben. Normalerweise unterstützt der Großteil des RTOS das Hinzufügen an der Vorderseite der Warteschlange, ohne dass Mutex erworben werden muss. Stellen Sie jedoch sicher, dass Sie das Hinzufügen zur Warteschlangenvorderseite so gering wie möglich halten, um die Daten nur schneller auszuführen. Normalerweise haben Warteschlangenstrukturen ein maximales Größenlimit, so dass Sie möglicherweise nicht alle Daten in die Warteschlange stellen, sodass es immer einfach ist, den Zeiger zu übergeben.

Prost!!

Sai
quelle
1

Warteschlangen sind von Natur aus nicht langsam. Die Umsetzung von ihnen kann sein.

Wenn Sie Daten blind kopieren und eine synchrone Warteschlange verwenden, wird die Leistung beeinträchtigt.

Wie andere Plakate bereits angedeutet haben, gibt es schlossfreie Alternativen. Der Einzelproduzent / Einzelverbraucher-Fall ist unkompliziert; Für mehrere Produzenten und Konsumenten ist der sperrenfreie Warteschlangenalgorithmus von Michael und Scott (das sind ihre Nachnamen) der Standard und wird als Grundlage für Javas ConcurrentLinkedQueue verwendet .

Es ist in bestimmten Fällen möglich, den Bedarf an Warteschlangen zu optimieren, diese bieten jedoch Parallelitätsgarantien, die in der Regel erhebliche Vorteile für die Systemvereinfachung bieten, indem Sie Aufgaben entkoppeln können.

Jason S
quelle
Aus dem Artikel von Michael & Scott: "Es ist der eindeutige Algorithmus der Wahl für Maschinen, die ein universelles atomares Grundelement bereitstellen (z. B. Vergleichen und Tauschen oder Laden verknüpft / Speichern bedingt)." Während dies einen Thread möglicherweise nicht genau sperrt , findet hier eine Form der Synchronisierung statt.
JustJeff
du hast einen Punkt; Dies kann die Parallelitätsanforderung für den ausschließlichen Zugriff auf eine Speichersperre verringern.
Jason S