FIFO

Ein FIFO (First-In-First-Out) ist ein Pufferspeicher nach dem "Warteschlangen-Prinzip". Pufferspeicher dienen dazu, für einen Prozessor Daten aufzufangen, die er noch nicht verarbeiten kann. Ein FIFO funktioniert definitionsgemäß so, dass das erste Element (First In), welches "hinten" in die Warteschlange eingefügt wird, später auch als erstes "vorne" herausgeholt wird (First Out).

Das Gegenstück zu FIFO ist LIFO, worunter man einen dem "Stapel-Prinzip" folgenden Pufferspeicher versteht (Last In - First Out; Elemente werden stets "oben auf den Stapel" gelegt und auch stets von oben wieder heruntergenommen).

Ein bekanntes Beispiel für einen FIFO-Speicher ist der des UARTs im PC. Dieser sammelt ankommende Daten solange, bis er fast voll ist (meist 14 Bytes). Dann wird ein Interrupt ausgelöst und der Prozessor kann "auf einen Rutsch" alle Daten auf einmal auslesen. Ganz am Anfang hatten UARTs keinen FIFO und erzeugten für jedes empfangene Byte einen Interrupt, so wie es heute noch die meisten Mikrocontroller machen. Damit ist aber die CPU-Belastung wesentlich höher, was bei höheren Datenraten zu Problemen führen kann.

Die Umsetzung eines FIFOs in Software heißt Ringpuffer und weist auch eine feste Puffergröße auf. Wesentlicher Vorteil gegenüber der verketteten Liste ist die schnellere Ausführungszeit und der geringere Aufwand.

Standard-Ringpuffer

Vorteile:

• Simpel
• Leicht verständlich

Nachteile:

• Schell aber nicht optimal
• Daten können auch vom Typ struct sein

Beschreibung

Die Inhalte des Puffers werden in einem schlichten Array gespeichert und der Zugriff erfolgt über einen Integer-Index. Erreicht ein Index die Obergrenze springt dieser auf Null zurück. Ein größer-gleich statt nur eines ist-gleich Vergleichs ist sicherer gegenüber Programmfehlern, bei denen der Index verstellt wurde. <c> write = write + 1; if (write >= BUFFER_SIZE)

 write = 0;

</c> Haben Lese- und Schreib-Index den gleichen Wert wird der Puffer als leer angesehen. Wenn write+1 und read identisch sind wird der Puffer als voll angesehen. Nun fehlt noch der Sonderfall bei dem read gleich Null ist, hier funktioniert der write+1-Vergleich nicht mehr und die Abfrage einer zusätzlichen Bedingung ist zur voll-Abfrage erforderlich.

<c> read == write => leer

write + 1 == read || read == 0 && write+1 == BUFFER_SIZE => voll </c>

Bei konkurrentem Zugriff, zwischen UART-ISR und Hauptprogramm, muss ausgeschlossen werden, das das Hauptprogramm beim Lesen aus dem Puffer nicht durch den Interrupt unterbrochen werden kann. Ansonsten können Programmabstürze passieren, deren Ursache oft nicht nachvollziehbar ist. Als Abhilfe dienen Atomare Abschnitte, solche können durch keinen Interrupt unterbrochen werden. Die Radialkur deaktiviert alle Interrupte besser ist die Deaktivierung eines einzelnen Interrupts. Im Allgemeinen werden versäumte Interrupte nach erneuter Aktivierung nachgeholt, da ein Flag gesetzt wurde. Wichtig ist vorallem das die Ausführungszeit des Atomaren Abschnitts und der ISR geringer ist als der Intervall in dem Interrupte erfolgen, da ansonsten einer verloren gehen könnte.

<c> cli() ret = BufferOut(&var); sei() </c>

Code-Beispiel

<c>

1. define BUFFER_SIZE 23

struct Buffer {

 uint8_t data[BUFFER_SIZE];
 uint8_t read; // zeigt auf das Feld mit dem ältesten Inhalt
 uint8_t write; // zeigt immer auf leeres Feld

} buffer = {{}, 0, 0};

uint8_t BufferIn(uint8_t byte) {

 //if (write >= BUFFER_SIZE)
 //  write = 0; // erhöht sicherheit

 if (buffer.write + 1 == buffer.read || buffer.read == 0 && buffer.write + 1 == BUFFER_SIZE)
   return FAIL; // voll

 buffer.data[buffer.write] = byte;

 write = write + 1;
 if (write >= BUFFER_SIZE)
   write = 0;

}

uint8_t BufferOut(uint8_t *pByte) {

 if (buffer.read == buffer.write)
   return FAIL;
 *pByte = buffer.data[buffer.read];

 buffer.read = buffer.read + 1;
 if (buffer.read >= BUFFER_SIZE)
   buffer.read = 0;
 return SUCCESS;

} </c>

2ⁿ-Ringpuffer - die schnellste Lösung

Vorteile:

• Durch Bitmaske auf den Feld-Index write kann der nicht "Amoklaufen" und beliebige Inhalte im Speicher überschreiben
• Sehr einfach, sehr schnell
• Daten können auch vom Typ struct sein

Nachteile:

• Nur Größenfaktoren von 2ⁿ möglich
• Nur in speziellen Fällen Pointerreferenz möglich

Beschreibung

Wenn der Index am oberen Ende angekommen ist springt er an den Anfang zurück. Die Definition der Obergrenze wird nicht durch einen Vergleich realisiert, sondern durch Modulo-Arithmetik. Dies kann sehr einfach und schnell durch Maskieren des Index-Werts umgesetzt werden.

Beispiel: <c> ( write + 1 ) & MASK

15 = 0b00001111 15 + 1 = 16 = 0b000010000 16 & MASK = 0b000010000 & 0b000001111 = 0b000000000 </c>

Daraus folgt das write nur einen Wert zwischen 0 und 15 einnehmen kann. Das ganze funktioniert nur mit Zahlen der Reihe 2ⁿ.

Da der Puffer nur eine endliche Größe aufweist, muss eine voll/leer Indikation verfügbar sein. read == write bedeutet Puffer leer, entsprechend bedeutet write + 1 == read, dass keine weiteren Elemente mehr hinzugefügt werden können, denn sonst würde das Hinzufügen weiterer Daten einen Pufferüberlauf hervorrufen. Für die Behandlung des Pufferüberlaufs gibt es zwei Methoden, nichts tun und Fehler zurück geben oder ältesten Puffer-Inhalt verwerfen (read+1).

<c> read == ((write + 1) & MASK) </c>

Auch hier verhindert die Bitmaske einen möglichen Überlauf. Weiter zu beachten ist, dass ein Byte durch die voll/leer Indikation verloren geht, der Puffer hat hier nur eine größe von 15 statt 16 Byte

Und noch ein kleiner Trick. Bei einer Zahl der Reihe 2^n lässt sich auf einfache Weiße immer eine passende Bitmaske erzeugen und man sieht gleichzeitig klar die Anzahl der genutzten Bytes.

<c>

1. define SIZE 16
2. define MASK (SIZE-1)

16 = 0b010000 16 - 1 = 0b001111 </c>

Im Normalbetrieb sollte der Puffer nie voll ausgereizt sein und wenn der Puffer bereits überläuft ist es für die Systemstabilität und Fehleranlyse oft schon zu spät, denn von einem nicht mehr funktionierenden Gerät lässt sich nur wenig Information herauskitzeln. Da kann ein Frühwarmsystem mehr bieten, wobei zwei Ausprägungen typisch sind, Höchstwert merken und eine Meldeschwelle einführen.

<c>

freeMemory =  (read - write - 1 ) & MASK);
if (freeMemory < floodmark)
  floodmark = freeMemory;

</c>

<c>

if ( (read - write - 1 ) & MASK) <= FLOODMARK;
  FloodmarkExcess();

</c>

Code-Beispiel

<c>

1. define BUFFER_SIZE 16 // muss 2^n betragen (8, 16, 32, 64 ...)
2. define BUFFER_MASK (BUFFER_SIZE-1) // Klammern auf keinen Fall vergessen

struct Buffer {

 uint8_t data[BUFFER_SIZE];
 uint8_t read; // zeigt auf das Feld mit dem ältesten Inhalt
 uint8_t write; // zeigt immer auf leeres Feld

} buffer = {{}, 0, 0};

uint8_t BufferIn(uint8_t byte) {

 if (buffer.read == ((buffer.write + 1) & BUFFER_MASK))
   return FAIL;
 buffer.data[buffer.write] = byte;
 // buffer.data[buffer.write & BUFFER_MASK] = byte; // absolut Sicher
 buffer.write = (buffer.write+1) & BUFFER_MASK;

}

uint8_t BufferOut(uint8_t *pByte) {

 if (buffer.read == buffer.write)
   return FAIL;
 *pByte = buffer.data[buffer.read];
 buffer.read = (buffer.read+1) & BUFFER_MASK;
 return SUCCESS;

} </c>

Weblinks

• Circular buffer, englische Wikipedia