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 zum FIFO ist LIFO.

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
• Daten können auch vom Typ struct sein

Nachteile:

• Schnell aber nicht optimal

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.

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

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.

read == write => leer

write + 1 == read || read == 0 && write+1 == BUFFER_SIZE => voll

Bei gleichzeitigem Zugriff zwischen UART-ISR und Hauptprogramm muss ausgeschlossen werden, dass 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 Interrupts, besser ist die Deaktivierung eines einzelnen Interrupts. Im Allgemeinen werden versäumte Interrupts nach erneuter Aktivierung nachgeholt, da ein Flag gesetzt wurde. Wichtig ist vor allem, dass die Ausführungszeit des Atomaren Abschnitts und der ISR geringer ist als der Intervall in dem Interrupts erfolgen, da ansonsten ein Interrupt verloren gehen könnte.

cli()
ret = BufferOut(&var);
sei()

Code-Beispiel

#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 (buffer.write >= BUFFER_SIZE)
  //  buffer.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;

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

}

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;
}

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:

( write + 1 ) & MASK

15 = 0b00001111
15 + 1 = 16 = 0b000010000
16 & MASK = 0b000010000 & 0b000001111 = 0b000000000

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

read == ((write + 1) & MASK)

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 Weise immer eine passende Bitmaske erzeugen und man sieht gleichzeitig klar die Anzahl der genutzten Bytes.

# define SIZE 16
# define MASK (SIZE-1)

16 = 0b010000
16 - 1 = 0b001111

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ühwarnsystem mehr bieten, wobei zwei Ausprägungen typisch sind, Höchstwert merken und eine Meldeschwelle einführen.

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

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

Code-Beispiel

#define BUFFER_SIZE 16 // muss 2^n betragen (8, 16, 32, 64 ...)
#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)
{
  uint8_t next = ((buffer.write + 1) & BUFFER_MASK);
  if (buffer.read == next)
    return FAIL;
  buffer.data[buffer.write] = byte;
  // buffer.data[buffer.write & BUFFER_MASK] = byte; // absolut Sicher
  buffer.write = next;
  return SUCCESS;
}

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;
}

FIFO mit C-Präprozessor

#ifndef FIFO_H_
#define FIFO_H_

#include <stdint.h>

typedef struct {
	uint8_t _read;
	uint8_t _write;
	uint8_t _buffer[64];
} FIFO64_t;

typedef struct {
	uint8_t _read;
	uint8_t _write;
	uint8_t _buffer[128];
} FIFO128_t;

#define FIFO_init(fifo)		{ fifo._read = 0; fifo._write = 0; }

#define FIFO_available(fifo)	( fifo._read != fifo._write )

#define FIFO_read(fifo, size) (						\
	(FIFO_available(fifo)) ?					\
	fifo._buffer[fifo._read = (fifo._read + 1) & (size-1)] : 0	\
)

#define FIFO_write(fifo, data, size) {								\
	uint8_t tmphead = ( fifo._write + 1 ) & (size-1); 	/* calculate buffer index */	\
	if(tmphead != fifo._read) {				/* if buffer is not full */	\
		fifo._write = tmphead;				/* store new index */		\
		fifo._buffer[tmphead] = data;			/* store data in buffer */	\
	}											\
}

#define FIFO64_read(fifo)			FIFO_read(fifo, 64)
#define FIFO64_write(fifo, data)		FIFO_write(fifo, data, 64)

#define FIFO128_read(fifo)			FIFO_read(fifo, 128)
#define FIFO128_write(fifo, data)		FIFO_write(fifo, data, 128)

#endif /*FIFO_H_*/

Weblinks

• Circular buffer, englische Wikipedia