Ringpuffer AVR

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.

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.

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....

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.

>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...

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?