Hallo, ich habe eine kleine Routine für einen Ringpuffer "gebastelt". Source und Erläuterungen dazu im Anhang. Funktioniert zumindest im Simulator. Würde mich freuen wenn der ein oder andere mal drüberschaun könnte, zwecks Vorschläge zur Verbesserung bzw. Fehlerbeseitigung. Würde am Schluss das File entsprechend ändern, und nochmal hier einstellen, da haben alle was davon.
Zum Vergleich Ringbuffer in C: Dateien ringbuffer.h und ringbuffer.c http://www.ssalewski.de/USB-Sources/
@Ándre Dieser funktioniert nicht, wenn der Buffer eine 256er Grenze überschreitet. @Stefan Salewski Keine Gnade für langsame leser, und somit kein Überlaufschutz. @Benedikt Sehr kompakt, aber Register, die verändert werden sollten doch mit push/und pop gesichert und zurückgesetzt werden.
Bei diesen Ringpuffern fehlt mir etwas wichtiges: Die Initialisierung der Pointer/Indizes mit -1 (oder einem anderen negativen Wert), damit man einen leeren Ringpuffer erkennen kann und den Sonderfall korrekt behandeln kann. Das ist wichtig wenn z. B. beim Einfügen des ersten Elements etwas getriggert werden soll und insbesondere wenn man mal im Ringpuffer zurückgehen muss, z. B. um Daten anzuhängen oder Upzudaten. So habe ich das im Informatik-Studium gelernt und das benötige ich auch häufiger.
Erwin Meyer schrieb: > Bei diesen Ringpuffern fehlt mir etwas wichtiges: Die Initialisierung > der Pointer/Indizes mit -1 (oder einem anderen negativen Wert), damit > man einen leeren Ringpuffer erkennen kann und den Sonderfall korrekt > behandeln kann. Ich nehme an, dass Du so etwas meinst. Dieses Konzept setze ich schon seit Jahren erfolgreich ein:
1 | /* Beispiel wie man einen Ringbuffer gestalten kann.
|
2 | |
3 | Mittels MODULO Operator wird ein echtes Ringverhalten
|
4 | erzeugt.
|
5 | Der Überschreib-/Überleseschutz wird in den beiden Funktionen
|
6 | write_bu und read_bu realisiert.
|
7 | |
8 | */
|
9 | |
10 | |
11 | #include <stdio.h> |
12 | #include <string.h> |
13 | #define MAXB 10
|
14 | |
15 | unsigned char buffer[MAXB]; |
16 | |
17 | int ri=-1, wi=0; /* Globale Variablen für den Puffer |
18 | Der Leseindex wird mit -1 vorbelegt, um ein Überlesen des
|
19 | Schreibindex zu verhindern, wenn noch kein Schreiben statt gefunden
|
20 | hat
|
21 | */
|
22 | |
23 | int write_bu(unsigned char what) |
24 | {
|
25 | if ( ri == -1 ) |
26 | ri = 0; /* Initiales Schreiben */ |
27 | |
28 | if ( ((wi+1) % MAXB) != ri ) { /* Verhindert, dass der Schreibindex den Leseindex |
29 | überholt*/
|
30 | |
31 | buffer[wi++] = what; |
32 | wi = wi % MAXB; |
33 | return(1); /* Element gespeichert*/ |
34 | } else |
35 | return(0); /* Voll, kein Platz mehr */ |
36 | }
|
37 | unsigned char read_bu(void) { |
38 | |
39 | unsigned char result; |
40 | |
41 | result = 0; /* 0 = nichts zu lesen = Puffer leer , Voreinstellung*/ |
42 | |
43 | if ( ri < 0 ) /* ri == -1 bedeutet, dass noch keine initiales Schreiben |
44 | statt gefunden hat. Puffer ist leer */
|
45 | return(result); |
46 | |
47 | if ( ((ri+1) % MAXB) != wi ) { /* Letzte Schreibposition darf nicht überschritten werden */ |
48 | result = buffer[ri++]; /* Element lesen*/ |
49 | ri = ri % MAXB; |
50 | }
|
51 | return(result); |
52 | }
|
53 | |
54 | |
55 | |
56 | int main() |
57 | {
|
58 | |
59 | char text[15]="ABCDEFGHIJKLNM"; |
60 | char c; |
61 | int idx=0; |
62 | |
63 | for (; idx < 15; idx++ ){ |
64 | |
65 | |
66 | if (write_bu(text[idx]) == 0 ) |
67 | break; |
68 | |
69 | }
|
70 | while((c=read_bu())) |
71 | printf("%c ", c); |
72 | printf("\nri=%d wi=%d\n",ri,wi); |
73 | puts("\nEND"); |
74 | getch(); |
75 | |
76 | |
77 | |
78 | |
79 | }
|
Der Thread ist zwar schon uralt, da aber auch eine entsprechende Änderung im Wiki vorgenommen wurde, möchte ich das doch noch mal verstanden haben. Warum -1? Bei einem leeren Puffer ist W=R. Ein voller mit W=R gibt es nicht, denn es wird ja vor jedem Schreiben geprüft, ob beim nächsten Schritt W R eingeholt hätte. Wenn ja, wird W gar nicht erhöht. Also gibt es nur den Fall: W=R=Puffer leer. Und warum soll es eine Unterscheidung geben zwischen einem Puffer, der noch nie befüllt war, und einem Puffer, der beschrieben war und jetzt wieder leer ist? Leer ist doch leer.
Dispol schrieb: > Warum -1? Vermutlich deshalb: Erwin Meyer schrieb: > Das ist wichtig wenn z. B. beim Einfügen des ersten Elements etwas > getriggert werden soll und insbesondere wenn man mal im Ringpuffer > zurückgehen muss, z. B. um Daten anzuhängen oder Upzudaten. Wobei: ich hab das am AVR auch noch nie gebraucht. Ringpuffer dauernd bei UART, und da kommt man locker ohne das -1 aus. Wobei -1 oft eine ganz schlechte Entscheidung ist, wenn man den ringbuffer gerne 256 byte groß hätte. Dann müsste man den Datentyp ändern...
Erwin Meyer schrieb: > und insbesondere wenn man mal im Ringpuffer > zurückgehen muss, Seit wann geht man in einem Ringpuffer zurück? Wenn man so etwas braucht, dann setzt man B-Tree Funktionen ein und keinen Ringpuffer! Dispol schrieb: > Und warum soll es eine Unterscheidung geben zwischen einem Puffer, der > noch nie befüllt war, und einem Puffer, der beschrieben war und jetzt > wieder leer ist? Leer ist doch leer. Es geht um die Schreib- und Leseindexe wenn man mit Modulo arbeitet. Erst wenn der Schreibindex nicht mehr initial ist, dann ist alles egal. Aber solange noch beide Index inital auf 0 stehen, darf nicht gelesen wenn. Sonst ist der Ring kein Ring mehr, da der Leseindex dann VOR dem Schreibindex stehen würde....
Dispol schrieb: > Der Thread ist zwar schon uralt, da aber auch eine entsprechende > Änderung im Wiki vorgenommen wurde, möchte ich das doch noch mal > verstanden haben. > > Warum -1? Ganz einfach: Man geht zum nächsten Element im Ringpuffer durch Inkrementieren (Modulo N). Das bedeutet beim leeren Ringpuffer geht man zum Index 0 (und fügt die ersten Daten dort ein) und folglich sollte man den Index mit -1 Initialisieren. > Bei einem leeren Puffer ist W=R. Ein voller mit W=R gibt es nicht, denn > es wird ja vor jedem Schreiben geprüft, ob beim nächsten Schritt W R > eingeholt hätte. Wenn ja, wird W gar nicht erhöht. Das betrifft einen speziellen Ringpuffer und nur single-threaded Programme. Ich verwende Ringpuffer aber meist zum Datenaustausch zwischen Threads und da verwendet der Schreib-Thread einen lokalen Index, der nach/vor dem Einfügen neuer Daten den Wert für die nächsten Daten hat. Dazu gibt es einen globalen Index, der angibt wo die letzten neue Daten hingeschrieben wurden und der erst nach dem Schreiben upgedatet wird damit man keinen Lock benötigt, wenn nur ein Thread in den Ringpuffer schreibt. Es gibt also zwei Schreib-Indizes, W0 und W1 und der Schreib-Thread verwendet keinen Lese-Index. Die Lese-Threads verwenden dagegen keinenn Schreib-Index und nur Lese-Indizes: Einer für die Stelle von der zuletzt gelesen wurde und einen bis zu dem die neuen Daten auszulesen sind. Daneben gibt es noch weitere, denn es gibt ja auch den Fall das die Daten noch nicht komplett sind und dann muss man mit dem letzten Index zurück gehen - oder eben auch nicht wenn man zuvor noch am Anfang (Index = -1) war. Das macht in Summe also 5 Indizes schon bei nur einem schreibenden und nur einem lesenden Thread und dabei sind noch nicht alle genannt, denn um Anomalien zu verhindern dürfen die Lese-Threads den Index W1 nicht direkt verwenden, denn der könnte ja während des Auslesens Inkrementiert werden, so dass das Auslesen an falschen Indizes erfolgt und Daten ausgelassen werden, so das vor dem Auslesen der Wert erstmal gecacht werden muss. > Und warum soll es eine Unterscheidung geben zwischen einem Puffer, der > noch nie befüllt war, und einem Puffer, der beschrieben war und jetzt > wieder leer ist? Leer ist doch leer. Nein, ein Ringpuffer wird ja nur gefüllt aber nicht geleert. Wird das Ende erreicht, werden als Nächstes die Daten bei Index 0 überschrieben.
:
Bearbeitet durch User
OldMan schrieb: > Erwin Meyer schrieb: >> und insbesondere wenn man mal im Ringpuffer >> zurückgehen muss, > > Seit wann geht man in einem Ringpuffer zurück? Beispielsweise um nachzusehen wann die vorherigen Daten eintrafen. Damit lässt sich bestimmen ob die neuen Daten damit zusammen gehören, also zwei Teile eines Datenpakets sind, oder nicht. Dafür packe ich natürlich Strukturen in den Ringpuffer. > Wenn man so etwas braucht, dann setzt man B-Tree Funktionen ein und > keinen > Ringpuffer! Nein, sowas wie Bäume nimmt man für Dateisysteme, nicht für nacheinander eintreffende Daten.
Erwin Meyer schrieb: > Damit lässt sich bestimmen ob die neuen Daten damit zusammen gehören, > also zwei Teile eines Datenpakets sind, oder nicht. Damit wird die Trennung von Datenstrukturen wieder aufgehoben. Also genau das was man eigentlich nicht will. Wenn dein Schreiber entscheiden kann, wann der Elementtyp vollständig ist, dann kann er es als Datentyp genau dann hinzufügen, wenn es vollständig ist. Das ist dann exakt ein Element im Ringbuffer und eine Bufferoperation. Wenn der Reader entscheiden kann, dann entnimmt er die Daten genau dann, wenn sie vollständig sind. Denn Lesen kann er ohne zu entfernen bereits um das zu prüfen. Wenn beide entscheiden müssen hast du im Design etwas falsch gemacht und doppelte Arbeit erzeugt. Damit brauchts dann 1 ptr zum Schreiben und je einen pro Leser. Das ist ein Ringbuffer. Keine Mischstrukturen mit dann multiplizierte Zustandsraum. Der ist irgendwann nicht mehr wartbar weil abhängig vom Elementtyp.
Maxx schrieb: > Wenn dein Schreiber entscheiden kann, wann der Elementtyp vollständig > ist, dann kann er es als Datentyp genau dann hinzufügen, wenn es > vollständig ist. Im Prinzip wäre das möglich, nur braucht der Reader auch die Information ob möglicherweise unvollständige Daten gelesen wurden, allein schon um die Daten von mehreren Schnittstellen in der richtigen zeitlichen Reihenfolge zu verarbeiten. Beispielsweise bekommt man die Daten von einer parallelen Schnittstelle per Polling praktisch sofort, ein simples Register-Auslesen; bei einem UART hingeben werden Datenpakete häufig zerstückelt ausgegeben, so das innerhalb von x Millisekunden noch ein Rest kommen kann. Man sieht das wenn man die seriellen Daten mit der Select-Funktion einliest, das aus einem Datenpaket, das auch mit dem Oszilloskop betrachtet kompakt ist, von Select in mehreren Stücken kommt.
>Erst wenn der Schreibindex nicht mehr initial ist, dann ist alles egal. >Aber solange noch beide Index inital auf 0 stehen, darf nicht gelesen >wenn. >Sonst ist der Ring kein Ring mehr, da der Leseindex dann VOR dem >Schreibindex stehen würde.... Aber dass beide gleich stehen, (ob jetzt bei 0 oder sonstwo) ist doch ein ganz normaler Fall. Dann, wenn er "leer" ist. Wenn ich 1 Zeichen rein schreibe und das lese, stehen beide auf 1. Dann darf ich auch nichts lesen.
Erwin Meyer schrieb: > Beispielsweise bekommt man die Daten von einer parallelen Schnittstelle > per Polling praktisch sofort, ein simples Register-Auslesen; bei einem > UART hingeben werden Datenpakete häufig zerstückelt ausgegeben, so das > innerhalb von x Millisekunden noch ein Rest kommen kann. Dann ist die Lösung A: Ein Ringbuffer von Frames. Diese Frames werden genau dann hinzugefügt, wenn der Schreiber sie vollständig kennt. Braucht er dafür einen weiteren Speicherort, so ist der anzulegen (z.B. in Form von Lösung B, wobei Leser und Schreiber zwei Rollen des gleichen Thread sein können) Die Lösung B: Ein Ringbuffer des primitiven Datentyps (char?) die primitiven Daten werden exakt dann geschrieben, wenn sie herein kommen. Allein der Reader interpertiert die Daten und entnimmt sie. Er ist mit dem Interpretieren genau dann fertig wenn die Daten vollständig und durch ihn verarbeitet sind. Der Schreiber nutzt keine a-prioi Information aus der Interpretation. > Man sieht das > wenn man die seriellen Daten mit der Select-Funktion einliest, das aus > einem Datenpaket, das auch mit dem Oszilloskop betrachtet kompakt ist, > von Select in mehreren Stücken kommt. Das hat nichts mit dem Ringbuffer zu tun! Das ist eine Interpretation, die vor oder nach dem Ringbuffer erfolgen kann. Den Ringbuffer jedoch für die Interpretation und gleichzeitig für die inter-thread-Kommuniktaion zu nutzen halte ich für keine gute Idee. Ein solcher Ringuffer ist ein FIFO mit einer bestimmten Struktur. (Nicht mehr und nicht weniger) Die Aufbereitung der Daten vor und/oder nach dem Buffer ist der restlichen Programmlogik überlassen. Von der Vermischung beider Aufgaben rate ich dringend ab.
Erwin Meyer schrieb: > Bei diesen Ringpuffern fehlt mir etwas wichtiges: Die Initialisierung > der Pointer/Indizes mit -1 (oder einem anderen negativen Wert), damit > man einen leeren Ringpuffer erkennen kann und den Sonderfall korrekt > behandeln kann. Das ist doch Unsinn. Natürlich gibt es bei einem Ringpuffer eine gewisse Dualität der Situation Schreibzeiger=Lesezeiger. Das kann sowohl bedeuten: "komplett voll" als auch "leer". Läßt man beide Situationen zu, benötigt man entweder spezielle Werte für die Zeiger oder aber ein zusätzliches Bit an anderer Stelle, um die beiden Situationen unterscheiden zu können. Bei genauerer Betrachtung kommt aber nur ein völlig unfähiger Programmierer auf die Idee, das so zu machen. Denn der klitzekleine Vorteil, den Ringpuffer bis zum allerletzten (statt nur bis zum vorletzten) Element füllen zu können, wird durch einen Riesenhaufen Mehraufwand an Rechenzeit wegen der komplizierteren Verwaltung erkauft, das gilt insbesondere bei Multithreading. Deine Anwendung, soweit ich deren Struktur aus deiner Beschreibung rekonstruieren konnte, hätte ein fähiger Programmierer aber natürlich sowieso als Buffer-Pool mit zusätzlichem Ringpuffer zur Verwaltung von Verweisen in den Buffer-Pool realisiert. Das hätte den Sync-Aufwand minimiert und der Speicher-Mehrverbrauch durch den zusätzlichen Ringpuffer von (GesamtzahlDatenpuffer+3)*Sizeof(pointer) wäre garantiert geringer als der Speicherverbrauch durch die aufwendigere Synchronisation, von der riesigen Einsparung an Rechenzeit und Codegröße wollen wir erst garnicht reden...
c-hater schrieb: > ... Das hätte den Sync-Aufwand > minimiert und der Speicher-Mehrverbrauch durch den zusätzlichen > Ringpuffer von (GesamtzahlDatenpuffer+3)*Sizeof(pointer) wäre garantiert > geringer als der Speicherverbrauch durch die aufwendigere > Synchronisation, von der riesigen Einsparung an Rechenzeit und Codegröße > wollen wir erst garnicht reden... Nein, hier wird eben KEIN Sync verwendet. Ein Thread schreibt in den Ringpuffer und danach wird der Zähler mit den neuesten Daten inkrementiert (modulo n). Was andere Threads damit machen ist dem Schreiber egal; der kümmert sich nur um das Einlesen. Und die Leser prüfen nur ob ihr Zähler gleich dem vom Schreiber (Schreibe-Zähler) ist, denn daran erkennen sie ob neue Daten eingetroffen sind, woraufhin sie die Daten einlesen und ihren Zähler (Lese-Zähler) inkrementieren (modulo n). Dabei gibt es keinen großen Speicherverbrauch sondern im Gegenteil sehr geringen. Nach der ersten Runde ist der Ringpuffer gefüllt und danach werden die jeweils ältesten überschrieben. Einfacher geht es doch nicht.
Erwin Meyer schrieb: > Ein Thread schreibt in den Ringpuffer und danach wird der Zähler mit den > neuesten Daten inkrementiert (modulo n). Aber genau hier versteckt du die Synchronisation. Ohne geht es definitiv nicht aber sehr simpel. Sie steckt in der atomizität gegenüber des Lesers genau einen Wert von einem Schreiber an genau einem deterministischen Ortes einzufügen ... Eingangswerte prüfen, Ausgangswert setzen. Dabei hat der Ringbuffer einen Vorteil: Die Prüfung und das Setzen ist recht einfach, da man nur begrenzte Änderungen zulässt. Hebt man die Beschränkung auf. ( Mehrere Inkremente pro Schreibzugriff) so wird der Synchronisation schon wieder größer. (nur der Modulo reicht nicht mehr. Du musst zusätzlich obere Grenzen prüfen, liegt mehr als ein Wrapping innerhalb der Einfügemenge?) damit machst du dir die Simplizität völlig ohne Not wieder kaputt. Bzw baust dir Deadlocks oder Fehlersituationen ein, die unnötig sind. Was passiert denn, wenn du ein Frame größer als den Ringbuffer einfügen willst? Kannst du recovern? Wenn ja wo hast du das implementiert? Beim Aufrufer? Per Definition?
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.