mikrocontroller.net

Forum: Projekte & Code Ringpuffer AVR


Autor: André (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Stefan Salewski (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zum Vergleich Ringbuffer in C:

Dateien ringbuffer.h und ringbuffer.c

http://www.ssalewski.de/USB-Sources/

Autor: Benedikt K. (benedikt) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: n1bble (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Á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.

Autor: Erwin Meyer (nobodyy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: OldMan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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:
/* Beispiel wie man einen Ringbuffer gestalten kann.

   Mittels MODULO Operator wird ein echtes Ringverhalten
  erzeugt.
  Der Überschreib-/Überleseschutz wird in den beiden Funktionen
  write_bu und read_bu realisiert.

*/


#include <stdio.h>
#include <string.h>
#define MAXB  10

unsigned char buffer[MAXB];

int ri=-1, wi=0;            /* Globale Variablen für den Puffer
                       Der Leseindex wird mit -1 vorbelegt, um ein Überlesen des
                       Schreibindex zu verhindern, wenn noch kein Schreiben statt gefunden
                       hat
                      */

int write_bu(unsigned char what)
{
  if ( ri == -1 )
      ri = 0;          /* Initiales Schreiben */

  if ( ((wi+1) % MAXB) != ri ) { /* Verhindert, dass der Schreibindex den Leseindex
                                    überholt*/

    buffer[wi++] = what;
    wi = wi % MAXB;
    return(1);          /* Element gespeichert*/
  } else
    return(0);          /* Voll, kein Platz mehr */
}
unsigned char read_bu(void)  {

  unsigned char result;

  result = 0;              /* 0 = nichts zu lesen = Puffer leer , Voreinstellung*/

  if ( ri < 0 )            /* ri == -1 bedeutet, dass noch keine initiales Schreiben
                      statt gefunden hat. Puffer ist leer */
    return(result);

  if ( ((ri+1) % MAXB) != wi ) {    /* Letzte Schreibposition darf nicht überschritten werden */
        result = buffer[ri++];  /* Element lesen*/
        ri = ri % MAXB;
  }
  return(result);
}



int main()
{

  char text[15]="ABCDEFGHIJKLNM";
  char c;
  int idx=0;

  for (; idx < 15; idx++ ){


    if (write_bu(text[idx]) == 0 )
        break;

  }
  while((c=read_bu()))
      printf("%c ", c);
  printf("\nri=%d wi=%d\n",ri,wi);
  puts("\nEND");
  getch();




}

Autor: Dispol (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
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.

Autor: Michael Reinelt (fisa)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: OldMan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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....

Autor: Erwin Meyer (nobodyy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
Autor: Erwin Meyer (nobodyy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Maxx (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
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.

Autor: Erwin Meyer (nobodyy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Dispol (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: Maxx (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: c-hater (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Erwin Meyer (nobodyy)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Maxx (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.