Unterschied zw. Ringspeicher und FiFo

Ein Ringspeicher ist ein spezieller FIFO.

so implementiere ich immer einen FIFO als Ringspeicher:

1

#define FIFO_SIZE 8

2

3

struct {

4

  uint8 r;

5

  uint8 w;

6

  myDataType d[FIFO_SIZE];

7

} fifo = { 0, 0, { } };

8

9

10

int isEmpty(void) {

11

  return fifo.r == fifo.w;

12

}

13

14

int isFull(void) {

15

  return (fifo.w + 1) % FIFO_SIZE == fifo.r;

16

}

17

18

void put(myDataType d) {

19

  fifo.d[fifo.w] = d;

20

  fifo.w = (fifo.w + 1) % FIFO_SIZE;

21

}

22

23

myDataType get(void) {

24

  myDataType d = fifo.d[fifo.r];

25

  fifo.r = (fifo.r + 1) % FIFO_SIZE;

26

  return d;

27

}

Bei einer FIFO-Größe von n = 2 hoch x ist es am efferentesten, da die 
Modulu-Operation durch eine Bit-Maskierung ersetzt werden kann.

Maximal kann man n - 1 Einträge speichern. Würde man ihn ganz voll 
machen, gäbe es keinen unterschied zwischen voll und leer Bedingung.

Oldie schrieb:
> Werden beim FiFo die neu dazugekommenen Werte nicht rechtzeitig
> abgeholt, werden diese neuen Werte irgendwann den gesamten
> Speicherraum vollschreiben und dann ALLE möglichen (!) Tabellen
> und Variablen im Speicher verändern.
> Das Programm macht dann nur noch Blödsinn und schmiert
> irgendwann ab.

Passiert nur bei Leuten, die nicht programmieren können.
Andere implementieren ein FIFO full Signal, und sorgen dafür, dass ein 
FIFO nicht voller als voll werden kann.

Georg schrieb:
> Was in einem Hardware-FIFO drinsteckt, weis man meistens nicht, aber ich
> schätze kein Ringspeicher.

Selbstverständlich doch.
Wie denn sonst? Speicher bei jedem Zugriff komplett umkopieren?

http://electrosofts.com/verilog/fifo.html

Joe F. schrieb:
> Selbstverständlich doch.
> Wie denn sonst? Speicher bei jedem Zugriff komplett umkopieren?

Und selbstverständlich doch.

Es gibt durchaus in Hardware implementierte FIFOs auf Basis von 
Schieberegistern, z.B. bei Speicheroszilloskopen und insbesondere 
natürlich bei Kommunikationsschnittstellen.

Joe F. schrieb:
> Wie denn sonst? Speicher bei jedem Zugriff komplett umkopieren?

Was in diesem Fall eine einfache Shiftoperation wäre.

Da ist die Frage was einfacher zu bauen ist und was man braucht bzw 
will. Die Anforderungen entscheiden wesentlich was man nimmt. Das 
wiederum entscheidet wesentlich was produziert wird.

Eine einheitliche Bauform mehrfach auf dem DIE anzuornen und simpel in 
Reihe zu schalten ist einfacher als die Speicherzellen durch einen 
Schreib- und einen Lesezeiger zu Adresieren und dann, in Relation zur 
Shiftoperation gesehen, entsprechend komplex darauf zuzugreifen. Der 
Ring hat also nicht nur Vorteile.

Was besser oder einfacher ist, hängt unter anderem von der Verwendung 
ab. Ferner lohnt sich bei sehr kleinen FiFos der zusätzliche Aufwand für 
den Ringspeicher eher weniger.

Was ein sehr schönes Beispiel für einen kleinen FiFo ist. Bei dieser 
Größenordnung überlegt man sich zwei mal ob man den größeren Aufwand für 
den Ring betreibt. Das kann man machen, aber ohne weiteren Druck / 
Bedarf ist es oft nicht nötig.

Das ist ein besonderer FiFo der eines Lesezeigers oder einer Alternative 
Bedarf um diese Aufgabe zu erfüllen (siehe weitere Anforderungen). Ein 
Schiebergister ist auch ein FiFo, aber eine andere Implementierung mit 
anderen Zusatzeigenschaften als der Ringpuffer.

Oft will man zwar das was Du da schreibst, es ist aber nicht immer die 
Grundanforderung. Wenn Texas Instruments, dessen Datenblatt habe ich 
halt zuerst vom 74S722 erwischt, das Ding FiFo nennt, so werden die das 
wohl nicht völlig aus der Luft gegriffen haben. ;-)

Das Ding heißt FiFo. First in First out. Es heißt nicht First in at once 
out on demand.

Und auch das könnte man anders als einen Ringspeicher realisieren, 
beispielsweise als ein Shiftspeicher mit Lesezeiger, welcher dem ersten 
Datum folgt und ohne Schreibzeiger.

Oft baut man in der konkreten Realisierung einer Lösung weitere 
Eigenschaften in die Lösung mit ein. Diese werden dadurch aber nicht 
Bestandteil der Problemstellung. Daher sollte an das auch nicht als 
selbstverständlich mit einbeziehen. Ein konkreter FiFo hat konkrete 
Eigenschaften je nach Realisierung.

Die Klasse der FiFos hat ihren Namen aber von der Aufgabenstellug und 
allgemeinen Anforderung. Wird nur die FiFo-Eigenschaft gefordert ist die 
Bandbreite der Lösungsmöglichkeiten weiter als nur dieser eine Weg.

Bastler schrieb:
> FIFO's benutzt man um Geschwingigkeitsunterschiede zwischen
> verschiedenen Baugruppen auszugleichen.

Dies ist eine Anwendungsmöglichkeit. Es handelt sich aber nicht um die 
Definition des FIFOs.

Bastler schrieb:
> FIFO <> Schieberegister!

Niemand hat behauptet, dass es sich um ein- und dasselbe handelt. Es ist 
jedoch möglich, bestimmte Formen von FIFOs mit Hilfe entsprechender 
Schieberegister zu implementieren.

> Auch wenn das Ding nicht 1 sondern 8(9) Bit breit ist: wenn ich einen
> Wert schreibe, dann will ich den auch gleich wieder lesen können und
> nicht warten, bis die Schlange voll ist.

Es ist völlig irrelevant, was DU willst. Der Rest der Welt wird sich 
mit Sicherheit nicht Deinen Wünschen anpassen.

Die Definition von FIFO besagt ausschließlich, dass die zuerst 
geschriebenen Daten gelesen werden. Weitere Aussagen folgen nicht 
unmittelbar aus der Definition. Insbesondere folgt auch nicht 
unmittelbar aus der Definition, dass das Schreiben und Lesen überlappend 
stattfinden dürfen.

Dass natürlich für konkrete Anwendungsfälle noch weitere Anforderungen 
an den FIFO gestellt werden müssen, ist hingegen offensichtlich, z.B. 
simultanes Lesen und Schreiben. Und es gibt auch FIFO-Implementationen, 
die dies auch erfüllen.

Bastler schrieb:
> Genau FIFO, nicht First n times In, then First Out. Natürlich ist ein
> (seriell in/seriell out) Schieberegister auch ein FIFO, aber eben ein
> sehr spezielles.

Richtig. Dieses FiFo arbeitet so und ist damit ein spezielles FiFo. Das 
Gleiche gilt für deine spezielle Anforderung. Diesen beiden und dem 
Ringpuffer ist die generelle FiFo-Eigenschaft gemein. Also sind das 
alles FiFos, aber für unterschiedliche Aufgaben konstruiert und damit 
auch nicht immer gleichsam gut geeignet. Es ist nur die FiFo-Eigenschaft 
durch den Begriff gefordert.

Weitere Eigenschaften können hinzukommen, müssen aber nicht.!

Du beschreibst die Anwendung in der ein Datenstrom mit einer mittleren 
Datenrate X und schnellen Bursts auf ein anderes "Medium" mit einer für 
X  ausreichend hohen mittleren Daterate übertragen werden soll, welches 
aber nicht notwendig die Bursts ausreichend schnell verarbeiten kann.

Das ist eine mögliche Problemstellung.

Weitere Beispiele:

PIN-Eingabe am Handy oder Bankautomaten etc.
Befehlseingabe in der Shell

Beides wäre mit einem Shift-FiFo Lösbar. Allerding bietet dieses keine 
Korrekturmöglichkeit. Die Eingabe müßte komplett neu erfolgen. Läßt man 
dies außer Acht, so lautet hier die Kernanforderung:

Sammle die Eingabedaten und liefere sie (dann) in richtiger Reihenfolge 
ab.

Darin ist kein Verbot einer Latenz, eines zeitlichen Versatzes, 
enthalten. Manchmal ist der zeitliche Versatz sogar gefordert um das 
Gegenteil von deiner Anforderung zu erreichen. Daten werden langsam 
gesammelt und dann in einem Rutsch abgeholt.

Zu Modemzeiten hat an den Empfangspuffer oft manuell konfiguriert. Da 
wurde nicht jedes Byte einzelnd abgeholt. Dann gab es noch den 
Block-Mode bei Festplatten. Daten wurden (langsam) von der Scheibe 
gelesen und dann in einen Burst weitergeschckt, um den Bus nur kurz zu 
belegen und die Anzahl der Transfers gering zu halten.

Es gibt mit Sicherheit auch noch andere, bessere Beispiele für den 
Shift-FiFo. Ich hab nur gerade keines im Kopf parat.

Und dann gibt es noch Fimo. :P

Ich glaube nicht, daß er das mit Hardware-FiFo meinte, sondern eher 
einen einzelnen IC oder einen in einem größeren IC integrierten FiFo

Ist doch alles ok.

Dadurch wurde das Thema vertieft und man weiß nun, daß es viele 
unterschiedliche FiFo-Implementierungen gibt, zu denen auch Ringspeicher 
und Schieberegister gehören.