Wiki-Artikel: FIFO verschenkt einen Eintrag

[emp (Gast)]

Moin,
mir ist aufgefallen, dass beim FIFO im Wiki ( 
http://www.mikrocontroller.net/articles/FIFO ) ein Eintrag verschenkt 
wird.

Der Schreibzeiger zeigt auf den Eintrag, auf den als nächstes 
geschrieben wird. Der Eintrag, auf den der Schreibzeiger ist leer. Der 
Vergleich sieht so aus, dass der FIFO als voll gilt, wenn der 
Schreibzeiger +1 gleich dem Lesezeiger ist. Es könnte aber eben noch 
weiter geschrieben werden, bis der Schreibzeiger == Lesezeiger. Dies 
bringt natürlich wieder ein Problem, da der Vergleich Schreibzeiger == 
Lesezeiger genutzt wird, um zu erkennen, wann der FIFO leer ist.

Bei einem FIFO über ein Char-Array ist dies zu verschmerzen, denn jede 
weitere Variable, welche zusätzlich genutzt werden müsste, um FIFO voll 
bzw. FIFO leer zu markieren, kostet auch wieder 1 Byte Speicher. 
Zusätzlich ist der FIFO sehr gut für Producer/Consumer Systeme geeignet. 
Jede Seite schreibt nur eine Variable, dadurch werden keine Mutexe 
benötigt.

Nun benötige ich jedoch einen FIFO in dem ein ganzes Struct gespeichert 
werden kann. Gibt es eine Möglichkeit fest zu stellen, ob ein FIFO ganz 
voll bzw. leer ist (von mir aus mit zusätzlicher Variable) und dabei die 
Eigenschaft zu erhalten, dass der FIFO ohne Mutexe benutzt werden kann?

Konkret benötige ich ihn, um CAN-Nachricht per ISR in den FIFO zu 
speichern und von der Hauptschleife aus zu verarbeiten.

Grüße emp

[Karl H. (kbuchegg)]

> Bei einem FIFO über ein Char-Array ist dies zu verschmerzen

Es ist auch sonst in den meisten Fällen zu verschmerzen. Denn wenn du 
den FIFO wirklich randvoll voll werden lässt, hast du meist weitere 
Probleme. Ein FIFO in der gezeigten Form soll ungleichmässiges 
Eintreffen von Nachrichten auffangen und die zwischenspeichern bis sie 
abgearbeitet werden können. Wenn dabei der FIFO regelmässig bis zum Rand 
voll wird, ist dein Speichermanagement sowieso zu knapp ausgelegt.

Soll heissen: einen derartigen Zwischenspeicher dimensionierst du 
sowieso immer etwas zu groß.

[Matthias L. (Gast)]

Beitrag "Re: ATMEGA32 USART sendet ein Zeichen zuviel"

[Genervt (Gast)]

emp schrieb:
> Nun benötige ich jedoch einen FIFO in dem ein ganzes Struct gespeichert
> werden kann.

Dann speichere nur die Adresse oder den Index eines arrays in dem Fifo.
Ansonsten gebe ich Karl Heinz recht, wenn der Fifo so voll wird dann 
hast du spätestens dann ein Problem, wenn noch eine Nachricht rein soll 
bevor es wieder Platz gibt.

[Peter D. (peda)]

emp schrieb:
> Konkret benötige ich ihn, um CAN-Nachricht per ISR in den FIFO zu
> speichern und von der Hauptschleife aus zu verarbeiten.

Dann leg einfach ein Array von Structs an. Und jede Struct kann als leer 
oder gültig markiert werden.
Z.B. ein Längenbyte von 255 kennzeichnet die Struct als frei, da nur 
Längen von 0-8 gültig sind.


Peter

[emp (Gast)]

Karl Heinz Buchegger schrieb:
> Soll heissen: einen derartigen Zwischenspeicher dimensionierst du
> sowieso immer etwas zu groß.

Das ist klar, aber wenn ich meinen FIFO mit X Feldern mehr kalkulier und 
dann immer noch eins mehr zugeben muss, ist das auch am Sinn vorbei.

Matthias Lipinsky schrieb:
> Beitrag "Re: ATMEGA32 USART sendet ein Zeichen zuviel"

Klingt gut, ist mir in ner ISR aber zu viel Aufwand.

Peter Dannegger schrieb:
> emp schrieb:
> Z.B. ein Längenbyte von 255 kennzeichnet die Struct als frei, da nur
> Längen von 0-8 gültig sind.

Genau dies versaut leider, dass der FIFO ohne Mutex Threadsicher ist.

[Peter D. (peda)]

emp schrieb:
> Genau dies versaut leider, dass der FIFO ohne Mutex Threadsicher ist.

Warum?

Du mußt doch nur das Längenbyte nach dem Lesen auf 255 setzen und das 
ist atomar.


Peter