Forum: PC-Programmierung Ring-Buffer interrupt safe


von Ing. ET (Gast)


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
1
#include <stdio.h>
2
#include <string.h>
3
 
4
#define BUFFER_SIZE 25
5
#define ERROR_CHAR -1
6
 
7
void buffer_char(char c);
8
char unbuffer_char(void);
9
 
10
//a buffer with BUFFER_SIZE slots
11
char circular_buffer[BUFFER_SIZE];
12
 
13
//integers to index circular_buffer
14
int start, end;
15
 
16
int main(int argc, char *argv[])
17
{
18
        char sentence[] = {"The quick brown dog jumps over the lazy fox."};
19
        int i;
20
 
21
        //add sentence into the buffer
22
        for (i = 0; i < strlen(sentence); i++) {
23
                buffer_char(sentence[i]);
24
        }
25
 
26
        //read the contents of the buffer excluding the last element
27
        while(start != end) {
28
                printf("%c", unbuffer_char());
29
        }
30
 
31
        printf("\n");
32
        return 0;
33
}
34
 
35
void buffer_char(char c)
36
{
37
        //Use modulo as a trick to wrap around the end of the buffer back to the beginning
38
        if ((end + 1) % BUFFER_SIZE != start) {
39
                circular_buffer[end] = c;
40
                end = (end + 1) % BUFFER_SIZE;
41
        }
42
        //otherwise, the buffer is full; don't do anything. you might want to
43
        //return an error code to notify the writing process that the buffer is full.
44
}
45
 
46
char unbuffer_char(void)
47
{
48
        if (end != start) {        
49
                char temp = circular_buffer[start];
50
                start = (start + 1) % BUFFER_SIZE;
51
                return(temp);
52
        }
53
        //otherwise, the buffer is empty; return an error code
54
        return ERROR_CHAR;
55
}


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
1
                char temp = circular_buffer[start];
2
                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

von (prx) A. K. (prx)


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

von Karl H. (kbuchegg)


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.

von Ing. ET (Gast)


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
1
 var & 0x1f
ersetzen

von (prx) A. K. (prx)


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.

von Karl H. (kbuchegg)


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.

von (prx) A. K. (prx)


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.

von Karl H. (kbuchegg)


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)

von Ing. ET (Gast)


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.
1
        if ((end + 1) % BUFFER_SIZE != start) {
2
                circular_buffer[end] = c;
3
                end = (end + 1) % BUFFER_SIZE;
4
        }

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

von Ing. ET (Gast)


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.

von Karl H. (kbuchegg)


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 :-)

von (prx) A. K. (prx)


Lesenswert?

Karl heinz Buchegger schrieb:

> Auch das probier ich gerne aus.

Race conditions auszuprobieren ist nicht so ganz einfach.

Bitte 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
Noch kein Account? Hier anmelden.