mikrocontroller.net

Forum: PC-Programmierung Ring-Buffer interrupt safe


Autor: Ing. ET (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich muss einen Puffer implementieren fuer eine UART.
Ein UART-Interrupt schreibt Zeichen in diesem Puffer.
Das Main-Programm liest.
Beim Lesen soll der UART RX Interrupt nicht disabled werden.

Angeblich gibt es solche Thread-safe Implementationen.
Wenn der Interrupt nur den Write-Index veraendert, das Main Programm nur 
den Read-Index veraendert, sollte nichts passieren.

Bei Wikipedia fand ich dieses Beispiel
#include <stdio.h>
#include <string.h>
 
#define BUFFER_SIZE 25
#define ERROR_CHAR -1
 
void buffer_char(char c);
char unbuffer_char(void);
 
//a buffer with BUFFER_SIZE slots
char circular_buffer[BUFFER_SIZE];
 
//integers to index circular_buffer
int start, end;
 
int main(int argc, char *argv[])
{
        char sentence[] = {"The quick brown dog jumps over the lazy fox."};
        int i;
 
        //add sentence into the buffer
        for (i = 0; i < strlen(sentence); i++) {
                buffer_char(sentence[i]);
        }
 
        //read the contents of the buffer excluding the last element
        while(start != end) {
                printf("%c", unbuffer_char());
        }
 
        printf("\n");
        return 0;
}
 
void buffer_char(char c)
{
        //Use modulo as a trick to wrap around the end of the buffer back to the beginning
        if ((end + 1) % BUFFER_SIZE != start) {
                circular_buffer[end] = c;
                end = (end + 1) % BUFFER_SIZE;
        }
        //otherwise, the buffer is full; don't do anything. you might want to
        //return an error code to notify the writing process that the buffer is full.
}
 
char unbuffer_char(void)
{
        if (end != start) {        
                char temp = circular_buffer[start];
                start = (start + 1) % BUFFER_SIZE;
                return(temp);
        }
        //otherwise, the buffer is empty; return an error code
        return ERROR_CHAR;
}


Es kann passieren, dass der unbuffer_char-code vom Interrupt 
unterbrochen wird und den buffer_char(char c) - code ausfuehrt.

z.B. zwischen den Zeilen
                char temp = circular_buffer[start];
                start = (start + 1) % BUFFER_SIZE;

Aber es sollte nichts passieren, da immer ein Slot frei bleibt.
(Puffer ist voll, wenn  BUFFER_SIZE-1 Slots belegt)

Kann mir jemand meine Vermutung bestaetigen oder mich korrigieren?
Danke und Gruss,
  Johannes

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Unabhängig von der Fragestellung kann ich von einer "% 25" Operation nur 
abraten. Divisionen sind auch auf PCs nicht sonderlich billig, wenn der 
Teiler keine Zweierpotenz ist. Also statt
  if (((i + 1) % 25) != k) ...
besser
  temp = i + 1;
  if (temp == 25) temp = 0;
  if (temp != k) ...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ing. ET schrieb:

> da immer ein Slot frei bleibt.

Die Vermutung kann ich nicht bestätigen.


                circular_buffer[end] = c;
end ist offenbar der Index in buffer an dem das nächste Zeichen abgelegt 
werden kann. Genauso wie start der Index des nächsten Zeichens ist, 
welches abgeholt werden kann.

Damit sorgt aber die vorhergehende Abfrage nicht dafür, dass immer ein 
Slot frei bleibt, sondern nur dass du den Buffer überfüllst, nämlich 
genau dann wenn nach der buffer_char Aktion end gleich start sein würde 
und damit das erste Überschreiben stattgefunden hätte.


Warum schreibst du dir nicht ein Testprogramm mit zusätzlichen Ausgaben 
dieser Indizes, so dass du deine Vermutungen ausprobieren kannst.

Autor: Ing. ET (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Unabhängig von der Fragestellung kann ich von einer "% 25" Operation nur

Klar, ich werde z.B. BUFFER_SIZE = 32 waehlen
und  var % BUFFER_SIZE mit
 var & 0x1f
ersetzen

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man muss darauf achten, dass die Indexvariablen atomar 
geladen/gespeichert werden, was bei "int" auf 8-Bit Prozessoren nicht 
der Fall ist. Solange die Werte im Bereich 0..255 bleiben ist das noch 
kein Problem, aber darüber hinaus funktioniert das Verfahren nicht mehr.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Beim Lesen soll der UART RX Interrupt nicht disabled werden.

Warum eigentlich nicht?
Der Interrupt geht ja nicht verloren. Er muss nur ein kleines bischen 
länger warten, bis er dann bearbeitet wird. Es ist auch davon 
auszugehen, dass in der kurzen Zeit, die es dauert den buffer 
auszulesen, auf der UART keine weiteren Zeichen vollständig empfangen 
werden können. Dazu reicht die Zeit einfach nicht. d.h. man läuft auch 
nicht Gefahr dass man etwas auf der UART verpasst.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:

>> da immer ein Slot frei bleibt.
>
> Die Vermutung kann ich nicht bestätigen.

Ich denke schon. Der Zustand start==end tritt nur auf, wenn der Puffer 
leer ist, buffer_char() hört vorher mit der Befüllung auf. Der Platz 
circular_buffer[(end+1)%BUFFER_SIZE] bleibt stets leer.

Unter der erwähnten Voraussetzung atomarer Lade- und Speicheroperationen 
für "start" und "end" sehe ich in diesem (Standard-)Verfahren keine race 
conditions.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Karl heinz Buchegger schrieb:
>
>>> da immer ein Slot frei bleibt.
>>
>> Die Vermutung kann ich nicht bestätigen.
>
> Ich denke schon. Der Zustand start==end tritt nur auf, wenn der Puffer
> leer ist, buffer_char() hört vorher mit der Befüllung auf.

Nochmal scharf darüber nachgedacht.


       if ((end + 1) % BUFFER_SIZE != start) {

wenn nach der Operation end identisch mit start werden würde, dann wird

                circular_buffer[end] = c;

nicht mehr ausgeführt.


Richtig. Der letzte Eintrag bleibt leer.

(Drum probier ich solche Sachen lieber aus. Da verknotet das Gehirn 
weniger)

Autor: Ing. ET (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Damit sorgt aber die vorhergehende Abfrage nicht dafür, dass immer ein
>Slot frei bleibt, sondern nur dass du den Buffer überfüllst, nämlich
>genau dann wenn nach der buffer_char Aktion end gleich start sein würde
>und damit das erste Überschreiben stattgefunden hätte.

Kann ich nicht nachvollziehen.
        if ((end + 1) % BUFFER_SIZE != start) {
                circular_buffer[end] = c;
                end = (end + 1) % BUFFER_SIZE;
        }

Die Abfrage verhindert, dass nach einer Schreibaktion die beiden indices 
gleich sein koennten.
Wenn man alle Slots des Puffers voll macht, dann haetten die beiden 
Indices den gleichen Wert und der Puffer waere NICHT ueberfuellt.
Aber man koennte nicht mehr unterscheiden, ob es sich um einen 1. leeren 
Puffer handelt oder 2. einen randvollen.
Durch das Freilassen eines Slots verhindert man Fall 2.

Genauer erklaert in
http://en.wikipedia.org/wiki/Circular_buffer

Autor: Ing. ET (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>(Drum probier ich solche Sachen lieber aus. Da verknotet das Gehirn
>weniger)

Mach ich auch. Aber die Ausgabe-Ergebnisse helfen hier nicht weiter.
Es geht darum, an welchen Stellen der Code unterbrochen werden kann, und 
was dann schlimmstenfalls passiert.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ing. ET schrieb:
>>(Drum probier ich solche Sachen lieber aus. Da verknotet das Gehirn
>>weniger)
>
> Mach ich auch. Aber die Ausgabe-Ergebnisse helfen hier nicht weiter.
> Es geht darum, an welchen Stellen der Code unterbrochen werden kann, und
> was dann schlimmstenfalls passiert.

Auch das probier ich gerne aus.

In jede Funktion am Anfang Debug Ausgaben der Indizes. Genauso wie am 
Ende vor dem Return.

Und dann hindert einen ja nichts daran, in der unbuffer_char Funktion 
testweise einen buffer_char Aufruf einzubauen und den zwischen den 
Anweisungen rumzuschieben :-)

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:

> Auch das probier ich gerne aus.

Race conditions auszuprobieren ist nicht so ganz einfach.

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.