Zur Frage der Puffer (Ring)

"Wenn Sie die Entwicklungskosten der Architektur als übermäßig empfinden, überlegen Sie, wie viel Sie die falsche Architektur kosten kann."

- Ich kann mich nicht genau an die Quelle erinnern

Einmal, "vor langer Zeit, in einer fernen Galaxie", kaufte ich Charles Weatherlys wundervolles Buch Etudes for Programmers, in dessen Einleitung der Autor die Notwendigkeit begründete, pädagogische Beispiele und Aufgaben zu studieren, bevor er mit der unabhängigen Programmierung begann. Ich empfehle Ihnen dringend, dieses Buch zu finden, das Vorwort zu lesen (und ohne anzuhalten, den Rest zu lesen und die darin angegebenen Probleme zu lösen), da ich die Notwendigkeit einer solchen Praxis nicht besser begründen kann. Selbst wenn Sie meiner Empfehlung folgen und beim Lesen des Buches viel Wissen und praktische Fähigkeiten erwerben, können Sie diesen Beitrag noch einmal lesen, da er mehreren anderen Themen gewidmet ist. Und wenn Sie meinen Empfehlungen nicht folgen, sollten Sie umso mehr unter die Katze gehen.

Vor nicht allzu langer Zeit habe ich in einem Beitrag, in dem ich schimpfte, meine Meinung zu einem inländischen RTOS geäußert, dass die Implementierung des Ringpuffers in der bekannten (und in bestimmten Aspekten absolut wunderbaren) mcucpp-Bibliothek nicht als ideal angesehen werden kann. Ich werde versuchen, meinen Standpunkt zu erklären und mir die ideale (soweit in der realen Welt möglich) Implementierung vorzustellen. Hinweis - Der Text, der Ihnen zur Kenntnis gebracht wurde, lag einige Zeit im "unvollendeten" Text, und dann tauchte ein so praktischer Fall auf.

Wir entwickeln weiterhin eine Bibliothek für die Arbeit mit einem Peripheriegerät und stehen als nächstes für die Speicherverwaltung und -pufferung an (ja, wir setzen die vorbereitenden Vorgänge fort, jedoch ohne sie in irgendeiner Weise). Woher kommt die Notwendigkeit, Puffer zu organisieren, und was für ein Tier ist das? Tatsache ist, dass ein erheblicher Teil der Peripherie eine begrenzte Geschwindigkeit aufweist und der Übertragungsprozess, der auf die eine oder andere Weise gestartet wird, eine bestimmte und manchmal sehr wichtige Zeit benötigt, verglichen mit der Erstellung eines anderen Teils der Informationen für die Übertragung. Natürlich kann vor Ablauf dieser Zeit die nächste Übertragung nicht durchgeführt und dementsprechend nicht gestartet werden.

Wir haben einen klassischen Fall eines Writer-Reader-Paares mit unterschiedlichen Geschwindigkeiten. Es ist einfach unmöglich, dieses Problem in einer allgemeinen Form zu lösen, da „bei einem willkürlich kleinen, aber nicht Null-Überschuss des Anforderungsflusses über den Servicefluss die Warteschlangengröße gegen unendlich tendiert“ und unendlich grundsätzlich unmöglich ist. Ein Sonderfall des Problems ist jedoch, dass ein Pufferspeicher mit ausreichender Kapazität gelöst werden kann, wenn lokale Anforderungsbursts vorliegen, der Servicefluss jedoch im Durchschnitt die Last bewältigen kann. Achten wir auf den Ausdruck „ausreichende Kapazität“, wir werden später lernen, wie man ihn berechnet, solange uns die Tatsache, dass dies grundsätzlich möglich ist, ausreicht.

Ob Pufferspeicher eine absolute Voraussetzung ist, ist natürlich nicht. Für die übertragenen Informationen können Sie einen Sperrdatensatz verwenden. Bei den empfangenen Informationen ist dies jedoch etwas schlimmer. Sie müssen irgendwo vor der Verarbeitung hinzugefügt werden, wenn Sie im Protokoll der obersten Ebene keine geeigneten Maßnahmen ergreifen (der magische Ausdruck xon / xoff wurde nicht von Grund auf neu geboren), was nicht immer möglich ist und führt in jedem Fall normalerweise zu einer signifikanten Begrenzung der Übertragungsrate. Es gibt auch eine Hardware-Implementierung von internen Puffern in Peripheriegeräten (mindestens für ein Element), dies wird jedoch nicht immer durchgeführt und die Puffergröße wird von oben streng begrenzt.

Daher werden wir weiterhin den Programmpuffer implementieren, für den es selbstverständlich wäre, die FIFO-Methode (dh die Warteschlange) zum Organisieren eines solchen Puffers zu verwenden, und die Warteschlange wiederum wird am besten in einem Ringpuffer mit zwei Zeigern implementiert. Wenn ich "best" schreibe, bedeutet dies überhaupt nicht, dass andere Implementierungen (z. B. eine Referenzwarteschlange) unmöglich sind oder andere schwerwiegende Fehler als schwerwiegende aufweisen. Dieser Ausdruck bedeutet nur, dass die Implementierung nicht zu kompliziert und recht effektiv sein wird, obwohl andere möglicherweise unbestreitbare Vorteile gegenüber dieser haben, für die sie etwas bezahlen müssen, weil DarZaNeBy.

Da es sehr unwahrscheinlich ist, dass Ihr MK-Modell über eine Hardware-Implementierung eines solchen Allzweckgeräts verfügt (einzelne Peripheriemodule können ihre eigenen Ringpuffer haben, haben aber nichts mit dem Thema dieses Beitrags zu tun), müssen wir einen Ringpuffer im linearen Speicher erstellen (implementieren auf Vektor, dies ist im Allgemeinen das einzige natürliche Objekt im adressierbaren Speicher), und dafür wird ein Pufferindex (oder vielleicht sogar zwei Indizes, aber dazu später mehr) benötigt. Meiner Meinung nach ist ein kreisförmiger Puffer mit zwei Zeigern (Indizes) der einzig akzeptable Weg, um eine Warteschlange in einem Vektor zu implementieren, aber es gibt unterschiedliche Sichtweisen zu diesem Thema, und ich habe mit eigenen Augen eine Implementierung im Stil von „x1 = x2; x2 = x3; ... x8 = neues Symbol ", wenn Sie so wollen, werde ich solche Exoten nicht in Betracht ziehen. Die Tatsache, dass das gegebene Fragment das Recht hat, in einer bestimmten, sehr begrenzten Situation zu existieren, macht es im Allgemeinen nicht akzeptabel.

Wir werden die korrekte Implementierung des Programmmoduls zum Organisieren des Zeigers betrachten und zunächst auf das erste Wort in der Definition achten. Der Unterschied zwischen einem korrekten und einem falschen Code besteht nicht nur darin, dass der richtige Code keine Fehler enthält, obwohl dies eine absolute Voraussetzung ist. Sogar der Code, der seine Funktionen vollständig ausführt, kann falsch sein, wenn er unverständlich ist oder wenn es eine Option gibt, die nicht weniger klar ist, aber schneller ausgeführt wird oder so schnell ausgeführt wird, aber klarer geschrieben ist, sodass das Konzept der Korrektheit etwas relativ ist. Wir setzen unsere Betrachtung unseres Beispiels für die Pufferimplementierung fort, um den Unterschied zwischen verschiedenen Korrektheitsgraden aufzuzeigen.

Bevor wir uns der Essenz zuwenden, ein wichtiger Punkt zur weiteren Diskussion. Ich meine, Ihr Compiler ist immer auf einer Otpimierungsstufe ungleich Null (-O2) eingeschaltet, sodass wir nicht über geringfügige Verbesserungen nachdenken müssen, wie 1) Präfixänderung gegenüber Postfix oder 2) Verwendung der Ergebnisse der vorherigen Operation oder 3) Differenz zwischen Inkrement und Addition Einheiten und so weiter - wir gehen davon aus, dass der Compiler viel für uns tun wird. Natürlich ist dies keine strenge Annahme, aber sonst müssen wir uns in den Darm des Assemblers stürzen, der in unserer Zeit nicht der Mainstream ist.

Ich möchte Sie daran erinnern, dass wir angewiesen wurden, den Index (Zeiger) des Ringpuffers zu implementieren. Das heißt, wir müssen das Verhalten einer Variablen erstellen, die nacheinander eine Reihe von Werten durchläuft, von einem Anfang bis zu einem Ende . Nehmen Sie sofort an, dass der Anfangswert Null ist, andernfalls müssen wir sofort einen mehr oder weniger korrekten Code schreiben. Dies widerspricht den Bildungszielen und wir haben es nicht eilig und der letzte ist Max.

Dieses Verhalten der Variablen kann mit der folgenden Konstruktion implementiert werden:

volatile int Counter = 0; Counter = (++Counter) % (Max+1); 

und genau diesen Code können wir in vielen (dh sehr oft) Fällen sehen. Was ist falsch? Erstens ist unsere Variable für einige Zeit (von der Durchführung der Inkrementierungsoperation bis zur Zuweisung des Ergebnisses) größer als der maximal zulässige Wert. Wenn in diesem Moment ein Interrupt auftritt, der den Wert dieser Variablen berücksichtigen muss, dann sage ich persönlich voraus Ich gehe nicht von den Ergebnissen aus. Deshalb schreiben wir das Programm neu:

 int Counter=0; Counter = (Counter + 1) % (Max + 1); 

Wir haben einen Fehler beseitigt, und der Code (im Folgenden meine ich den Code "ausführbar" bedeutet den vom Compiler generierten ausführbaren Code) ist nicht länger geworden und wird nicht mehr ausgeführt (tatsächlich wird er schneller ausgeführt, sondern nur, weil in der ersten Version Das Wort flüchtig wird in diesem Fall völlig überflüssig verwendet) und ist nicht weniger klar geworden (eher noch klarer, aber dies ist Geschmackssache).

Notwendiger Hinweis zu volatile - Diese Direktive wird benötigt, um eine Codeoptimierung zu vermeiden, die zu einer fehlerhaften Ausführung führt, und in diesem speziellen Fall (wenn sich der Wert der Variablen außerhalb des Bereichs des Moduls nicht ändert und keine sequentiellen Einträge darin enthalten sind) (Direktive ) völlig überflüssig. Ich empfehle dringend, dass Sie sich den generierten Code für beide Optionen auf godbolt.org ansehen. Warum Sie die flüchtige Direktive nicht missbrauchen sollten, im Gegensatz zum statischen Schlüsselwort, das nach Möglichkeit empfohlen wird. Nun, erstens verbieten wir die Optimierung, das heißt, der Code wird definitiv nicht schneller (höchstwahrscheinlich wird er größer und langsamer, aber wir bevorzugen strenge Formulierungen). Und zweitens ist dieses Wort in diesem speziellen Fall irreführend, da sich der Wert des Zählers in Bezug auf unser Programm in keiner Weise außerhalb unserer Kontrolle ändern kann. In einem Programm, das seinen Wert liest, dh in der Implementierung des Ringpuffers selbst, können Sie den Zähler außerhalb des Moduls als veränderbar betrachten, und dort ist er fraglich, daher ist dieses Attribut einfach nicht auf den Zähler anwendbar. Wenn eine Variable in verschiedenen Modulen unterschiedlich interpretiert werden soll, sollten unsere Services kombiniert werden. Wenn wir über die Organisation eines kritischen Abschnitts sprechen, beispielsweise bei der Implementierung einer Transaktion oder von atomaren Operationen, dann gibt diese Direktive überhaupt nichts.

Wir kehren zum Code zurück und sehen, dass das Programm immer noch falsch ist - was ist los - und dass es nicht das tut, was wir brauchen (siehe Beschreibung der Aufgabe), sondern etwas anderes (berechnet den Rest der Division), nur die Ergebnisse zusammenpassen. Nun, wir denken so (ich glaube nicht, aber die Autoren des Codes sicherlich), dass die Ergebnisse tatsächlich übereinstimmen, im allgemeinen Fall stimmen sie nicht überein, wir hatten nur Glück mit dem Bereich der Variablen (positive Werte). Darüber hinaus ist der Prozess der Ausführung des Codes länger als möglich, da wir im besten Fall die Ganzzahldivision durchführen (wenn sie Teil der Befehle unserer Architektur ist) und sie keinesfalls in einem Prozessorzyklus ausgeführt wird (ein charakteristischer Wert von 10 Zyklen) für eine 8-Bit-Architektur), und im schlimmsten Fall wird der Aufruf der Teilungsprozedur aus der Standardbibliothek angezeigt (und wenn eine kurze Teilung erfolgt), beträgt die Ausführungszeit zehn Taktzyklen.

Warum ist es also immer noch möglich, einen so völlig falschen Ansatz sehr oft zu treffen? Hier vom Publikum sagen sie mir, dass der Compiler mit dem Wert von Max + 1, der eine Zweierpotenz ist, anstelle der Divisionsoperation die Operation der bitweisen Multiplikation auf die entsprechende Maske (gleich Max) setzen wird, die sehr schnell ausgeführt wird und alles in Ordnung ist.

Ich würde dieser Aussage zustimmen und diesen Ansatz verfolgen, wenn nicht unter folgenden Umständen:

• Dies ist nur für Mach möglich, der in der Kompilierungsphase statisch definiert wurde.
• Dies geschieht nur, wenn die Optimierung aktiviert ist.
• Dies geschieht nur, wenn Mach diese Bedingung erfüllt.
• Dies tritt nicht bei allen Kardinaltypen auf.

Darüber hinaus wird in diesem speziellen Fall (wenn die Variable als Vorzeichen definiert ist) zusätzlich zum Befehl zum Multiplizieren (logisch) mit der Maske ein Vergleichsbefehl mit Null und eine Verzweigung für negative Werte generiert, und obwohl diese Verzweigung niemals für unseren Bereich gilt Es wird ausgeführt, es nimmt Speicherplatz im Speicher ein (und im Fall einer austauschbaren Funktion dauert es mehrere Male) und es wird einige Zeit dauern, um die Vergleichsoperation durchzuführen. Wenn Sie es nicht glauben, folgen wir erneut der angegebenen Site und überzeugen uns selbst. Ein weiteres Argument zugunsten der nicht unterzeichneten Kardinäle, denen ich kürzlich einen ganzen Beitrag gewidmet habe.

Wenn wir daher die logische Multiplikation mit einer Maske verwenden möchten (erhalten durch Optimieren der Berechnung des Restes), sollten wir das Modul entsprechend umschreiben:

 typedef uint8_t Counter_t; typedef int8_t sCounter_t; static inline Counter_t NextCounter(const Counter_t Counter) { #if IS_POWER2(Max + 1) return (Counter + 1) & Max #else return (Counter + 1) % (Max + 1); #endif }; 

In dieser Version ist alles vollkommen klar und kontrollierbar und alles ist wahr (obwohl eine Reihe von Mängeln bestehen geblieben sind, aber sie sind jetzt offensichtlich und nicht maskiert), daher ist es richtig, obwohl es korrekter ist und wir werden sie jetzt suchen. Der Hauptnachteil ist meiner Meinung nach eine Verletzung des KISS-Prinzips, da die Verwendung der Restoperation durch Division dieses Prinzip völlig vernachlässigt. Daher werden wir jetzt alle Mängel mit einem Schlag beseitigen (keine Sorge um ihr Schicksal, sie werden 100.500 Mal wiedergeboren, da nicht alle Programmierer für Arduino meine Beiträge lesen).

Aber zuerst eine leichte Abweichung zur Seite. Wie können wir eine Überprüfung der Zweierpotenz (eine Binärzahl kann als {0} 1 {0} dargestellt werden) implementieren, die wir gerade verwendet haben?


Und wie können wir die Überprüfung implementieren, dass eine Zahl eine richtige Folge von Einheiten {0} 1 {1} in binärer Notation ist - eine Option liegt auf der Hand

 #define IsRightSequence(N) IsPower2 ((N) + 1) 

und der zweite ist trivial

 #define IsRightSequence(N) ( (((N) + 1) & (N)) == 0) 

Anmerkung: Ich kann nicht anders, als mich an den großartigen Satz zu erinnern: "Eine transzendentale Zahl in einem transzendentalen Grad ist immer transzendent, es sei denn, das Gegenteil ist offensichtlich oder trivial."

Und wie können wir überprüfen, ob eine Zahl eine Folge von Einheiten {0} 1 {1} {0} ist?

 #define IsSequence(N) IsPower2( (N) ^ ((N) << 1)) 

Und schließlich - wie man das niedrigstwertige Bit einer Zahl auswählt (ich weiß nicht, warum dies notwendig sein könnte, aber es wird nützlich sein)

 #define LowerBit(N) ((((N) - 1) ^ (N)) & (N)). 

Aber er hat sich ausgedacht, was nützlich sein kann

 #define IsRightSequence(N) (IsSequence(N) && (LowerBit(N) == 1)) 

Eine merkwürdige Beobachtung - diese Makros sind nicht ganz korrekt. Es stellt sich heraus, dass 0 sowohl eine Zweierpotenz als auch eine richtige Sequenz ist (natürlich auch eine Sequenz), was etwas seltsam ist. Aber 1 ist all diese Objekte zu Recht, so dass Null anscheinend nur separat betrachtet werden muss. Eine weitere interessante Eigenschaft dieser Makros ist, dass wir keine Annahmen über die Länge des Arguments treffen, dh, sie funktionieren mit jedem Kardinaltyp korrekt.

Es gibt ein wundervolles Buch, "Tricks for Programmers", in dem Sie die genannten Makros und viele andere ebenso unterhaltsame und lehrreiche Aufgaben finden. Ich empfehle es dringend, es zu lesen, zumal es nicht zu viele Buchstaben enthält.

Aber zurück zu unserem Ringpufferindex. Wir haben die richtige Lösung gegeben, aber noch korrekter versprochen, was bedeutet, dass unsere letzte Lösung Mängel aufweist (wer würde daran zweifeln). Eine davon - die Länge des Puffers sollte in der Kompilierungsphase statisch bestimmt werden, die zweite - im Falle einer erfolglosen Länge ist die Ausführungszeit sehr lang und es gibt immer noch eine bestimmte Anzahl von Fehlern in einem relativ kleinen Teil des Programms, was uns an einen Witz über 4 Fehler beim Schreiben des Wortes "mehr" erinnert. Wir werden sie alle beseitigen (einige werden für später übrig bleiben) und sofort, wofür wir schließlich die Lösung für das ursprüngliche Problem schreiben werden, wie es ist:

 static inline Counter_t NextCounter(const Counter_t Counter) { if ((Counter + 1) > Max) { return 0; } else { return Counter + 1; }; }; 

(Wie Sie bereits verstanden haben, bin ich ein Anhänger der ägyptischen Klammern und es gibt nichts zu tun).

Lassen Sie uns darauf achten, dass wir den Zustand des Problems einfach aus einer natürlichen Sprache in der gewählten Programmiersprache umgeschrieben haben, sodass es sich als äußerst klar und verständlich herausstellt. Ist es möglich, es zu verbessern - zweifellos, aber nur unter dem Gesichtspunkt der Geschwindigkeit des Codes, da es einfach keine anderen Mängel für diese Lösung gibt (es gibt keine offensichtlichen Mängel, tatsächlich existieren sie und wir werden sie erfolgreich beseitigen).

Bewerten wir die rechnerische Komplexität dieser Lösung - Addition mit Einheit (1) und Vergleich (2) immer, dann Zuweisung von Null (1) (selten) oder Addition (1) (fast immer) -, was 1 + 2 + 1 + Δ ~ 4 Elementar ergibt Operationen und Nullspeicher. Es ist möglich, dass ein guter Compiler im richtigen Modus bestimmte Optimierungen vornimmt und die Ausführungszeit des Codes verkürzt. Es ist jedoch besser, dies explizit zu tun. Hier ist die folgende Option:

 static inline Counter_t NextCouner(const Counter_t Counter) { register sCounter_t Tmp; Tmp = (Counter + 1); if (Tmp > Max) { Tmp = 0; }; return Tmp; }; 

Wir bewerten die Komplexität - Addition und Vergleich immer, weisen null (selten) zu - ungefähr 3 Operationen und ein Speicherelement. Tatsächlich hatte die vorherige Version auch ein Speicherelement (implizit), so dass wir einen Nettogewinn in einer Elementaroperation haben. Darüber hinaus hatte die vorherige Version zwei weitere Nachteile - 1) verstieß gegen das DRY-Prinzip (berechnete den Anstieg zweimal um eins) und 2) hatte mehr als einen Austrittspunkt, was nicht gut ist. Wir haben auch nicht das Verständnis verloren, das heißt, wir haben es geschafft, ein paar Kaninchen mit einem Schuss zu töten, und wir haben auch keine Patronen ausgegeben - es ist nur eine Geschichte im Stil von Baron Münchhausen.

Beachten Sie, dass ich das Konstrukt if ( (Tmp = Counter + 1) > Max) verwendet habe, obwohl es eine explizite Anweisung an den Compiler enthält, zu versuchen, keine redundanten Übertragungen vorzunehmen. Dies ist ein Aroma in der offensichtlichsten Form. Ich mag den vom Zuweisungsoperator zurückgegebenen Wert einfach nicht und versuche, ihn nicht zu verwenden. Ich kann den Grund für dieses starke Gefühl nicht erklären, laut Freud ist dies höchstwahrscheinlich ein psychologisches Trauma in der Kindheit. Moderne Compiler sind durchaus in der Lage, einfache Optimierungen selbst durchzuführen, und außerdem habe ich ein Registerqualifikationsmerkmal hinzugefügt, damit der Code für meine Version und der richtige (aus Sicht der C-Sprache) übereinstimmen. Trotzdem schränke ich Ihre Freiheit, die Ihnen vorzuziehende Methode anzuwenden, keineswegs ein.

Wir verbessern uns weiter, weil der Perfektion keine Grenzen gesetzt sind und wir sie noch nicht erreicht haben. Um dies zu erreichen, formulieren wir das ursprüngliche Problem etwas neu und lassen nur die Anforderung der Variablen im Wertebereich, ohne die Richtung der Änderung anzugeben. Mit diesem Ansatz können Sie das Programm wie folgt umschreiben

 static inline Counter_t NextCouner(const Counter_t Counter) { register Counter_t Tmp; Tmp = (Counter - 1); if (Tmp < 0) { Tmp = ; }; return Tmp; }; 

Auf den ersten Blick hat sich nicht viel geändert, aber wir bekommen trotzdem einen Zeitgewinn. Natürlich nicht aufgrund der Tatsache, dass der Vorgang des Verringerns um eins schneller funktioniert als der Vorgang des Erhöhens um ihn (obwohl ich eine ähnliche Version gehört habe), sondern aufgrund der Besonderheiten des Vergleichs. Wenn ich in den vorherigen Versionen den Vergleich als zwei Elementaroperationen betrachtet habe (zuerst subtrahieren wir und treffen dann eine Entscheidung), wird in diesem Fall das Ergebnis der vorherigen Operation verwendet, um eine Entscheidung direkt zu treffen, und der Vergleich erfordert eine Elementaroperation, die immer zu zwei Operationen und einer Zuordnung führt (selten) und wir haben eine Operation gespeichert (ohne etwas zu verlieren), wie das Sprichwort sagt: "Eine Kleinigkeit, aber nett." Ist die resultierende Lösung ideal - leider nein. Es ist der Lösung mit einer Maske (die genau 2 Elementaroperationen erfordert) in Bezug auf die Geschwindigkeit etwas unterlegen, und dies ist möglicherweise der einzige Nachteil.

Es gibt eine noch schnellere Lösung: Erhöhen (verringern) Sie einfach den Zählerwert und tun Sie nichts anderes. Dies ist jedoch nur dann möglich, wenn der Maximalwert mit dem Wert übereinstimmt, der für den akzeptierten Typ am repräsentativsten ist. Für einen 8-Bit-Zähler (dh vom Typ uint8_t) ist es 255. Dann schreiben wir einfach Counter = Counter + 1 und nehmen mein Wort dafür, dass das Schreiben von Counter + = 1 oder ++ Counter völlig optional ist, obwohl es viele sind und sie werden schreiben und absolut richtig sein. Wenn wir die Version über die Notwendigkeit, Zeichen zu speichern, nicht ernsthaft in Betracht ziehen (da die erste Option die längste ist), macht dies keinen Sinn, zumindest wenn wir ein Programm für die ARM- oder AVR-Architektur schreiben (für andere, die ich gerade nicht überprüft habe, vermute ich, dass das Ergebnis sein wird das gleiche) unter dem GCC-Compiler (der Autor versteht, dass sie das Programm im Editor der integrierten Programmierumgebung schreiben, dies ist nur eine Sprachrevolution aus der Vergangenheit, als Computer groß und Speicher klein waren) und mit auf jeder Ebene aktivierter Optimierung, weil Der angegebene Code ist absolut identisch.

Moderne Compiler sind in Bezug auf die Optimierung sehr, sehr fortgeschritten und generieren natürlich wirklich sehr guten Code, wenn Sie den entsprechenden Modus aktiviert haben. Obwohl ich bereit bin zuzustimmen, dass solche Sprachkonstrukte keinen Schaden anrichten und unter bestimmten Bedingungen nützlich sein können, stelle ich nur fest, dass Counter ++ - Ausdrücke (in diesem speziellen Fall natürlich) eindeutig vermieden werden sollten, da sie für völlig andere Situationen gedacht sind und dazu führen können langsamerer Code, obwohl optional.

Eine andere Frage ist, dass ein Puffer mit 256 Elementen nicht immer akzeptabel ist. Wenn Sie jedoch über genügend Speicher verfügen, warum nicht? Wenn Sie bei dieser Implementierung den Puffer am Seitenrand ausrichten können, kann der Zugriff auf die Elemente sehr schnell erfolgen, da Sie nicht mehr von Index zu Index wechseln müssen (das Schlüsselwort union zeigt Ihnen die Implementierung einer solchen Funktion an. Ich werde sie nicht einbringen, um nicht zu lernen schlecht), aber dies ist bereits eine sehr, sehr spezifische Entscheidung mit einer starken Bindung an die Architektur, die im schlimmsten Sinne des Wortes gefährlich nahe an Tricks liegt, und dies ist nicht unser Stil.

Natürlich verbietet uns niemand, einen Wrapper zu schreiben, der diese oder jene Methode abhängig vom Wert der maximalen (und minimalen, da viele Methoden einfach nicht mit einem Minimum ungleich Null arbeiten) Zählerwerte aufruft. Ich habe daher bereits die Grundprinzipien einer solchen Lösung vorgeschlagen Wir werden dies als Übung anbieten.

Zusammenfassend lässt sich sagen, dass wir verschiedene Implementierungen von Arbeiten mit einem Ringindex zusammenführen und ihre Eigenschaften bewerten werden.

Die zweite Zeile in Klammern zeigt die Anzahl der Puffergrößenwerte (nicht mehr als 256), für die diese Implementierung verfügbar ist. Wir meinen jedoch, dass ein Puffer der Größe 0 uns nicht interessiert.

Wie Sie aus dieser Tabelle ersehen können, DarZaNeBy (mein Lieblingsausdruck, wie Sie vielleicht bemerkt haben) und die Vorteile auf Kosten der Nachteile gekauft werden, kann nur eindeutig festgestellt werden, dass das Inkrement mit der Verifikation einen erfolgreicheren Konkurrenten in Form einer Dekrementierung mit Verifikation hat und nicht in die nächste Runde geht unter keinen Umständen.

Ein notwendiger Hinweis - es gibt Programmiersprachen, in denen wir überhaupt nicht über die Implementierung des Index nachdenken müssten, sondern einfach den Intervalltyp verwenden könnten. Leider kann ich die Implementierung dieser Konstrukte im Code nicht als optimal bezeichnen, da diese Konstrukte (und diese Sprachen) nicht zur Optimierung zur Laufzeit vorgesehen sind, aber es ist schade.

Also haben wir das richtige Modul (was für ein starker Name für die Inline-Funktion) für die Arbeit mit dem Index erstellt, und jetzt können wir mit der Implementierung des Ringpuffers selbst beginnen.

Und für den Anfang sollten wir entscheiden, was genau wir von diesem Programmobjekt wollen. Es ist absolut notwendig, ein Datenelement in einen Puffer einfügen und extrahieren zu können - zwei Hauptmethoden, eine Art Getter und Setter. Es ist theoretisch möglich, sich einen Puffer ohne eine dieser Methoden oder sogar ohne beide vorzustellen (wenig kann rein theoretisch vorgestellt werden), aber der praktische Wert einer solchen Implementierung ist eine große Frage. Die nächste notwendige Funktionalität - das Überprüfen auf Informationen - kann entweder als separate Methode oder als spezieller Wert (oder Attribut) implementiert werden, der durch Lesen zurückgegeben wird. Normalerweise bevorzugen sie die erste Methode, da sie verständlicher und nicht zu teuer ist.
Die Überprüfung des Puffers auf Vollständigkeit ist jedoch bereits eine große Frage - dieser Vorgang erfordert zusätzliche Zeit, die immer für die Aufzeichnung aufgewendet wird, obwohl uns niemand zwingt, ihn zu verwenden - also lass es sein. Wir brauchen nichts anderes aus dem Puffer. Erinnern wir uns an diesen Satz für die Zukunft.

Zurück zur Implementierung. Wir brauchen einen Platz zum Speichern der Elemente der Warteschlange und zwei Indizes - einen zum Schreiben in den Puffer und einen zum Lesen daraus. Wie genau wir diesen Ort (und diese Hinweise) erhalten, ist ein Thema für eine separate Diskussion. Lassen Sie uns diesen Moment vorerst in Klammern lassen und glauben, dass wir sie einfach haben. Einige (einschließlich der Autoren des Buches "Programmieren für Mathematiker", das ich respektiere, ich empfehle es zu lesen) verwenden ebenfalls den Zähler für ausgefüllte Stellen, aber wir werden dies nicht tun und ich werde versuchen zu zeigen, warum dies böse ist.

Erstens über die Indizes - wir bemerken sofort, dass dies Indizes sind, keine Zeiger, obwohl ich es mir manchmal erlaubt habe, so genannt zu werden.Warum Indizes (Speichern von Informationen über die Nummer des Warteschlangenelements) und nicht Zeiger (Speichern von Informationen über die Position im Speicher des Warteschlangenelements) eine sehr schwierige Frage sind, gibt es Situationen, in denen Zeiger rentabler sind, aber dies ist eindeutig nicht unser Fall. Unsere Warteschlangen sind kurz (selbst bei 256 sehen wir vorsichtig aus), sodass Indizes weniger Platz beanspruchen, elementare Operationen für sie schneller sind und es keine Probleme mit der Atomizität von Operationen gibt (in einer normalen Architektur sollte es keine mit Zeigern geben, aber mit 8-Bit-Indizes werden natürlich nie passieren, wenn Sie keinen 4-Bit-Controller haben. Die zusätzlichen Kosten für den Wechsel vom Index zum Zeiger sind nicht zu hoch (vorausgesetzt, die Elemente der Warteschlange sind klein).


Darüber hinaus sind viele Tricks, die die Geschwindigkeit zum Erhalten des nächsten Werts erhöhen, bei Verwendung des Zeigers nicht mehr verfügbar. Und wenn Sie auch die Meinung berücksichtigen, dass Zeiger schwieriger zu verstehen sind (nicht, dass mir diese Meinung richtig erschien, aber existiert), dann ist die Wahl klar - Indizes.

Aber was genau Indizes zeigen sollten - hier ist der Vorstellungsspielraum innerhalb der Größe des Max-Puffers (und sogar mehr als dieser) unbegrenzt, aber ein sehr kleiner Satz von Optionen hat praktische Bedeutung. Für den Aufzeichnungsindex gibt es zwei Möglichkeiten: 1) Geben Sie den Ort an, an dem das letzte Element aufgezeichnet wurde, und 2) Geben Sie den Ort an, an dem das nächste Element aufgezeichnet wird. Da die erste Option unmittelbar nach dem Erstellen der Warteschlange etwas seltsam aussieht, wählen wir die zweite, zumal dies uns in Zukunft einen spürbaren Gewinn verspricht. Für den Leseindex nehmen wir sofort an, dass er auf das Element zeigt, das beim nächsten Lesen gelesen wird. Sofort gibt es ein einfaches (im Sinne der Überprüfung) Kriterium, dass die Warteschlange nicht leer ist - die Indizes sind nicht gleich. Aber das zweite Problem tritt auf - wenn wir genau Mach-Elemente in die Warteschlange stellen,dann stimmen die Indizes überein und wir können diese Situation nicht von einer leeren Warteschlange unterscheiden.

Die erste Lösung für dieses Problem („offensichtliche, verständliche und einfache falsche Lösung“) wurde oft verwendet und besteht darin, einen Zähler für die Anzahl der im Puffer platzierten Elemente oder im fortgeschrittenen Fall das Flag der Vollständigkeit einzurichten. Warum lehne ich es ab - dies ist 1) zusätzlicher Speicherplatz, 2) die Zeit, die für die Arbeit damit aufgewendet wurde (sie sind klein, aber es gibt) 3) bis der Index übereinstimmt, ist der Zählerwert redundant, da er mit der Indexdifferenz übereinstimmt, 4) Bei einer Puffergröße von 256 Elementen sollte der Zähler länger als die Indizes sein und darf kein nativer Typ sein. 5) Es gibt einen weiteren Nachteil (fast fatal), aber dazu später mehr. Wie oben erwähnt, ist es teilweise möglich, diese Mängel zu beheben, indem nicht ein Zähler, sondern eine vollständige Flagge organisiert wird, aber es gibt eine viel bessere Lösung.

Wir müssen nur eine Situation vermeiden, in der die Indizes nach dem nächsten Datensatz zusammenfallen können (die Tatsache, dass sie nach dem Lesen zusammenfallen können, ist offensichtlich), und dafür müssen wir die mögliche Anzahl von Elementen im Puffer auf 1 weniger als möglich begrenzen. Hier ist seine Implementierung:

 #define NeedOverflowControl YES typedef uint8_t Data_t; static Data_t BufferData[Max]; static Counter_t BufferWriteCounter=0, BufferReadCounter=BufferWriteCounter; void BufferWrite(const data_t Data) { BufferData[BuffWriteCounter] = Data; register counter_t Tmp = NextCount(BufferWriteCounter); #if (NeedOverflowControl == YES) if (Tmp == BufferReadCounter) {BufferOverflow();} else #endif { BufferWriteCounter = Tmp; } }; 

Es gibt eine leichte Unrichtigkeit in der vorherigen Funktion, ich schlage vor, sie zu finden und selbst zu beheben, obwohl ... es immer noch gibt, aber wir werden fortfahren:

  inline int BufferIsEmpty(void) { return ( BufferReadCounter == BufferWriteCounter ); }; inline int BufferIsFull(void) { return ( BufferReadCounter == NextCounter(BufferWriteCounter) ); }; #define DataSizeIsSmaller (sizeof(data_t) < sizeof(counter_t)) data_t BufferRead(void) { #if DataSizeIsSmaller register data_t Tmp = BufferData[BufferReadCounter]; #else register counter_t Tmp = BufferReadCounter; #endif BufferReadCounter = NextCount(BufferReadCounter); #if DataSizeIsSmaller return Tmp; #else return BufferData[Tmp]; #endif }; 

Achten wir auf die Situation, in der wir die Überlaufverarbeitungsprozedur aufgerufen haben (wenn wir das Flag für den Verarbeitungsbedarf gesetzt haben). Als wir versuchten, das letzte nicht belegte Byte des Puffers zu schreiben, haben wir dies nicht durch Verschieben des Schreibindex gemeldet. Wir können es nicht lesen - wie ich und Mit der ausgewählten Implementierungsoption wird die Pufferkapazität um eins reduziert. Beachten Sie auch, dass wir zuerst das nächste Element in die Warteschlange stellen und erst dann durch Verschieben des Index darüber informieren. Die umgekehrte Reihenfolge kann zu sehr unangenehmen Konsequenzen führen.

Bevor wir uns den Code mit dem Flag ansehen, lassen Sie uns ein wenig über den Überlauf sprechen. Er tritt auf, wenn wir das nächste Element nicht in den Puffer einfügen können, und wir haben verschiedene Möglichkeiten, das Problem zu lösen, darunter gute und so weiter.

Zuallererst die (richtige und gute) Methode Nummer

1), um diese Situation im Prinzip durch Auswahl der richtigen Puffergröße zu verhindern (es gibt eine Unteroption dieser Methode - erhöhen Sie die Puffergröße, falls erforderlich, aber in der Welt der eingebetteten Programmierung hat sie keine Wurzeln geschlagen, und tatsächlich sieht es zweifelhaft aus - Mal mussten wir den Puffer vergrößern, wo es eine Garantie gibt, dass wir es nicht immer wieder tun müssen).
Die nächste Methode (richtig, aber schlechter, obwohl immer noch gut) Nummer

2), um das Auftreten eines Überlaufs mit einem Rückgabewert zu melden und das Schreiben in den Puffer anzuhalten - der sogenannte Blockierungsdatensatz, der jedoch nicht immer implementiert ist.

Und hier sind zwei falsche und schlechte Wege:

3) und 4) ignorieren das Problem und tun so, als wäre alles in Ordnung („Lächeln und Winken“). Warum sind sie schlecht - weil wir nur so tun, als wäre alles in Ordnung, kann das Dirichlet-Prinzip (das Problem von N-Zellen und N + 1-Vögeln) nicht verletzt werden und wir verlieren das Datenelement, und warum gibt es zwei Möglichkeiten? dass wir

3) das zuletzt aufgezeichnete Datenelement

verlieren können und 4) das erste der noch nicht übertragenen Elemente verlieren können .

Welche dieser Methoden ist schlechter - „beide sind schlechter“, obwohl sich einige für eine bestimmte Aufgabe als akzeptabler herausstellen, aber der Hauptnachteil ist nicht zu beseitigen - wir sind gezwungen, Informationen zu verlieren. Daher wird am häufigsten Methode 3 verwendet, da die Implementierung einfacher ist (hierfür reicht es aus, den Datensatzindex unverändert zu lassen), was ich im vorherigen Beispiel getan habe, wenn die Überlaufverarbeitung leer ist.

Es gibt einen anderen Weg - kontrollieren Sie die Situation überhaupt nicht (in unserem Beispiel kommentieren Sie die Zeile mit der Definition aus, aber nicht die Zeile mit der tatsächlichen Prüfung), während wir

5) den gesamten gefüllten Puffer verlieren - auf den ersten Blick scheint es die schlimmste zu sein, da die Verluste am größten sind groß, in der Tat ist dies nicht ganz richtig, da jeder Datenverlust böse ist, aber es hat einen klaren Vorteil - diese Methode ist schneller, da der Überlauf überhaupt nicht kontrolliert.

Eine interessante Beobachtung: Bei einer schnellen Suche im Internet wurde kein Algorithmus für die Datenwiederherstellung bei einem Elementverlust gefunden, im Gegensatz zu einer Elementverzerrung, bei der Blockcodes einwandfrei funktionieren.

Die Option mit dem Überlauf-Flag verliert überraschenderweise nur sehr wenig an Geschwindigkeit, wenn sie richtig geschrieben ist, verliert aber dennoch, und aus dem Speicher gewinnen wir natürlich ein Element, aber wir müssen Platz für das Flag nehmen, damit die Einsparungen in Frage kommen . Wir werden die Option mit dem Zähler einfach nicht in Betracht ziehen, da ich bereits 4 seiner Mängel aufgelistet habe und es an der Zeit ist, die fünfte, wie ich versprochen habe, zusätzlich zu der tödlichen zu erinnern. In der zuvor vorgeschlagenen Implementierung haben Indizes die Eigenschaften von MRSW (Multi-Reader Single-Writer) gemäß der Klassifizierung von „Die Kunst der Mulpiprozessor-Programmierung“ (ich empfehle das Lesen, absolut erstaunliche Arbeit) und bei atomaren Operationen ist es nicht erforderlich, die Indizes (für den nativen Typ) zu ändern keine Mittel zur Synchronisation.Ein notwendiger und sehr wichtiger Hinweis: Die Synchronisation ist nicht nur unter dem Gesichtspunkt des Zusammenspiels von Schreiben und Lesen erforderlich, beide Funktionen sind unter diesem Gesichtspunkt in keiner Weise wiederverwendbar und unsicher, was wichtig ist, sich daran zu erinnern.

Der Zähler verfügt jedoch über die MRMW-Eigenschaft, und ohne Synchronisierung können Sie einfach nicht mit dem Wort "vollständig" arbeiten (es sei denn, Ihr Ziel ist es natürlich, ein "plötzlich fehlerhaftes" Programm zu erstellen). Wenn wir die Tatsache berücksichtigen, dass wir ein Modul für die Arbeit mit Peripheriegeräten schreiben und dementsprechend das Schreiben oder Lesen von einem Interrupt aus aufgerufen werden kann, ist das Problem der Synchronisation unbedingt zu berücksichtigen. Interessanterweise erlaubt das Flag, das ähnliche Eigenschaften zu haben scheint, dennoch das Arbeiten ohne Synchronisationswerkzeuge (lustig, nicht wahr, aber es hat eine vollständig wissenschaftliche Erklärung - die Änderungsoperation wird atomar, und die Logik des Flags erlaubt und sogar Überschneidungen Datensätze), was durch das folgende Fragment des Programms veranschaulicht wird.

Bitte beachten Sie, dass ein solcher Ansatz (ein Flag ohne Synchronisationstools) nur möglich ist, wenn bestimmte Bedingungen erfüllt sind, die in Ihrem Fall sorgfältig geprüft werden sollten. Details finden sich in der Literatur, ich werde sie nicht geben, weil ich diese Methode zur Organisation des Puffers für nicht allzu gut halte, und ich zitiere sie nur, um zu zeigen, dass nicht die erfolgreichste Lösung ordentlich implementiert werden kann, und um ein anderes Konzept zu demonstrieren, das ich in Betracht ziehe sehr nützlich und an die ich mich halten möchte.

 typedef uint8_t data_t; static data_t BufferData[Max]; static counter_t BufferWriteCounter=0, BufferReadCounter=WriteCounter; static int8_t BufferHaveData = 0; void BufferWrite(const data_t Data) { if ((BufferWriteCounter == BufferReadCounter) && (BufferHaveDataFlag == 1)) {BufferOverflow();} else { BufferData[BufferWriteCounter] = Data; BufferHaveDataFlag = 1; BufferWriteCounter = NextCounter(BufferWriteCounter); }; }; inline int BufferIsEmpty(void) { return ((BufferReadCounter==BufferWriteCounter) && (BufferHaveDataFlag == 0));}; data_t BufferRead(void) { register counter_t Tmp; Tmp = BufferReadCounter; BufferReadCounter = NextCount(BufferReadCounter); if (BufferReadCount == BufferWriteCounter) { BufferHaveDataFlag = 1; }; return BufferData[Tmp]; }; 

Beachten Sie erneut, dass wir beim Schreiben zuerst das Flag setzen und dann den Index ändern und beim Lesen zuerst die Indizes überprüfen und dann das Flag steuern, was uns wiederum vor Problemen bewahrt und etwas mit dem Umgang mit Ressourcen gemeinsam hat, um das gegenseitige Blockieren zu beseitigen .

Im Allgemeinen sollte dieses Fragment im richtigen Stil umgeschrieben werden (mit Ausnahme der magischen Konstanten 0 und 1, wenn Sie denken, dass dies keine magischen Konstanten sind, dann irren Sie sich), und wenn Sie es verwenden, dann tun Sie es, ich verstecke das korrigierte Code im Spoiler, nicht weil es mir peinlich ist, aber um keine weitere Runde des Heiligen Krieges (bedeutungslos und gnadenlos), Hasser von Transfers, anzuregen, sollten Sie diesen Button nicht öffnen,


, , 0 1, . , , , 0 1. , , , , BufferFullFlag , BufferIsNotEmptyFlag . , KISS , , , , , « ».

Auf jeden Fall denke ich nicht, dass die Implementierung mit dem Flag gut ist. Ich empfehle daher dringend, sich mit dem Puffer abzustimmen, der nicht vollständig verwendet wird, und die Implementierung mit zwei Indizes und ohne zusätzliche Felder zu akzeptieren.

Eigentlich stellte sich ein unerwartet umfangreicher Beitrag für ein so einfaches Thema heraus, dass ich darüber nachdachte, mehr über Synchronisation und kritische Abschnitte zu schreiben, aber dies ist das nächste Mal.

PS Und abschließend, was genau hat mir in der genannten Bibliothek nicht gefallen, aber gleichzeitig haben die Autoren des inländischen RTOS dies ohne den geringsten Zweifel in ihren Code aufgenommen:

1. Es werden zwei Implementierungen des Puffers angegeben - eine für die Größe der Zweierpotenz (ich hoffe, ich habe gezeigt, dass dies völlig unnötig ist) und die zweite für die verbleibenden Fälle, aber Sie müssen die Version mit Stiften auswählen, natürlich machen sie keinen Fehler, es gibt überall Überprüfungen.
2. Es wurden völlig unnötige Methoden durchgeführt, wie das Löschen des letzten Elements oder der direkte Zugriff aus dem Pufferelement.
3. Der Datenpuffer ist auf eine Ganzzahl ausgerichtet.
4. Bei der Umsetzung von Grad 2 ein Fehler bei der Überprüfung der Belegungsrate.
5. Bei der Implementierung einer beliebigen Größe wird ein Zähler verwendet
6. Kritische Abschnitte sind überhaupt nicht organisiert, was in der richtigen Implementierung (mit zwei Indizes) einfach nicht benötigt wird, aber man kann nicht ohne sie auskommen, die Verwendung von atomaren Operationen ist eindeutig nicht ausreichend.
7. Einige Stil Nachlässigkeit, Art von Linien
   
   

    return ((_writeCount - Atomic::Fetch(&_readCount)) & (size_type)~(_mask)) != 0; 

   
   vor allem die zweite Hälfte - genau dafür wird C verantwortlich gemacht, und die Sprache selbst ist nicht schuld, sie erlaubt Ihnen nur, dies zu schreiben, anstatt die verständlicheren
   
   

    size_type(~(_mask)) 

   
   aber nicht zwingen, es zu tun.

PPS Ich hoffe, der Autor der Bibliothek erklärt sich damit einverstanden, diese Kritik als konstruktiv zu betrachten und entsprechende Korrekturen vorzunehmen.